You are looking at a specific version 20131024:160733 of this paper. See the latest version.

Paper 2013/685

Solving shortest and closest vector problems: The decomposition approach

Anja Becker, Nicolas Gama and Antoine Joux

Abstract

In this paper, we present a heuristic algorithm for solving exact, as well as approximate, SVP and CVP for lattices. This algorithm is based on a new approach which is very different from and complementary to the sieving technique. This new approach frees us from the kissing number bound and allows us to solve SVP and CVP in lattices of dimension $n$ in time $2^{0.377n}$ using memory $2^{0.292n}$. The key idea is to no longer work with a single lattice but to move the problems around in a tower of related lattices. We initiate the algorithm by sampling very short vectors in a dense overlattice of the original lattice that admits a quasi-orthonormal basis and hence an efficient enumeration of vectors of bounded norm. Taking sums of vectors in the sample, we construct short vectors in the next lattice of our tower. Repeating this, we climb all the way to the top of the tower and finally obtain solution vector(s) in the initial lattice as a sum of vectors of the overlattice just below it. The complexity analysis relies on the Gaussian heuristic. This heuristic is backed by experiments in low and high dimensions that closely reflect these estimates when solving hard lattice problems in the average case.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
latticeshortest vector problemclosest vector problemdecomposition techniquestructural reductionsieving
Contact author(s)
anja becker @ epfl ch
History
2014-06-13: last of 3 revisions
2013-10-24: received
See all versions
Short URL
https://ia.cr/2013/685
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.