Cryptography from Ideal Lattices

on YouTube ↗01h 08m

" summary

Shows concrete claims and limits: structured matrices cut storage from O(n^2) to nearly linear (example: n in the hundreds, log q≈8), yielding practical speedups but requiring algebraic structure; security reductions require power-of-two cyclotomics or fields with known integer bases; worst-case hardness gives a quantum reduction from ideal-SVP to search Ring-LWE under Gaussian error (σ ≈ αq), while search→decision needs q ≡ 1 mod m so the polynomial splits and automorphisms let CRT-slot recovery work.

AI-written summary · about

" chapters (12)

1. 0:00Ideal lattice cryptography intro
2. 4:34Structured matrices in crypto
3. 7:07Talk roadmap
4. 7:50Number fields math
5. 14:35Ideals and algebraic number theory
6. 18:12Geometric embeddings of number fields
7. 26:46Ideal lattices definition
8. 37:42Ring-SIS hardness
9. 47:05Ring-LWE efficiency
10. 51:27Ring-LWE variants
11. 1:01:34Module lattices future
12. 1:05:31Open problems and conclusion

" related talks

• 01h 36mAlgorithms for Algebraic Lattices: Classical and QuantumLéo Ducas · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 15mAlgebraic Lattices and Ring Learning with ErrorsChris Peikert · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 08mThe Mathematics of Lattices IVinod Vaikuntanathan · Cryptography Boot Camp 2015
• 39mLattice Based Cryptography PrimerBob Relyea · DevConf.CZ 2021
• 40mPost-QuantumJames Howe, Thomas Prest, Thijs Laarhoven, Corentin Jeudy · RSAC 2021
• 01h 04mUsing Lattices for CryptanalysisNadia Heninger · 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 04mThe Mathematics of Lattices IIVinod Vaikuntanathan · Cryptography Boot Camp 2015