Point Lattices

Let B be a set of vectors $(\bold{b_1},\bold{b_2},\ldots{},\bold{b_n})$ in ${\Bbb R}^n$. If these vectors are independent, then they form a basis of ${\Bbb R}^n$ and any point $\bold{x}$ in n-space may be written as a linear combination of vectors in B:

$$\bold{x} = \sum_{i=1}^n r_i\bold{b_i}, \quad\text{for } r_i \in {\Bbb R}, 1 \leq i \leq n.$$

Consider the set of points $L \subset {\Bbb R}^n$ which may be written as the sum of integer multiples of the basis vectors:

$$L = \left\{ \bold{x} = (x_1,x_2,\ldots{},x_n) \; \colon \; \b... ... \quad\text{for } z_i \in {\Bbb Z}, 1 \leq i \leq n \right\}.$$

We call this set L the point lattice (or just lattice) described by the basis B. Point lattices are pervasive structures in mathematics, and have been studied extensively. See [25], for example, for a survey of the field. In the area of combinatorial mathematics alone it is possible to phrase many different problems as questions about lattices. Integer programming [20], factoring polynomials with rational coefficients [27], integer relation finding [16], integer factoring [35], and diophantine approximation [36] are just a few of the areas where lattice problems arise. In some cases, such as integer programming existence problems, it is necessary to determine whether a convex body in ${\Bbb R}^n$ contains a lattice point (for some specific lattice). In other cases the items of interest are short vectors in the lattice. As we shall see below, for certain cryptographic applications, we would like to be able to quickly determine the Euclidean-norm shortest nonzero vector in a lattice. It is important to note that the difficulty of finding the Euclidean-norm shortest nonzero vector in a lattice is an open question. If $\bold{x} = (x_1,\ldots{},x_n)$, then the sup-norm of $\bold{x}$, denoted $\Vert\bold{x}\Vert _\infty$, is defined as

$$\Vert\bold{x}\Vert _\infty = \max_{1 \leq i \leq n} \vert x_i\vert.$$

It is known that finding the sup-norm shortest nonzero vector in a lattice is NP-hard [5]. Based on this evidence, we suspect that finding the Euclidean-norm shortest nonzero vector for any given lattice is also computationally difficult. However, it may be possible to find the shortest nonzero vector for many lattices quickly. Indeed, current techniques for finding short vectors are slow in theory but often perform well in practice. The remainder of this chapter establishes the environment for our study of lattices and specific applications to cryptography. Section 1.2 discusses reduced bases of lattices and lattice reduction theory. Section 1.3 mentions some of the algorithms which currently exist for computing a reduced lattice basis B' given a basis B of a particular point lattice. In particular, we detail the operation of the Lenstra-Lenstra-Lovász (LLL) basis reduction algorithm [27], which is currently the best known method for finding short vectors in a lattice.