Cryptology ePrint Archive: Report 2015/730

Indistinguishability Obfuscation from Functional Encryption for Simple Functions, And a New Bootstrapping Theorem for iO

Prabhanjan Ananth and Abhishek Jain and Amit Sahai

Abstract: We show how to construct indistinguishability obfuscation (iO) for circuits from any non-compact functional encryption (FE) scheme with sub-exponential security against unbounded collusions. We accomplish this by giving a generic transformation from any such FE scheme into a compact FE scheme. By composing this with the transformation from sub-exponentially secure compact FE to iO (Ananth and Jain [CRYPTO'15], Bitansky and Vaikuntanathan [FOCS'15]), we obtain our main result.

Our result provides a new pathway to iO.

We use our technique to identify a simple function family for FE that suffices for our general result. We show that the function family F is complete, where every f in F consists of three evaluations of a Weak PRF followed by finite operations. We believe that this may be useful for realizing iO from weaker assumptions in the future.

Another corollary of our technique is a new bootstrapping theorem for iO. All previous bootstrapping theorems for iO required the following: In order to obfuscate a family of circuits C, it was necessary to obfuscate a shallow circuit family C' but where the size of the shallow circuit C' grew with the size of the general circuit C to be obfuscated. Our techniques give the first bootstrapping theorem where given subexponentially secure iO for a simple family of circuits C' of size k, it is possible to obfuscate a circuit of a size that is any polynomial in k.

Category / Keywords:

Date: received 21 Jul 2015, last revised 20 Oct 2015

Contact author: prabhanjan va at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20151021:052748 (All versions of this report)

Short URL: ia.cr/2015/730

Discussion forum: Show discussion | Start new discussion