Cryptology ePrint Archive: Report 2016/888

Finding closest lattice vectors using approximate Voronoi cells

Thijs Laarhoven

Abstract: The two classical hard problems underlying the security of lattice-based cryptography are the shortest vector problem (SVP) and the closest vector problem (CVP). For SVP, lattice sieving currently has the best (heuristic) asymptotic time complexity: in high dimensions $d$, sieving can solve SVP in time $2^{0.292d + o(d)}$, using $2^{0.208d + o(d)}$ memory [Becker-Ducas-Gama-Laarhoven, SODA'16]. The best heuristic time complexity to date for CVP is $2^{0.377d + o(d)}$, using $2^{0.292d + o(d)}$ memory [Becker-Gama-Joux, ANTS'14].

In practice, the memory requirements of exponential-space algorithms makes it difficult to run these directly on high-dimensional lattices, and perhaps the most promising application of such methods is as part of a hybrid with lattice enumeration. A faster algorithm for solving the closest vector problem with preprocessing (CVPP) in low dimensions could be used to speed up enumeration for solving SVP or CVP in high dimensions, but so far it is not even clear whether the fastest heuristic SVP algorithms can solve CVP at all.

Our contributions are two-fold. First, we show that with sieving, we can heuristically solve CVP with equivalent asymptotic costs as SVP, improving upon the best complexities of Becker-Gama-Joux. Our second and main contribution is that by constructing approximate Voronoi cells of the lattice as preprocessing, we obtain significantly better complexities for CVPP. We can heuristically solve CVPP in $2^{d/4 + o(d)}$ time and space, and the time complexity can be further reduced to as little as $2^{\varepsilon d + o(d)}$ for arbitrary $\varepsilon > 0$, using $(1/\varepsilon)^{O(d)}$ space.

Preliminary experiments for CVPP support these claims, and in dimension $50$ we roughly obtain a factor $2000$ speedup compared to the fastest sieving algorithms for solving SVP/CVP (without preprocessing). This may be a first step towards a practical hybrid between enumeration and sieving-based methods.

Category / Keywords: lattices, sieving algorithms, Voronoi cells, shortest vector problem (SVP), closest vector problem (CVP), bounded distance decoding (BDD)

Original Publication (with major differences): Selected Areas in Cryptography (SAC) 2016

Date: received 12 Sep 2016, last revised 19 Dec 2016

Contact author: mail at thijs com

Available format(s): PDF | BibTeX Citation

Note: Extended version of arXiv:1607.04789

Version: 20161219:141310 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]