arXiv:2609.38915

Semi-Quantum Cryptography with Certified Deletion

Yael Tauman Kalai, Justin Raizes

cs.CRquant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations

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.

Related papers

Quantum Proofs of Deletion for Learning with Errors

Alexander Poremba

Quantum information has the property that measurement is an inherently destructive process. This feature is most apparent in the principle of complementarity, which states that mutually incompatible observables cannot be measured at the same time. Recent work by Broadbent and Islam (TCC 2020) builds on this aspect of quantum mechanics to realize a cryptographic notion called certified deletion. While this remarkable notion enables a classical verifier to be convinced that a (private-key) quantum ciphertext has been deleted by an untrusted party, it offers no additional layer of functionality. In this work, we augment the proof-of-deletion paradigm with fully homomorphic encryption (FHE). We construct the first fully homomorphic encryption scheme with certified deletion - an interactive protocol which enables an untrusted quantum server to compute on encrypted data and, if requested, to simultaneously prove data deletion to a client. Our scheme has the desirable property that verification of a deletion certificate is public; meaning anyone can verify that deletion has taken place. Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors (LWE) distribution in the form of a quantum state was deleted. As an application of our protocol, we construct a Dual-Regev public-key encryption scheme with certified deletion, which we then extend towards a (leveled) FHE scheme of the same type. We introduce the notion of Gaussian-collapsing hash functions - a special case of collapsing hash functions defined by Unruh (Eurocrypt 2016) - and we prove the security of our schemes under the assumption that the Ajtai hash function satisfies a certain strong Gaussian-collapsing property in the presence of leakage.

Leibniz international proceedings in informaticsJan 1, 20236 citations

Quantum Proofs of Deletion for Learning with Errors

Alexander Poremba

Quantum information has the property that measurement is an inherently destructive process. This feature is most apparent in the principle of complementarity, which states that mutually incompatible observables cannot be measured at the same time. Recent work by Broadbent and Islam (TCC 2020) builds on this aspect of quantum mechanics to realize a cryptographic notion called certified deletion. While this remarkable notion enables a classical verifier to be convinced that a (private-key) quantum ciphertext has been deleted by an untrusted party, it offers no additional layer of functionality. In this work, we augment the proof-of-deletion paradigm with fully homomorphic encryption (FHE). We construct the first fully homomorphic encryption scheme with certified deletion -- an interactive protocol which enables an untrusted quantum server to compute on encrypted data and, if requested, to simultaneously prove data deletion to a client. Our scheme has the desirable property that verification of a deletion certificate is public; meaning anyone can verify that deletion has taken place. Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors (LWE) distribution in the form of a quantum state was deleted. As an application of our protocol, we construct a Dual-Regev public-key encryption scheme with certified deletion, which we then extend towards a (leveled) FHE scheme of the same type. We introduce the notion of Gaussian-collapsing hash functions -- a special case of collapsing hash functions defined by Unruh (Eurocrypt 2016) -- and we prove the security of our schemes under the assumption that the Ajtai hash function satisfies a certain strong Gaussian-collapsing property in the presence of leakage.

arXiv:2203.01610Mar 3, 20223 citations

The Entire Quantum Computer on a Classical Leash

Yael Tauman Kalai, Dakshita Khurana, Justin Raizes

We show that a classical client with no quantum hardware can use a single untrusted and potentially malicious quantum server as if it were its own trusted quantum computer. Through the server, the client can privately choose and run quantum computations, prepare quantum states, and process quantum states supplied by other parties. It can also keep quantum memory on the server, hidden from the server itself, and use that memory in later computations so its quantum state persists across rounds of interaction. Together, these capabilities let a purely classical party act as a quantum party in a variety of interactive protocols. We expect this virtual quantum computer to be a broadly useful tool. As immediate applications, we resolve two known open problems: (1) classical verification of quantum sampling with negligible computational soundness error, and (2) remote state preparation of arbitrary efficiently preparable quantum states. Underlying all of these results is a general-purpose, maliciously secure two-party computation protocol between a classical client and a quantum server, which we construct assuming only the post-quantum hardness of learning with errors.

quant-pharXiv:2610.31775Oct 26, 20260 citations

Quantum Cryptography with Classical Communication: Parallel Remote State Preparation for Copy-Protection, Verification, and More

Alexandru Gheorghiu, Tony Metger, Alexander Poremba

