Code Obfuscation: Is It Possible?

The problem of program obfuscation, which practitioners have been engaged in for many years, has recently received attention in the theoretical community as well. This was initiated by the work of Barak etal who formulated the notion circuit obfuscation. Loosely speaking, the goal of circuit obfuscation is to make a circuit "unintelligible" while preserving its functionality. More formally, this is captured via the "virtual black box" property, which asserts that any predicate that can be computed by a polynomial time distinguisher from the obfuscated circuit can also be computed from the input-output behavior of the circuit (i.e., given black-box access to the circuit). Barak et al show that there exist contrived families of functions which are strongly unlearnable from their input-output behavior, and yet any obfuscated circuit notion of code obfuscation. In contrast, Canetti and Wee show how to obfuscate point functions under various complexity assumptions. A point function "I_x" is a boolean function of the form "I_x(y)=1" if and only if "x=y" (one make think of "x" as a password and the obfuscation of "I_x" as a public program that checks whether "y" is a valid password or not). Thus, it would seem possible that most programs of interest can be obfuscated even though in principle general purpose obfuscators do not exist.

In new work, Professor Goldwasser and Yael Tauman, show that this is unlikely to be the case. We consider the notion of obfuscation w.r.t. auxiliary input, which corresponds to the setting where the adversary which is given the obfuscated circuit may have some a priori information. This is essentially the case of interest in any usage of obfuscation we imagine. We prove that there exist many natural classes of functions that cannot be obfuscated w.r.t to auxiliary input, both when the auxiliary input is dependent on the function being obfuscated and even when the auxiliary input is independent of the function being obfuscated.

We also give a positive result. In particular, we show that any obfuscator for the class of point functions is also an obfuscator w.r.t. independent auxiliary input.