Limits of Obfuscation

January 23, 2006
Yael Tauman Kalai | MIT

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

Speaker Details

Yael Tauman Kalai is currently completing her Ph.D. in cryptography at MIT under the supervision of Shafi Goldwasser. Prior to this, she received her master’s degree from Adi Shamir at the Weizmann Institute, and her BS from the Hebrew University of Jerusalem.