Cryptography Reference
In-Depth Information
Random Lattices
It is possible to give a relatively precise description of how Minkowski's minima
behave “generically”, namely for so-called random lattices. The precise definition
of a random lattice is somewhat technical but the idea is that there is a natural way
to pick a lattice “uniformly at random” (see, e.g., [6] for details).
It is proved in [7] that a random lattice of rank
n
satisfies asymptotically, with
overwhelming probability,
n
2
1
/
n
∀
1
≤
i
≤
n
,λ
i
(
L
)
≈
vol
(
L
)
(12.1)
π
e
This means that all minima are close to each other and to the radius of an
n
-
dimensional ball of volume vol
.
Furthermore, [7] also shows that asymptotically, in a random
n
-rank lattice
L
,
there exists with overwhelming probability a lattice basis
(
L
)
(
b
1
,...,
b
n
)
such that
n
2
1
/
n
b
i
≈
(
)
.
∀
1
≤
i
≤
n
,
vol
L
(12.2)
π
e
Such a basis consists of very short vectors, since their norms are close to the successive
minima. Thus, random lattices typically have nice bases.
In applications, lattices are often not picked at random in the previous sense but
constructed in a particular way. Such nonrandom lattices can sometimes behave quite
differently from random lattices: for example, the first minimum can be arbitrarily
small compared to vol
n
for lattices constructed in an ad hoc way. However, it
is often a reasonable heuristic to infer the “typical” behavior of lattices in a given
problem from the case of random lattices, and assume that the previous properties
hold most often nonetheless.
1
/
(
L
)
Reduction Notions and LLL
We just mentioned that random lattices always have nice bases: what about general
lattices? The goal of lattice reduction is to prove the existence of nice lattice bases
in every lattice, and to describe procedures to find such bases. These nice bases are
referred to as reduced.
There are multiple definitions of a reduced basis: usually, one first defines a notion
of reduction, then shows that there exist bases which are reduced in this sense, and
finally proves that bases which are reduced in this sense have interesting properties,
mathematical (how short are the vectors of a reduced basis?) and computational (how
easy is it to compute the basis?).
One classical notion of reduction, which will be enough for our purposes, is the
Lenstra-Lenstra-Lovász reduction [251] (LLL for short). It is not very strong (in
the sense that vectors of an LLL-reduced basis are not necessarily very short) but
