TR01-057 Authors: Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang

Publication: 16th August 2001 14:08

Downloads: 1400

Keywords:

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.