Lower Bounds on the Overhead of Indistinguishability Obfuscation

Explore the theoretical foundations of indistinguishability obfuscation through this 49-minute conference talk that establishes fundamental lower bounds on obfuscation overhead. Examine how multi-output circuits of size s require significant computational overhead when obfuscated, with the speaker demonstrating that under the worst-case assumption that NP is not in BPP, any efficient indistinguishability obfuscation scheme must output circuits of size s + o(s/log s). Learn about the innovative proof techniques that connect obfuscation theory to meta-complexity, building upon the NP-hardness of circuit minimization for multi-output circuits. Discover how this research integrates advanced concepts from cryptography and complexity theory to prove that secure and efficient iO schemes must incur at least an s/log s additive overhead in the size of obfuscated circuits. Gain insights into cutting-edge theoretical computer science research that bridges obfuscation, circuit complexity, and computational hardness assumptions, presented as part of collaborative work advancing our understanding of the fundamental limitations of cryptographic obfuscation schemes.