Cryptography Reference
In-Depth Information
for some
l
1
,...,l
n
+
1
∈ Z
. Every non-zero vector with
l
n
+
1
=
0 is of length at least
λ
1
.
Since
2
2
M
2
2
M
2
<
2
λ
1
/
4
(
e
,M
)
=
e
+
=
M
) has length at most
λ
1
/
√
2. Since
v
is a closest vector to
w
it follows
the vector (
e
,
±
L
has length at least
that
e
≤
e
+
x
for all
x
∈
L
, and so every other vector (
u
,M
)
∈
as large. Finally, suppose
|
l
n
+
1
|≥
2. Then
2
2
(2
M
)
2
(
u
,l
n
+
1
M
)
≥
(0
,l
n
+
1
M
)
≥
and so
(
u
,l
n
+
1
M
)
≥
2
(
e
,M
)
.
Lemma
18.3.2
shows that the CVP can be reduced to SVP as long as the target vector
is very close to a lattice vector, and assuming one has a good guess
M
for the distance.
However, when using algorithms such as LLL that solve the approximate SVP it is not
possible, in general, to make rigorous statements about the success of the embedding
technique. As mentioned earlier, the LLL algorithm often works better than the theoretical
analysis predicts. Hence, the embedding technique can potentially be useful even when
w
is not so close to a lattice point. For further discussion see Lemma 6.15 of Kannan [
296
].
{
b
1
,...,
b
n
}
R
n
and let
w
∈ R
n
.Let
M
=
Exercise 18.3.3
Let
be a basis for a lattice in
max
1
≤
i
≤
n
. Show that the output (
e
,M
) of the embedding technique (using LLL) on
the basis of equation (
18.3
) is the same as the output of the Babai nearest plane algorithm
when run on the LLL-reduced basis.
b
i
Exercise 18.3.4
Solve the following CVP instance using the embedding technique and a
computer algebra package.
−
265
287
56
,
B
=
−
460
448
72
w
=
(100
,
80
,
100)
.
−
50
49
8
18.4 Enumerating all short vectors
We present a method to enumerate all short vectors in a lattice, given any basis. We will
show later that the performance of this enumeration algorithm depends on the quality of
the lattice basis. Throughout this section,
denotes the Euclidean norm.
The first enumeration method was given by Pohst in 1981. Further variants were given
by Finke and Pohst, Kannan [
295
,
296
], Helfrich [
255
] and Schnorr and Euchner [
473
].
These methods are all deterministic and are guaranteed to output a non-zero vector of
minimum length. The time complexity is exponential in the lattice dimension, but the
storage requirements polynomial. This approach is known by the name “sphere decoding”
in the communications community (see [
396
]).
v
