Gerard Salton
Lecture Series

Thursday, September 22, 2005
4:15 pm
B17 Upson Hall

Shafi Goldwasser

On the Impossibility of Obfuscation with Auxiliary Input

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, its mere 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 where Ipasswd(y)=1 if and only if y=passwd. 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 w.r.t. auxiliary input, which corresponds to the setting where the adversary, which is given the obfuscated circuit, may have some additional priori 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 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.

This is joint work with Yael Tauman Kalai.


Shafi Goldwasser is the RSA Professor of Electrical Engineering and Computer Science in MIT, and a professor of mathematical sciences at the Weizmann Institute of Science, Israel. She received her Ph.D in computer science from UC Berkeley in 1983. She joined MIT in 1983, and in 1997 became the first holder of the RSA Professorship. She is a member of the Theory of Computation group at MIT Computer Science and Artificial Intelligence Laboratory.

Goldwasser's research areas include complexity theory, cryptography and computational number theory. She is the co-inventor of zero-knowledge proofs, which probabilistically and interactively demonstrate the validity of an assertion without conveying any additional knowledge, and are a key tool in the design of cryptographic protocols. Her work in complexity theory includes the classification of approximation problems, showing that some problems in NP remain hard even when only an approximate solution is needed.

For these groundbreaking results, Goldwasser has twice won the Gödel Prize in theoretical computer science: first in 1993 (for "The knowledge complexity of interactive proof systems"), and again in 2001 (for "Interactive Proofs and the Hardness of Approximating Cliques"). Other awards include the ACM Grace Murray Hopper Award (1996) for outstanding young computer professional of the year and the RSA Award in Mathematics (1998) for outstanding mathematical contributions to cryptography. In 2001 she was elected to the American Academy of Arts and Sciences, in 2004 she was elected to the National Academy of Science, and in 2005 to the National Academy of Engineering.