🔢 mathematics

Hybrid Encryption with Certified Deletion in Preprocessing Model

This paper introduces and formalizes hybrid encryption with certified deletion in the preprocessing model (pHE-CD), proposing two constructions that combine information-theoretic key encapsulation with data encapsulation mechanisms to achieve either fully information-theoretic security or computationally secure encryption with everlasting certified deletion for arbitrarily long messages.

Original authors: Kunal Dey, Reihaneh Safavi-Naini

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kunal Dey, Reihaneh Safavi-Naini

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are Alice, and you have a very sensitive secret you want to send to your friend, Bob. You put the secret in a digital box (encryption) and mail it to him.

In the old, classical world, there's a big problem: Bob can make a perfect photocopy of the box before you ask him to throw it away. Even if you demand he deletes the original, he might have a hidden copy. If a hacker later steals Bob's key, they can open that hidden copy and read your secret. You have no way to prove he actually deleted the data.

This paper introduces a new way to send secrets using quantum physics (the science of the very small) to solve this problem. It's called "Hybrid Encryption with Certified Deletion."

Here is how it works, broken down into simple concepts:

1. The Magic Rule: You Can't Copy Quantum Data

The whole system relies on a rule of the universe called the "No-Cloning Theorem." In the quantum world, you cannot make a perfect copy of a piece of information without destroying the original. It's like trying to photocopy a soap bubble; the act of copying pops the bubble.

2. The Two-Part Lock System (The "Hybrid" Part)

The authors propose a system that combines two types of locks to handle messages of any length (not just one bit):

Lock A (The Key Generator): This part uses a pre-shared secret between Alice and Bob (like a secret handshake they did earlier). It creates a temporary, one-time key. This part is so strong that even a super-computer with infinite power couldn't break it.
Lock B (The Data Container): This part holds the actual message. It uses the temporary key from Lock A to seal the message inside a quantum box.

3. The "Certified Deletion" Trick

Here is the magic moment. Alice sends the quantum box to Bob. Later, Alice says, "I want you to delete that box."

The Choice: Bob must choose one of two paths, but he cannot do both:
1. Path 1 (Read): He uses his key to open the box and read the message. But because of quantum physics, the moment he reads it, the "deletion certificate" becomes impossible to generate. He can read, but he can't prove he deleted it.
2. Path 2 (Delete): He performs a specific quantum measurement on the box to "erase" it. This action destroys the ability to read the message later. However, this action produces a Certificate of Deletion.
The Certificate: Bob sends this certificate back to Alice. Alice checks it. If it's valid, she knows for a fact that Bob cannot read the message anymore, even if he keeps the key. The data is gone forever.

4. Two Different "Flavors" of Security

The paper offers two versions of this system, depending on how strong you want the protection to be:

Version 1 (The "Unbreakable" Vault):
- How it works: Uses only the laws of physics and perfect randomness.
- The Guarantee: Even if a villain has a super-computer that can do infinite calculations, they cannot break the code or fake a deletion. It is secure forever.
- The Catch: It requires a lot of "quantum fuel" (randomness) for every message, similar to how a One-Time Pad works.
Version 2 (The "Everlasting" Vault):
- How it works: It uses standard computer encryption (like the AES algorithm used in your bank app) mixed with the quantum deletion trick.
- The Guarantee:
  - Before Bob deletes the file: The security relies on the fact that current computers can't break the code (computational security).
  - After Bob deletes the file and gets a valid certificate: The security becomes unbreakable forever. Even if a future super-computer is invented that can break all current codes, it will still be impossible to recover the data because the quantum certificate proves the data was physically destroyed.
- The Benefit: This version is much more efficient and uses standard technology (like AES) combined with quantum coding.

The Big Picture

The paper claims to have built a system where:

Alice can outsource data to Bob (like a cloud server).
Bob can either read the data OR delete it and prove it.
If Bob deletes it, Alice gets proof that the data is gone.
If Bob deletes it, no one (not even a future super-computer) can ever recover the data, even if they steal Bob's keys later.

The authors emphasize that this doesn't rely on "math puzzles" that might be solved by future computers. Instead, it relies on the fundamental laws of physics (quantum mechanics) and the fact that you can't copy a quantum state without destroying it. They also note that this technology can be built using existing quantum tools (like those used in Quantum Key Distribution).

Technical Summary: Hybrid Encryption with Certified Deletion in Preprocessing Model

Problem Statement

The paper addresses the fundamental challenge of Encryption with Certified Deletion (CD). In a standard outsourcing scenario, Alice encrypts data for Bob (or a cloud server), but classical information theory dictates that digital data can be copied perfectly. Consequently, if the encryption key is later compromised or the encryption scheme is broken, the adversary can recover the plaintext even if the server claims to have deleted the ciphertext.

While Broadbent and Islam (BI) proposed a symmetric-key solution using quantum information (specifically Wiesner coding and the no-cloning theorem) to achieve information-theoretic certified deletion, their scheme is limited to one-time use and requires a secret key length at least as long as the message. Subsequent Public-Key Encryption with Certified Deletion (PKE-CD) schemes allow key reuse but rely on computational hardness assumptions (post-quantum cryptography), which are vulnerable to future advances in computing. The authors identify a gap: a need for encryption with certified deletion that avoids computational hardness assumptions while supporting arbitrary message lengths and key reuse.

