Registered Attribute-Based Encryption with Publicly Verifiable Certified Deletion, Everlasting Security, and More

This paper presents the first Registered Attribute-Based Encryption (RABE) schemes that support both certified deletion and certified everlasting security in both privately and publicly verifiable settings, thereby enabling decentralized, fine-grained access control with irreversible data deletion and information-theoretic security against future adversaries.

The Gist

Imagine you have a super-secure digital safe (encryption) where you store your most precious secrets. You want to share these secrets with specific people based on rules (e.g., "Only doctors in New York can read this"). This is the world of Attribute-Based Encryption (ABE).

But here's the problem: In the digital world, once you copy a file, you can never truly delete it. Even if you tell someone to "delete" their copy, they might have a hidden backup. If their computer is hacked later, or if they get a master key, they can recover your secret. This is the nightmare of data permanence.

This paper introduces a revolutionary solution: Certified Deletion. It's like a magical shredder that, once used, makes it physically impossible to recover the paper, even if you find the original blueprints later.

However, most existing "shredders" rely on a single, powerful "God-like" authority to manage the keys. If that authority is hacked or corrupted, the whole system fails. This paper solves that by moving to a Decentralized system (Registered ABE), where no single person holds all the keys.

Here is the breakdown of their breakthrough, explained with simple analogies:

1. The Core Problem: The "Key Escrow" Trap

In traditional systems, a central boss (the Authority) holds the master key to everyone's safe.

• The Risk: If the boss is bribed, hacked, or makes a mistake, everyone's secrets are exposed. This is called "Key Escrow."
• The Goal: The authors wanted a system where users generate their own keys, and a neutral "Curator" just helps organize them, without ever seeing the secrets.

2. The New Magic Trick: "Shadow" Registration

To make certified deletion work in this decentralized world, the authors invented a new tool called Shadow Registered ABE (Shad-RABE).

• The Analogy: Imagine a theater play. The actors (users) have their scripts (keys). Usually, the director (Authority) holds the master script. In this new play, the director is blindfolded and only sees "shadows" of the actors.
• How it works: The system uses "Shadow" simulations. It allows the security proof to pretend that the system is working one way, while actually working another, without the "Director" ever needing to know the real secrets. This allows them to prove the system is secure even if the "Director" is malicious.

3. The Two Types of "Shredders" (Deletion)

The paper builds two versions of this system, depending on who needs to verify the deletion:

A. The Private Shredder (Privately Verifiable)

• How it works: You send a message. The receiver gets a quantum "ticket" (a special key). To delete the message, they burn the ticket and get a receipt.
• The Catch: Only the person who sent the message (who holds the matching key) can check if the receipt is real.
• The Metaphor: You send a letter. The receiver burns the envelope and gives you a receipt. Only you have the special ink to verify that the receipt is genuine. No one else can check.

B. The Public Shredder (Publicly Verifiable)

• How it works: This is the bigger breakthrough. Anyone in the world can look at the receipt and say, "Yes, this data is definitely gone forever."
• The Magic: They use a concept called "One-Shot Signatures."
  • Imagine a magic stamp that can stamp "YES" OR "NO," but never both.
  • To read the message, you need the "YES" stamp.
  • To delete the message, you use the stamp to make a "NO" signature.
  • The Quantum Rule: Once you stamp "NO," the laws of quantum physics say it is physically impossible to go back and stamp "YES" again. The ink has changed the paper forever.
  • The Result: Anyone can see the "NO" stamp and know the message is destroyed. No secret keys are needed to verify this.

4. The "Everlasting" Guarantee

The paper goes even further with Certified Everlasting Security.

• The Fear: What if in 50 years, computers become so powerful (Quantum Computers) that they can break today's encryption?
• The Solution: Once the deletion certificate is created, the security becomes Information-Theoretic.
• The Metaphor: It's not just that the lock is hard to pick; it's that the key never existed anymore. Even if a super-intelligent alien with infinite computing power arrives in the year 3000, they cannot recover the data because the quantum state required to unlock it was physically destroyed during the deletion process. The data is gone forever, not just "hard to find."

Summary of the Achievement

The authors have built the first system that combines:

