Lattices

Lattices are geometric objects that can be pictorially described as the set of intersection points of a regular (but not necessarily orthogonal) n-dimentional infinite grid (See Fig. 1).

[A lattice: ###### !]

Figure 1: A Lattice in 2 dimensions

Despite their apparent simplicity, lattices are powerful combinatorial objects that can be used to solve many complex problems in mathematics and computer science. In particular they have been widely used in crypotology. Quite peculiarly lattices have been proven useful both in cryptanalysis (i.e., breaking cryptosystems) and cryptography (i.e., designing secure cryptographic functions based on the hardness of certain lattice problems).

Lattices are usually specified by a basis (i.e., n linearly indepentent vectors) such that any lattice point can be obtained as an integer linear combination of the basis vectors. For example, the (red) lattice point x in Fig. 1 is a linear combination of the two (blue) basis vectors with integer coefficients 3 and 2.

The same lattice (i.e., the same set of intersection points) can be represented by several different bases. For example, the lattice from Figure 1 can also be generated by the following basis:

[Another basis]

Figure 2: A different basis for the same lattice

Notice that in order to obtain vector x, now the basis vectors must be multiplied by 1 and 1. However, the set of points that can be expressed as an integer linear combination of the basis vectors is exactly the same for the two bases.

The two most fundamental lattice problems are the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP).