On Low End Obfuscation and Learning

on YouTube ↗46m

" summary

Shows an exact characterization: a program class admits information‑theoretic (perfect) obfuscation exactly when it is whitebox learning–exactly learnable from representation‑dependent hints, and proper obfuscation corresponds to proper learning. Gives a quasi‑polynomial canonicalization algorithm for decision trees. Proves a concrete impossibility: assuming one‑way functions, there is no polynomial‑time proper indistinguishability obfuscator mapping into 3‑CNF (and more generally no obfuscation into any class whose dual is PAC‑learnable). Also separates deterministic, perfect and randomized notions via random self‑reductions.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 0:27Program Obfuscation
3. 2:16Indistinguishability Obfuscation
4. 5:10Does (computational) iO exist?
5. 6:34Does statistical iO exist?
6. 7:09This work: "Low-End" Obfuscation
7. 8:16"Low-End" Obfuscation - why?
8. 12:27Exact learning implies (information theoretic) iO
9. 19:16Characterizing Information-Theoretic iO
10. 25:48Learning in the mistake bound model
11. 28:29PAC Learning for Negative Results
12. 32:42Result 3: Separating Notions of Information-Theoretic iO
13. 41:46Open problems

" related talks

• 01h 26mObfuscation 1Amit Sahai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 48mTales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential PrivacyRahul Ilango · Minimal Complexity Assumptions for Cryptography 2023
• 01h 08mExpedition to Obfustopia: Indistinguishability Obfuscation from Well-Studied Assumptions to New...Rachel Lin · Obfuscation
• 01h 15mThe Journey Towards Program ObfuscationYael Tauman Kalai · Simons Institute Workshop: New Developments in Obfuscation
• 38mRecent Advances on Foundations of Program ObfuscationRachel Lin · Lattices: New Cryptographic Capabilities 2020
• 01h 04mTutorial on obfuscationRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 01h 03mFrom Program Obfuscation to Unclonable CryptographyPrabhanjan Ananth · Obfuscation
• 31mObfuscation of Probabilistic Circuits and ApplicationsHuijia Lin · Securing Computation (Simons Institute, June 2015)