



01910nas a2200121   4500008004100000245008000041210006900121260001300190520150500203100002001708700002301728856003701751       2024                        eng d00aQuantum One-Wayness of the Single-Round Sponge with Invertible Permutations0 aQuantum OneWayness of the SingleRound Sponge with Invertible Per  c3/7/20243 a<p>Sponge hashing is a novel 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 short digest which consists of a subset of the final output bits. While much is known about the post-quantum security of the sponge construction in the case when the block function is modeled as a random function or permutation, the case of invertible permutations, which more accurately models the construction underlying SHA-3, has so far remained a fundamental open problem.<br />In this work, we make new progress towards overcoming this barrier and show several results. First, we prove the &quot;double-sided zero-search&quot; conjecture proposed by Unruh (eprint&#39; 2021) and show that finding zero-pairs in a random 2n-bit permutation requires at least Ω(2n/2) many queries -- and this is tight due to Grover&#39;s algorithm. At the core of our proof lies a novel &quot;symmetrization argument&quot; 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.</p>1 aCarolan, Joseph1 aPoremba, Alexander  uhttps://arxiv.org/abs/2403.04740