Limits on the Power of Indistinguishability Obfuscation and Functional Encryption

摘要: Recent breakthroughs in cryptography have positioned indistinguishability obfuscation as a "central hub" for almost all known cryptographic tasks, and an extremely powerful building block new tasks resolving long-standing foundational open problems. However, constructions based on always rely non-black-box techniques, thus the extent to which it can be used has been completely unexplored so far. We present framework proving meaningful negative results power of obfuscation. By considering oracle-aided circuits, we capture common techniques that far These include, particular, such punctured programming approach Sahai Waters (STOC '14) its variants, well sub-exponential security assumptions. Within our prove first tightly related notion functional encryption. Our are follows: -- There is no fully black-box construction collision-resistant function family from obfuscator circuits. key-agreement protocol with perfect completeness private-key encryption scheme Specifically, any potential must suffer exponential loss, cannot circumvented using captures may wide variety primitives manner (e.g., Obfuscating or generating key uses evaluation circuit puncturable pseudorandom function), only assume underlying themselves manner.