Paper 2017/638

From Single-Key to Collusion-Resistant Secret-Key Functional Encryption by Leveraging Succinctness

Fuyuki Kitagawa, Ryo Nishimaki, and Keisuke Tanaka


We show how to construct secret-key functional encryption (SKFE) supporting unbounded polynomially many functional decryption keys, that is, collusion-resistant SKFE solely from SKFE supporting only one functional decryption key. The underlying single-key SKFE needs to be weakly succinct, that is, the size of its encryption circuit is sub-linear in the size of functions. We show we can transform any quasi-polynomially secure single-key weakly-succinct SKFE into quasi-polynomially secure collusion-resistant one. In addition, if the underlying single-key SKFE is sub-exponentially secure, then so does the resulting scheme in our construction. Some recent results show the power and usefulness of collusion-resistant SKFE. From our result, we see that succinct SKFE is also a powerful and useful primitive. In particular, by combining our result and the result by Kitagawa, Nishimaki, and Tanaka (ePrint 2017), we can obtain indistinguishability obfuscation from sub-exponentially secure weakly succinct SKFE that supports only a single functional decryption key.

Available format(s)
Publication info
A major revision of an IACR publication in EUROCRYPT 2018
Secret-key functional encryptionCollusion-resistanceSuccinctnessObfuscation
Contact author(s)
kitagaw1 @ is titech ac jp
ryo nishimaki @ gmail com
2018-02-19: last of 5 revisions
2017-07-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fuyuki Kitagawa and Ryo Nishimaki and Keisuke Tanaka},
      title = {From Single-Key to Collusion-Resistant Secret-Key Functional Encryption by Leveraging Succinctness},
      howpublished = {Cryptology ePrint Archive, Paper 2017/638},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.