Lattice Algorithms

Fromm the IBM Almaden page

Lattice algorithms

Shortest vector problem. The shortest vector problem (SVP) is the problem of finding the shortest nonzero vector in a lattice. This problem goes back to the 19th century work of Gauss. SVP has come to be identified as the most important computational task concerning lattices. Algorithms for SVP have an important role in combinatorial optimization, computer algebra, coding theory, and cryptography. Miki Ajtai, Ravi Kumar, and D. Sivakumar have developed a randomized algorithm for SVP that runs in time exp(cn). This improves the previous exp(cn log n) time algorithms for this problem.

Ravi Kumar, D. Sivakumar: On polynomial approximation to the shortest lattice vector length. SODA 2001: 126-127; Journal version SIDMA 2003: 16(3):422-425

Miklós Ajtai, Ravi Kumar, D. Sivakumar: A sieve algorithm for the shortest lattice vector problem. STOC 2001: 601-610

Miklós Ajtai, Ravi Kumar, D. Sivakumar: An overview of the sieve algorithm for the shortest lattice vector problem. CaLC 2001: 1-3

Closest vector problem. Given the basis vectors of a lattice and a point x not in the lattice, the closest vector problem is to find a lattice vector that is closest to x . This problem often arises in cryptanalysis. Miki Ajtai, Ravi Kumar, and D. Sivakumar, building on earlier work, have developed an algorithm to compute an "approximately" close lattice vector to a given point x. The running time of this algorithm is exp( cn), improving the previous exp(cn log n) time algorithm.

Miklós Ajtai, Ravi Kumar, D. Sivakumar: Sampling short lattice vectors and the closest lattice vector problem. CCC 2002: 53-57