Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations
<|reference_start|>Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations: 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.<|reference_end|>
@article{carolan2024quantum,
    title={Quantum One-Wayness of the Single-Round Sponge with Invertible
  Permutations},
    author={Joseph Carolan and Alexander Poremba},
    journal={arXiv preprint arXiv:2403.04740},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.04740},
    primaryClass={quant-ph cs.CR}
}