LIMITS OF OBFUSCATION
Speaker: YAEL TAUMAN KALAI , M.I.T. -- CSAIL
Date: March 1 2006
Time: 4:00PM
Location: Building 2, Room 143
Contact: Shirley Entzminger, 617 253 4347, daisymae@math.mit.edu
T O D A Y...
Special
APPLIED MATHEMATICS SEMINAR
DATE: Wednesday, March 1, 2006
TIME: 4:00 PM
LOCATION: Building 2, Room 143
(Reception at 3:30 PM in Room 2-349)
Title: LIMITS OF OBFUSCATION
Speaker: YAEL TAUMAN KALAI (M.I.T. -- CSAIL)
ABSTRACT:
The goal of program obfuscation is to make a program completely "unintelligible" while preserving its functionality. Obfuscation is a cryptographer's dream: nearly any cryptographic task could be achieved *securely* by writing a simple program and then obfuscating it (if possible!). In addition, obfuscation has been used for years in attempts to prevent reverse engineering.
Barak et al (2001) formalized the notion of obfuscation and demonstrated the existence of a (contrived) class of functions that provably cannot be obfuscated. In contrast, Canetti and Wee gave an obfuscator for 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 obfuscation is impossible.
We argue that this is unlikely to be the case, by showing that general classes of functions that one would like to obfuscate, are actually not obfuscatable. In particular, we show that for one of our classes, given an obfuscation of two functions in the class, each with a *secret* of its own, one can compute a hidden function of these secrets. Surprisingly, this holds even when the secrets are chosen completely independently of each other. Our results hold in an augmentation of the formal obfuscation model of Barak et al (2001) that includes auxiliary input.
Joint work with Shafi Goldwasser.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Massachusetts Institute of Technology
Department of Mathematics
Cambridge, MA 02139
See other events that are part of
See other events happening in March 2006
