  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.
