Paper 2021/1018

Obfustopia Built on Secret-Key Functional Encryption

Fuyuki Kitagawa, Ryo Nishimaki, and Keisuke Tanaka


We show that indistinguishability obfuscation (IO) for all circuits can be constructed solely from secret-key functional encryption (SKFE). In the construction, SKFE needs to be secure against an unbounded number of functional key queries, that is, collusion-resistant. Our strategy is to replace public-key functional encryption (PKFE) in the construction of IO proposed by Bitansky and Vaikuntanathan (FOCS 2015) with puncturable SKFE. Bitansky and Vaikuntanathan introduced the notion of puncturable SKFE and observed that the strategy works. However, it has not been clear whether we can construct puncturable SKFE without assuming PKFE. In particular, it has not been known whether puncturable SKFE is constructed from standard SKFE. In this work, we show that a relaxed variant of puncturable SKFE can be constructed from collusion-resistant SKFE. Moreover, we show that the relaxed variant of puncturable SKFE is sufficient for constructing IO. In addition, we also study the relation of collusion-resistance and succinctness for SKFE. Functional encryption is said to be weakly succinct if the size of its encryption circuit is sub-linear in the size of functions. We show that collusion-resistant SKFE can be constructed from weakly succinct SKFE supporting only one functional key. By combining the above two results, we show that IO for all circuits can be constructed from weakly succinct SKFE supporting only one functional key.

Note: This is the full version of the conference proceedings version, which appeared in Eurocrypt 2018. This is also the merged full version of Cryptology ePrint report 2017/361 and 2017/638

Available format(s)
Publication info
A major revision of an IACR publication in EUROCRYPT 2018
Indistinguishability obfuscationsecret-key functional encryptionsuccinctnesscollusion-resistance
Contact author(s)
ryo nishimaki zk @ hco ntt co jp
ryo nishimaki @ gmail com
fuyuki kitagawa yh @ hco ntt co jp
2021-08-06: received
Short URL
Creative Commons Attribution


      author = {Fuyuki Kitagawa and Ryo Nishimaki and Keisuke Tanaka},
      title = {Obfustopia Built on Secret-Key Functional Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1018},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.