Lattices, Multilinear Maps and Program Obfuscation

on YouTube ↗01h 29m

" summary

Describes a concrete lattice-based multilinear map construction that chains LWE samples by trapdoor preimage sampling so A0·D1·D2···Dk evaluates to (∏Si)·Aℓ plus noise, with correctness requiring Q large because noise multiplies across levels. Gives a practical weakness: encodings of zero behave like trapdoors and enable a zeroizing attack that extracts integer relations when enough zero evaluations exist. Builds a private constrained PRF by embedding permutation branching programs, but current security needs exponential modulus and heavy repetition; reducing Q and proving IO from LWE remain open.

AI-written summary · about

" chapters (17)

1. 0:00Introduction
2. 1:02Multilinear Maps
3. 24:24Agenda
4. 25:24Preparation
5. 27:02Brief History
6. 28:58Notation
7. 31:37Trapdoor Sampling
8. 38:57Evaluation
9. 45:16Proof Strategy
10. 50:08Insecure Example
11. 50:34Lewis Question
12. 51:26Secure Example
13. 53:58General Framework
14. 57:19Private constraint PRF
15. 57:50Pseudorandom function
16. 58:23Constraint
17. 58:54Private Constraint

" related talks

• 54mGraph-Induced Multilinear Maps from LatticesShai Halevi · The Mathematics of Modern Cryptography
• 51mMultilinear Maps and Attacks IISanjam Garg · Cryptography Boot Camp 2015
• 01h 04mThe Mathematics of Lattices IIVinod Vaikuntanathan · Cryptography Boot Camp 2015
• 01h 16mMultilinear Maps Over the Integers: From Design to SecurityTancrède Lepoint · The Mathematics of Modern Cryptography
• 01h 03mLockable ObfuscationVenkata Koppula · Lattices: New Cryptographic Capabilities 2020
• 01h 05mObfuscation from Noisy Linear FEShweta Agrawal · Lattices: New Cryptographic Capabilities 2020
• 01h 00mMultilinear Maps and Attacks ISanjam Garg · Cryptography Boot Camp 2015
• 01h 06mObfuscation: Past, Present, and Possible FuturesAmit Sahai · Securing Computation (Simons Institute, June 2015)