Cryptography Reference
In-Depth Information
y
U
+
y
w
w
b
n
b
n
U
+
b
n
w
U
Figure 18.1 Illustration of the Babai nearest plane method. The
x
-axis represents the subspace
U
(which has dimension
n
−
1) and the
y
-axis is perpendicular to
U
.
We now explain how to algebraically find
y
and
w
.
Lemma 18.1.1
Let
n
l
j
b
j
w
=
(18.1)
j
=
1
L and
w
=
n
−
1
j
=
1
l
j
b
j
+
b
n
. Then
y
is such that the
with l
j
∈ R
. Define
y
=
l
n
b
n
∈
l
n
y
is minimal, and
w
is the orthogonal projection of
w
onto
distance between
w
and U
+
U
+
y
.
b
1
,...,
b
n
−
1
}
Proof
We use the fact that
U
=
span
{
. The distance from
w
to
U
+
y
is
u
∈
U
inf
w
−
(
u
+
y
)
.
=
j
=
1
l
j
b
j
be any element of
L
for
l
j
∈ Z
Let
w
be as in equation (
18.1
) and let
y
.One
=
n
−
1
j
=
1
l
j
b
j
+
l
n
b
n
for some
l
j
∈ R
can write
y
,1
≤
j
≤
n
−
1.
2
Lemma
A.10.5
shows that, for fixed
w
and
y
,
w
−
(
u
+
y
)
is minimised by
u
=
n
−
1
j
=
1
(
l
j
−
l
j
)
b
j
∈
U
. Indeed
2
(
l
n
−
l
n
)
2
b
n
2
.
w
−
(
u
+
y
)
=
It follows that one must take
l
n
=
, and so the choice of
y
in the statement of the Lemma
is correct (note that one can add any element of
L
to
y
and it is still a valid choice).
l
n
