Milner Lecture 2006

Shafi Goldwasser:
On the Impossibility of Obfuscation

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

Abstract:

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.

This is a public lecture, open to all. It is one of a range of events comprising the University of Edinburgh Informatics Jamboree, 7-9 June, 2006.

Biography:

Shafrira (Shafi) Goldwasser is the RSA Professor of electrical engineering and computer science at MIT, and is also professor of mathematical sciences at the Weizmann Institute of Science, Israel.

Her first degree was in mathematics from CMU, and she then moved to Berkeley for graduate study. She joined MIT in 1983, becoming the first RSA Professor in 1997.

Her research areas include complexity theory, cryptography and computational number theory. She is the co-inventor of zero-knowledge proofs, which use interactive protocols to demonstrate with high probability the validity of an assertion, without conveying any other information than its validity; these are a key tool in the design of such things as anonymous electronic money. In complexity theory she applied interactive proofs to show that some problems in NP remain hard even when only an approximate solution is needed.

Shafi Goldwasser was the first person to be twice a co-winner of the Gödel Prize: first in 1993 for the original work on interactive proof systems, and again in 2001 for the work on hardness of approximation. She has also won the ACM Grace Murray Hopper Award and the RSA Award in Mathematics. She is a member of the American Academy of Arts and Sciences, the U.S. National Academy of Science, and the U.S. National Academy of Engineering.