Paper 2022/969

Certified Everlasting Functional Encryption

Taiga Hiroka, Kyoto University
Tomoyuki Morimae, Kyoto University
Ryo Nishimaki, NTT (Japan)
Takashi Yamakawa, NTT (Japan)

Computational security in cryptography has a risk that computational assumptions underlying the security are broken in the future. One solution is to construct information-theoretically-secure protocols, but many cryptographic primitives are known to be impossible (or unlikely) to have information-theoretical security even in the quantum world. A nice compromise (intrinsic to quantum) is certified everlasting security, which roughly means the following. A receiver with possession of quantum encrypted data can issue a certificate that shows that the receiver has deleted the encrypted data. If the certificate is valid, the security is guaranteed even if the receiver becomes computationally unbounded. Although several cryptographic primitives, such as commitments and zero-knowledge, have been made certified everlasting secure, there are many other important primitives that are not known to be certified everlasting secure. In this paper, we introduce certified everlasting FE. In this primitive, the receiver with the ciphertext of a message $m$ and the functional decryption key of a function $f$ can obtain $f(m)$ and nothing else. The security holds even if the adversary becomes computationally unbounded after issuing a valid certificate. We, first, construct certified everlasting FE for P/poly circuits where only a single key query is allowed for the adversary. We, then, extend it to $q$-bounded one for NC1 circuits where $q$-bounded means that $q$ key queries are allowed for the adversary with an a priori bounded polynomial $q$. For the construction of certified everlasting FE, we introduce and construct certified everlasting versions of secret-key encryption, public-key encryption, receiver non-committing encryption, and a garbling scheme, which are of independent interest.

Available format(s)
Publication info
Quantum Cryptography Functional Encryption Certified Deletion
Contact author(s)
taiga hiroka @ yukawa kyoto-u ac jp
tomoyuki morimae @ yukawa kyoto-u ac jp
ryo nishimaki zk @ hco ntt co jp
takashi yamakawa ga @ hco ntt co jp
2022-07-28: approved
2022-07-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Taiga Hiroka and Tomoyuki Morimae and Ryo Nishimaki and Takashi Yamakawa},
      title = {Certified Everlasting Functional Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2022/969},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.