• Calendar

January 10, Tuesday
12:00 – 14:00

Informally, program obfuscation aims at making a program "unintelligible" while preserving its functionality. Whereas practitioners have been attempting to obfuscate programs for many years, it has only recently received attention in the theoretical community.

Barak et al formalized the notion of obfuscation, and showed that there exist (contrived) classes of functions that cannot be obfuscated. In contrast, Canetti and Wee showed, under various complexity assumptions, how to obfuscate 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 obfuscators do not exist.

We show that this is unlikely to be the case. In particular, 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 additional a priori information.

We first argue that any useful positive result about the possibility of obfuscation must satisfy this extended definition. We then prove that there exist many natural classes of functions that cannot be obfuscated w.r.t. auxiliary input, both when the auxiliary input is dependent of the function being obfuscated and even when the auxiliary input is independent of the function being obfuscated

A short bio: I did my undergraduate studies in the Hebrew university in 1994-1997. I did my Master's degree in the Weizmann Institute in 1998-2001, under the supervision of Adi Shamir. I am currently doing my PhD at MIT, under the supervision of Shafi Goldwasser.