Summer 2015

Obfuscation with Constant Multiplicative Size Overhead

Monday, June 8th, 2015 2:45 pm3:15 pm

Add to Calendar


Prabhanjan Ananth, UCLA

2015 Simons Award Winner 




Calvin Lab Auditorium

All current constructions of indistinguishability obfuscation create obfuscated programs where the size of the obfuscated program is at least a factor of a security parameter larger than the size of the original program, plus additive terms involving a polynomial in the security parameter and a bound on the size of the input to the program being obfuscated. 

In this work, we show how to construct the first indistinguishability obfuscation scheme that achieves only a constant multiplicative overhead in the size of the program.  The security of our construction requires only the existence of a (sub-exponentially secure) indistinguishability obfuscation scheme for circuits that has any polynomial multiplicative overhead and one-way functions.

Joint work with Abhishek Jain and Amit Sahai.