Cryptography Reference
In-Depth Information
The paper by Agrell, Eriksson, Vardy and Zeger [
7
] gives an excellent survey and
comparison of the various enumeration techniques. They conclude that the Schnorr-Euchner
variant is much more efficient than the Pohst or Kannan versions.
18.5 Korkine-Zolotarev bases
We present a notion of reduced lattice basis that has better properties than an LLL-reduced
basis.
m
. An ordered basis
Definition 18.5.1
Let
L
be a lattice of rank
n
in
R
{
b
1
,...,
b
n
}
for
L
is
Korkine-Zolotarev reduced
1
if
1.
b
1
is a non-zero vector of minimal length in
L
;
2.
|
µ
i,
1
|
<
1
/
2for2
≤
i
≤
n
;
3. the basis
is Korkine-Zolotarev reduced (this is the
orthogonal projection of the basis of
L
onto the orthogonal complement of
b
1
)
where
b
i
is the Gram-Schmidt orthogonalisation and
µ
i,j
=
{
b
2
−
µ
2
,
1
b
1
,...,
b
n
−
µ
n,
1
b
1
}
b
i
,
b
j
b
j
,
b
j
/
.
One problem is that there is no known polynomial-time algorithm to compute a Korkine-
Zolotarev basis.
{
b
1
,...,
b
n
}
Theorem 18.5.2
Let
be a Korkine-Zolotarev reduced basis of a lattice L.
Then
1.
for
1
≤
i
≤
n
4
i
+
3
4
λ
i
;
3
λ
i
≤
2
b
i
≤
i
+
2.
γ
n
det(
L
)
2
.
n
n
i
=
1
i
+
3
2
b
i
≤
4
i
=
1
Proof
See Theorem 2.1 and 2.3 of Lagarias, Lenstra and Schnorr [
324
].
As we have seen, for lattices of relatively small dimension it is practical to enumerate
all short vectors. Hence, one can compute a Korkine-Zolotarev basis for lattices of small
dimension. Schnorr has developed the
block Korkine-Zolotarev
lattice basis reduction
algorithm, which computes a Korkine-Zolotarev basis for small-dimensional projections
of the original lattice and combines this with the LLL algorithm. The output basis can
be proved to be of a better quality than an LLL-reduced basis. This is the most powerful
algorithm for finding short vectors in lattices of large dimension. Due to lack of space we
are unable to present this algorithm; we refer to Schnorr [
468
] for details.
1
Some authors also call it Hermite-Korkine-Zolotarev (HKV) reduced.
