University Homepage School Homepage School Contacts School Search

The Milner Lecture

Before he left Edinburgh for Cambridge, Robin Milner very kindly donated a sum of money to fund an annual lecture in Computer Science at the University of Edinburgh, to be given by someone from outside the University who has done or is doing excellent and original theoretical work which has a perceived significance for practical computing. The spirit of the proposal is to keep a live connection between theory and application in computer science.

Milner Lecture 2006

Professor Shafi Goldwasser
RSA Professor of Electrical Engineering and Computer Science at Massachusetts Institute of Technology

5.15 pm on Wednesday, 7 June 2006, Swann Lecture Theatre, Michael Swann Building, The King's Buildings

On the Impossibility of Obfuscation

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.