Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations

• URL: http://arxiv.org/abs/2403.04740v4
• Date: Thu, 16 Jan 2025 00:28:43 GMT
• Title: Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations
• Authors: Joseph Carolan, Alexander Poremba,
• Abstract summary: 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.
• Score: 49.1574468325115
• License:
• Abstract: Sponge hashing is a widely used class of cryptographic hash algorithms which underlies the current international hash function standard SHA-3. In a nutshell, a sponge function takes as input a bit-stream of any length and processes it via a simple iterative procedure: it repeatedly feeds each block of the input into a so-called block function, and then produces a digest by once again iterating the block function on the final output bits. While much is known about the post-quantum security of the sponge construction when the block function is modeled as a random function or one-way permutation, the case of invertible permutations, which more accurately models the construction underlying SHA-3, has so far remained a fundamental open problem. In this work, we make new progress towards overcoming this barrier and show several results. First, we prove the "double-sided zero-search" conjecture proposed by Unruh (eprint' 2021) and show that finding zero-pairs in a random $2n$-bit permutation requires at least $\Omega(2^{n/2})$ many queries -- and this is tight due to Grover's algorithm. At the core of our proof lies a novel "symmetrization argument" which uses insights from the theory of Young subgroups. Second, we consider more general variants of the double-sided search problem and show similar query lower bounds for them. As an application, we prove the quantum one-wayness of the single-round sponge with invertible permutations in the quantum random oracle model.

Related papers

• Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
  We present a new highly simplified construction of a purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting. Our purifier has exponentially better space complexity than the previous one, and quadratically better dependence on the soundness-completeness gap of the algorithm being purified.
  arXiv  Detail & Related papers  (2025-02-13T12:04:39Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  We propose two principled algorithms for the test-time compute of large language models. We prove theoretically that the failure probability of one algorithm decays to zero exponentially as its test-time compute grows.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• 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)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• 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)
• The NISQ Complexity of Collision Finding [2.9405711598281536]
  A fundamental primitive in modern cryptography, collision-resistant hashing ensures there is no efficient way to find inputs that produce the same hash value. Quantum adversaries now require full-scale computers equipped with the power of NISQ. In this paper, we investigate three different models for NISQ algorithms achieve tight bounds for all of them.
  arXiv  Detail & Related papers  (2022-11-23T13:55:28Z)
• 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)
• Quantum Search for Scaled Hash Function Preimages [1.3299507495084417]
  We present the implementation of Grover's algorithm in a quantum simulator to perform a quantum search for preimages of two scaled hash functions. We show that strategies that suggest a shortcut based on sampling the quantum register after a few steps of Grover's algorithm can only provide some marginal practical advantage in terms of error mitigation.
  arXiv  Detail & Related papers  (2020-09-01T18:00:02Z)
• Sparse Hashing for Scalable Approximate Model Counting: Theory and Practice [36.8421113576893]
  Given a CNF formula F on n variables, the problem of model counting or #SAT is to compute the number of satisfying assignments of F. Recent years have witnessed a surge of effort towards developing efficient algorithmic techniques.
  arXiv  Detail & Related papers  (2020-04-30T11:17:26Z)
• Quantum Attacks without Superposition Queries: the Offline Simon's Algorithm [7.819565615098435]
  We introduce a new quantum algorithm which uses Simon's subroutines in a novel way. We obtain improved quantum-time/classical-data tradeoffs with respect to the current literature. We improve some previous superposition attacks by reducing the data complexity.
  arXiv  Detail & Related papers  (2020-02-27T21:05:54Z)

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.