Paper 2001/069
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 {\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 complexitytheoretic applications, ranging from software protection to homomorphic encryption to complexitytheoretic 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.
Metadata
 Available format(s)
 PS
 Category
 Foundations
 Publication info
 Published elsewhere. Extended abstract in CRYPTO 2001. Also posted on Electronic Colloquium on Computational Complexity.
 Keywords
 complexity theorysoftware protectionhomomorphic encryptionRice's Theoremsoftware watermarkingpseudorandom functionsstatistical zero knowledge
 Contact author(s)
 boaz @ wisdom weizmann ac il
 History
 20010815: received
 Short URL
 https://ia.cr/2001/069
 License

CC BY
BibTeX
@misc{cryptoeprint:2001/069, author = {Boaz Barak and Oded Goldreich and Russell Impagliazzo and Steven Rudich and Amit Sahai and Salil Vadhan and Ke Yang}, title = {On the (Im)possibility of Obfuscating Programs}, howpublished = {Cryptology ePrint Archive, Paper 2001/069}, year = {2001}, note = {\url{https://eprint.iacr.org/2001/069}}, url = {https://eprint.iacr.org/2001/069} }