**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 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, it is straightforward to
parallelize on most computer architectures. 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 an 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.

**Category / Keywords: **foundations / lattice, shortest vector problem, closest vector problem, decomposition technique, structural reduction, sieving

**Date: **received 24 Oct 2013, last revised 27 Feb 2014

**Contact author: **anja becker at epfl ch

**Available format(s): **PDF | BibTeX Citation

**Version: **20140227:070948 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]