Cryptography Reference
In-Depth Information
and so
(
A
|
x
n
−
1
+
µ
n,n
−
1
x
n
|≤
−
x
n
B
n
)
/B
n
−
1
.
To phrase this as a bound on
x
n
−
1
one uses the fact that, for any
a
∈ R
,b
∈ R
≥
0
,
the solutions
x
∈ R
to
|
x
+
a
|≤
b
satisfy
−
(
b
+
a
)
≤
x
≤
b
−
a
. Hence, writing
M
1
=
A
x
n
B
n
/B
n
−
1
one has
−
−
(
M
1
+
µ
n,n
−
1
x
n
)
≤
x
n
−
1
≤
M
1
−
µ
n,n
−
1
x
n
.
Exercise 18.4.4
Generalise the above discussion to show that for 1
≤
i<n
one has
−
(
M
1
+
M
2
)
≤
x
i
≤
M
1
−
M
2
where
n
A
/B
i
x
j
B
j
M
1
=
−
j
=
i
+
1
and
M
2
=
j
=
i
+
1
µ
j,i
x
j
.
Exercise 18.4.5
Write pseudocode for the algorithm to enumerate all short vectors of a
lattice.
The algorithm to find a non-zero vector of minimal length is then straightforward. Set
A
to be
2
, enumerate all vectors of length at most
A
and, for each vector, compute the
length. One is guaranteed to find a shortest vector in the lattice. Schnorr and Euchner [
473
]
organised the search in a manner to minimise the running time.
The running time of this algorithm depends on the quality of the basis in several ways.
First, it is evidently important to have a good bound
A
for the length of the shortest vector.
Taking
A
b
1
2
=
b
1
i
s o
nly sensible if
b
1
is already rather short; alternatively one may
=
n
2
πe
det(
L
)
1
/n
using the Gaussian heuristic (one can choose a small
bound for
A
and then, if the search fails, increase
A
accordingly). Second, one sees that
if
b
n
is very short then the algorithm searches a huge range of values for
x
n
, and similarly
if
b
n
−
1
choose, say,
A
b
i
is very short etc. Hence, the algorithm performs best if the values
descrease
rather gently.
To solve SVP in practice using enumeration one first performs LLL and other pre-
computation to get a sufficiently nice basis. We refer to Kannan [
295
,
296
], Schnorr and
Euchner [
473
] and Agrell, Eriksson, Vardy and Zeger [
7
] for details. The best complexity
statement in the literature is due to Hanrot and Stehle.
Theorem 18.4.6
(Hanrot and Stehl´e[
249
]) There exists a polynomial p
(
x,y
)
∈ R
[
x,y
]
m
with basis consisting of vectors with
coefficients bounded by B, one can compute all the shortest non-zero vectors in L in at
most p
(log(
B
)
,m
)
n
n/
2
e
+
o
(
n
)
bit operations.
such that, for any n-dimensional lattice L in
Z
