### Certified Everlasting Functional Encryption

##### Abstract

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)
Category
Foundations
Publication info
Preprint.
Keywords
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
History
2022-07-28: approved
See all versions
Short URL
https://ia.cr/2022/969

CC BY

BibTeX

@misc{cryptoeprint:2022/969,
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{https://eprint.iacr.org/2022/969}},
url = {https://eprint.iacr.org/2022/969}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.