Cryptography Reference
In-Depth Information
18
Algorithms for the closest and shortest
vector problems
This chapter presents several algorithms to find lattice vectors close to a given vector.
First we consider two methods due to Babai that, although not guaranteed to solve the
closest vector problem, are useful in several situations in the topic. Then we present an
exponential-time algorithm to enumerate all vectors close to a given point. This algorithm
can be used to solve the closest and shortest vector problems. We then briefly mention a
lattice basis reduction algorithm that is guaranteed to yield better approximate solutions to
the shortest vector problem.
The closest vector problem (CVP) was defined in Section
16.3
. First, we remark that the
shortest distance from a given vector
w
n
to a lattice vector
v
∈ R
∈
L
can be quite large
compared with the lengths of short vectors in the lattice.
2
Example 18.0.1
Consider the lattice in
=
(0
,
500) has distance 500 from the closest lattice point, despite the fact that the first
successive minimum is 1.
R
with basis (1
,
0) and (0
,
1000). Then
w
≥
√
n/
2 for all
n
and
w
Exercise 18.0.2
Let
L
= Z
=
(1
/
2
,...,
1
/
2). Show that
w
−
v
v
∈
L
. Hence, show that if
n>
4 then
w
−
v
>λ
n
for all
v
∈
L
.
18.1 Babai's nearest plane method
b
1
,...,
b
n
}
Let
L
be a full rank lattice given by an (ordered) basis
{
b
1
,...,
b
n
}
and let
{
n
. Babai [
17
] presented a method to
inductively find a lattice vector close to
w
. The vector
v
be the corresponding Gram-Schmidt basis. Let
w
∈ R
∈
L
output by Babai's method is
not guaranteed to be such that
w
−
v
is minimal. Theorem
18.1.6
shows that if the lattice
basis is LLL-reduced then
is within an exponential factor of the minimal value.
We now describe the method. Define
U
w
−
v
and let
L
=
=
span
{
b
1
,...,
b
n
−
1
}
L
∩
U
be
the sublattice spanned by
{
b
1
,...,
b
n
−
1
}
. The idea of the nearest plane method is to find a
y
is minimal. One then sets
w
vector
y
∈
L
such that the distance from
w
to the plane
U
+
y
(in other words,
w
∈
to be the orthogonal projection of
w
onto the plane
U
+
U
+
y
and
w
∈
U
⊥
). Let
w
=
w
−
L
then
w
∈
w
L
. One inductively
solves the (lower dimensional) closest vector problem of
w
in
L
to get
y
∈
−
y
∈
U
. Note that if
w
∈
L
.The
y
.
solution to the original instance of the CVP is
v
=
y
+
