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 ``unreadable'' 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 ``unreadability'' 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 inherently unobfuscatable in the following
sense: there is a predicate pi such that (a) given any program that
computes a function f in F, the value pi(f) can be efficiently computed,
yet (b) given 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 approximately preserve the functionality, and (c) only need to
work for very restricted models of computation TC0). We also rule out
several potential applications of obfuscators, by constructing
``unobfuscatable'' signature schemes, encryption schemes, and pseudorandom
function families.

## Recent comments

13 hours 2 min ago

15 hours 18 min ago

17 hours 9 min ago

20 hours 48 min ago

1 day 10 hours ago

1 day 13 hours ago

1 day 19 hours ago

2 days 5 hours ago

2 days 6 hours ago

2 days 7 hours ago