Quantum Proofs of Deletion for Learning with Errors

• URL: http://arxiv.org/abs/2203.01610v4
• Date: Sat, 7 Jan 2023 01:29:09 GMT
• Title: Quantum Proofs of Deletion for Learning with Errors
• Authors: Alexander Poremba
• Abstract summary: We construct the first fully homomorphic encryption scheme with certified deletion. 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 distribution in the form of a quantum state was deleted.
• Score: 91.3755431537592
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Relating Quantum Tamper-Evident Encryption to Other Cryptographic Notions [0.0]
  A quantum tamper-evident encryption scheme is a non-interactive symmetric-key encryption scheme mapping classical messages to quantum ciphertexts. This quantum cryptographic primitive was first introduced by Gottesman in 2003. We further our understanding of tamper-evident encryption by formally relating it to other cryptographic primitives in an information-theoretic setting.
  arXiv  Detail & Related papers  (2024-11-05T02:20:29Z)
• Measuring Quantum Information Leakage Under Detection Threat [7.82527155589504]
  Gentle quantum leakage is proposed as a measure of information leakage to arbitrary eavesdroppers. Measures are used to encode the desire of the eavesdropper to evade detection. Global depolarizing noise is shown to reduce gentle quantum leakage.
  arXiv  Detail & Related papers  (2024-03-18T03:07:09Z)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  We show that targetcollapsing enables publiclyverifiable deletion (PVD) We build on this framework to obtain a variety of primitives supporting publiclyverifiable deletion from weak cryptographic assumptions.
  arXiv  Detail & Related papers  (2023-03-15T15:00:20Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
  arXiv  Detail & Related papers  (2023-02-28T18:58:11Z)
• Obfuscation of Pseudo-Deterministic Quantum Circuits [14.026980555435841]
  We show how to obfuscate pseudo-deterministic quantum circuits in the classical oracle model. Our obfuscator outputs a quantum state $ketwidetildeQ$ repeatedly on arbitrary inputs.
  arXiv  Detail & Related papers  (2023-02-22T01:14:20Z)
• Cryptography with Certified Deletion [16.354530084834863]
  We propose a new, unifying framework that yields an array of cryptographic primitives with certified deletion. primitives enable a party in possession of a quantum ciphertext to generate a classical certificate that the encrypted plaintext has been information-theoretically deleted.
  arXiv  Detail & Related papers  (2022-07-05T00:48:06Z)
• Quantum Encryption with Certified Deletion, Revisited: Public Key, Attribute-Based, and Classical Communication [10.973034520723957]
  Broadbent and Islam proposed a quantum cryptographic primitive called quantum encryption with certified deletion. In this primitive, a receiver in possession of a quantum ciphertext can generate a classical certificate that the encrypted message is deleted. Although deletion certificates are privately verifiable, which means a verification key for a certificate has to be kept secret, in the definition by Broadbent and Islam, we can also consider public verifiability.
  arXiv  Detail & Related papers  (2021-05-12T01:41:46Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)
• Quantum-secure message authentication via blind-unforgeability [74.7729810207187]
  We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability. This notion defines a function to be predictable if there exists an adversary who can use "partially blinded" access to predict values. We show the suitability of blind unforgeability for supporting canonical constructions and reductions.
  arXiv  Detail & Related papers  (2018-03-10T05:31:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.