23.1 Lattices – Introduction to Cryptography with Coding Theory, 3rd Edition

23.1 Lattices

Let v1, , vn be linearly independent vectors in n-dimensional real space Rn. This means that every n-dimensional real vector v can be written in the form

v=a1v1++anvn

with real numbers a1, , an that are uniquely determined by v. The lattice generated by v1, , vn is the set of vectors of the form

m1v1++mnvn

where m1, , mn are integers. The set {v1, , vn} is called a basis of the lattice. A lattice has infinitely many possible bases. For example, suppose {v1, v2} is a basis of a lattice. Let k be an integer and let w1=v1+kv2 and w2=v2. Then {w1, w2} is also a basis of the lattice: Any vector of the form m1v1+m2v2 can be written as m1w1+m2w2 with m1=m1 and m2=m2km1, and similarly any integer linear combination of w1 and w2 can be written as an integer linear combination of v1 and v2.

Example

Let v1=(1, 0) and v2=(0, 1). The lattice generated by v1 and v2 is the set of all pairs (x, y) with x, y integers. Another basis for this lattice is {(1, 5), (0, 1)}. A third basis is {(5, 16), (6, 19)}. More generally, if abcd is a matrix with determinant ±1, then {(a, b), (c, d)} is a basis of this lattice (Exercise 4).

The length of a vector v=(x1, , xn) is

v=x12++xn21/2.

Many problems can be related to finding a shortest nonzero vector in a lattice. In general, the shortest vector problem is hard to solve, especially when the dimension of the lattice is large. In the following section, we give some methods that work well in small dimensions.

Example

A shortest vector in the lattice generated by

(31, 59) and (37, 70)

is (3, 1) (another shortest vector is (3, 1)). How do we find this vector? This is the subject of the next section. For the moment, we verify that (3, 1) is in the lattice by writing

(3, 1)=19(31, 59)+16(37, 70).

In fact, {(3, 1), (1, 4)} is a basis of the lattice. For most purposes, this latter basis is much easier to work with than the original basis since the two vectors (3, 1) and (1, 4) are almost orthogonal (their dot product is (3, 1)(1, 4)=1, which is small). In contrast, the two vectors of the original basis are nearly parallel and have a very large dot product. The methods of the next section show how to replace a basis of a lattice with a new basis whose vectors are almost orthogonal.