Informally, an <i>obfuscator</i> <b>O</b> is an (efficient, probabilistic)
"compiler" that takes as input a program (or circuit) <b>P</b> and
produces a new program <b>O(P)</b> that has the same functionality as <b>P</b>
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 <b>O(P)</b>
is a "virtual black box," in the sense that anything one can
efficiently compute given <b>O(P)</b>, one could also efficiently compute
given oracle access to <b>P</b>.
<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 <b>F</b> that are <i> unobfuscatable </i>
in the following sense: there is a property <b>\pi : F -> {0,1}</b>
such that (a) given <i>any program</i> that computes a function
<b>f\in F</b>, the value <b>\pi(f)</b> can be efficiently computed, yet (b) given
<i>oracle access</i> to a (randomly selected) function <b>f\in F</b>, no
efficient algorithm can compute <b>\pi(f)</b> much better than random
guessing.
<p>
We extend our impossibility result in a number of ways, including
even obfuscators that (a) are not necessarily computable in polynomial
time, (b) only <i>approximately</i> preserve the functionality, and
(c) only need to work for very restricted models of computation
(<b>TC_0</b>). We also rule out several potential applications of
obfuscators, by constructing "unobfuscatable" signature schemes,
encryption schemes, and pseudorandom function families.