  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.
