Cryptography Reference
In-Depth Information
m
be a lattice and write
V
m
for the
Definition 16.1.22
Let
L
⊆ R
⊆ R
R
-vector space
spanned by the vectors in
L
.The
dual lattice
of
L
is
L
∗
={
y
∈
V
:
x
,
y
∈Z
for all
x
∈
L
}
.
Exercise 16.1.23
Show that the dual lattice is a lattice. Let
B
be a basis matrix of a full
rank lattice
L
. Show that (
B
T
)
−
1
is a basis matrix for the dual lattice. Hence, show that the
determinant of the dual lattice is det(
L
)
−
1
.
16.2 The Hermite and Minkowski bounds
We state the following results without rigorously defining the term volume and without giv-
ing proofs (see Section 1.3 of Micciancio and Goldwasser [
378
], Chapter 1 of Siegel [
504
],
Chapter 6 of Hoffstein, Pipher and Silverman [
261
] or Chapter 12 of Cassels [
113
]for
details).
m
with basis
Theorem 16.2.1
(Blichfeldt) Let L be a lattice in
R
{
b
1
,...,
b
n
}
and S any
measurable set such that S
⊂
span
{
b
i
:1
≤
i
≤
n
}
. If the volume of S exceeds
det(
L
)
then
there exist two distinct points
v
1
,
v
2
∈
S such that
(
v
1
−
v
2
)
∈
L.
Proof
See Theorem 1.3 of [
378
] or Section III.2.1 of [
113
].
m
with basis
Theorem 16.2.2
(Minkowski Convex body theorem) Let L be a lattice in
R
{
b
1
,...,
b
n
}
and let S be any convex set such that S
⊂
span
{
b
i
:1
≤
i
≤
n
}
,
0
∈
S and if
S. If the volume of S is >
2
n
det(
L
)
then there exists a non-zero lattice
v
∈
S then
−
v
∈
point
v
∈
S
∩
L.
Proof
See Section III.2.2 of Cassels [
113
], Theorem 6.28 of Hoffstein, Pipher and Silver-
man [
261
], Theorem 1.4 of Micciancio and Goldwasser [
378
], or Theorem 6.1 of Stewart
and Tall [
527
].
The convex body theorem is used to prove Theorem
16.2.3
. The intuition behind this
result is that if the shortest non-zero vector in a lattice is large then the volume of the lattice
cannot be small.
∈ N
. There is a constant
0
<γ
n
≤
Theorem 16.2.3
Let n
n such that, for any lattice L of
n
having first minimum λ
1
(for the Euclidean norm),
λ
1
<γ
n
det(
L
)
2
/n
.
Proof
See Theorem 1.5 of [
378
], Theorem 6.25 of [
261
], or Theorem 12.2.1 of [
113
].
R
rank n in
Exercise 16.2.4
Show that the convex body theorem is tight. In other words, find a lattice
L
in
n
for some
n
and a symmetric convex subset
S
n
such that the volume of
S
is
R
⊆ R
2
n
det(
L
) and yet
S
∩
L
={
0
}
.
det(
L
)
1
/n
. Show that, with
Exercise 16.2.5
Show that, with respect to the
∞
norm,
λ
1
≤
(
n
! det(
L
))
1
/n
n
det(
L
)
1
/n
/e
.
respect to the
1
norm,
λ
1
≤
≈
