Constant-Rate Certified Deletion
Abstract
We present a unified framework for upgrading a broad class of cryptographic primitives to support constant-rate certified deletion. Previous constructions require a linear number of qubits per encrypted bit of certified-deletable plaintext. In contrast, we obtain the first constant-rate constructions in the plain model that achieve certified deletion while preserving everlasting security. Our approach applies to a wide range of "all-or-nothing"-type primitives based on BB84-style encodings, including commitment schemes, public-key encryption, attribute-based encryption, and fully homomorphic encryption. Beyond this class, we also obtain constant-rate certified deletion for primitives built from subspace coset states, such as blind delegation, secure software leasing, functional encryption, and differing-inputs iO, and CCA-PKE. Importantly, our framework does not introduce any additional assumptions beyond those required by the underlying certified deletion primitives. Finally, under the hardness of SIS, we show that public verifiability can be incorporated into BB84- and coset-based certified deletion. In combination with our constant-rate constructions, this yields publicly verifiable certified deletion schemes with constant rate.
Related
- Semi-Quantum Cryptography with Certified Deletion
- Certified Randomness with Optimal Rate
- Constant Rate Codes with Fully Addressable Transversal T: Good Codes, Sparse Checks
- Constant-rate quantum codes with low-weight stabilizers and full logical Clifford actions via transversal and fold-transversal gates
- Hyperbolic color codes with constant rate and polynomial distance
BibTeX
@misc{chung2026constantrate,
title = {{Constant-Rate Certified Deletion}},
author = {Kai-Min Chung and Tzu-Hsiang Huang and Wei-Hsiang Hung and Shota Yamada},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03590},
eprint = {2610.03590},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03590},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Constant-Rate Certified Deletion
AU - Kai-Min Chung
AU - Tzu-Hsiang Huang
AU - Wei-Hsiang Hung
AU - Shota Yamada
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03590
UR - https://arxiv.org/abs/2610.03590
AB - We present a unified framework for upgrading a broad class of cryptographic primitives to support constant-rate certified deletion. Previous constructions require a linear number of qubits per encrypted bit of certified-deletable plaintext. In contrast, we obtain the first constant-rate constructions in the plain model that achieve certified deletion while preserving everlasting security. Our approach applies to a wide range of "all-or-nothing"-type primitives based on BB84-style encodings, including commitment schemes, public-key encryption, attribute-based encryption, and fully homomorphic encryption. Beyond this class, we also obtain constant-rate certified deletion for primitives built from subspace coset states, such as blind delegation, secure software leasing, functional encryption, and differing-inputs iO, and CCA-PKE. Importantly, our framework does not introduce any additional assumptions beyond those required by the underlying certified deletion primitives. Finally, under the hardness of SIS, we show that public verifiability can be incorporated into BB84- and coset-based certified deletion. In combination with our constant-rate constructions, this yields publicly verifiable certified deletion schemes with constant rate.
ER -