Paper 2013/665

The Impossibility of Obfuscation with a Universal Simulator

Henry Cohn, Shafi Goldwasser, and Yael Tauman Kalai

Abstract

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 $$ be a circuit family with super-polynomial pseudo-entropy, and suppose $$ is a candidate obfuscator with universal simulator $$. We demonstrate the existence of an adversary $$ that, given the obfuscation $$, learns a predicate the simulator $$ cannot learn from the code of $$ and black-box access to $$. Furthermore, this is true in a strong sense: for \emph{any} secret predicate $$ that is not learnable from black-box access to $$, there exists an adversary that given $$ efficiently recovers $$, whereas given oracle access to $$ and given the code of the adversary, it is computationally hard to recover $$. 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.

Note: Added a note: "This is an out of date draft. The paper was merged with More on the Impossibility of Virtual-Black-Box Obfuscation with Auxiliary Input by Nir Bitansky, Ran Canetti, Omer Paneth, and Alon Rosen to form The Impossibility of Obfuscation with Auxiliary Input or a Universal Simulator by all seven authors (available as arXiv:1401.0348)."