Pseudorandom Obfuscation

on YouTube ↗01h 06m

" summary

Defines pseudorandom obfuscation (PRO): if a circuit’s truth table is computationally indistinguishable from uniform then its obfuscation must also look uniform. Gives constructions from evasive LWE using FHE-style key chains, blind garbled circuits and a pseudo-drowning trick to compress a large “magic ciphertext,” but proves PRO is self‑defeating by yielding pseudorandom witness encryption that leaks contradictions. Proposes a weaker iPRO/xI/O notion (compatible with SXDH/pairings) that avoids the linear-algebra counterexamples and sketches when the evasive-LWE heuristic does and does not work.

AI-written summary · about

" chapters (10)

1. 0:00Pseudorandom obfuscation intro
2. 11:04Defining pseudorandom obfuscation
3. 21:22Applications in fully homomorphic encryption
4. 24:46Succinct garbling
5. 31:22Witness encryption
6. 37:47PRO self-defeating nature
7. 44:44Weaker iO notion
8. 49:49xI/O from PRO
9. 1:01:42Summary and future
10. 1:03:32Q&A

" related talks

• 31mObfuscation of Probabilistic Circuits and ApplicationsHuijia Lin · Securing Computation (Simons Institute, June 2015)
• 01h 12mApplications of Obfuscation ICraig Gentry · Cryptography Boot Camp 2015
• 01h 04mTutorial on obfuscationRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 38mRecent Advances on Foundations of Program ObfuscationRachel Lin · Lattices: New Cryptographic Capabilities 2020
• 50mApplications of Obfuscation IICraig Gentry · Cryptography Boot Camp 2015
• 01h 26mObfuscation 1Amit Sahai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 58mObfuscation 2Aayush Jain · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 03mLockable ObfuscationVenkata Koppula · Lattices: New Cryptographic Capabilities 2020