Registered Attribute-Based Encryption with Publicly Verifiable Certified Deletion, Everlasting Security, and More
This work addresses the critical problem of achieving irreversible data deletion in decentralized cryptographic systems for users and organizations concerned with data privacy and regulatory compliance. It is an incremental advancement in cryptographic primitives.
This paper introduces the first Registered Attribute-Based Encryption (RABE) schemes that support certified deletion, ensuring encrypted data can be irreversibly deleted. It presents both privately and publicly verifiable RABE with Certified Deletion (RABE-CD) and extends these to include Certified Everlasting Deletion (RABE-CED), which provides information-theoretic message privacy against unbounded adversaries after deletion.
Certified deletion ensures that encrypted data can be irreversibly deleted, preventing future recovery even if decryption keys are later exposed. Although existing works have achieved certified deletion across various cryptographic primitives, they rely on central authorities, leading to inherent escrow vulnerabilities. This raises the question of whether certified deletion can be achieved in decentralized frameworks such as Registered Attribute-Based Encryption (RABE) that combines fine-grained access control with user-controlled key registration. This paper presents the first RABE schemes supporting certified deletion and certified everlasting security. Specifically, we obtain the following: - We first design a privately verifiable RABE with Certified Deletion (RABE-CD) scheme by combining our newly proposed shadow registered ABE (Shad-RABE) with one-time symmetric key encryption with certified deletion. - We then construct a publicly verifiable RABE-CD scheme using Shad-RABE, witness encryption, and one-shot signatures, allowing any party to validate deletion certificates without accessing secret keys. - We also extend to privately verifiable RABE with Certified Everlasting Deletion (RABE-CED) scheme, integrating quantum-secure RABE with the certified everlasting lemma. Once a certificate is produced, message privacy becomes information-theoretic even against unbounded adversaries. -We finally realize a publicly verifiable RABE-CED scheme by employing digital signatures for the BB84 states, allowing universal verification while ensuring that deletion irreversibly destroys information relevant to decryption.