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 



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.