Summer 2015

Solving SVP and CVP in 2^n time with Discrete Gaussian Sampling

Tuesday, July 7th, 2015 11:00 am12:00 pm

Add to Calendar

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.