Historical Talk on Lattice-Based Cryptography

on YouTube ↗01h 40m

" summary

Ajtai’s 1996 paper introduces a worst-case to average-case reduction for lattice problems and spawns the SIS/LWE reductions that underpin modern schemes; 1998 shows NP-hardness for SVP and LLL-based attacks break many knapsack proposals. Practical advances shrink keys from quadratic matrices to structured, cyclic/anti-circulant lattices using FFT/NTT so storage is near-linear and speeds match SHA-2; small moduli (≈16-bit) suffice. Regev gives a quantum reduction linking injective LWE to worst-case lattices, and Gentry’s 2009 FHE exploit LWE variants for bootstrapping.

AI-written summary · about

" chapters (18)

1. 0:00Intro
2. 4:54What are Lattices
3. 5:43History of Lattices
4. 7:36The Importance of the Problem
5. 11:32Discrete Log
6. 12:54Discrete Log Proof
7. 15:01Lattice vs Discrete Log
8. 17:37Solution
9. 19:37Hardness
10. 23:03Chinese remainder theorem
11. 29:40subsetsum
12. 31:40knapsack
13. 35:30the Curie lattice
14. 37:19periodic modulo Q
15. 48:31shortcomings
16. 51:33cryptography in lattice
17. 52:46survey talk
18. 56:08open problems

" related talks

• 39mLattice Based Cryptography PrimerBob Relyea · DevConf.CZ 2021
• 01h 04mThe Mathematics of Lattices IIVinod Vaikuntanathan · Cryptography Boot Camp 2015
• 40mPost-QuantumJames Howe, Thomas Prest, Thijs Laarhoven, Corentin Jeudy · RSAC 2021
• 01h 08mThe Mathematics of Lattices IVinod Vaikuntanathan · Cryptography Boot Camp 2015
• 57mAlgorithms for Lattice Problems, in PracticeElena Kirshanova, Pierre-Alain Fouque · 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 04mUsing Lattices for CryptanalysisNadia Heninger · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 07mLattices and Encrypted ComputationVinod Vaikuntanathan · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020