Cryptography Reference
In-Depth Information
it is computationally inexpensive: we can compute LLL-reduced basis of lattices of
relatively large dimension quickly.
We will not need a precise definition of LLL reduction, but the following few
properties will come in handy. All lattices admit LLL-reduced bases, and any LLL-
reduced basis
(
b
1
,...,
b
d
)
of a lattice
L
satisfies
2
(
d
−
1
)/
4
1
/
d
.
1.
b
1
≤
(
vol
L
)
2
(
d
−
1
)/
2
2. For all 1
≤
i
≤
d
,
b
i
≤
λ
i
(
L
).
2
d
(
d
−
1
)/
4
vol
L
3.
b
1
×···×
b
d
≤
.
The vectors of an LLL-reduced basis are thus at most exponentially far from the
minima.
12.2.5 Lattice Problems in Practice
There are many computational problems related to lattices. Some of them are easy:
for example, given bases of two lattices
L
1
,
n
, it is easy to decide if
L
1
⊂
Z
L
2
in
L
2
,
or to find a basis of
L
1
∩
L
2
. However, many lattice problems are believed to be
computationally hard for lattices of high dimension.
The most famous lattice problem is the Shortest Vector Problem (SVP for short):
given a basis of a lattice
L
, find
v
. A related problem is
the Closest Vector Problem (CVP for short): given a basis of a lattice
L
and a target
vector
t
∈
L
such that
v
=
λ
1
(
L
)
n
, find
v
∈ Z
∈
L
minimizing
t
−
v
, that is, such that
t
−
v
≤
t
−
w
for all
w
L
.
There are NP-hardness results for both SVP and CVP [285], so efficient algorithms
for solving these problems in large lattice dimensions are unlikely to exist. The best
known algorithms are exponential or worse [8, 210].
The best that can be done with more efficient algorithms is finding approximate
solutions: for example,
∈
γ
-SVP is the problem of finding a vector
v
∈
L
such that
grows with respect to lattice dimension
d
.
In particular, LLL and its variants provide polynomial algorithms for
a
d
-SVP (and
the similarly defined
a
d
-CVP) for certain constants
a
v
≤
γλ
1
(
L
)
, and becomes easier as
γ
1; thus, SVP and CVP can
be approximated within an exponential factor in polynomial time.
In practice, in low dimension, say
>
100, as is the case in most instances of the
attacks presented hereafter, the most important lattice problems become easy: for
instance, exact SVP and CVP can be quickly solved using existing tools. The main
reason is that lattice reduction algorithms behave better than their worst-case bounds:
see, for instance, [306] for the case of LLL, and [152] for the case of BKZ.
However, when the lattice dimension becomes very high, it is difficult to predict
experimental results in advance. Several factors seem to influence the result: the
lattice dimension, the input basis, the structure of the lattice, and, in the case of CVP,
the distance of the target vector to the lattice. What is always true is that one can
quickly approximate SVP and CVP up to exponential factors with an exponentiation
base very close to 1 (see [152] for concrete values of the exponentiation bases), but
≤
