Obfuscation: Past, Present, and Possible Futures

on YouTube ↗01h 06m

" summary

Claims a concrete route to indistinguishability obfuscation by encoding matrix branching programs into candidate multilinear maps and proving security under a new multilinear subgroup elimination assumption. Construction uses Kilian-style randomized conjugation, CRT-based parallel encodings (one prime per input bucket), structured noise that cancels only on correct evaluation, and final zero test at level K. Proof needs 2^n hybrids (handled by subexponential hardness) and ≈O(n) parallel primes; remaining issues: input‑mixing attacks, heavy concrete overhead, and reliance on currently experimental multilinear map candidates.

AI-written summary · about

" chapters (14)

1. 0:00Introduction
2. 1:14Computer Science Analogy
3. 2:43Secure Multiparty Computation
4. 4:41Obfuscation Defined
5. 8:25How is it Useful
6. 12:56Structured Noise
7. 14:21Multilinear Maps
8. 17:47Constructing Obfuscation
9. 19:38Randomization
10. 22:04Multilinear Map
11. 27:01Assumptions
12. 37:47Hybrids
13. 43:57Zeroing Out
14. 48:34Evaluation

" related talks

• 58mObfuscation IAmit Sahai · Cryptography Boot Camp 2015
• 01h 02mObfuscation IIAmit Sahai · Cryptography Boot Camp 2015
• 01h 04mHow to Encrypt a FunctionalityAmit Sahai · Quantum Games and Protocols
• 01h 26mObfuscation 1Amit Sahai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 04mCryptanalysis of Candidate Program ObfuscatorsYilei Chen · Lattices: New Cryptographic Capabilities 2020
• 51mMultilinear Maps and Attacks IISanjam Garg · Cryptography Boot Camp 2015
• 38mRecent Advances on Foundations of Program ObfuscationRachel Lin · Lattices: New Cryptographic Capabilities 2020
• 58mObfuscation 2Aayush Jain · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025