Obfuscation II

on YouTube ↗01h 02m

" summary

Candidate obfuscator compiles circuits into a matrix branching program randomized by Kilian randomization and protected by multilinear encodings and per-input alphas. Proof rules out algebraic attacks by mapping each algebraic monomial to a unique input, testing each via the Schwartz‑Zippel lemma, and relying on a new multilinear subgroup elimination assumption to hybrid-split inputs. Construction yields IO for NC1 (and via further assumptions to larger classes), but requires large fields, subexponential hardness and huge concrete blowups (astronomical additive factors like ~2^100).

AI-written summary · about

" chapters (11)

1. 0:00Obfuscation Construction
2. 2:01Security vs. Algebraic Attacks
3. 10:50Unbounded Simulation vs. Algebraic Attacks GGHRSW, BR, BGKPS, MSW
4. 25:12Warm-up (Special-Case) Assumption k=1 Mmap over composite N, with 2 large prime factors: - One "special" prime factor
5. 31:04The Assumption (GLW14): Multilinear Subgroup Elimination k Mmap over composite N, with many large prime factors
6. 33:07How to argue security • We need proof of indistinguishability: iO(C) to iO(C)
7. 34:55Overall reduction strategy
8. 38:05Lesson: Ability to make this (minor) type of change is actually sufficient!
9. 38:20Hybrids intuition
10. 50:36Ways forward • Gain confidence in Multilinear Subgroup Elimination Assumption over Mmap candidates by attack/defend cycle. successful examples from past: block ciphers (AESI. Bilinear assumptions over specific elliptic curve families)
11. 54:16What are we leaving on the table?

" related talks

• 01h 06mObfuscation: Past, Present, and Possible FuturesAmit Sahai · Securing Computation (Simons Institute, June 2015)
• 01h 04mCryptanalysis of Candidate Program ObfuscatorsYilei Chen · Lattices: New Cryptographic Capabilities 2020
• 01h 04mHow to Encrypt a FunctionalityAmit Sahai · Quantum Games and Protocols
• 51mObfuscation via GGH15 Encodings, 10 Years LaterHoeteck Wee · Obfuscation
• 01h 04mTutorial on obfuscationRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 56mToward Obfuscation from Affine Determinant ProgramsMark Zhandry · Obfuscation
• 01h 26mObfuscation 1Amit Sahai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 06mTowards general-purpose program obfuscation via local mixingRan Canetti, Claudio Chamon, Eduardo R. Mucciolo, Andrei E. Ruckenstein · Obfuscation