• People
• Events
• Research

Informally, program obfuscation aims at making a program "unintelligible" while preserving its functionality. Whereas practitioners have been engaged in attempts of program obfuscation for many years for purposes of defeating software reverse engineering, its mere theoretical possibility has only recently received attention in the theoretical community.

In particular, the work of Barak et. al. formalized the goal of circuit obfuscation via the "virtual black box" property, which asserts that any predicate that can be computed (in polynomial time) 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). It was shown that (contrived) classes of functions that are not obfuscatable exist. In contrast, Canetti and Wee show, under various complexity assumptions, how to obfuscate a particular class of simple functions, called the point (or password) functions, which take the value 1 on exactly one input and are zero on all other inputs. Thus, it seemed completely possible that most functions of interest can be obfuscated even though in principle general purpose obfuscators do not exist.

In this talk we will show that this is unlikely to be the case. In particular, we consider the notion of obfuscation in settings where the adversary, which is given the obfuscated circuit, may have some additional prior information. We first argue that any useful positive result about the possibility of obfuscation must satisfy this extended definition. We will then prove that there exist many natural classes of functions that cannot be obfuscated with respect 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.

Joint work with Yael Tauman Kalai.