Lattice Based Cryptography Primer

on YouTube ↗39m

" summary

Defines lattices and the concrete hard problems used for security: SVP SIS LWE and shows reductions between them, explains how LWE adds small errors and uses error correction to recover shared keys, and how signatures use short vectors as trapdoors. Covers practical choices: Kyber: q=3395, polynomial degree 256, eta=2; public keys ≈800 bytes, ring/module optimizations, NTT for fast polynomial multiplies, seed-based key expansion, and warns about decryption failures, side channels, and parameter selection.

AI-written summary · about

" chapters (16)

1. 0:00Start
2. 0:25Goals
3. 4:23Short Vector Problem
4. 7:13The Shortest Integer Problem
5. 10:01Signing
6. 12:15Decision Problem
7. 16:36Error Correction
8. 17:35Error Issues
9. 20:21Fourier Transform
10. 24:46Nist Algorithms
11. 25:26Order of the Polynomial
12. 27:30The Encrypt Operation
13. 30:08Parameter Sizes
14. 31:26Sabre
15. 35:19Signing Operations
16. 37:21Avoid Decryption Errors

" related talks

• 01h 40mHistorical Talk on Lattice-Based CryptographyDaniele Micciancio · The Mathematics of Modern Cryptography
• 41mLattice based cryptographyLéo Ducas · Post-Quantum Cryptography Conference Amsterdam 2023
• 01h 04mThe Mathematics of Lattices IIVinod Vaikuntanathan · Cryptography Boot Camp 2015
• 01h 08mThe Mathematics of Lattices IVinod Vaikuntanathan · Cryptography Boot Camp 2015
• 01h 42mMathematics of LatticesDaniele Micciancio · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 07mLattices and Encrypted ComputationVinod Vaikuntanathan · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 57mFun with LatticesJose Cardona · LambdaConf 2019
• 01h 04mUsing Lattices for CryptanalysisNadia Heninger · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020