Constant-Rate Certified Deletion
Framework achieves first constant-rate certified deletion in the plain model across BB84-style and coset-state primitives, cutting qubit overhead per encrypted bit.
The paper presents a unified framework upgrading a broad class of cryptographic primitives to constant-rate certified deletion, where prior constructions needed a linear number of qubits per encrypted bit. It covers BB84-style all-or-nothing primitives including commitments, public-key encryption, attribute-based encryption, and fully homomorphic encryption, plus coset-state primitives such as blind delegation, secure software leasing, functional encryption, differing-inputs iO, and CCA-PKE. Under SIS hardness, public verifiability is added, yielding publicly verifiable constant-rate certified deletion schemes, with no additional assumptions beyond the underlying primitives.
- First constant-rate certified deletion constructions in the plain model preserving everlasting security
- Applies to BB84-style primitives (PKE, ABE, FHE, commitments) and subspace coset-state primitives
- Public verifiability achieved under SIS hardness without extra assumptions
- Reduces qubit cost from linear per plaintext bit to constant rate
Full article161 words · extracted from arxiv.org · click to collapse
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.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2610.03590