⚛️ quantum physics

Constant-Rate Certified Deletion

This paper presents a unified framework that upgrades a broad class of cryptographic primitives to support constant-rate certified deletion in the plain model without additional assumptions, achieving the first such constructions that preserve everlasting security and enable public verifiability under standard hardness assumptions.

Original authors: Kai-Min Chung, Tzu-Hsiang Huang, Wei-Hsiang Hung, Shota Yamada

Published 2026-10-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kai-Min Chung, Tzu-Hsiang Huang, Wei-Hsiang Hung, Shota Yamada

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

In the modern digital world, the right to be forgotten is a legal concept that demands more than just deleting a file; it requires proof that the data is truly gone. This is a fundamental challenge because classical information, like a text message or a photo, can be copied endlessly. Even if a file is locked with a secret code, a future breakthrough in computing or a leaked key could allow an adversary to unlock it and recover the original content. The only way to guarantee that data has been erased is to rely on the laws of physics, specifically the strange rules of quantum mechanics. In the quantum realm, information behaves differently: it cannot be copied perfectly, and the act of measuring it inevitably disturbs it. This destructive nature offers a unique opportunity: if a piece of data is stored in a quantum state, one can force a user to measure it in a specific way to prove they have destroyed it, leaving them with no way to recover the original information.

For years, researchers have been working on a method called certified deletion, which allows a user to generate a certificate proving they have deleted a secret. However, a major hurdle has always been efficiency. Previous methods required a massive amount of quantum storage to protect even a tiny amount of data. To encrypt a single bit of information, these older schemes needed a number of quantum particles that grew linearly with the security level, making the system impractical for large messages. It was like trying to send a postcard but needing a warehouse full of shipping containers just to protect the ink on the paper. This inefficiency meant that while the concept was theoretically sound, it was too heavy to be useful in real-world applications like secure messaging or cloud storage.

A team of researchers has now solved this problem by developing a new framework that achieves constant-rate certified deletion. This means the amount of quantum storage required grows in direct proportion to the size of the message, rather than exploding with the security requirements. In their new system, the overhead is minimal; for a large message, the quantum data needed is only slightly larger than the message itself, allowing for a rate of efficiency that was previously thought impossible in standard settings. They achieved this by creating a unified method that works for a wide variety of cryptographic tools, including systems used for public-key encryption, attribute-based access, and fully homomorphic encryption, which allows computations on encrypted data.

The researchers demonstrated that their approach works for two distinct types of quantum encodings. The first type relies on a method similar to the famous BB84 protocol, which is used for secure key distribution. The second type uses more complex structures known as subspace coset states, which enable more advanced features like blind delegation and secure software leasing. In both cases, the new framework allows the message to be encrypted and then deleted with a certificate that is verified without needing to trust the person doing the deleting. Crucially, this efficiency is achieved without introducing any new, unproven assumptions about the hardness of mathematical problems; it relies only on the same foundations that the original cryptographic schemes used.

Beyond just making the process faster and lighter, the team also showed how to make the deletion verification public. In many security scenarios, it is not enough for just the sender to know the data is gone; a third party or a public auditor should be able to verify the deletion without needing access to secret keys. Previous attempts to add this public verification feature destroyed the efficiency gains, requiring a linear amount of extra data that negated the benefits. The researchers overcame this by using a technique involving constrained signatures, a type of digital signature that can be verified by anyone but can only be created under specific conditions. By combining this with their constant-rate framework, they created a system where anyone can verify that data has been deleted, and the system remains efficient enough to handle large messages.

The work provides a unified solution that upgrades a broad class of cryptographic primitives to support this high-efficiency, verifiable deletion. For the first time, it is possible to have a system where the quantum data required to protect a message is roughly the same size as the message itself, while still guaranteeing that the data can be provably erased. This breakthrough removes the significant overhead that previously made certified deletion impractical, opening the door for these quantum-secure features to be integrated into future privacy-preserving technologies. The researchers proved that these results hold even against adversaries with unlimited computing power, provided the deletion certificate is successfully verified, ensuring that the data is gone forever in a way that classical systems can never achieve.

Technical Summary: Constant-Rate Certified Deletion

1. Problem Statement

The paper addresses the fundamental challenge of Certified Deletion (CD) in cryptography. CD allows a user to prove to a third party that they have deleted a piece of data, even if the data was previously encrypted. This is motivated by the "right to be forgotten" in privacy regulations (e.g., GDPR).

In the classical world, CD is impossible because classical information can be copied arbitrarily; an adversary could retain a copy of the ciphertext and decrypt it later if the secret key is leaked. Quantum information offers a solution via the no-cloning theorem and the uncertainty principle, which prevent an adversary from copying a state and measuring it in two incompatible bases simultaneously.

However, existing CD constructions in the plain model (without random oracles) suffer from a critical inefficiency: they require a linear number of qubits ( $\Theta(\lambda)$ ) to encrypt a single classical bit. This results in a total communication cost of $\Theta(n\lambda)$ for an $n$ -bit message, yielding a subconstant rate ( $O(\log \lambda)/\Theta(\lambda)$ ). The primary barrier to achieving constant-rate CD (where the number of qubits is proportional to the message size, $O(n)$ ) is the proof technique used in prior works (specifically [BK23]), which relies on "guessing" the entire message string to delay dependence on the actual message. This guessing step incurs an exponential security loss in the message length, making it infeasible for long messages.

2. Methodology

The authors propose a unified framework to overcome the exponential security loss barrier, enabling constant-rate CD for two broad classes of primitives: those based on BB84 states and those based on subspace coset states.

Core Technical Innovations

