Audio and Slides
of Talk
November 22, 2006 -3:30 pm
Limits of Obfuscation
November 23, 2006 -3:30 pm
New Proofs for Hard Core Predicates
The goal of program obfuscation is to make a program completely
"unintelligible" while preserving its functionality.
Obfuscation is a cryptographer's dream: nearly any cryptographic
task could be achieved securely by writing a simple
program and then obfuscating it (if possible!). In addition,
obfuscation has been used for years in attempts to prevent
reverse engineering.
Barak et. al. (2001) formalized the notion of obfuscation
and demonstrated the existence of a (contrived) class of functions
that provably cannot be obfuscated. In contrast, Canetti and
Wee gave an obfuscator for a particular
class of simple functions, called point functions, that output
1 on a single point (and output 0 everywhere else). Thus,
it seemed completely possible that most functions of interest
can be obfuscated, even though in principle general
purpose obfuscation is impossible.
We argue that this is unlikely to be the case, by showing
that general classes of functions that one would like to obfuscate,
are actually not obfuscatable. In particular, we show that
for one of our classes, given an obfuscation of two functions
in the class, each with a secret of its own, one can
compute a hidden function of these secrets. Surprisingly,
this holds even when the secrets are chosen completely independently
of each other. Our results hold in an augmentation of the
formal obfuscation model of Barak et. al. (2001) that includes
auxiliary input.
We will also discuss alternatives to go outside the standard
software model, in which general program obfuscation may be
doable after all.
Joint work with Yael Tauman Kalai (a postdoc at the Weizmann
Institute)
Thematic Program Home page
The Fields Institute Coxeter Lecture Series (CLS) brings a leading
mathematician to the Institute to give a series of three lectures
in the field of the current thematic program. The first talk is
an overview for a general mathematical audience, postdoctoral
fellows and graduate students. The other two talks are chosen,
in collaboration with the organizers of the thematic program,
to target specialists in the field.
|
|
