Cryptography Reference
In-Depth Information
b
i
2
. By part 4 of Lemma
A.10.3
it follows that
b
i
x
B
≥
,
which completes the proof.
Theorem
17.2.12
shows that an LLL-reduced lattice basis has good properties. In par-
ticular, the first vector of an LLL-reduced lattice basis has length at most 2
(
n
−
1)
/
2
times the
length of a shortest non-zero vector.
{
b
1
,...,
b
n
}
=
Theorem 17.2.12
Let
be an LLL-reduced basis with δ
3
/
4
for a lattice
L
⊂ R
m
. Let the notation be as above. In particular,
b
is the Euclidean norm.
2
(
n
−
1)
/
2
λ
1
.
1.
b
1
≤
2
(
n
−
1)
/
2
λ
i
for
1
2.
n. (This may look strange, but it tends to be used for
fixed i and varying j, rather than the other way around.)
3.
2
(1
−
i
)
/
2
λ
i
≤
b
j
≤
≤
j
≤
i
≤
2
(
n
−
1)
/
2
λ
i
.
b
i
≤
≤
i
=
1
2
n
(
n
−
1)
/
4
det(
L
)
.
4.
det(
L
)
b
i
≤
2
(
n
−
1)
/
4
det(
L
)
1
/n
.
5.
b
1
≤
Proof
b
i
≥
2
(
i
−
1)
/
2
b
1
1. From part 1 of Lemma
17.2.8
we have
. Hence, part 1 implies
b
i
λ
1
≥
1
≤
i
≤
n
min
1
≤
i
≤
n
2
(1
−
i
)
/
2
b
1
≥
min
2
(1
−
n
)
/
2
b
1
=
.
The result follows since
b
1
=
b
1
.
2. Let
w
1
,...,
w
i
∈
L
be linearly independent lattice vectors such that max
{
w
1
,...,
b
k
(
j
)
w
i
} =
λ
i
.Let
k
(
j
) be defined as in Lemma
17.2.11
so that
w
j
≥
.
Renumber the vectors
w
j
so that
k
(1)
≤
k
(2)
≤···≤
k
(
i
). We claim that
j
≤
k
(
j
).
If not then
w
1
,...,
w
j
would belong to the span of
{
b
1
,...,
b
j
−
1
}
and would be linearly
dependent.
Finally
2
(
k
(
j
)
−
1)
/
2
b
k
(
j
)
≤
2
(
n
−
1)
/
2
2
(
n
−
1)
/
2
λ
i
,
b
j
≤
w
j
≤
which proves the result.
3. The upper bound on
b
i
is given by part 2.
Since
{
b
1
,...,
b
i
}
are linearly independent we have
λ
i
≤
max
1
≤
j
≤
i
b
j
and by part
2
(
i
−
1)
/
2
b
i
b
i
≤
3 of Lemma
17.2.8
each
b
j
≤
.Using
b
i
we obtain the lower
.
4. By Lemma
16.1.14
we have det(
L
)
bound on
b
i
=
i
=
1
b
i
b
i
≤
. The result follows from
2
(
i
−
1)
/
2
b
i
b
i
≤
.
