Subject: Interesting Talk at HARVARD next Thursday.
From: Shafi Goldwasser (shafi@theory.lcs.mit.edu)
Date: Fri Jul 20 2001 - 20:29:24 EDT
[I thought this might be of interest considering the several POPL
papers we've seen recently on obfuscation. --Mitch]
Title: On the (Im)possibility of Obfuscating Programs
Speaker: Boaz Barak (Weizmann Institute of Science)
Time: Thursday 7/26, 3 PM
Place: Room G125, Maxwell Dworkin Laboratory, Harvard University
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, but 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 inherently unobfuscatable in the following
sense: there is a property p such that (a) given *any* program that
computes a function f inthe family F, the value p(f) can be efficiently
computed, yet (b) given oracle access to a (randomly selected) function f
in the familiy F, no efficient algorithm can compute p(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 (e.g., TC_0). We also rule
out several potential applications of obfuscators, by constructing
``unobfuscatable'' signature schemes, encryption schemes, and pseudorandom
function families.
Joint work with Oded Goldreich, Russell Impagliazzo , Steven Rudich,
Amit Sahai, Salil Vadhan and Ke Yang.
This archive was generated by hypermail 2b28 : Mon Jul 23 2001 - 12:18:05 EDT