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, shortest vector and closest vector problems on lattices. The algorithm can be seen as a modified sieving algorithm for which the vectors of the intermediate sets lie in overlattices or translated cosets of overlattices. The key idea is hence 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 an overlattice of the original lattice that admits a quasiorthonormal 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. Finally, we obtain solution vector(s) in the initial lattice as a sum of vectors of an overlattice. 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. This new approach allows us to solve not only shortest vector problems, but also closest vector problems, in lattices of dimension $n$ in time $2^{0.3774\,n}$ using memory $2^{0.2925\,n}$. Moreover, the algorithm is straightforward to parallelize on most computer architectures.
Note: The great part of the paper is published at ANTS 2014 under the title ``A Sieve Algorithm Based on Overlattices". We added here the section ``Example for cocyclic lattices or qary lattices" which gives a concrete example of a tower of lattices one might consider at first trial.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Minor revision.ANTS2014: Eleventh Algorithmic Number Theory Symposium ANTSXI
 Keywords
 latticeshortest vector problemclosest vector problemdecomposition techniquestructural reductionsieving
 Contact author(s)
 anja becker @ epfl ch
 History
 20140613: last of 3 revisions
 20131024: received
 See all versions
 Short URL
 https://ia.cr/2013/685
 License

CC BY
BibTeX
@misc{cryptoeprint:2013/685, author = {Anja Becker and Nicolas Gama and Antoine Joux}, title = {Solving shortest and closest vector problems: The decomposition approach}, howpublished = {Cryptology ePrint Archive, Paper 2013/685}, year = {2013}, note = {\url{https://eprint.iacr.org/2013/685}}, url = {https://eprint.iacr.org/2013/685} }