The goal of code obfuscation is to make a program completely "unintelligible" while preserving its functionality.  Obfuscation has been used for years in attempts to prevent reverse engineering, e.g., in copy protection and licensing schemes.  Recently, spammers have utilized it to conceal code that spawns pop-ups.  Finally, 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!).

 

Barak et al (2001) formalized the notion of obfuscation and demonstrated the existence of a (contrived) class of functions that 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 *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.

Monday, April 17 , 2006

3330 Walnut Street

307 Levine Hall

3:00pm - 4:15 pm