On the (im)possibility of obfuscating programs

Abstract. Informally, an obfuscator O is an (ecient, probabilistic) \compiler " that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is \unintel-ligible " in some sense. Obfuscators, if they exist, would have a wide vari-ety of cryptographic and complexity-theoretic applications, ranging from software protection to homomorphic encryption to complexity-theoretic analogues of Rice’s theorem. Most of these applications are based on an interpretation of the \unintelligibility " condition in obfuscation as mean-ing that O(P) is a \virtual black box, " in the sense that anything one can eciently compute given O(P), one could also eciently compute given oracle access to P. In this work, we initiate a theoretical investigation of obfuscation. Our main result is that, even under very weak formalizations of the above in-tuition, obfuscation is impossible. We prove this by constructing a family of functions F that are inherently unobfuscatable in the following sense