A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QEFID

• URL: http://arxiv.org/abs/2410.03453v2
• Date: Mon, 14 Oct 2024 12:18:39 GMT
• Title: A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QEFID
• Authors: Amit Behera, Giulio Malavolta, Tomoyuki Morimae, Tamer Mour, Takashi Yamakawa,
• Abstract summary: 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.
• Score: 16.5193119873963
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While in classical cryptography, one-way functions (OWFs) are widely regarded as the "minimal assumption," the situation in quantum cryptography is less clear. Recent works have put forward two concurrent candidates for the minimal assumption in quantum cryptography: One-way state generators (OWSGs), postulating the existence of a hard search problem with an efficient verification algorithm, and EFI pairs, postulating the existence of a hard distinguishing problem. Two recent papers [Khurana and Tomer STOC'24; Batra and Jain FOCS'24] showed that OWSGs imply EFI pairs, but the reverse direction remained open. In this work, we give strong evidence that the opposite direction does not hold: We show that there is a quantum unitary oracle relative to which EFI pairs exist, but OWSGs do not. In fact, we show a slightly stronger statement that holds also for EFI pairs that output classical bits (QEFID). As a consequence, we separate, via our oracle, QEFID, and one-way puzzles from OWSGs and several other Microcrypt primitives, including efficiently verifiable one-way puzzles and unclonable state generators. In particular, this solves a problem left open in [Chung, Goldin, and Gray Crypto'24]. Using similar techniques, we also establish a fully black-box separation (which is slightly weaker than an oracle separation) between private-key quantum money schemes and QEFID pairs. One conceptual implication of our work is that the existence of an efficient verification algorithm may lead to qualitatively stronger primitives in quantum cryptography.

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)
• 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)
• Pseudo-Entanglement is Necessary for EFI Pairs [0.0]
  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.
  arXiv  Detail & Related papers  (2024-06-11T01:44:16Z)
• 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)
• Commitments from Quantum One-Wayness [0.0]
  This work studies one-way state generators, a natural quantum relaxation of one-way functions. A fundamental question is whether this type of quantum one-wayness suffices to realize quantum cryptography. We prove that one-way state generators with pure state outputs imply quantum bit commitments and secure multiparty computation.
  arXiv  Detail & Related papers  (2023-10-17T18:48:22Z)
• 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)
• 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)
• 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)
• Backflash Light as a Security Vulnerability in Quantum Key Distribution Systems [77.34726150561087]
  We review the security vulnerabilities of quantum key distribution (QKD) systems. We mainly focus on a particular effect known as backflash light, which can be a source of eavesdropping attacks.
  arXiv  Detail & Related papers  (2020-03-23T18:23:12Z)

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.