Pseudorandom Strings from Pseudorandom Quantum States

• URL: http://arxiv.org/abs/2306.05613v2
• Date: Wed, 13 Sep 2023 23:16:11 GMT
• Title: Pseudorandom Strings from Pseudorandom Quantum States
• Authors: Prabhanjan Ananth, Yao-Ting Lin, Henry Yuen
• Abstract summary: We study the relationship between notions of pseudorandomness in the quantum and classical worlds. We show that a natural variant of pseudorandom generators called quantum pseudorandom generators (QPRGs) can be based on the existence of logarithmic output length PRSGs. We also study the relationship between other notions, namely, pseudorandom function-like state generators and pseudorandom functions.
• Score: 6.79244006793321
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the relationship between notions of pseudorandomness in the quantum and classical worlds. Pseudorandom quantum state generator (PRSG), a pseudorandomness notion in the quantum world, is an efficient circuit that produces states that are computationally indistinguishable from Haar random states. PRSGs have found applications in quantum gravity, quantum machine learning, quantum complexity theory, and quantum cryptography. Pseudorandom generators, on the other hand, a pseudorandomness notion in the classical world, is ubiquitous to theoretical computer science. While some separation results were known between PRSGs, for some parameter regimes, and PRGs, their relationship has not been completely understood. In this work, we show that a natural variant of pseudorandom generators called quantum pseudorandom generators (QPRGs) can be based on the existence of logarithmic output length PRSGs. Our result along with the previous separations gives a better picture regarding the relationship between the two notions. We also study the relationship between other notions, namely, pseudorandom function-like state generators and pseudorandom functions. We provide evidence that QPRGs can be as useful as PRGs by providing cryptographic applications of QPRGs such as commitments and encryption schemes. Our primary technical contribution is a method for pseudodeterministically extracting uniformly random strings from Haar-random states.

Related papers

• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem. We show that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions. We show that our assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives.
  arXiv  Detail & Related papers  (2024-10-10T16:10:10Z)
• Existential Unforgeability in Quantum Authentication From Quantum Physical Unclonable Functions Based on Random von Neumann Measurement [45.386403865847235]
  Physical Unclonable Functions (PUFs) leverage inherent, non-clonable physical randomness to generate unique input-output pairs. Quantum PUFs (QPUFs) extend this concept by using quantum states as input-output pairs. We show that no random unitary QPUF can achieve existential unforgeability against Quantum Polynomial Time adversaries. We introduce a second model where the QPUF functions as a nonunitary quantum channel, which also guarantees existential unforgeability.
  arXiv  Detail & Related papers  (2024-04-17T12:16:41Z)
• Pseudorandom unitaries with non-adaptive security [43.15464425520681]
  We present a PRU construction that is a concatenation of a random Clifford unitary, a pseudorandom binary phase operator, and a pseudorandom permutation operator. We prove that this PRU construction is secure against non-adaptive distinguishers assuming the existence of quantum-secure one-way functions.
  arXiv  Detail & Related papers  (2024-02-22T18:56:37Z)
• Non Deterministic Pseudorandom Generator for Quantum Key Distribution [0.0]
  Quantum Key Distribution thrives to achieve perfect secrecy of One time Pad (OTP) through quantum processes. One of the crucial components of QKD are Quantum Random Number Generators(QRNG) for generation of keys. This paper proposes a pseudorandom generator based on post quantum primitives.
  arXiv  Detail & Related papers  (2023-11-06T11:03:03Z)
• Quantum Conformal Prediction for Reliable Uncertainty Quantification in Quantum Machine Learning [47.991114317813555]
  Quantum models implement implicit probabilistic predictors that produce multiple random decisions for each input through measurement shots. This paper proposes to leverage such randomness to define prediction sets for both classification and regression that provably capture the uncertainty of the model.
  arXiv  Detail & Related papers  (2023-04-06T22:05:21Z)
• Pseudorandom (Function-Like) Quantum State Generators: New Definitions and Applications [7.2051162210119495]
  We explore new definitions, new properties and applications of pseudorandom states. Pseudorandom quantum states (PRS) are efficiently constructible states that are computationally indistinguishable from being Haar-random. We show that PRS generators with logarithmic output length imply commitment and encryption schemes with classical communication.
  arXiv  Detail & Related papers  (2022-11-02T19:24:55Z)
• Cryptography from Pseudorandom Quantum States [6.164147034988822]
  One-way functions imply the existence of pseudorandom states, but Kretschmer (TQC'20) recently constructed an oracle relative to which there are no one-way functions but pseudorandom states still exist. We study the intriguing possibility of basing interesting cryptographic tasks on pseudorandom states. A consequence of (a) is that pseudorandom states are sufficient to construct maliciously secure multiparty protocols in the dishonest majority setting.
  arXiv  Detail & Related papers  (2021-12-18T22:53:16Z)
• 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)
• Preparing random states and benchmarking with many-body quantum chaos [48.044162981804526]
  We show how to predict and experimentally observe the emergence of random state ensembles naturally under time-independent Hamiltonian dynamics. The observed random ensembles emerge from projective measurements and are intimately linked to universal correlations built up between subsystems of a larger quantum system. Our work has implications for understanding randomness in quantum dynamics, and enables applications of this concept in a wider context.
  arXiv  Detail & Related papers  (2021-03-05T08:32:43Z)
• Quantum Random Number Generation using a Solid-State Single-Photon Source [89.24951036534168]
  Quantum random number generation (QRNG) harnesses the intrinsic randomness of quantum mechanical phenomena. We demonstrate QRNG with a quantum emitter in hexagonal boron nitride. Our results open a new avenue to the fabrication of on-chip deterministic random number generators.
  arXiv  Detail & Related papers  (2020-01-28T22:47:43Z)

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.