The Impossibility of Obfuscation with a Universal Simulator

We show that indistinguishability obfuscation implies that all functions with sufficient "pseudo-entropy" cannot be obfuscated under a virtual black box definition with a universal simulator. Let F = {fs} be a circuit family with super-polynomial pseudo-entropy, and suppose O is a candidate obfuscator with universal simulator S. We demonstrate the existence of an adversary A that, given the obfuscation O(fs), learns a predicate the simulator S cannot learn from the code of A and black-box access to fs. Furthermore, this is true in a strong sense: for any secret predicate P that is not learnable from black-box access to fs, there exists an adversary that given O(fs) efficiently recovers P (s), whereas given oracle access to fs and given the code of the adversary, it is computationally hard to recover P (s).

We obtain this result by exploiting a connection between obfuscation with a universal simulator and obfuscation with auxiliary inputs, and by showing new impossibility results for obfuscation with auxiliary inputs.