The Mathematics of Lattices I

on YouTube ↗01h 08m

" summary

Introduces lattices as integer linear combinations and frames the key problems: SVP (shortest nonzero vector) and SIVP (short independent vectors). States concrete algorithmic facts: exact SVP best known in 2^n time and polynomial-time algorithm giving a 2^{n/2} approximation. Gives a cryptographic construction: SIS (short integer solutions) yields a family f_A(r)=A·r mod q that is collision-resistant, and proves a worst-case→average-case reduction using discrete Gaussians and the smoothing lemma to relate SIS hardness to worst-case lattice problems (≈√n loss).

AI-written summary · about

" chapters (14)

1. 0:00The Mathematics of Lattices
2. 3:16Good Basis, Bad Basis
3. 5:19Hard Problems
4. 14:14SVP: Algorithms and Complexity
5. 22:21Why Lattice-based Crypto?
6. 23:45Cryptographic Hardness
7. 24:36From Hardness to Usefulness
8. 26:53What I Won't Get to Tell You
9. 27:43Short Integer Solutions (SIS)
10. 31:17Generalized SIS (GSIS)
11. 35:00Collision-Resistant Hash Function
12. 46:061-D Gaussian Distribution
13. 46:472-D Gaussian Distribution
14. 51:24Worst-Case/Average-Case Reduction

" related talks

• 01h 42mMathematics of LatticesDaniele Micciancio · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 39mLattice Based Cryptography PrimerBob Relyea · DevConf.CZ 2021
• 01h 40mHistorical Talk on Lattice-Based CryptographyDaniele Micciancio · The Mathematics of Modern Cryptography
• 01h 36mAlgorithms for Algebraic Lattices: Classical and QuantumLéo Ducas · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 32mThe Short Integer Solutions Problem and Cryptographic ApplicationsDaniele Micciancio · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 03mComplexity of Lattice ProblemsNoah Stephens-Davidowitz · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 08mCryptography from Ideal LatticesDamien Stehlé · The Mathematics of Modern Cryptography
• 01h 15mAlgebraic Lattices and Ring Learning with ErrorsChris Peikert · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020