## On the (Im)possibility of Obfuscating Programs

#### Webpage for a paper by Boaz Barak, Oded Goldreich,
Rusell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang

#### Abstract

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.

#### Material available on-line

Back to
either Oded Goldreich's homepage.
or general list of papers.