We present a generic construction of indistinguishability obfuscation from public-key functional encryption with succinct ciphertexts and sub-exponential security. This shows the equivalence of indistinguishability obfuscation and public-key functional encryption, a primitive that has so far seemed to be much weaker, lacking the power and the staggering range of applications of indistinguishability obfuscation.
As an application, we obtain a new candidate IO construction based on the functional encryption scheme of Garg, Gentry, Halevi, and Zhandry [Eprint 14] under their assumptions on multi-linear graded encodings. We also show that, under the Learning with Errors assumptions, our techniques imply that any indistinguishability obfuscator can be converted to one where obfuscated circuits are of linear size in the size of the original circuit plus a polynomial overhead in its depth.
Our reduction highlights the importance of ciphertext succinctness in functional encryption schemes, which we hope will serve as a pathway to new IO constructions based on solid cryptographic foundations.
Category / Keywords: foundations / obfuscation, functional encryption Original Publication (with minor differences): FOCS 2015 Date: received 25 Feb 2015, last revised 18 Jul 2015 Contact author: nirbitan at csail mit edu Available format(s): PDF | BibTeX Citation Version: 20150719:023055 (All versions of this report) Short URL: ia.cr/2015/163 Discussion forum: Show discussion | Start new discussion