Cryptology ePrint Archive: Report 2001/069

On the (Im)possibility of Obfuscating Programs

Boaz Barak and Oded Goldreich and Russell Impagliazzo and Steven Rudich and Amit Sahai and Salil Vadhan and Ke Yang

Abstract: Informally, an {\em obfuscator} $O$ is an (efficient, 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 ``unintelligible'' in some sense. Obfuscators, if they exist, would have a wide variety 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 meaning that $O(P)$ is a ``virtual black box,'' in the sense that anything one can efficiently compute given $O(P)$, one could also efficiently 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 intuition, obfuscation is impossible. We prove this by constructing a family of functions $F$ that are {\em \inherently unobfuscatable} in the following sense: there is a property $\pi : F \rightarrow \{0,1\}$ such that (a) given {\em any program} that computes a function $f\in F$, the value $\pi(f)$ can be efficiently computed, yet (b) given {\em oracle access} to a (randomly selected) function $f\in F$, no efficient algorithm can compute $\pi(f)$ much better than random guessing.

We extend our impossibility result in a number of ways, including even obfuscators that (a) are not necessarily computable in polynomial time, (b) only {\em approximately} preserve the functionality, and (c) only need to work for very restricted models of computation ($TC_0$). We also rule out several potential applications of obfuscators, by constructing ``unobfuscatable'' signature schemes, encryption schemes, and pseudorandom function families.

Category / Keywords: foundations / complexity theory, software protection, homomorphic encryption, Rice's Theorem, software watermarking, pseudorandom functions, statistical zero knowledge

Publication Info: Extended abstract in CRYPTO 2001. Also posted on Electronic Colloquium on Computational Complexity.

Date: received 15 Aug 2001

Contact author: boaz at wisdom weizmann ac il

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20010815:163452 (All versions of this report)

Short URL: ia.cr/2001/069

Discussion forum: Show discussion | Start new discussion