Cryptography Reference
In-Depth Information
for 1
n
be the coefficients from the Gram-Schmidt process. Fix 1
/
4
<δ<
1.
The (ordered) basis is
LLL-reduced
(with factor
δ
) if the following conditions hold:
≤
j<i
≤
(Size reduced)
|
µ
i,j
|≤
1
/
2for1
≤
j<i
≤
n
.
(Lovasz condition)
B
i
≥
δ
µ
i,i
−
1
B
i
−
1
−
for 2
≤
i
≤
n
.
It is traditional to choose
δ
=
3
/
4intheLovasz condition.
Exercise 17.2.5
Which of the following basis matrices represents an LLL-reduced basis
(with
δ
=
3
/
4)?
10
02
,
04
10
,
1
,
50
04
,
10 0
09
.
2
31
−
Exercise 17.2.6
Prove that an equivalent formulation (more in the flavour of the Lagrange-
Gauss method) of the Lovasz condition is
µ
i,i
−
1
B
i
−
1
=
b
i
+
µ
i,i
−
1
b
i
−
1
2
B
i
+
≥
δB
i
−
1
.
2
Exercise 17.2.7
Find an ordered basis
{
b
1
,
b
2
}
in
R
that is LLL-reduced, but has the
property that
b
2
<
b
1
and that the ordered basis
{
b
2
,
b
1
}
is not LLL-reduced.
For the moment we do not concern ourselves with the question of whether an LLL-
reduced basis can exist for every lattice
L
. In Section
17.4
we will present the LLL
algorithm, which constructs such a basis for any lattice (hence, giving a constructive
existence proof for an LLL-reduced basis).
The following properties of an LLL-reduced basis hold.
Lemma 17.2.8
Let
{
b
1
,...,
b
n
}
be an LLL-reduced basis with δ
=
3
/
4
for a lattice L
⊂
m
. Let the notation be as above. In particular,
R
b
is the Euclidean norm.
2
i
−
j
B
i
for
1
1. B
j
≤
≤
j
≤
i
≤
n.
2
(
2
+
2
i
−
2
)
B
i
for
1
2. B
i
≤
b
i
≤
≤
i
≤
n.
b
i
2
(
i
−
1)
/
2
3.
b
j
≤
for
1
≤
j
≤
i
≤
n.
Proof
(
4
−
1
1
1. The Lovasz condition implies
B
i
≥
4
)
B
i
−
1
=
2
B
i
−
1
and the result follows by
induction.
