Fun with Lattices

on YouTube ↗01h 57m

" summary

Explains that some lattice problems have average-case hardness equal to worst-case hardness, focuses on the shortest vector problem and the closest-vector variant, and uses Gram–Schmidt, Hadamard bounds and the Minkowski convex body theorem to give concrete lower and upper bounds (upper ≈ sqrt(n)·det(B)^(1/n)). Shows how a NTRUEncrypt-style ring construction and the GGH scheme encode messages via a good/bad basis pair, notes GGH is practically breakable while lattice assumptions drive modern post‑quantum work.

AI-written summary · about

" chapters (27)

1. 0:00Intro
2. 0:53What are Lattices
3. 2:51Table of Contents
4. 4:44Goal
5. 7:14Linear Combinations
6. 9:17General Points
7. 10:38Inner Product
8. 14:16Lattices
9. 17:15Ndimensional Ball
10. 17:41Linearly Independent
11. 18:06Linearly Dependent
12. 25:33Proof
13. 26:25Partition
14. 27:09Proof of conjecture
15. 30:26Proof of uniqueness
16. 31:51Linear transformation
17. 33:07When
18. 44:24Volume
19. 44:51Original Lattice
20. 45:02Cryptography
21. 48:10Discrete logarithms
22. 49:11RSA
23. 49:42DiffieHellman
24. 50:54Similar Problems
25. 53:47Minimize
26. 55:28Intermission
27. 56:13orthogonality

" related talks

• 39mLattice Based Cryptography PrimerBob Relyea · DevConf.CZ 2021
• 01h 07mLattices and Encrypted ComputationVinod Vaikuntanathan · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 04mUsing Lattices for CryptanalysisNadia Heninger · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 40mPost-QuantumJames Howe, Thomas Prest, Thijs Laarhoven, Corentin Jeudy · RSAC 2021
• 57mChallenges in Evaluating Costs of known Lattice AttacksTanja Lange, Daniel J. Bernstein · Lattices: Geometry, Algorithms and Hardness 2020
• 30mOn the Concrete Security of LWE with Small SecretLynn Chua · Lattices: Geometry, Algorithms and Hardness 2020
• 25mThe Whole is Greater than the Sum of its Parts: Linear Garbling and ApplicationsValerio Pastro · Securing Computation (Simons Institute, June 2015)
• 54mAttribute-based Encryption for CircuitsVinod Vaikuntanathan · The Mathematics of Modern Cryptography