1. Decentralization: No single boss holds the keys (solving the "Key Escrow" problem).
2. Fine-Grained Access: Only people with the right attributes (e.g., "Doctor," "New York") can read the data.
3. Certified Deletion: You can prove the data is destroyed.
4. Public Verification: Anyone can check the proof (not just the sender).
5. Everlasting Security: Even future super-computers cannot recover the data once it's deleted.

In a nutshell: They created a digital safe where you can invite specific people in, and then, with a single click, prove to the entire world that the safe has been melted down into dust, and no amount of future technology can ever put it back together. And they did it without needing a single "God" to watch over the whole process.

Technical Summary

Here is a detailed technical summary of the paper "Registered Attribute-Based Encryption with Publicly Verifiable Certified Deletion, Everlasting Security, and More" by Murshid, Sarkar, and Mandal.

1. Problem Statement

The paper addresses a critical gap in modern cryptography: the integration of Certified Deletion (CD) and Certified Everlasting Deletion (CED) into Registered Attribute-Based Encryption (RABE) without relying on a trusted central authority.

• The Context:
  • Certified Deletion: A mechanism ensuring that encrypted data, once deleted, is irretrievable even if decryption keys are later compromised. This relies on quantum mechanics (No-Cloning Theorem) and is impossible in purely classical settings.
  • Registered ABE (RABE): A decentralized encryption paradigm where users generate their own key pairs and register only their public keys with a "curator." The curator aggregates these keys into a master public key without ever seeing user secret keys, thereby eliminating the key-escrow vulnerability inherent in traditional Attribute-Based Encryption (ABE).
• The Challenge:
  • Existing certified deletion schemes (e.g., Broadbent et al., Hiroka et al.) rely on a central authority to manage keys or verify deletions.
  • In a decentralized RABE setting, the curator holds no secret information, making it difficult to coordinate the "destruction" of decryption capabilities required for certified deletion.
  • Current RABE schemes lack mechanisms to prove that data has been irreversibly deleted, either privately (to the sender) or publicly (to any third party).
  • There is no existing solution for Certified Everlasting Security (information-theoretic security after deletion) in a decentralized, attribute-based framework.

2. Methodology and Technical Approach

The authors propose a modular framework that combines advanced cryptographic primitives to achieve their goals. The core methodology involves three main pillars:

A. The Shadow Registered ABE (Shad-RABE) Primitive

To bridge the gap between decentralized registration and the simulation requirements of certified deletion, the authors introduce a new primitive called Shadow Registered ABE (Shad-RABE).

• Concept: Shad-RABE extends standard RABE with "simulation" algorithms (SimKeyGen, SimRegPK, SimCT, SimCorrupt, Reveal).
• Function: These algorithms allow a security challenger to generate "fake" keys and ciphertexts that are computationally indistinguishable from real ones but allow the challenger to "reveal" secret keys corresponding to specific messages later.
• Construction: It is built using:
  • Indistinguishability Obfuscation (iO): To obfuscate decryption circuits.
  • Zero-Knowledge Arguments (ZKA): To prove the validity of ciphertexts without revealing secrets.
  • Lattice-based RABE: For post-quantum security.
• Role: Shad-RABE serves as the foundational building block, enabling the security proofs for certified deletion in a setting where the curator is untrusted.

B. Hybrid Encryption Strategies

The paper proposes four distinct schemes based on two verification models (Private vs. Public) and two security levels (Standard CD vs. Everlasting CED):

1. RABE-PriVCD (Privately Verifiable Certified Deletion):

   • Mechanism: Uses a Two-Layer Encryption approach.
     • Layer 1: Encrypts a symmetric key using Shad-RABE based on attributes.
     • Layer 2: Encrypts the actual message using Symmetric Key Encryption with Certified Deletion (SKE-CD).
   • Verification: The sender holds the symmetric key (verification key) and can privately verify the deletion certificate.

2. RABE-PubVCD (Publicly Verifiable Certified Deletion):

   • Mechanism: Replaces the symmetric key with Witness Encryption (WE) and One-Shot Signatures (OSS).
     • The message is encrypted via WE, where the statement is "a valid signature on 0 exists."
     • The deletion certificate is a signature on 1.
     • Due to the One-Shot property, generating a signature on 1 makes it impossible to generate a signature on 0, rendering the Witness Encryption undecryptable.
   • Verification: Anyone can verify the signature on 1 using the public key, enabling public auditability.

