Quantum Cryptography in Algorithmica

• URL: http://arxiv.org/abs/2212.00879v2
• Date: Tue, 2 May 2023 18:57:50 GMT
• Title: Quantum Cryptography in Algorithmica
• Authors: William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal
• Abstract summary: We show that in a black-box setting, quantum cryptography based on pseudorandom states is possible even if one-way functions do not exist. We also introduce a conjecture that would generalize our results to multi-copy secure pseudorandom states.
• Score: 0.7524721345903025
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We construct a classical oracle relative to which $\mathsf{P} = \mathsf{NP}$ yet single-copy secure pseudorandom quantum states exist. In the language of Impagliazzo's five worlds, this is a construction of pseudorandom states in "Algorithmica," and hence shows that in a black-box setting, quantum cryptography based on pseudorandom states is possible even if one-way functions do not exist. As a consequence, we demonstrate that there exists a property of a cryptographic hash function that simultaneously (1) suffices to construct pseudorandom states, (2) holds for a random oracle, and (3) is independent of $\mathsf{P}$ vs. $\mathsf{NP}$ in the black-box setting. We also introduce a conjecture that would generalize our results to multi-copy secure pseudorandom states. We build on the recent construction by Aaronson, Ingram, and Kretschmer (CCC 2022) of an oracle relative to which $\mathsf{P} = \mathsf{NP}$ but $\mathsf{BQP} \neq \mathsf{QCMA}$, based on hardness of the OR $\circ$ Forrelation problem. Our proof also introduces a new discretely-defined variant of the Forrelation distribution, for which we prove pseudorandomness against $\mathsf{AC^0}$ circuits. This variant may be of independent interest.

Related papers

• Quantum-Computable One-Way Functions without One-Way Functions [0.6349503549199401]
  We construct a classical oracle relative to which $mathsfP = mathsfNP$ but quantum-computable quantum-secure trapdoor one-way functions exist. Our result implies multi-copy pseudorandom states and pseudorandom unitaries, but also classical-communication public-key encryption, signatures, and oblivious transfer schemes.
  arXiv  Detail & Related papers  (2024-11-04T19:40:01Z)
• Quantum State Learning Implies Circuit Lower Bounds [2.2667044928324747]
  We establish connections between state tomography, pseudorandomness, quantum state, circuit lower bounds. We show that even slightly non-trivial quantum state tomography algorithms would lead to new statements about quantum state synthesis.
  arXiv  Detail & Related papers  (2024-05-16T16:46:27Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  Sponge hashing is a widely used class of cryptographic hash algorithms. Intrepid permutations have so far remained a fundamental open problem. We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
  arXiv  Detail & Related papers  (2024-03-07T18:46:58Z)
• Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
  A subset state with respect to $S$, a subset of the computational basis, is [ frac1sqrt|S|sum_iin S |irangle. We show that for any fixed subset size $|S|=s$ such that $s = 2n/omega(mathrmpoly(n))$ and $s=omega(mathrmpoly(n))$, a random subset state is information-theoretically indistinguishable from a Haar random state even provided
  arXiv  Detail & Related papers  (2023-12-23T15:52:46Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms.
  arXiv  Detail & Related papers  (2023-05-09T20:53:27Z)
• 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)
• On Submodular Contextual Bandits [92.45432756301231]
  We consider the problem of contextual bandits where actions are subsets of a ground set and mean rewards are modeled by an unknown monotone submodular function. We show that our algorithm efficiently randomizes around local optima of estimated functions according to the Inverse Gap Weighting strategy.
  arXiv  Detail & Related papers  (2021-12-03T21:42:33Z)
• The Acrobatics of BQP [1.7136832159667206]
  We show that in the black-box setting the behavior of quantum-time ($mathsfBQP$) can be remarkably decoupled from that of classical complexity classes like $mathsfNP$. We also introduce new tools that might be of independent interest. These include a "quantum-aware" version of the random restriction method, a concentration theorem for the block sensitivity of $mathsfAC0$ circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.
  arXiv  Detail & Related papers  (2021-11-19T19:40:05Z)
• Quantum Pseudorandomness and Classical Complexity [0.08158530638728499]
  We show that cryptographic pseudorandom quantum states and pseudorandom unitary transformations exist. We discuss implications of these results for cryptography, complexity theory, and quantum tomography.
  arXiv  Detail & Related papers  (2021-03-16T20:54:12Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity.
  arXiv  Detail & Related papers  (2020-12-03T14:03:20Z)
• 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)

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.