Paper 2022/295

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). This results in a new and powerful cryptographic notion called fully homomorphic encryption 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 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. We introduce an encoding based on Gaussian coset states which is highly generic and suggests that essentially any LWE-based cryptographic primitive admits a classically-verifiable quantum proof of deletion. 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. In terms of security, we distinguish between two types of attack scenarios: a semi-honest adversary that follows the protocol exactly, and a fully malicious adversary that is allowed to deviate arbitrarily from the protocol. In the former case, we achieve indistinguishable ciphertexts, even if the secret key is later revealed after deletion has taken place. In the latter case, we provide entropic uncertainty relations for Gaussian cosets which limit the adversary's ability to guess the delegated ciphertext once deletion has taken place. Our results enable a form of everlasting cryptography and give rise to new privacy-preserving quantum cloud applications, such as private machine learning on encrypted data with certified data deletion.

Available format(s)
Cryptographic protocols
Publication info
Preprint. Minor revision.
quantum proofs of deletionlearning with errorsfully homomorphic encryption
Contact author(s)
aporemba @ caltech edu
2022-03-07: received
Short URL
Creative Commons Attribution


      author = {Alexander Poremba},
      title = {Quantum Proofs of Deletion for Learning with Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2022/295},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.