Compressed Permutation Oracles

• URL: http://arxiv.org/abs/2509.18586v1
• Date: Tue, 23 Sep 2025 03:13:48 GMT
• Title: Compressed Permutation Oracles
• Authors: Joseph Carolan,
• Abstract summary: We develop and prove soundness of a compressed permutation oracle.<n>We re-prove essentially all known quantum query lower bounds in the random permutation model.
• Score: 0.6768558752130311
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The analysis of quantum algorithms which query random, invertible permutations has been a long-standing challenge in cryptography. Many techniques which apply to random oracles fail, or are not known to generalize to this setting. As a result, foundational cryptographic constructions involving permutations often lack quantum security proofs. With the aim of closing this gap, we develop and prove soundness of a compressed permutation oracle. Our construction shares many of the attractive features of Zhandry's original compressed function oracle: the purification is a small list of input-output pairs which meaningfully reflect an algorithm's knowledge of the oracle. We then apply this framework to show that the Feistel construction with seven rounds is a strong quantum PRP, resolving an open question of (Zhandry, 2012). We further re-prove essentially all known quantum query lower bounds in the random permutation model, notably the collision and preimage resistance of both Sponge and Davies-Meyer, hardness of double-sided zero search and sparse predicate search, and give new lower bounds for cycle finding and the one-more problem.

Related papers

• Quantum Lifting for Invertible Permutations and Ideal Ciphers [47.33103206862089]
  We derive the first lifting theorems for establishing security in the quantum random permutation and ideal cipher models.<n>These theorems relate the success probability of an arbitrary quantum adversary to that of a classical algorithm making only a small number of classical queries.
  arXiv  Detail & Related papers  (2025-04-25T09:07:55Z)
• Permutation Superposition Oracles for Quantum Query Lower Bounds [14.957648729581502]
  We show how to use the resulting oracle simulation to bound the success probability of an algorithm for any predicate on input-output pairs. We show that the one-round sponge construction is unconditionally preimage resistant in the random permutation model.
  arXiv  Detail & Related papers  (2024-07-12T19:27:13Z)
• 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)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  Sponge hashing is a widely used class of cryptographic hash algorithms.<n>Intrepid permutations have so far remained a fundamental open problem.<n>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)
• 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.<n>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)
• On the Two-sided Permutation Inversion Problem [45.69327512339002]
  We study the setting in which the oracle allows for quantum queries to both the forward and inverse direction of the permutation. We prove several theorems connecting the hardness of the resulting variations of the inversion problem. Our results indicate that, perhaps surprisingly, the inversion problem does not become significantly easier when the adversary is granted oracle access to the inverse.
  arXiv  Detail & Related papers  (2023-06-23T18:31:48Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound. This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
  arXiv  Detail & Related papers  (2023-01-05T11:05:22Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
  arXiv  Detail & Related papers  (2022-02-10T18:59:52Z)
• Tight Bounds for Inverting Permutations via Compressed Oracle Arguments [0.0]
  Zhandry studied interactions between quantum query algorithms and the quantum oracle corresponding to random functions. We introduce a similar interpretation for the case when the oracle corresponds to random permutations instead of random functions. Because both random functions and random permutations are highly significant in security proofs, we hope that the present framework will find applications in quantum cryptography.
  arXiv  Detail & Related papers  (2021-03-16T11:05:48Z)
• Introducing Structure to Expedite Quantum Search [0.0]
  We present a novel quantum algorithm for solving the unstructured search problem with one marked element. Our algorithm is optimal in the total number of elementary gates up to a multiplicative constant. We show how toally reduce the number of elementary gates required to solve the unstructured search problem with multiple marked elements.
  arXiv  Detail & Related papers  (2020-06-10T13:29:47Z)

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.