Quantum mechanical effects have enabled the construction of cryptographic primitives that are impossible classically. For example, quantum copy-protection allows for a program to be encoded in a quantum state in such a way that the program can be evaluated, but not copied. Many of these cryptographic primitives are two-party protocols, where one party, Bob, has full quantum computational capabilities, and the other party, Alice, is only required to send random BB84 states to Bob. In this work, we show how such protocols can generically be converted to ones where Alice is fully classical, assuming that Bob cannot efficiently solve the LWE problem. In particular, this means that all communication between (classical) Alice and (quantum) Bob is classical, yet they can still make use of cryptographic primitives that would be impossible if both parties were classical. We apply this conversion procedure to obtain quantum cryptographic protocols with classical communication for unclonable encryption, copy-protection, computing on encrypted data, and verifiable blind delegated computation. The key technical ingredient for our result is a protocol for classically-instructed parallel remote state preparation of BB84 states. This is a multi-round protocol between (classical) Alice and (quantum polynomial-time) Bob that allows Alice to certify that Bob must have prepared n uniformly random BB84 states (up to a change of basis on his space). While previous approaches could only certify one- or two-qubit states, our protocol allows for the certification of an n-fold tensor product of BB84 states. Furthermore, Alice knows which specific BB84 states Bob has prepared, while Bob himself does not. Hence, the situation at the end of this protocol is (almost) equivalent to one where Alice sent n random BB84 states to Bob. This allows us to replace the step of preparing and sending BB84 states in existing protocols by our remote-state preparation protocol in a generic and modular way.

arXiv:2201.13445Leibniz international proceedings in informaticsJan 31, 202210 citations

Quantum Encryption with Certified Deletion

Islam, Rabib

In the context of classical information, every message is composed of 0s and 1s; these messages can generally be copied at will. However, when quantum phenomena are used to model information, this guarantee no longer exists. This difference gives rise to a range of cryptographic possibilities when one considers encoding certain messages as quantum information. In our case, we analyze a potential benefit of encoding part of an encryption scheme’s ciphertext as quantum information. We call this type of ciphertext a quantum ciphertext. In particular, quantum ciphertexts are useful when one wants to be able to prove the deletion of the plaintext underlying a ciphertext. Since classical ciphertexts can be copied, clearly such feat is impossible using classical information alone. However, we show that quantum encodings allow such certified deletion. More precisely, we show that it is possible to encrypt classical data into a quantum ciphertext such that the recipient of the ciphertext can produce a classical string which proves to the originator that the recipient has relinquished any chance of recovering the plaintext, should the decryption key be revealed. Our scheme is feasible with current quantum technology: the honest parties only require quantum devices for single-qubit preparation and measurements, and the scheme is robust against noise in these devices. Furthermore, we provide a proof of security which requires only a finite amount of communication, and which therefore avoids the common technique of relying on the analysis of an asymptotic case.

Jan 20, 202039 citations

Semi-Quantum Cryptography: Designing Protocols with Classical Verification

Yusuf Alnawakhtha

Properties of quantum mechanics such as entanglement and the no-cloning theorem enable new forms of cryptography that are unattainable in classical models of computation. Quantum information, however, is harder to process, store, and transmit than classical information. As such, it is desirable to construct semi-quantum cryptographic protocols where only a subset of the parties have quantum capabilities while the rest operate classically. In this dissertation, we analyze the security of semi-quantum protocols based on two approaches: (i) nonlocality-based techniques and (ii) the hardness of the Learning with Errors (LWE) problem. In the first part of the dissertation, we leverage a form of Bell test to construct a quantum position verification (QPV) protocol. Initial QPV protocols required verifiers to prepare and send quantum states to an honest prover to achieve security against adversaries with bounded memory or entanglement. Later work constructed QPV protocols with classical verifiers but required additional assumptions such as the hardness of LWE or of random circuit sampling. We construct a variant of QPV where classical verifiers verify the spatial locations of two provers. We use the nonlocal correlations produced by the two provers to show security against adversaries with bounded quantum memory without making any computational intractability assumptions. In the second part of the dissertation, we use trapdoor claw-free functions (TCFs) to construct semi-quantum cryptographic protocols. TCFs, which are constructible from the hardness of LWE, have been shown to be immensely valuable in the construction of classically verifiable quantum cryptographic protocols. As opposed to previous work where the server is asked to prepare a claw state and perform Pauli-X and Z measurements, we use a technique that leverages the entire range of qubit measurements on the XY-plane. We use this technique to construct three protocols: (i) a one-round blind remote state preparation protocol that delegates the preparation of an arbitrary state on the XY-plane up to a Pauli-X correction; (ii) a two-round proof of quantumness whose security is directly in terms of the hardness of LWE and only requires the prover to prepare and measure a single claw state; and (iii) a 1-of-2 Puzzle with a single qubit auxiliary state.

Jan 1, 20250 citations