Cryptography Reference
In-Depth Information
m
for a lattice and let
Exercise 18.4.1
Let
{
b
1
,...,
b
n
}
be an (ordered) basis in
R
b
1
,...,
b
n
}
m
. Show that the projection
{
be the Gram-Schmidt orthogonalisation. Let
v
∈ R
of
v
onto
b
i
is
v
,
b
i
2
b
i
.
b
i
=
j
=
1
x
j
b
j
then this projection is
Show that if
v
n
x
i
+
b
i
.
x
j
µ
j,i
j
=
i
+
1
b
1
,...,
b
n
}
Lemma 18.4.2
Let
{
b
1
,...,
b
n
}
be an (ordered) basis for a lattice and let
{
b
i
2
. Let
v
be the Gram-Schmidt orthogonalisation. Fix A
∈ R
>
0
and write B
i
=
=
i
=
1
x
i
b
i
be such that
2
v
≤
A.For
1
≤
i
≤
n define
n
z
i
=
x
i
+
µ
j,i
x
j
.
j
=
i
+
1
Then for
1
≤
i<n
n
z
i
B
i
≤
A.
i
=
1
Proof
Exercise
18.4.1
gives a formula
z
i
b
i
for the projection of
v
onto each
b
i
. Since the
vectors
b
i
are orthogonal we have
n
n
i
=
1
2
z
i
b
i
2
z
i
B
i
.
v
=
=
i
=
1
The result follows.
b
n
Theorem 18.4.3
Let the notation be as in Lemma
18.4.2
. Then one has x
n
≤
A/
2
and,
for
1
≤
i<n
x
i
+
2
n
n
z
j
B
j
.
B
i
≤
−
µ
j,i
x
j
A
j
=
i
+
1
j
=
i
+
1
x
n
and Lemma
18.4.2
implies
z
n
B
n
≤
Proof
Note that
z
n
=
A
, which proves the first
statement. The second statement is also just a re-writing of Lemma
18.4.2
.
=
i
=
1
x
i
b
i
, which follows from the above results. First, witho
ut los
s of generality we may
assume that
x
n
≥
We now sketch the enumeration algorithm for finding all short lattice vectors
v
x
n
≤
√
A/B
i
. For each candidate
x
n
0. By Theorem
18.4.3
we know 0
≤
one knows that
µ
n,n
−
1
x
n
)
2
B
n
−
1
≤
x
n
B
n
(
x
n
−
1
+
A
−
