International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: On the (Im)possibility of Obfuscating Programs

Authors:
Boaz Barak
Oded Goldreich
Russell Impagliazzo
Steven Rudich
Amit Sahai
Salil P. Vadhan
Ke Yang
Download:
URL: http://eprint.iacr.org/2001/069
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2001-11481,
  title={On the (Im)possibility of Obfuscating Programs},
  booktitle={IACR Eprint archive},
  keywords={foundations / complexity theory, software protection, homomorphic encryption, Rice's Theorem, software watermarking, pseudorandom functions, statistical zero knowledge},
  url={http://eprint.iacr.org/2001/069},
  note={Extended abstract in CRYPTO 2001.  Also posted on Electronic Colloquium on Computational Complexity. boaz@wisdom.weizmann.ac.il 11549 received 15 Aug 2001},
  author={Boaz Barak and Oded Goldreich and Russell Impagliazzo and Steven Rudich and Amit Sahai and Salil P. Vadhan and Ke Yang},
  year=2001
}