Cryptography Reference
In-Depth Information
w
=
7
/
2
b
1
. Since
w
−
y
2
=
7
/
2
=
3 we return the solution
3
b
1
+
2
b
2
=
(9
,
6
,
3)
.
Exercise 18.1.12
Show that the vector
v
output by the Babai nearest plane method lies in
the parallelepiped
'
(
)
n
l
j
b
j
:
l
j
∈ R
1
2
w
+
,
|
l
j
|≤
j
=
1
centered on
w
. Show that this parallelepiped has volume equal to the volume of the lattice.
Hence, show that if
w
does not lie in the lattice then there is exactly one lattice point in this
parallelepiped.
Some improvements to the Babai nearest plane algorithm are listed in Section 3.4 of
[
233
]. Similar methods (but using a randomised choice of plane) were used by Klein [
306
]
to solve the CVP when the target vector is particularly close to a lattice point. Another
variant of the nearest plane algorithm is given by Lindner and Peikert [
352
]. The nearest
plane algorithm is known by the name “VBLAST” in the communications community
(see [
396
]).
18.2 Babai's rounding technique
An alternative to the nearest plane method is the rounding technique. This is simpler to
compute in practice, since it does not require the computation of a Gram-Schmidt basis, but
harder to analyse in theory. This method is also not guaranteed to solve CVP. Let
b
1
,...,
b
n
be a basis for a full rank lattice in
n
. Given a target
w
n
we can write
R
∈ R
n
w
=
l
i
b
i
i
=
1
with
l
i
∈ R
. One computes the coefficients
l
i
by solving the system of linear equations
(since the lattice is full rank we can also compute the vector (
l
1
,...,l
n
)as
w
B
−
1
). The
rounding technique is simply to set
n
i
=
1
v
=
l
i
b
i
where
is the closest integer to the real number
l
. This procedure can be performed
using any basis for the lattice. Babai has proved that
l
is within an exponential
factor of the minimal value if the basis is LLL-reduced. The method trivially generalises to
non-full-rank lattices as long as
w
lies in the
v
−
w
R
-span of the basis.
Theorem 18.2.1
Let
b
1
,...,
b
n
be an LLL-reduced basis (with respect to the Euclidean
norm and with factorδ
n
. Then the output
v
of the Babai rounding
=
3
/
4
) for a latticeL
⊆ R