3. RABE-PriVCED & RABE-PubVCED (Certified Everlasting Deletion):

   • Mechanism: These schemes achieve Information-Theoretic Security after deletion.
   • Core Technology: They utilize BB84 states (quantum states encoded in random bases) and the Certified Everlasting Lemma.
   • Process:
     • The message is masked using a quantum one-time pad derived from BB84 states.
     • The basis information ($\theta$) and masked message are encrypted classically using RABE.
     • Deletion: The user measures the quantum state in the wrong basis (Hadamard basis). This irreversibly destroys the information about the original state ($x$).
   • Security: Even if an adversary has unlimited computational power in the future, they cannot recover the message because the quantum information required to unmask it has been physically destroyed.
   • Public Version: Uses Coherently Signed BB84 states (signing the quantum state itself) to allow public verification of the deletion certificate.

C. Post-Quantum Instantiation

All schemes are instantiated using Lattice-based assumptions to ensure resistance against quantum computers:

• RABE: Based on the $\ell$-succinct LWE assumption (Champion et al.).
• iO: Based on Equivocal LWE and NTRU assumptions.
• ZKA: Based on plain LWE.
• Signatures/OSS: Based on LWE and One-Way Functions.

3. Key Contributions

1. First RABE with Certified Deletion: The paper presents the first lattice-based Registered Attribute-Based Encryption schemes supporting both Certified Deletion (CD) and Certified Everlasting Deletion (CED).
2. Introduction of Shad-RABE: A novel primitive that enables simulation-based security proofs in decentralized, attribute-based settings, overcoming the lack of a trusted authority.
3. Public Verifiability in Decentralized Settings: The construction of RABE-PubVCD and RABE-PubVCED allows any third party to verify that data has been deleted, without needing access to secret keys or a central authority.
4. Everlasting Security without Escrow: The schemes guarantee that once a deletion certificate is issued, the data is secure against unbounded adversaries (information-theoretic security), solving the problem of future cryptanalysis or quantum computing advances.
5. Comprehensive Framework: The paper provides generic constructions, security proofs, and concrete lattice-based instantiations for four distinct variants (Private/Public $\times$ CD/CED).

4. Results

• Security Proofs: The authors prove that their schemes satisfy:
  • Indistinguishability under Chosen-Plaintext Attack (IND-CPA) for standard encryption.
  • Certified Deletion Security: Even with access to secret keys after deletion, the message remains hidden (computationally secure).
  • Certified Everlasting Security: Even with unbounded computational power after deletion, the message remains hidden (information-theoretically secure).
• Correctness: The schemes ensure that authorized users can decrypt messages and that valid deletion certificates are always accepted.
• Efficiency: The schemes maintain the "compactness" property of RABE, where the master public key size grows logarithmically with the number of users, and updates are efficient ($O(\log N)$).

5. Significance

This work represents a major advancement in the intersection of quantum cryptography and decentralized access control.

• Solving the Escrow Problem: By removing the need for a trusted central authority to manage keys or verify deletions, the paper enables the deployment of certified deletion in large-scale, trust-minimized systems (e.g., cloud storage, blockchain-based data sharing).
• Future-Proofing Data Privacy: The "Everlasting Security" feature is crucial for long-term data protection. It ensures that data deleted today remains secure even if quantum computers or new algorithms break current encryption standards in the future.
• Regulatory Compliance: The Publicly Verifiable aspect is vital for compliance with regulations like GDPR (Right to be Forgotten), where third-party auditors or regulators need to verify that data has been deleted without compromising the system's security or requiring trust in the data holder.
• Theoretical Foundation: The introduction of Shad-RABE provides a new toolkit for researchers to build other decentralized quantum-safe primitives that require simulation-based security arguments.

In summary, the paper successfully bridges the gap between the theoretical guarantees of quantum certified deletion and the practical requirements of decentralized, fine-grained access control, offering a robust, post-quantum secure solution for the future of data privacy.