Pseudorandomness in the (Inverseless) Haar Random Oracle Model

• URL: http://arxiv.org/abs/2410.19320v1
• Date: Fri, 25 Oct 2024 06:13:01 GMT
• Title: Pseudorandomness in the (Inverseless) Haar Random Oracle Model
• Authors: Prabhanjan Ananth, John Bostanci, Aditya Gulati, Yao-Ting Lin,
• Abstract summary: We study the (in)feasibility of quantum pseudorandom notions in a quantum analog of the random oracle model. In this model, all the parties, including the adversary, have oracle access to the same Haar random unitary.
• Score: 5.307303460914328
• License:
• Abstract: We study the (in)feasibility of quantum pseudorandom notions in a quantum analog of the random oracle model, where all the parties, including the adversary, have oracle access to the same Haar random unitary. In this model, we show the following: - (Unbounded-query secure) pseudorandom unitaries (PRU) exist. Moreover, the PRU construction makes two calls to the Haar oracle. - We consider constructions of PRUs making a single call to the Haar oracle. In this setting, we show that unbounded-query security is impossible to achieve. We complement this result by showing that bounded-query secure PRUs do exist with a single query to the Haar oracle. - We show that multi-copy pseudorandom state generators and function-like state generators (with classical query access), making a single call to the Haar oracle, exist. Our results have two consequences: (a) when the Haar random unitary is instantiated suitably, our results present viable approaches for building quantum pseudorandom objects without relying upon one-way functions and, (b) for the first time, we show that the key length in pseudorandom unitaries can be generically shrunk (relative to the output length). Our results are also some of the first usecases of the new "path recording" formalism for Haar random unitaries, introduced in the recent breakthrough work of Ma and Huang.

Related papers

• Pseudorandom Function-like States from Common Haar Unitary [1.0067421338825544]
  We construct classically-accessible adaptive secure PRFSGs in the invertible quantum Haar random oracle (QHRO) model. Our PRFSG constructions resemble the classical EvenMansour encryption based on a single permutation, and are secure against any unbounded number of queries.
  arXiv  Detail & Related papers  (2024-11-05T15:48:27Z)
• 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)
• The power of a single Haar random state: constructing and separating quantum pseudorandomness [2.2748974006378937]
  We show, perhaps surprisingly, that such an oracle is construct quantum pseudorandomness. A weaker notion, called single-copy pseudorandom states (1PRS), satisfies this property with respect to a single copy.
  arXiv  Detail & Related papers  (2024-04-04T08:36:44Z)
• 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 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)
• A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles [7.454028086083526]
  We study the (quantum) security of pseudorandom generators (PRGs) constructed from random oracles. We prove a "lifting theorem" showing, roughly, that if such a PRG is unconditionally secure against classical adversaries making unboundedly many queries to the random oracle, then it is also (unconditionally) secure against quantum adversaries in the same sense.
  arXiv  Detail & Related papers  (2024-01-25T17:13:51Z)
• 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)
• 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)
• Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism [103.36492220921109]
  We show that although Strong Proportionality is a well-motivated and basic axiom, there is no deterministic strategyproof mechanism satisfying the property. We then identify a randomized mechanism called Random Rank which satisfies Strong Proportionality in expectation. Our main characterizes Random Rank as the unique mechanism that achieves universal truthfulness, universal anonymity, and Strong Proportionality in expectation.
  arXiv  Detail & Related papers  (2022-05-30T00:51:57Z)
• Using Randomness to decide among Locality, Realism and Ergodicity [91.3755431537592]
  An experiment is proposed to find out, or at least to get an indication about, which one is false. The results of such experiment would be important not only to the foundations of Quantum Mechanics.
  arXiv  Detail & Related papers  (2020-01-06T19:26:32Z)

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.