Paper 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.

Note: Extended version of arXiv:1607.04789