Solving SVP and CVP in 2^n time with Discrete Gaussian Sampling – Noah Stephens-Davidowitz
summary
Randomized exact-SVP algorithm runs in 2^n time by starting with ~2^n samples from the discrete Gaussian (via GPV), repeatedly pairing vectors grouped by bucket by coset mod 2L and outputting averages so the Gaussian parameter drops by sqrt2 each round. Analysis shows output size stays about 2^{n/2} and that ~1.38^n samples suffice to hit a shortest vector, thanks to a telescoping collision bound (Banaszczyk) that limits cumulative loss. The method also yields fast DGS and reductions to CVP/BDD.
AI-written summary · about
chapters (11)
- 0:00Intro
- 0:17Before We Start
- 1:05The Shortest Vector Problem
- 1:34Progress on SVP
- 3:36Discrete Gaussian Distribution
- 6:54Converting Gaussian Vectors
- 13:20Sampling from the Conditional Distribution
- 18:53How Many Vectors Do We Get?
- 22:21Final Algorithm
- 30:01Summary of Results
- 31:29Open Questions/Future Work
related talks
01h 13mAlgorithms for Lattice Problems
19mProvable Sieving Algorithms for SVP and CVP in the l_p norm
01h 06mHardness of the Shortest Vector Problem: A Simplified Proof and a Survey
59mSome Recent Results Showing that Lattice Problems Are (sort of) Equivalent in All Norms
01h 03mComplexity of Lattice Problems
01h 08mThe Mathematics of Lattices I
47mDequantizing the Quantum Singular Value Transform
01h 28mThe Learning With Errors Problem and Cryptographic Applications