Classical client verifies quantum data deletion on remote servers
Semi-Quantum Cryptography with Certified Deletion
Cryptography and Security
Summary
Encrypted data sent to a server can be deleted and verified to ensure it's gone, even if encryption keys leak later. The authors show how to upload and manage this encrypted quantum data using only regular classical communication. They also introduce ways for clients to check if their data was improperly accessed and to get it back while confirming its deletion. This advances secure data management by bridging classical communication with quantum-encrypted data.
What this means in practice
- •For cloud security teams: Verify that quantum-encrypted client data on cloud servers is properly deleted using classical communication methods.
- •For cybersecurity auditors: Audit encrypted data storage systems non-destructively to detect unauthorized data access before data retrieval.
Authors
Yael Tauman Kalai, Justin Raizes
Abstract
Certified deletion allows a client to upload encrypted data to a server as a quantum state, then later request that the server delete their data and detect whether the server complies. If verification passes, then the data on the server will remain hidden even if the decryption key is later leaked. In publicly verifiable certified deletion, the verification key is published so that anyone may check for deletion compliance. In this work, we give a general compiler to publicly verifiable certified deletion that allows the client to initially upload the *quantum* ciphertext using purely *classical* communication, assuming the post-quantum hardness of LWE in the plain model. Our approach can be applied to a wide variety of primitives, including commitments and public-key, attribute-based, identity-based, and fully-homomorphic encryption. Moreover, our constructions allow the client to classically manage the encrypted data beyond just verifying its deletion. The classical client may non-destructively audit the ciphertext via a Proof of No Intrusion to check whether it has been leaked to a third party. The classical client may also retrieve the data while simultaneously verifying its deletion from the server. Thus, they do not have to choose between retrieving the data and protecting it against future key leakage. As our core technical contribution, we give a classical-communication protocol and simulation technique that allows adapting purification-based security arguments for BB84-style states which are prepared through classical interaction. It makes the required purification available in a hybrid experiment, despite the classical transcript uniquely determining the prepared state in a real execution.