Cryptography Reference
In-Depth Information
The vector
w
satisfies
n
−
1
w
−
l
j
b
j
+
(
b
n
−
y
=
l
n
b
n
)
∈
U
j
=
1
which shows that
w
∈
U
+
y
.Also
n
−
n
1
w
=
l
j
b
j
−
l
j
b
j
−
b
n
=
)
b
n
w
−
l
n
(
l
n
−
l
n
(18.2)
j
=
1
j
=
1
which is orthogonal to
U
. Hence,
w
is the orthogonal projection of
w
onto
U
+
y
.
b
n
+
n
−
1
i
=
1
µ
n,i
b
i
. Show that
Exercise 18.1.2
Let the notation be as above and write
b
n
=
n
−
1
w
=
µ
n,i
)
b
i
.
(
l
i
−
l
n
i
=
1
n
and
Exercise 18.1.3
Let
{
b
1
,...,
b
n
}
be an ordered basis for a lattice
L
.Let
w
∈ R
<
2
b
i
∈
−
≤
≤
suppose that there is an element
v
L
such that
v
w
for all 1
i
n
. Prove
that the nearest plane algorithm outputs
v
.
The following Lemma is needed to prove the main result, namely Theorem
18.1.6
.
{
b
1
,...,
b
n
}
Lemma 18.1.4
Let
be LLL-reduced (with respect to the Euclidean norm, and
=
with factor δ
3
/
4
). If
v
is the output of Babai's nearest plane algorithm on input w then
2
2
n
−
1
b
n
2
.
−
≤
w
v
4
1
4
b
1
2
2
Proof
We prove the result by induction. Certainly, if
n
=
1 then
w
−
v
≤
as
required.
Now suppose
n
≥
=
+
y
where
y
∈
2. Recall that the output of the method is
v
y
L
y
,
w
is the orthogonal projection of
w
onto
U
minimises the distance from
w
to
U
+
+
y
,
and
y
is the output of the algorithm on
w
=
w
−
y
in
L
. By the inductive hypothesis we
w
−
y
1
4
(2
n
−
1
b
n
−
1
know that
2
≤
−
1)
2
. Hence
y
)
2
w
+
w
−
y
)
2
w
−
(
y
+
=
w
−
(
y
+
w
2
w
−
y
2
=
w
−
+
b
n
2
n
−
1
b
n
−
1
1
2
−
1
2
≤
4
+
4
using equation (
18.2
).
Finally, part 1 of Lemma
17.2.8
implies that this is
4
+
4
2
2
n
−
1
−
1
b
n
2
≤
from which the result follows.