Methodology

The authors propose a framework called Hybrid Encryption with Certified Deletion in the Preprocessing Model (pHE-CD). This approach leverages the correlated randomness model, where Alice and Bob share private correlated random strings (generated via a public distribution $P(X, Y, Z)$ ) prior to the encryption phase.

The methodology relies on composing two distinct cryptographic primitives:

Information-Theoretic Key Encapsulation Mechanism (iKEM): This component establishes a shared secret key between Alice and Bob using their correlated randomness. It provides security against computationally unbounded adversaries without relying on hardness assumptions.
Data Encapsulation Mechanism with Certified Deletion (DEM-CD): This component encrypts the actual message using the key derived from the iKEM. The DEM-CD is responsible for the certified deletion property.

The security of the composed system is analyzed against two types of adversaries:

Computationally Bounded Adversaries: Adversaries limited to quantum polynomial time (QPT).
Computationally Unbounded Adversaries: Adversaries with unlimited computational power.

The paper defines Everlasting Certified Deletion Security (EV-CD), where confidentiality is computational prior to the verification of a deletion certificate, but becomes information-theoretic once a valid certificate is issued.

Key Contributions

1. Formalization of pHE-CD

The authors introduce and formalize the pHE-CD scheme, extending the hybrid encryption paradigm to the preprocessing model with certified deletion. They define appropriate security notions for both encryption (IND-qe-CPA) and certified deletion (EV-qe-CD) in this setting.

2. Two Constructions

The paper presents two specific constructions based on the pHE-CD framework, offering different security trade-offs:

Construction 1 (Fully Information-Theoretic):
- Components: Combines an information-theoretic iKEM with an information-theoretically secure DEM-CD (instantiated using the Broadbent-Islam one-time SKE-CD scheme).
- Properties: Provides information-theoretic security for both encryption and certified deletion.
- Limitations: Requires a fresh key for each encryption (similar to OTP) and does not support key reuse in the traditional sense, though it supports arbitrarily long messages directly without bit-by-bit repetition.
Construction 2 (Computational Encryption, Everlasting Deletion):
- Components: Combines an information-theoretic iKEM with a computationally secure DEM (using symmetric primitives like AES) adapted for certified deletion.
- Properties:
  - Encryption: Provides computational security (quantum-resistant) against QPT adversaries.
  - Certified Deletion: Provides everlasting security. Before certificate verification, security is computational; after successful verification, the security becomes information-theoretic, guaranteeing that even an unbounded adversary with the decryption key cannot learn the plaintext.
- Efficiency: This construction is key-efficient, using a constant-length key. It supports arbitrarily long messages by encrypting each bit independently and concatenating the ciphertexts.

3. Security Proofs

The authors provide rigorous composition theorems proving that the security of the pHE-CD scheme reduces to the security of its components:

Encryption Security: If the iKEM is IND-qe-CEA secure and the DEM-CD is IND-OT secure, the resulting pHE-CD is IND-qe-CPA secure.
Deletion Security: If the iKEM is IND-qe-CEA secure and the DEM-CD is one-time EV-CD secure, the resulting pHE-CD is EV-qe-CD secure.
The proofs utilize a hybrid-game argument, demonstrating that any adversary breaking the pHE-CD can be transformed into an adversary breaking either the iKEM or the DEM-CD.

Results

Feasibility: The paper demonstrates that hybrid encryption with certified deletion is achievable in the preprocessing model without relying on unproven computational hardness assumptions.
Security Guarantees:
- Construction 1 achieves unconditional (information-theoretic) security for both encryption and deletion.
- Construction 2 achieves computational security for encryption and everlasting security for deletion. This means that once a valid deletion certificate is verified, the data is information-theoretically removed from the adversary's view, even if the adversary later obtains the decryption key.
Implementation: The constructions utilize Wiesner conjugate coding, which is closely related to the BB84 QKD protocol and can be implemented using current quantum technology.
Scalability: Both schemes support the encryption of arbitrarily long messages.

Significance and Claims

The authors claim that their work replaces the reliance on computational hardness assumptions found in existing PKE-CD schemes with fundamental principles of quantum information theory. By utilizing the preprocessing model and correlated randomness, they achieve:

Robustness against future advances: The security does not depend on the difficulty of mathematical problems (like factoring or lattice problems) that could be broken by future algorithms or quantum computers.
Everlasting Confidentiality: Specifically for Construction 2, the paper highlights the unique property where confidentiality transitions from computational to information-theoretic upon successful deletion verification. This ensures that even if the encryption scheme is broken in the future, data that has been verifiably deleted remains secure.
Practicality: The use of Wiesner coding suggests that these schemes are implementable with today's quantum technology, unlike some theoretical quantum cryptographic proposals.

The paper concludes by noting that while the iKEM component relies on correlated randomness (which can be derived from QKD), extending the security of qKEMs to adversaries with encapsulation-oracle access remains a direction for future work. The authors do not claim to have solved all open problems in quantum cryptography but have provided a formal framework and concrete constructions that advance the state of the art in certified deletion without computational assumptions.