Welcome to the resource topic for
**2001/069**

**Title:**

On the (Im)possibility of Obfuscating Programs

**Authors:**
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, 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.

**ePrint:**
https://eprint.iacr.org/2001/069

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .