Abstract
We give $2^{n+o(n)}$-time algorithms for the two most central computational lattice problems, SVP and CVP, improving on the $4^{n+o(n)}$-time algorithm of Micciancio and Voulgaris. Our primary technical tool is an algorithm for sampling from the discrete Gaussian distribution, based on the elementary yet powerful observation that vectors from the discrete Gaussian distribution can be carefully combined to obtain exact samples from a narrower discrete Gaussian. The SVP algorithm is nearly immediate after this observation. The CVP algorithm requires more work, including analysis of the "structure" of approximate closest vectors.