Paper 2017/275

Simple and Generic Constructions of Succinct Functional Encryption

Fuyuki Kitagawa, Ryo Nishimaki, and Keisuke Tanaka


We propose simple generic constructions of succinct functional encryption. Our key tool is exponentially-efficient indistinguishability obfuscator (XIO), which is the same as indistinguishability obfuscator (IO) except that the size of an obfuscated circuit (or the running-time of an obfuscator) is slightly smaller than that of a brute-force canonicalizer that outputs the entire truth table of a circuit to be obfuscated. A ``compression factor'' of XIO indicates how much XIO compresses the brute-force canonicalizer. In this study, we propose a significantly simple framework to construct succinct functional encryption via XIO and show that XIO is a powerful enough to achieve cutting-edge cryptography. In particular, we propose the following constructions: Single-key weakly succinct secret-key functional encryption (SKFE) is constructed from XIO (even with a bad compression factor) and one-way function. Single-key weakly succinct public-key functional encryption (PKFE) is constructed from XIO with a good compression factor and public-key encryption. Single-key weakly succinct PKFE is constructed from XIO (even with a bad compression factor) and identity-based encryption. Our new framework has side benefits. Our constructions do not rely on any number theoretic or lattice assumptions such as decisional Diffie-Hellman and learning with errors assumptions. Moreover, all security reductions incur only polynomial security loss. Known constructions of weakly succinct SKFE or PKFE from XIO with polynomial security loss rely on number theoretic or lattice assumptions.

Note: Revised the title and introduction. Only minor edits in the technical parts.

Available format(s)
Publication info
A minor revision of an IACR publication in PKC 2018
Indistinguishability ObfuscationFunctional EncryptionSuccinctness
Contact author(s)
ryo nishimaki @ gmail com
kitagaw1 @ is titech ac jp
2018-02-16: last of 8 revisions
2017-03-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fuyuki Kitagawa and Ryo Nishimaki and Keisuke Tanaka},
      title = {Simple and Generic Constructions of Succinct Functional Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2017/275},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.