Algorithms for Lattice Problems, in Practice
summary
Gives a concrete criterion when lattice reduction actually recovers an LWE secret: compare the unusually short vector’s length to the BKZ/GSA output and pick blocksize β accordingly, with simulators predicting the threshold and experiments (∼10k core‑hours) confirming it. Implements sieving (Jessica) and shows Jessica sieve beats enumeration at ≈70 dimensions; shows BKZ simulation can approach a 1/8 exponent in practice via larger preprocessing; analyzes quantum impacts (Grover speedups need costly QRAM). All code and data live in FPL/Jessica repositories on GitHub.
AI-written summary · about
chapters (17)
- 0:00Introduction
- 0:40Title
- 1:07Estimates
- 2:48Matrix Entry
- 4:50Decision Variant
- 8:24Strong Lattice Reduction
- 9:54HighLevel View
- 13:59In Practice
- 15:31Code
- 23:05STP
- 31:37Saving
- 33:06Compare
- 33:46Bucketing
- 34:11Cost
- 43:25Classical vs Quantum Estimates
- 48:02Quantum Circuits
- 51:54Lower Bounds
related talks
30mOn the Concrete Security of LWE with Small Secret
01h 40mHistorical Talk on Lattice-Based Cryptography
39mLattice Based Cryptography Primer
57mChallenges in Evaluating Costs of known Lattice Attacks
01h 04mThe Mathematics of Lattices II
40mPost-Quantum
49mLattice-Based Zero Knowledge and Applications
01h 06mLattice-based Zero-knowledge Proofs