Faculty Candidate: Yael Tauman Kalai/Electrical Engineering and Computer Science Department MIT Limits of Obfuscation in ACES 2.302

Contact Name: 
Jenna Whitney
Date: 
Mar 7, 2006 11:00am - 12:00pm


There is a signup schedule for thi

s event.

Speaker Name/Affiliation: Yael Tauman Kalai/Electrical Eng

ineering and Computer Science MIT

Talk Title: Limits of Obfuscatio

n

Date/Time: March 7 2006 at 11:00 a.m.

Coffee: 10:45 a.m.<

br>
Location: ACES 2.302

Host: Anna Gal

Talk Abstract:The goal of code obfuscation is to make a program completely
unintelli

gible while preserving its functionality. Obfuscation
has been used fo

r years in attempts to prevent reverse engineering
e.g. in copy prote

ction and licensing schemes. Recently spammers
have utilized it to co

nceal code that spawns pop-ups. Finally
obfuscation is a cryptographe

r''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 demonst

rated the existence of a (contrived) class of functions
that cannot be

obfuscated. In contrast Canetti and Wee gave
an obfuscator for a parti

cular class of simple functions called point
functions that output 1

on a single point (and output 0 everywhere
else). Thus it seemed compl

etely possible that most functions of interest can be obfuscated
even

though in principle general purpose obfuscation is impossible.

We ar

gue that this is unlikely to be the case by showing
that general class

es of functions that one would like to obfuscate are
actually not obfu

scatable. 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 obfusca

tion model of Barak et
al (2001) that includes auxiliary input.