Cryptography from Pseudorandom Quantum States

• URL: http://arxiv.org/abs/2112.10020v2
• Date: Tue, 15 Mar 2022 16:45:53 GMT
• Title: Cryptography from Pseudorandom Quantum States
• Authors: Prabhanjan Ananth, Luowen Qian, Henry Yuen
• Abstract summary: 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.
• Score: 6.164147034988822
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Pseudorandom states, introduced by Ji, Liu and Song (Crypto'18), are efficiently-computable quantum states that are computationally indistinguishable from Haar-random states. 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. Motivated by this, we study the intriguing possibility of basing interesting cryptographic tasks on pseudorandom states. We construct, assuming the existence of pseudorandom state generators that map a $\lambda$-bit seed to a $\omega(\log\lambda)$-qubit state, (a) statistically binding and computationally hiding commitments and (b) pseudo one-time encryption schemes. A consequence of (a) is that pseudorandom states are sufficient to construct maliciously secure multiparty computation protocols in the dishonest majority setting. Our constructions are derived via a new notion called pseudorandom function-like states (PRFS), a generalization of pseudorandom states that parallels the classical notion of pseudorandom functions. Beyond the above two applications, we believe our notion can effectively replace pseudorandom functions in many other cryptographic applications.

Related papers

• Correcting Subverted Random Oracles [55.4766447972367]
  We prove that a simple construction can transform a "subverted" random oracle which disagrees with the original one at a small fraction of inputs into an object that is indifferentiable from a random function. Our results permit future designers of cryptographic primitives in typical kleptographic settings to use random oracles as a trusted black box.
  arXiv  Detail & Related papers  (2024-04-15T04:01:50Z)
• Real-Valued Somewhat-Pseudorandom Unitaries [5.294604210205507]
  We show that even though real-valued unitaries cannot be completely pseudorandom, we can still obtain some pseudorandom properties without giving up on a real-valued unitary. Our analysis shows that an even simpler construction: applying a random (binary) phase followed by a random computational-basis permutation, would suffice.
  arXiv  Detail & Related papers  (2024-03-25T12:37:50Z)
• 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)
• Pseudorandom Strings from Pseudorandom Quantum States [6.79244006793321]
  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.
  arXiv  Detail & Related papers  (2023-06-09T01:16:58Z)
• 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)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state. Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
  arXiv  Detail & Related papers  (2023-02-07T10:57:36Z)
• 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)
• Quantum Pseudoentanglement [4.3053817709507]
  Entanglement is a quantum resource, in some ways analogous to randomness in classical computation. We give a construction of pseudoentangled states with entanglement entropy arbitrarily close to $log n$ across every cut. We discuss applications of this result to Matrix Product State testing, entanglement distillation, and the complexity of the AdS/CFT correspondence.
  arXiv  Detail & Related papers  (2022-11-01T21:04:49Z)
• Testing randomness of series generated in Bell's experiment [62.997667081978825]
  We use a toy fiber optic based setup to generate binary series, and evaluate their level of randomness according to Ville principle. Series are tested with a battery of standard statistical indicators, Hurst, Kolmogorov complexity, minimum entropy, Takensarity dimension of embedding, and Augmented Dickey Fuller and Kwiatkowski Phillips Schmidt Shin to check station exponent. The level of randomness of series obtained by applying Toeplitz extractor to rejected series is found to be indistinguishable from the level of non-rejected raw ones.
  arXiv  Detail & Related papers  (2022-08-31T17:39:29Z)
• 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)
• Gaussian conversion protocols for cubic phase state generation [104.23865519192793]
  Universal quantum computing with continuous variables requires non-Gaussian resources. The cubic phase state is a non-Gaussian state whose experimental implementation has so far remained elusive. We introduce two protocols that allow for the conversion of a non-Gaussian state to a cubic phase state.
  arXiv  Detail & Related papers  (2020-07-07T09:19:49Z)

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.