arXiv:2609.38915
Semi-Quantum Cryptography with Certified Deletion
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.
AI Summary
Certified deletion uses quantum ciphertexts to make data unrecoverable after an accepted deletion certificate, even if the decryption key subsequently leaks. This paper asks whether a fully classical client can upload, audit, and retrieve such data from a quantum server using only classical communication. Assuming post-quantum hardness of LWE, it constructs a plain-model compiler for publicly verifiable certified deletion. The construction splits each message bit into a quantum claw-state share carrying a phase and a classical share containing a masked bit and a trapdoor. Encapsulating the classical share under a semantically hiding primitive gives applications to public-key, attribute-based, identity-based, and fully homomorphic encryption, and commitments, assuming the corresponding underlying primitive. Decryption uses the original scheme’s secret keys. The technical ingredient combines trapdoor claw-free functions with witness-preserving arguments of knowledge. Coherent extraction, phase injection, and uncomputation permit purification-based security proofs despite the classical preparation transcript determining the real prepared state. Extraction has inverse-polynomial approximation error, but its precision changes only the reduction’s runtime; the resulting protocol has negligible security error. Applying an existing compiler yields non-destructive proofs of no intrusion: search security holds in the plain model, while decisional security uses the quantum random oracle model. A further protocol lets a classical decryptor retrieve plaintext while deleting the server’s access, using fresh randomness erased after the session. The guarantees are computational, not everlasting. The preparation technique provides neither simulation-secure nor verifiable remote state preparation, so it does not generically replace quantum communication in arbitrary protocols.
The largest contribution of ChatGPT was in the applications section, where it was asked to import definitions and prove specific applications based on the main technical sections.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.