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
$
\mathcal{F}
$
\mathcal{F}
that are
inherently unobfuscatable in the following sense: there is a property π:
$
\mathcal{F}
$
\mathcal{F}
→ {0,1} such that (a) given
any program that computes a function
f ∈
$
\mathcal{F}
$
\mathcal{F}
, the value π(
f) can be efficiently computed, yet (b) given
oracle access to a (randomly selected) function
f ∈
$
\mathcal{F}
$
\mathcal{F}
, no efficient algorithm can compute π(
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
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.