Graph-Induced Multilinear Maps from Lattices

on YouTube ↗54m

" summary

Construction gives multilinear maps built from standard lattice/LWE ingredients that encode secrets as small matrices and lets multiplication only along prescribed paths: graph controls which multiplications are allowed. Key result: private-encoding N-party non‑interactive key agreement works using chains, but public encodings remain fragile. Main attack: two or more encodings of zero concatenate to produce a working trapdoor that breaks LWE instances. Mitigations include randomized similarity transforms (safeguards) and using large cyclotomic rings with levels; these harden but do not yet have full reductions.

AI-written summary · about

" chapters (12)

1. 0:00Intro
2. 0:23Multilinear Maps (MMAPs)
3. 2:00Previous MMAP Constructions
4. 3:29Two "Modes" of Using MMAPS
5. 9:19Graph-Induced MMAPS
6. 14:13Application: Non-interactive Multipartite KA
7. 14:38Non-interactive Multipartite KA From Graph-Based MMAPS
8. 16:52Application to Obfuscation
9. 24:12Our Graph-based Construction
10. 34:48Who Can Encode?
11. 36:18A Commutative Variant
12. 50:45Conclusions and Future Work

" related talks

• 01h 29mLattices, Multilinear Maps and Program ObfuscationYilei Chen · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 00mMultilinear Maps and Attacks ISanjam Garg · Cryptography Boot Camp 2015
• 01h 07mLattices and Encrypted ComputationVinod Vaikuntanathan · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 57mTutorial: Encrypted Computation from LatticesHoeteck Wee · Lattices: New Cryptographic Capabilities 2020
• 51mMultilinear Maps and Attacks IISanjam Garg · Cryptography Boot Camp 2015
• 57mLattice Assumptions with Hints: Succinct LWE and its ApplicationsDavid Wu · Obfuscation
• 01h 06mObfuscation: Past, Present, and Possible FuturesAmit Sahai · Securing Computation (Simons Institute, June 2015)
• 01h 04mThe Mathematics of Lattices IIVinod Vaikuntanathan · Cryptography Boot Camp 2015