Constant-rate certified deletion improves cryptographic security methods
Constant-Rate Certified Deletion
Cryptography and Security
Summary
Secure deletion means being able to prove that encrypted information has been truly erased. Previous methods to prove deletion needed a lot of extra quantum data, making them inefficient. The authors introduce a new way to achieve this proof at a constant rate, meaning the overhead doesn't grow with the size of the data. Their method works for many cryptographic systems, including encryption and secure software services, without adding new security assumptions. They also show it's possible to make these deletion proofs publicly verifiable under certain technical assumptions.
What this means in practice
- •For security software engineers: Build encrypted systems that can prove data deletion efficiently for better compliance and trust.
- •For cloud service developers: Enable cloud platforms to offer certified deletion guarantees for encrypted user data with constant overhead.
Authors
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.