A Cryptographic Approach to Software Obfuscation

26 Sep
Computer Science Colloquium Series
Craig Gentry, IBM Thomas J. Watson Research Center
Thursday, September 26, 2013 - 4:00pm
Maxwell Dworkin G125

The goal of software obfuscation is to make a program "unintelligible" while preserving its functionality.  For decades, program obfuscation for general programs remained an art.  Obfuscation was first rigorously defined and studied by Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan and Yang.  Most famously, they defined a notion of virtual black box (VBB) obfuscation, and proved that this notion is impossible to realize in general:  i.e., some functions are VBB unobfuscatable.

Barak et al. also defined a weaker notion of indistinguishability obfuscation (iO), which avoids their impossibility results.  iO provides the same functionality guarantees as VBB obfuscation, but a weaker security guarantee - namely, that for any two circuits C0, C1 of similar size that compute the same function, it is hard to distinguish an obfuscation of C0 from an obfuscation of C1.  Despite this seemingly weak guarantee, iO provides "best possible obfuscation":  roughly speaking, in a provable sense, an indistinguishability obfuscator obfuscates circuits as well as any other obfuscator.

In this talk, we will describe new developments this year that for the first time provide a cryptographic approach to general-purpose iO (for all circuits), where our iO is secure unless an attacker can solve cryptographic problems that we believe to be intractible.  We will also discuss some implications of our results.

This talk is based on joint works with Sanjam Garg, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters.

Speaker Bio: 

Craig Gentry is a research scientist in the cryptography group at the IBM Thomas J. Watson Research Center.  He received his Ph.D. in computer science from Stanford in 2009 and won the 2009 ACM Doctoral Dissertation Award and the 2010 ACM Grace Murray Hopper Award for his work on developing the first fully homomorphic encryption scheme.  His research tends toward the mathematical side of applied cryptography, both constructive (designing efficient and highly functional cryptosystems) and destructive (cryptanalysis). 

Salil Vadhan
Gioia Sweetland