** Next:** Reduced Lattice Bases
** Up:** Introduction
** Previous:** Introduction

#

Point Lattices

Let *B* be a set of vectors
in
.
If these vectors are independent, then they form a basis of
and any point
in *n*-space may be written as a linear
combination of vectors in *B*:

Consider the set of points
which may be written as the sum of
*integer* multiples of the basis vectors:

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
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
,
then the *sup-norm*
of ,
denoted
,
is defined as

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.

** Next:** Reduced Lattice Bases
** Up:** Introduction
** Previous:** Introduction
*Brian A. LaMacchia*

*1999-10-30*