Abstract
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.