NEW TIME: Wednesday,March 8, Volen 101, 2-3pm
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.
Joint work with Yael Tauman
Host: Liuba Shrira