[Colloquium] Guest Speaker @ TTI-C: Tauman Kalai (TODAY @10:00am)

[Katherine Cumming]

TTI-C Guest Speaker
 
Presented by:  Toyota Technological Institute at Chicago
 
Speaker: Yael Tauman Kalai, MIT
Speaker's home page: http://www.mit.edu/~tauman/
 
Date: Thursday, February 16 2006 
Location: TTI-C Conference Room
Time:  10:00 am
 
Title:
 
Limits of Obfuscation
 
Abstract:
 
The goal of code obfuscation is to make a program completely
"unintelligible" while preserving its functionality.  Obfuscation has been
used for years in attempts to prevent reverse engineering, e.g., in copy
protection and licensing schemes.  Recently, spammers have utilized it to
conceal code that spawns pop-ups.  Finally, 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!).
 
Barak et al (2001) formalized the notion of obfuscation and demonstrated the
existence of a (contrived) class of functions that 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)
 
----------------------------------------------------------------------------
------
If you have questions, or would like to meet the speaker, please contact
Katherine at 773-834-1994 or kcumming at tti-c.org.   
For information on future TTI-C talks and events, please go to the TTI-C
Events page:  http://www.tti-c.org/events.html.  TTI-C (1427 East 60th
Street, Chicago, IL  60637)
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20060216/f6a9e62c/attachment.htm