# On the (Im)possibility of Obfuscating Programs

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

### Abstract

Informally, an *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
programs **F** that are *unobfuscatable** *in
the sense that (a) given *any*
efficient program **P' **that computes
the same function as a program **P**\in **F**, the “source code” **P** can be efficiently reconstructed, yet (b) given *oracle access* to a (randomly selected) program
**P**\in **F**, no efficient algorithm can reconstruct **P** (or even distinguish a certain bit in the code from random)
except with negligible probability.

We extend our impossibility result in a number of ways, including even
obfuscators that (a) are not necessarily computable in
polynomial time, (b) only *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.

### Versions

*Advances in Cryptology -
CRYPTO `01, *vol. 2139 of Lecture Notes in Computer Science, pp. 1-18,
Santa Barbara, CA, August 19-23, 2001. Springer-Verlag.
[Springer page]
*Electronic Colloquium on
Computational Complexity *TR01-057.

*Cryptology ePrint Archive *Report
2001/069.

[postscript][compressed
postscript]
- Revision, December 2007. [pdf]
- Revision, August 2010. [pdf]

[ back to Salil Vadhan's research
interests ]