Pseudo-Entanglement is Necessary for EFI Pairs

• URL: http://arxiv.org/abs/2406.06881v2
• Date: Thu, 10 Oct 2024 09:22:34 GMT
• Title: Pseudo-Entanglement is Necessary for EFI Pairs
• Authors: Manuel Goulão, David Elkouss,
• Abstract summary: We consider a new quantum resource, pseudo-entanglement, and show that the existence of EFI pairs implies the existence of pseudo-entanglement. Our result has important implications for the field of computational cryptography.
• Score: 0.0
• License:
• Abstract: Regarding minimal assumptions, most of classical cryptography is known to depend on the existence of One-Way Functions (OWFs). However, recent evidence has shown that this is not the case when considering quantum resources. Besides the well known unconditional security of Quantum Key Distribution, it is now known that computational cryptography may be built on weaker primitives than OWFs, e.g., pseudo-random states [JLS18], one-way state generators [MY23], or EFI pairs of states [BCQ23]. We consider a new quantum resource, pseudo-entanglement, and show that the existence of EFI pairs, one of the current main candidates for the weakest computational assumption for cryptography (necessary for commitments, oblivious transfer, secure multi-party computation, computational zero-knowledge proofs), implies the existence of pseudo-entanglement, as defined by [ABF+24, ABV23] under some reasonable adaptations. We prove this by constructing a new family of pseudo-entangled quantum states given only EFI pairs. Our result has important implications for the field of computational cryptography. It shows that if pseudo-entanglement does not exist, then most of cryptography cannot exist either. Moreover, it establishes pseudo-entanglement as a new minimal assumption for most of computational cryptography, which may pave the way for the unification of other assumptions into a single primitive. Finally, pseudo-entanglement connects physical phenomena and efficient computation, thus, our result strengthens the connection between cryptography and the physical world.

Related papers

• Revocable Encryption, Programs, and More: The Case of Multi-Copy Security [48.53070281993869]
  We show the feasibility of revocable primitives, such as revocable encryption and revocable programs. This suggests that the stronger notion of multi-copy security is within reach in unclonable cryptography.
  arXiv  Detail & Related papers  (2024-10-17T02:37:40Z)
• A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QEFID [16.5193119873963]
  We show that there is a quantum unitary oracle relative to which EFI pairs exist, but OWSGs do not. We separate, via our oracle, QEFID, and one-way puzzles from OWSGs and several other Microcrypt primitives.
  arXiv  Detail & Related papers  (2024-10-04T14:11:56Z)
• Oracle Separation Between Quantum Commitments and Quantum One-wayness [0.6882042556551611]
  We show that there exists a unitary quantum oracle relative to which quantum commitments exist but no (efficiently verifiable) one-way state generators exist. Recent work has shown that commitments can be constructed from one-way state generators, but the other direction has remained open.
  arXiv  Detail & Related papers  (2024-10-04T12:26:21Z)
• Exponential Quantum One-Wayness and EFI Pairs [18.481934628015004]
  In classical cryptography, one-way functions are widely considered to be the minimal computational assumption. There are currently two major candidates for the minimal assumption: the search quantum generalization of one-way functions are one-way state generators (OWSG) We show that IV-OWSGs are precisely equivalent to EFI pairs, with an exponential loss in the reduction.
  arXiv  Detail & Related papers  (2024-04-21T15:55:00Z)
• 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)
• One-Wayness in Quantum Cryptography [9.09597656634436]
  We study properties of one-way state generators (OWSGs), which are a quantum analogue of one-way functions. We show that Quantum digital signatures are equivalent to OWSGs. We introduce an variant of OWSGs, which we call secretly-verifiable and statistically-invertible OWSGs.
  arXiv  Detail & Related papers  (2022-10-07T08:21:21Z)
• On the computational hardness needed for quantum cryptography [10.760579667794476]
  We show that EFI pairs are necessary for a large class of quantum-cryptographic applications. We construct EFI pairs from minimalistic versions of commitments schemes, oblivious transfer, and general secure multiparty proofs. This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting.
  arXiv  Detail & Related papers  (2022-09-09T03:22:05Z)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  We propose a variational quantum attack algorithm (VQAA) for classical AES-like symmetric cryptography. In the VQAA, the known ciphertext is encoded as the ground state of a Hamiltonian that is constructed through a regular graph.
  arXiv  Detail & Related papers  (2022-05-07T03:15:15Z)
• Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
  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.
  arXiv  Detail & Related papers  (2022-03-03T10:07:32Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Efficient simulatability of continuous-variable circuits with large Wigner negativity [62.997667081978825]
  Wigner negativity is known to be a necessary resource for computational advantage in several quantum-computing architectures. We identify vast families of circuits that display large, possibly unbounded, Wigner negativity, and yet are classically efficiently simulatable. We derive our results by establishing a link between the simulatability of high-dimensional discrete-variable quantum circuits and bosonic codes.
  arXiv  Detail & Related papers  (2020-05-25T11:03:42Z)

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.