arXiv:2610.03590 · Lecture notes in computer science
Constant-Rate Certified Deletion
Kai-Min Chung, Tzu-Hsiang Huang, Wei-Hsiang Hung, Shota Yamada
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.
AI Summary
Certified deletion lets a recipient certify that quantum-encoded data has been erased, with information-theoretic secrecy after certification even if computational assumptions later fail. This paper asks whether this everlasting-security guarantee can be achieved in the plain model with constant quantum communication per plaintext bit, rather than security-parameter-dependent overhead. It gives generic constant-rate compilers for BB84-style and subspace-coset-state encodings, without additional assumptions beyond the underlying certified-deletion primitives. The BB84 theorem encodes $k$ field elements using $2n$ qudits when $3k+\Theta(\lambda)\leq 2n$, giving asymptotic rate $1/3$. An unbalanced variant is stated to achieve any constant rate $1-\epsilon$ for sufficiently long messages. The coset construction approaches rate $1/4$. Applications include commitments, encryption, ABE and FHE; the coset framework additionally covers primitives allowing partial information, including functional encryption, software leasing and blind delegation. The proofs replace whole-message guessing, whose security loss is exponential in message length, with coordinate-wise guessing. They handle the resulting leakage through conditional seedless quantum extraction and efficiently checkable structural predicates; the BB84 analysis uses MDS codes and coherent decoding, while the coset analysis uses a leakage-adapted purification. Under SIS, compact constrained signatures add public verifiability with an additive $\operatorname{poly}(\lambda)$-qubit overhead, preserving constant rate for sufficiently long messages. Rate counts quantum, not total, communication. The public-verifiability compiler is limited to all-or-nothing applications: coherent evaluation obstructs several other primitives, and an appropriate CCA decryption oracle remains unresolved.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.