Cryptography Reference
In-Depth Information
Hence, one sets
=
4 b 1 +
2 b 2 =
v
(10 , 8 , 6) .
Note that this is a different so l ution to the one found in Example 18.1.11 , though both
solutions satisfy
= 5.
w
v
Exercise 18.2.5 Prove that if b 1 ,..., b n are orthogonal basis vectors for a lattice L then
the Babai rounding technique produces a correct solution to the CVP with respect to the
Euclidean norm. Show also that the Babai rounding technique gives the same result as the
Babai nearest plane method in this case.
Exercise 18.2.6 Show that the nearest plane and rounding methods produce a linear
combination of the lattice basis where the vector b n has the same coefficient.
Exercise 18.2.7 Consider the lattice with basis
701
1 7 1
30 0
and let
w
=
(100 , 205 , 305) .
Find a lattice vector v close to w using the rounding technique. What is
v
w
?
The Babai rounding algorithm is known by the name “zero forcing” in the communica-
tions community (see [ 396 ]).
18.3 The embedding technique
Another way to solve CVP is the embedding technique , due to Kannan (see page 437
onwards of [ 296 ]). Let B be a basis matrix for a lattice L and suppose w
n (in practice,
∈ R
n ). A solution to the CVP corresponds to integers l 1 ,...,l n such that
we assume w
∈ Q
n
w
l i b i .
i =
1
i = 1 l i b i is such that
The crucial observation that e
is small.
The idea of the embedding technique is to define a lattice L that contains the short vector
e .Let M
=
w
e
∈ R > 0 (for example, M
=
1). The lattice L is defined by the vectors (which are
n + 1 )
a basis for
R
( b 1 , 0) ,..., ( b n , 0) , ( w ,M ) .
(18.3)
Search WWH ::




Custom Search