



@article {3507,
	title = {Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations},
	year = {2024},
	month = {3/7/2024},
	abstract = {<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>},
	url = {https://arxiv.org/abs/2403.04740},
	author = {Joseph Carolan and Alexander Poremba}
}
