Algorithms for Lattice Problems
summary
Survey of concrete SVP algorithms and their costs: classic sieving is implemented and practical but lacks proofs; a provable 2^{n} provable sieving method via averaging is built and correct, with a plausible but unproven path to 2^{n/2}. Heuristic sieves using locality‑sensitive hashing achieve 2^{0.29n} heuristics in practice but only assume random distributions. BKZ reduces gamma‑SVP in dimension N to exact SVP in dimension k with approximation roughly k^{N/k}; open problems focus on closing gaps between heuristics, proofs, and quantum speedups.
AI-written summary · about
chapters (17)
- 0:00Introduction
- 1:05What is a Lattice
- 2:10Shortest Vector Problem
- 4:25Other Lattice Problems
- 5:28Civic Algorithms
- 10:36Ruling it out
- 14:39Silly thought
- 15:14When
- 17:49Why
- 19:07Better
- 22:27Open Problem
- 23:25Living Algorithms
- 25:41Open Problem 2
- 35:37Open Problem 4
- 38:25Open Question
- 46:13LML
- 52:37BKZ
related talks
19mProvable Sieving Algorithms for SVP and CVP in the l_p norm
59mSome Recent Results Showing that Lattice Problems Are (sort of) Equivalent in All Norms
01h 08mThe Mathematics of Lattices I
33mSolving SVP and CVP in 2^n time with Discrete Gaussian Sampling – Noah Stephens-Davidowitz
01h 06mHardness of the Shortest Vector Problem: A Simplified Proof and a Survey
37mSolving SVP and CVP in 2^n time with Discrete Gaussian Sampling – Daniel Dadush
57mChallenges in Evaluating Costs of known Lattice Attacks
01h 40mHistorical Talk on Lattice-Based Cryptography