Cryptography Reference
In-Depth Information
m
be a lattice. A
sublattice
is a subset
L
⊂
Let
L
⊂ R
L
that is a lattice.
m
matrix formed by taking the rows to be
basis vectors
b
i
. Thus
B
i,j
is the
j
th entry of the row
b
i
and
A
basis matrix
B
of a lattice
L
is an
n
×
n
∈ Z
}
L
={
x
B
:
x
.
By assumption, the rows of a basis matrix are always linearly independent.
2
generated by
2
. The corresponding
Example 16.1.2
The lattice in
R
{
(1
,
0)
,
(0
,
1)
}
is
L
= Z
=
1
01
.Any2
basis matrix is
B
×
2 integer matrix
B
of determinant
±
1 is also a basis
matrix for
L
.
We will mainly assume that the basis vectors
b
i
for a lattice have integer entries. In
cryptographic applications, this is usually the case. We interchangeably use the words
points
and
vectors
for elements of lattices. The vectors in a lattice form an Abelian group
under addition. When
n
2 there are infinitely many choices for the basis of a lattice.
An alternative approach to lattices is to define
L
≥
n
and to have a general length func-
tion
q
(
v
). One finds this approach in topics on quadratic forms or optimisation problems,
e.g. Cassels [
113
] and Schrijver [
478
]. In particular, Section 6.2 of [
478
] presents the LLL
algorithm in the context of reducing the lattice
L
= Z
n
with respect to a length function
= Z
corresponding to a positive-definite rational matrix.
We now give an equivalent definition of lattice, which is suitable for some applications.
A subset
L
m
is called
discrete
if, for any real number
r>
0, the set
⊆ R
{
v
∈
L
:
v
≤
r
}
m
that is discrete. The following result
is finite. It is clear that a lattice is a subgroup of
R
shows the converse.
R
m
is a lattice.
Lemma 16.1.3
Every discrete subgroup of
Proof
(Sketch) Let
be a linearly independent subset of
L
of maximal size.
The result is proved by induction. The case
n
{
v
1
,...,
v
n
}
1 is easy (since
L
is discrete there is
an element of minimal non-zero length). When
n>
1 consider
V
=
=
span
{
v
1
,...,
v
n
−
1
}
and set
L
=
V
. By induction,
L
is a lattice and so has a basis
b
1
,...,
b
n
−
1
.Theset
L
∩
∩{
n
−
1
L
i
=
1
x
i
b
i
+
x
n
v
n
:0
≤
x
i
<
1for1
≤
i
≤
n
−
1 and 0
<x
n
≤
1
}
is finite and so
has an element with smallest
x
n
, call it
b
n
. It can be shown that
{
b
1
,...,
b
n
}
is a basis for
L
. For full details see Theorem 6.1 of [
527
].
m
:
x
A
Exercise 16.1.4
Given an
m
×
n
integer matrix
A
show that ker(
A
)
={
x
∈ Z
=
0
}
−
×
is a lattice. Show that the rank of the lattice is
m
rank(
A
). Given an
m
n
integer matrix
{
∈ Z
m
:
x
A
≡
}
A
and an integer
M
show that
x
0
(mod
M
)
is a lattice of rank
m
.
n
using the
following construction. The motivation is that a linear map that preserves lengths preserves
volumes. Note that if the initial basis for
L
consists of vectors in
In the case
m>n
it is sometimes convenient to project the lattice
L
into
R
n
then the resulting basis
Z
does not necessarily have this property.
