|
On the (Im)possibility of Obfuscating Programs
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich,
Amit Sahai, Salil Vadhan and Ke Yang
See also Can We Obfuscate Programs? - An non-technical description of
these results and their meaning.
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 "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 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 unobfuscatable in the following sense:
there is a property pi : F -> {0,1} 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 (TC_0). We
also rule out several potential applications of obfuscators, by constructing
"unobfuscatable" signature schemes, encryption schemes, and pseudorandom
function families.
Versions
-
Advances in Cryptology - CRYPTO `01, vol. 2139 of Lecture Notes
in Computer Science, pp. 1-18, Santa Barbara, CA, August 19-23, 2001. Springer-Verlag.
-
Electronic Colloquium on Computational Complexity TR01-057.
Cryptology ePrint Archive Report 2001/069.
[postscript]
Powerpoint XP presentation
home | research | links | cv | pictures
|