[Colloquium] REMINDER: today's talk by Yael Tauman Kalai

[Margery Ishmael]

DEPARTMENT OF COMPUTER SCIENCE - TALK

Date: Friday, March 10, 2006
Time: 2:30 p.m.
Place: Ryerson 251

-------------------------------------------

Speaker:  YAEL TAUMAN KALAI

From:  MIT

Url:  http://www.mit.edu/~tauman/

Title:  Limits of Code Obfuscation

Abstract:

The goal of code obfuscation is to make a program completely
"unintelligible" while preserving its functionality.  Code 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, code
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 code 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.)

***The talk will be followed by refreshments in Ryerson 255***

-------------------------------------------------------

Host:  Lance Fortnow

People in need of assistance should call 773-834-8977 in advance.

For information on future CS talks: http://www.cs.uchicago.edu/events




-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20060310/b993b31c/attachment.htm