Cryptography Reference
In-Depth Information
n
definition of
L
says that it is the kernel of the group homomorphism
Z
→ Z
/
M
Z
to
i
=
1
a
i
x
i
. The image of this morphism is the subgroup
sending
(
x
1
,...,
x
n
)
generated by gcd
(
M
,
a
1
,
a
2
,...,
a
n
)
, and hence
M
n
vol
(
L
)
=[Z
:
L
]=
a
n
)
.
gcd
(
M
,
a
1
,
a
2
,...,
12.2.4 Lattice Reduction
As previously noted, any lattice has a basis. In fact, any lattice of dimension 2 or more
has infinitely many bases. However, some of these bases are “better” than others, in
the sense that they give more compact descriptions of the lattice and make it easier
to answer various questions about the lattice.
In the case of Euclidean vector spaces, it is usually convenient to work with
orthogonal bases. Lattices, on the other hand, do not always admit orthogonal bases.
Nevertheless, it can be shown that one can always find so-called
reduced bases
,
consisting of “relatively short” vectors that are “not too far” from being orthogonal.
Giving precise definitions for such notions as “short vectors” and “reduced bases”,
showing that such vectors or such bases exist, and describing methods to find them
is the purpose of the theory of lattice reduction.
Minkowski's Successive Minima
In order to explain what a reduced basis is, we need to define what is meant by short
lattice vectors. Let
L
be a lattice of dimension
n
. Since any closed hyperball
centered at 0 contains finitely many vectors of
L
, there exists a nonzero vector in
L
of minimal length. The Euclidean norm of that shortest nonzero vector is called the
first minimum
of
L
, and is denoted by
≥
1in
R
λ
1
(
)>
λ
1
(
)
L
0. Any vector
v
in
L
of norm
L
is called a shortest vector of
L
. It is never unique, since
v
is also a shortest vector.
For that reason, one must be careful when defining the
second-to-shortest
vector
of a lattice. Minkowski [289] defined the other minima as follows. For all 1
−
≤
i
≤
dim
(
L
)
,the
i
th
minimum
λ
i
(
L
)
is defined as the minimum of max
1
≤
j
≤
i
v
j
over all
families of
i
linearly independent lattice vectors
v
1
,...,
v
i
∈
L
. Clearly, the minima
are increasing:
. And it is not difficult to see that there
always exist linearly independent lattice vectors
v
1
,...,
λ
1
(
L
)
≤
λ
2
(
L
)
≤ ··· ≤
λ
d
(
L
)
v
d
reaching simultaneously
the minima, that is
for all
i
.
As a side note, perhaps surprisingly, it is not the case in general that such vectors
form a basis of
L
. In fact, one can find lattices (of dimension
v
i
=
λ
i
(
L
)
5) in which there is
no basis at all formed by vectors of length equal to the successive minima.
≥
