Paper 2026/2699

Registered Functional Encryption with Certified Everlasting Security

Abstract

Registered functional encryption removes the trusted authority bottleneck of standard functional encryption by allowing users to register their own public keys, with a transparent aggregation procedure producing a compact master public key. On the other hand, certified everlasting deletion enables a recipient to produce a classical certificate guaranteeing that a ciphertext has been information-theoretically destroyed, even against computationally unbounded adversaries. In this work, we initiate the study of registered functional encryption with certified everlasting deletion (RFE-CED), combining both properties for the first time. We define the syntax and security of RFE-CED, capturing two complementary guarantees: everlasting privacy, which bounds the trace distance between residual adversarial states after certified deletion, and post-verification indistinguishability, which ensures the adversary cannot distinguish the encrypted message even after the deletion certificate is verified. To construct RFE-CED, we also introduce public-slot registered functional encryption (PS-RFE) as a building block, in which each registered function takes both a secret and an arbitrary public input. Combining PS-RFE with a pseudorandom and authenticated BB84 encodings, we obtain a secure slotted RFE-CED scheme with the help of an interactive version of certified everlasting lemma.