  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
$\widetilde{O}(4^{n})$-time and $\widetilde{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.
