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.