Solving the Closest Vector Problem in $2^n$ Time--- The Discrete Gaussian Strikes Again!

Abstract

We give a $2^{n+o(n)}$-time and space randomized algorithm for solving the exact Closest Vector Problem (CVP) on $n$-dimensional Euclidean lattices. This improves on the previous fastest algorithm, the deterministic $\tilde{O}(4^n)$-time and $\tilde{O}(2^n)$-space algorithm of Micciancio and Voulgaris. We achieve our main result in three steps. First, we show how to modify the sampling algorithm from [ADRS15] to solve the problem of discrete Gaussian sampling over lattice shifts, $L-t$, with very low parameters. While the actual algorithm is a natural generalization of [ADRS15], the analysis uses substantial new ideas. This yields a $2^{n+o(n)}$-time algorithm for approximate CVP for any approximation factor $\gamma =1+2^{-o(n/\log n)}$. Second, we show that the approximate closest vectors to a target vector $t$ can be grouped into "lower-dimensional clusters," and we use this to obtain a recursive reduction from exact CVP to a variant of approximate CVP that "behaves well with these clusters." Third, we show that our discrete Gaussian sampling algorithm can be used to solve this variant of approximate CVP. The analysis depends crucially on some new properties of the discrete Gaussian distribution and approximate closest vectors, which might be of independent interest.

References in corpus (3)

• Solving the Shortest Vector Problem in $2^n$ Time via Discrete Gaussian Sampling
• On the Closest Vector Problem with a Distance Guarantee
• Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle

Cited by in corpus (4)

• Solving the Shortest Vector Problem in $2^n$ Time via Discrete Gaussian Sampling
• Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One
• A Note on the Concrete Hardness of the Shortest Independent Vectors Problem in Lattices
• Space-efficient classical and quantum algorithms for the shortest vector problem