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

on YouTube ↗37m

" summary

Claims an exact CVP algorithm running in 2^n time by sampling from a shifted discrete Gaussian and combining collisions; samples require parameters bounded by the largest Gram–Schmidt length and yield enough hits to target the heaviest cosets. Uses an HKZ basis to learn last K coordinates of the closest vector, recurse on 2^K shifts to reduce dimension, and proves the sampler eventually hits a bucket with the exact closest vector. Algorithm is randomized, matches prior leading term, and leaves determinism and simplification open.

AI-written summary · about

" chapters (22)

1. 0:00Intro
2. 0:27Lattices
3. 0:44Closest Vector Problem (CVP)
4. 1:02Applications of SVP & CVP
5. 1:47Main Result
6. 2:38Outline
7. 4:13Shifted Discrete Gaussian
8. 4:46Discrete Gaussian and CVP
9. 6:38Approximate CVP via DGS
10. 8:36Hermite-Korkine-Zolotarev Basis
11. 10:10Shifted DGS Sampler
12. 13:22Averaging Discrete Gaussians
13. 15:06Shifted DGS Combiner
14. 18:31Key Inequality
15. 19:26Hope for Exact CVP
16. 20:08Clustering approx. closest vectors
17. 21:54How many closest vectors?
18. 22:54Dimension Reduction via Clustering
19. 28:56High Level Algorithm
20. 30:07Key Challenges
21. 32:22Conclusions
22. 33:49Open Problems

" related talks

• 19mProvable Sieving Algorithms for SVP and CVP in the l_p normPriyanka Mukhopadhyay · Lattices: Geometry, Algorithms and Hardness 2020
• 01h 13mAlgorithms for Lattice ProblemsNoah Stephens-Davidowitz · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 06mHardness of the Shortest Vector Problem: A Simplified Proof and a SurveyHuck Bennett · Quantum and Lattices Joint Reunion Workshop
• 59mSome Recent Results Showing that Lattice Problems Are (sort of) Equivalent in All NormsNoah Stephens-Davidowitz · Quantum and Lattices Joint Reunion Workshop
• 01h 03mComplexity of Lattice ProblemsNoah Stephens-Davidowitz · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 08mThe Mathematics of Lattices IVinod Vaikuntanathan · Cryptography Boot Camp 2015
• 01h 00mA Reverse Minkowski TheoremNoah Stephens-Davidowitz · Lattices: Geometry, Algorithms and Hardness 2020
• 01h 36mAlgorithms for Algebraic Lattices: Classical and QuantumLéo Ducas · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020