Position-Wise Guessing with Linear Extractors:
Instead of guessing the entire message string (which causes exponential loss), the authors employ a position-wise guessing strategy. They replace the simple XOR extractor (used in [BK23]) with a high-rate linear extractor based on a Maximum Distance Separable (MDS) code over a finite field $\mathbb{F}$ .
- The message $m$ is masked using a linear map $R$ applied to a quantum state, plus a random pad $r$ .
- The security proof proceeds by guessing one field element of the message at a time. To prevent the adversary from gaining information about the unguessed parts, the authors introduce a fresh random pad $r$ that computationally one-time pads the leakage of the remaining message bits.
Deferred Sampling and Purification:
To restore the "cut-and-choose" argument in the constant-rate setting, the authors defer the sampling of the basis string $\theta$ (or the subspace parameters) until after the adversary outputs their deletion certificate.
- They utilize purification techniques to treat the quantum state as an entangled EPR pair between the challenger and the adversary.
- By introducing the random pad $r$ , they can delay the choice of $\theta$ without altering the joint distribution of the adversary's view. This allows the challenger to measure the state in the correct basis only after verifying the certificate, ensuring the adversary has effectively measured in the wrong basis for the relevant bits.
Efficiently Checkable Predicates:
A crucial step in the proof is transferring the security argument from an "ideal world" (where encryption is trivial) to the "real world" (where encryption relies on computational assumptions). The authors define an efficiently checkable predicate that verifies whether the adversary's residual state satisfies a specific structural condition (e.g., being close to a state where errors are sparse).
- For BB84 states, this involves applying a Fourier transform and using the error-correction capability of the MDS code to recover the error vector.
- For subspace coset states, they utilize a clever purification strategy that separates the leakage from the entangled part of the state, circumventing the entanglement issues that plagued previous attempts to apply this technique to coset states.
Public Verifiability via Constrained Signatures:
To achieve Publicly Verifiable Deletion (PVD) without sacrificing the constant rate, the authors incorporate Constrained Signatures (CS) based on the Shortest Integer Solution (SIS) assumption.
- Instead of signing individual qubits (which would add linear overhead), they sign the entire superposition of the quantum state coherently.
- They use a constrained signing key associated with a predicate that checks if a string belongs to the valid set defined by the quantum encoding (e.g., $T_{x,\theta}$ ).
- By leveraging function privacy of CS and 4-wise independent hash functions (to simulate a random oracle), they ensure that signing the superposition does not leak information about the underlying message or basis, while maintaining a signature size that is polynomial in the security parameter $\lambda$ but independent of the message length $n$ .

3. Key Contributions and Results

A. Constant-Rate Certified Deletion for BB84 States

The authors establish a theorem for CD based on BB84 states that achieves a rate of $(1-\epsilon)$ for any constant $\epsilon > 0$ .

Scope: Applies to "all-or-nothing" primitives including Commitment Schemes, Secret-Key Encryption (SKE), Public-Key Encryption (PKE), Attribute-Based Encryption (ABE), Fully Homomorphic Encryption (FHE), Timed-Release Encryption, and Witness Encryption.
Mechanism: Uses MDS codes over finite fields and the position-wise guessing technique.
Result: The communication cost is $O(n)$ qubits for an $n$ -bit message, a significant improvement over the previous $\Theta(n\lambda)$ .

B. Constant-Rate Certified Deletion for Subspace Coset States

The authors extend the framework to subspace coset states, achieving a rate of $1/4$ .

Scope: Applies to primitives beyond "all-or-nothing," including Blind Delegation, Secure Software Leasing, Functional Encryption (FE), Differing-Inputs Indistinguishability Obfuscation (diO), and CCA-PKE.
Mechanism: Utilizes a novel purification technique that avoids the entanglement barriers present in BB84-based proofs when applied to coset states.
Result: This is the first constant-rate construction for these advanced primitives in the plain model.

C. Publicly Verifiable Certified Deletion (PVD)

Under the hardness of the SIS assumption, the authors construct PVD schemes that preserve the constant-rate property.

Significance: Previous PVD constructions either required linear overhead (destroying the rate) or relied on strong assumptions like Indistinguishability Obfuscation (iO).
Result: The paper provides the first constant-rate PVD schemes for both BB84 and coset-state-based primitives, assuming only SIS.

4. Significance and Claims

The paper claims to resolve a long-standing open problem in quantum cryptography: constructing certified deletion schemes with constant rate in the plain model while maintaining everlasting security (security against unbounded adversaries after deletion).

Overcoming Barriers: The work explicitly identifies and overcomes the "guessing barrier" inherent in the [BK23] proof technique, which previously limited CD to logarithmic message lengths.
Unified Framework: It provides a generic compiler that upgrades a wide range of cryptographic primitives to support CD without introducing new assumptions beyond those required by the underlying primitives (except for SIS for PVD).
Practical Efficiency: By reducing the qubit overhead from linear in the security parameter to a constant factor, the results make certified deletion theoretically viable for large-scale data applications.
Modesty: The authors note that while they achieve constant rates, the rate for BB84 states is approximately $1/3$ (or $1-\epsilon$ with unbalanced parameters) and $1/4$ for coset states, rather than approaching 1. They also acknowledge that their PVD compiler for subspace coset states does not currently extend to all "beyond all-or-nothing" primitives (like diO or FE) due to difficulties in coherently uncomputing signatures within classical functionalities, though it works for CCA-PKE.

In summary, this work demonstrates that certified deletion can be achieved with high efficiency (constant rate) and strong security guarantees (everlasting security and public verifiability) using standard lattice assumptions, marking a significant step forward in the practicality of quantum-secure data deletion.