The Mathematics of Lattices II

on YouTube ↗01h 04m

" summary

Defines short integer solutions (SIS) and decisional LWE and gives the concrete reductions: SIS yields collision-resistant hashes, LWE (search ↔ decisional up to polynomial blowup in M) yields one-way functions, PRGs and Regev-style public-key encryption by publishing many LWE samples as encryptions of zero and using a random short R per ciphertext. Uses Babai rounding and trapdoor bases (short basis of Λ⊥(A)) to invert LWE/SIS; constructs A with a short kernel vector via the leftover hash lemma. Open problem: lattice-based trapdoor permutations from worst‑case hardness.

AI-written summary · about

" chapters (15)

1. 0:00Introduction
2. 4:25Learning with Errors
3. 11:30Decisional LWE
4. 13:54Coding Theory
5. 15:03Pseudorandom Generator
6. 15:58Encryption
7. 17:59Decryption
8. 19:12Devious Method
9. 20:55Public Key
10. 23:35Public Encryption
11. 31:35Q Size
12. 35:05Good and Bad
13. 39:05Close Vectors
14. 42:25Trapdoor
15. 51:25SIS Function

" related talks

• 01h 40mHistorical Talk on Lattice-Based CryptographyDaniele Micciancio · The Mathematics of Modern Cryptography
• 39mLattice Based Cryptography PrimerBob Relyea · DevConf.CZ 2021
• 01h 42mMathematics of LatticesDaniele Micciancio · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 57mLattice Assumptions with Hints: Succinct LWE and its ApplicationsDavid Wu · Obfuscation
• 01h 29mLattices, Multilinear Maps and Program ObfuscationYilei Chen · 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 07mLattices and Encrypted ComputationVinod Vaikuntanathan · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 57mAlgorithms for Lattice Problems, in PracticeElena Kirshanova, Pierre-Alain Fouque · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020