Cryptography Reference
In-Depth Information
Due to lack of space we refer to the original papers for further details about enumeration
algorithms. Pujol and Stehl´e[
455
] give an analysis of issues related to floating-point
implementation.
In practice, the most efficient methods to compute the SVP are heuristic “pruning”
methods. These methods are still exponential in the lattice dimension, and are not guaranteed
to output the shortest vector. The extreme pruning algorithm of Gama, Nguyen and Regev
[
227
] is currently the most practical method.
A quite different approach, leading to non-deterministic algorithms (in other words, the
output is a non-zero vector in the lattice that, with high probability, has minimal length)
is due to Ajtai, Kumar and Sivakumar (see [
322
] for a survey). The running time and
storage requirements of the algorithm are both exponential in the lattice dimension. For
some experimental results we refer to Nguyen and Vidick [
417
]. Micciancio and Voulgaris
[
394
] have given an improved algorithm, still requiring exponential time and storage.
18.4.1 Enumeration of closest vectors
n
.Let
A
The above ideas can be adapted to list lattice points close to some
w
∈ R
∈ R
>
0
and
=
i
=
1
x
i
b
i
=
i
=
1
z
i
b
i
as
2
suppose we seek all
v
∈
L
such that
v
−
w
≤
A
. Write
v
before and write
n
y
i
b
i
.
w
=
i
=
1
2
Then
v
−
w
≤
A
is equivalent to
n
y
i
)
2
b
i
2
(
z
i
−
≤
A.
i
=
1
It follows that
y
n
−
A/B
n
≤
y
n
+
A/B
n
x
n
≤
and so on.
Lemma 18.4.7
Let the notation be as above and define
n
A
/B
i
z
j
B
j
M
i
=
−
j
=
i
+
1
and N
i
=
j
=
i
+
1
µ
j,i
x
j
for
1
=
i
=
1
x
i
b
i
satisfies
2
≤
i
≤
n.If
v
v
−
w
≤
A then,
for
1
≤
i
≤
n
y
i
−
M
i
−
N
i
≤
x
i
≤
y
i
+
M
i
−
N
i
.
Exercise 18.4.8
Prove Lemma
18.4.7
.
