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.
|
