Cryptography Reference
In-Depth Information
17
Lattice basis reduction
The goal of lattice basis reduction is to transform a given lattice basis into a “nice” lattice
basis consisting of vectors that are short and close to orthogonal. To achieve this, one
needs both a suitable mathematical definition of “nice basis” and an efficient algorithm to
compute a basis satisfying this definition.
Reduction of lattice bases of rank 2 in
2
was given by Lagrange
1
and Gauss. The
algorithm is closely related to Euclid's algorithm and we briefly present it in Section
17.1
.
The main goal of this section is to present the lattice basis reduction algorithm of Lenstra,
Lenstra and Lovasz, known as the LLL or L
3
algorithm. This is a very important algorithm
for practical applications. Some basic references for the LLL algorithm are Section 14.3 of
Smart [
513
], Section 2.6 of Cohen [
127
] and Chapter 17 of Trappe and Washington [
547
].
More detailed treatments are given in von zur Gathen and Gerhard [
220
], Gr otschel, Lovasz
and Schrijver [
245
], Section 1.2 of Lovasz [
356
], and Nguyen and Vallee [
416
]. I also highly
recommend the original paper [
335
].
The LLL algorithm generalises the Lagrange-Gauss algorithm and exploits the Gram-
Schmidt orthogonalisation. Note that the Gram-Schmidt process is not useful, in general,
for lattices since the coefficients
µ
i,j
do not usually lie in
R
and so the resulting vectors are
not usually elements of the lattice. The LLL algorithm uses the Gram-Schmidt vectors to
determine the quality of the lattice basis, but ensures that the linear combinations used to
update the lattice vectors are all over
Z
Z
.
17.1 Lattice basis reduction in two dimensions
2
be linear independent vectors and denote by
L
the lattice for which they are
a basis. The goal is to output a basis for the lattice such that the lengths of the basis vectors
are as short as possible (in this case, successive minima). Lagrange and Gauss gave the
following criteria for a basis to be reduced and then developed Algorithm
22
to compute
such a basis.
Let
b
1
,
b
2
∈ R
1
The algorithm was first written down by Lagrange and later by Gauss, but is usually called the “Gauss algorithm”. We refer to
[
408
] for the original references.
