Paper 2015/163

Indistinguishability Obfuscation from Functional Encryption

Nir Bitansky and Vinod Vaikuntanathan


Indistinguishability obfuscation (IO) is a tremendous notion, powerful enough to give rise to almost any known cryptographic object. Prior candidate IO constructions were based on specific assumptions on algebraic objects called multi-linear graded encodings. We present a generic construction of indistinguishability obfuscation from public-key functional encryption with succinct encryption circuits and subexponential security. This shows the equivalence of indistinguishability obfuscation and public-key functional en- cryption, a primitive that has previously seemed to be much weaker, lacking the power and the staggering range of applications of indistinguishability obfuscation. Our main construction can be based on functional encryption schemes that support a single functional key, and where the encryption circuit grows sub-linearly in the circuit-size of the function. We further show that sublinear succinctness in circuit-size for single-key schemes can be traded with sublinear succinctness in the number of keys (also known as the collusion-size) for multi-key schemes. We also show that, under the Learning with Errors assumption, our techniques imply that any indistinguishability obfuscator can be converted into one where the size of obfuscated circuits is twice that of the original circuit plus an additive overhead that is polynomial in its depth, input length, and the security parameter.

Available format(s)
Publication info
Published elsewhere. Major revision. FOCS 2015
obfuscationfunctional encryption
Contact author(s)
nbitansky @ gmail com
2018-07-03: last of 5 revisions
2015-02-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nir Bitansky and Vinod Vaikuntanathan},
      title = {Indistinguishability Obfuscation from Functional Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2015/163},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.