Welcome to the resource topic for 2001/069
Title:
On the (Im)possibility of Obfuscating Programs
Authors: Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang
Abstract:Informally, an {\em 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 {\em \inherently
unobfuscatable} in the following sense: there is a
property \pi : F \rightarrow \{0,1\} such that (a) given {\em
any program} that computes a function f\in F, the
value \pi(f) can be efficiently computed, yet (b) given
{\em 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 {\em 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.
ePrint: https://eprint.iacr.org/2001/069
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .