Lower Bounds on the Overhead of Indistinguishability Obfuscation

on YouTube ↗49m

" summary

Under the assumption NP not in BPP the work proves a concrete inefficiency: efficient iO for multi-output Boolean circuits must add about s/log s additive overhead (formally no iO that outputs size s+ o(s/log s)). The argument combines iO, collision-resistant hashing, PRFs and a connection to meta-complexity (Levin reductions and the NP-hardness of multi-output circuit minimization) to construct explicit multi-output families that force the blowup; result holds conditionally and is constructive.

AI-written summary · about

" chapters (9)

1. 0:00Obfuscation lower bounds intro
2. 2:13Weak lower bound multibit circuits
3. 7:42Metacomplexity gap MCSP
4. 15:37Levin reductions assumptions
5. 25:41Gap MCSP NP completeness
6. 30:24Multi-output MCSP overhead
7. 33:02Direct proof simplified circuits
8. 44:23Summary future directions
9. 46:16Q&A metacomplexity obfuscation

" related talks

• 52mIndistinguishability Obfuscation via Mathematical Proofs of EquivalenceZhengzhong Jin · Proof Complexity and Meta-Mathematics 2023
• 48mTales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential PrivacyRahul Ilango · Minimal Complexity Assumptions for Cryptography 2023
• 31mObfuscation of Probabilistic Circuits and ApplicationsHuijia Lin · Securing Computation (Simons Institute, June 2015)
• 37mMutual Empowerment Between Circuit Obfuscation and Circuit MinimizationIlya Volkovich · Minimal Complexity Assumptions for Cryptography 2023
• 01h 12mApplications of Obfuscation ICraig Gentry · Cryptography Boot Camp 2015
• 50mApplications of Obfuscation IICraig Gentry · Cryptography Boot Camp 2015
• 57mIndistinguishability Obfuscation from Well-Founded AssumptionsAayush Jain · Simons Institute Workshop: New Developments in Obfuscation
• 01h 26mObfuscation 1Amit Sahai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025