|
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.
Bio:
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.
|