On the computational hardness needed for quantum cryptography

• URL: http://arxiv.org/abs/2209.04101v2
• Date: Thu, 24 Nov 2022 23:47:14 GMT
• Title: On the computational hardness needed for quantum cryptography
• Authors: Zvika Brakerski, Ran Canetti, Luowen Qian
• Abstract summary: 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.
• Score: 10.760579667794476
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the classical model of computation, it is well established that one-way functions (OWF) are minimal for computational cryptography: They are essential for almost any cryptographic application that cannot be realized with respect to computationally unbounded adversaries. In the quantum setting, however, OWFs appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and Yamakawa 2022), and the question of whether such a minimal primitive exists remains open. We consider EFI pairs -- efficiently samplable, statistically far but computationally indistinguishable pairs of (mixed) quantum states. Building on the work of Yan (2022), which shows equivalence between EFI pairs and statistical commitment schemes, we show that EFI pairs are necessary for a large class of quantum-cryptographic applications. Specifically, we construct EFI pairs from minimalistic versions of commitments schemes, oblivious transfer, and general secure multiparty computation, as well as from $\mathsf{QCZK}$ proofs from essentially any non-trivial language. We also construct quantum computational zero knowledge ($\mathsf{QCZK}$) proofs for all of $\mathsf{QIP}$ from any EFI pair. This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting: they are simple to describe, essential, and also serve as a linchpin for demonstrating equivalence between primitives.

Related papers

• 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)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• 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)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• 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)
• Computation-aided classical-quantum multiple access to boost network communication speeds [61.12008553173672]
  We quantify achievable quantum communication rates of codes with computation property for a two-sender cq-MAC. We show that it achieves the maximum possible communication rate (the single-user capacity), which cannot be achieved with conventional design.
  arXiv  Detail & Related papers  (2021-05-30T11:19:47Z)
• 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)
• 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.