Tutorial: Encrypted Computation from Lattices

on YouTube ↗57m

" summary

Fast tutorial on building fully homomorphic encryption from lattices: constructs an LWE-based template where ciphertexts are matrices satisfying T·A ≈ X·T, then makes A small via a gadget bit-decomposition (G and G⁻¹) so multiplication preserves noise; shows two noise-control tricks — reorder G⁻¹ and compile circuits as branching-programs — and proves a linear-algebra lemma (existence of small H) that underpins correctness. Demonstrations are algebraic and the final scheme is concrete and practical under standard LWE parameters.

AI-written summary · about

" chapters (5)

1. 0:00Start
2. 1:42fully homomorphic encryption
3. 26:24small, small, ...
4. 35:55eigenvectors, revisited
5. 51:35conclusion

" related talks

• 01h 07mLattices and Encrypted ComputationVinod Vaikuntanathan · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 45mFully Homomorphic Encryption IShai Halevi · Cryptography Boot Camp 2015
• 01h 29mLattices, Multilinear Maps and Program ObfuscationYilei Chen · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 54mGraph-Induced Multilinear Maps from LatticesShai Halevi · The Mathematics of Modern Cryptography
• 46mRunning Circuits of Unbounded Depth over Encrypted Data, Securely, Using Lattices...Ji Luo · Obfuscation
• 57mLattice Assumptions with Hints: Succinct LWE and its ApplicationsDavid Wu · Obfuscation
• 01h 05mSuccinct Randomized Encodings from LatticesGiulio Malavolta · Obfuscation
• 31mIdentity-Based EncryptionParhat Abla, Huiwen Jia · RSA Conference 2024