Cryptography Reference
In-Depth Information
One sees that taking the linear combination of rows with coefficients (
−
l
1
,...,
−
l
n
,
1)
gives the vector
(
e
,M
)
.
Hence, we might be able to find
e
by solving the SVP problem in the lattice
L
. One can
then solve the CVP by subtracting
e
from
w
.
Example 18.3.1
Consider the basis matrix
35
72
−
100
B
=
−
−
10
0
25
−
−
20
279
678
3
. We solve the CVP instance with
w
for a lattice in
(100
,
100
,
100).
Apply the LLL algorithm to the basis matrix (taking
M
R
=
=
1)
35
72
−
100
0
−
10
0
−
25
0
−
20
−
279
678
0
100
100
100
1
for the lattice
L
. This gives the basis matrix
01
0
1
50
1
0
.
05
1
−
4
55
−
21
−
4
The first row is (0
,
1
,
0
,
1), so we know that (0
,
1
,
0) is the difference between
w
and a
lattice point
v
. One verifies that
v
=
−
=
(100
,
100
,
100)
(0
,
1
,
0)
(100
,
99
,
100) is a lattice
point.
The success of the embedding technique depends on the size of
e
compared with the
lengths of short vectors in the original lattice
L
. As we have seen in Exercise
18.0.2
,
e
can
be larger than
λ
n
, in which case the embedding technique is not likely to be a good way to
solve the closest vector problem.
n
and denote by λ
1
the
Lemma 18.3.2
Let
{
b
1
,...,
b
n
}
be a basis for a lattice L
⊆ Z
n
and let
v
shortest Euclidean length of a non-zero element of L. Let
w
∈ R
∈
L be a closest
=
−
=
lattice point to
w
. Define
e
w
v
. Suppose that
e
<λ
1
/
2
and let M
e
. Then
(
e
,M
)
is a shortest non-zero vector in the lattice L
of the embedding technique.
Proof
All vectors in the lattice
L
are of the form
n
l
n
+
1
(
e
,M
)
+
l
i
(
b
i
,
0)
i
=
1
