We give a @math -time and space randomized algorithm for solving the exact Closest Vector Problem (CVP) on @math -dimensional Euclidean lattices. This improves on the previous fastest algorithm, the deterministic @math -time and @math -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, @math , with very low parameters. While the actual algorithm is a natural generalization of [ADRS15], the analysis uses substantial new ideas. This yields a @math -time algorithm for approximate CVP for any approximation factor @math . Second, we show that the approximate closest vectors to a target vector @math 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.
Improving on the Voronoi cell based techniques of Micciancio and Voulgaris (SIAM J. Comp. 13), and Sommer, Feder and Shalvi (SIAM J. Disc. Math. 09), we give a Las Vegas @math expected time and space algorithm for CVPP (the preprocessing version of the Closest Vector Problem, CVP). This improves on the @math deterministic runtime of the Micciancio Voulgaris algorithm, henceforth MV, for CVPP (which also solves CVP) at the cost of a polynomial amount of randomness (which only affects runtime, not correctness). As in MV, our algorithm proceeds by computing a short path on the Voronoi graph of the lattice, where lattice points are adjacent if their Voronoi cells share a common facet, from the origin to a closest lattice vector. Our main technical contribution is a randomized procedure that given the Voronoi relevant vectors of a lattice - the lattice vectors inducing facets of the Voronoi cell - as preprocessing and any "close enough" lattice point to the target, computes a path to a closest lattice vector of expected polynomial size. This improves on the @math path length given by the MV algorithm. Furthermore, as in MV, each edge of the path can be computed using a single iteration over the Voronoi relevant vectors. As a byproduct of our work, we also give an optimal relationship between geometric and path distance on the Voronoi graph, which we believe to be of independent interest.