Cryptology ePrint Archive: Report 2015/1023

Indistinguishability Obfuscation with Constant Size Overhead

Prabhanjan Ananth and Abhishek Jain and Amit Sahai

Abstract: Present constructions of indistinguishability obfuscation (iO) 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.

In this work, we construct the first iO scheme that achieves only a {\em constant} multiplicative overhead (in fact, the constant is 2) in the size of the program. The security of our construction requires the existence of sub-exponentially secure \iO for circuits (that has any polynomial multiplicative overhead in the circuit size) and one-way functions.

Category / Keywords:

Date: received 22 Oct 2015, last revised 16 Nov 2015

Contact author: prabhanjan va at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20151116:181951 (All versions of this report)

Short URL: ia.cr/2015/1023

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]