Cryptography Reference
In-Depth Information
2
Example 16.3.3
Let
L
⊂ R
be the lattice with basis matrix
1001
.
0
B
=
0
2008
Then every lattice vector is of the form (1001
a,
2008
b
) where
a,b
∈ Z
. Hence the shortest
non-zero vectors are clearly (1001
,
0) and (
−
1001
,
0). Similarly, the closest vector to
w
(5432
,
6000) is clearly (5005
,
6024).
Why is this example so easy? The reason is that the basis vectors are orthogonal. Even
in large dimensions, the SVP and CVP problems are easy if one has an orthogonal basis for
a lattice. When given a basis that is not orthogonal it is less obvious whether there exists
a non-trivial linear combination of the basis vectors that give a vector strictly shorter than
the shortest basis vector. A basis for a lattice that is “as close to orthogonal as it can be” is
therefore convenient for solving some computational problems.
=
