| Abstract: |
Sponge paradigm, used in the design of SHA-3, is an alternative hashing technique to the popular Merkle-Damg\r ard paradigm. We revisit the problem of finding $B$-block-long collisions in sponge hash functions in the auxiliary-input random permutation model, in which an attacker gets a piece of $S$-bit advice about the random permutation and makes $T$ (forward or inverse) oracle queries to the random permutation.
Recently, significant progress has been made in the Merkle-Damg\r ard setting and optimal bounds are known for a large range of parameters, including all constant values of $B$. However, the sponge setting is widely open: there exist significant gaps between known attacks and security bounds even for $B=1$.
Freitag, Ghoshal and Komargodski (CRYPTO 2022) showed a novel attack for $B=1$ that takes advantage of the inverse queries and achieves advantage $\Omega(\min(S^2T^2/2^{2c}$, $ (S^2T/2^{2c})^{2/3})+T^2/2^r)$, where $r$ is bit-rate and $c$ is the capacity of the random permutation. However, they only showed an $O(ST/2^c+T^2/2^r)$ security bound, leaving open an intriguing quadratic gap. For $B=2$, they beat the general security bound %$O(ST^2/2^c+T^2/2^r)$,
by Coretti, Dodis,
Guo (CRYPTO 2018) for arbitrary values of $B$. However, their highly non-trivial argument is quite laborious, and no better (than the general) bounds are known for $B\geq 3$.
In this work, we study the possibility of proving better security bounds in the sponge setting. To this end,
\begin{itemize}
\item For $B=1$, we prove an improved $O(S^2T^2/2^{2c}+S/2^c+T/2^c+T^2/2^r)$ bound. Our bound strictly improves the bound by Freitag et al., %Ghoshal and Komargodski,
and is optimal for $ST^2\leq 2^c$. %and is optimal up to a factor of $(ST^2/2^c)^{2/3}$ for $ST^2>2^c$.
\item For $B=2$, we give a considerably simpler and more modular proof, recovering the bound obtained by Freitag et al. %, Ghoshal and Komargodski.
\item We obtain our bounds by adapting the recent multi-instance technique of Akshima, Guo and Liu (CRYPTO 2022) which bypasses limitations of prior techniques in the Merkle-Damg\r ard setting. To complement our results, we provably show that the recent multi-instance technique cannot further improve our bounds for $B=1,2$, and the general %$O(ST^2/2^c+T^2/2^r)$
bound by Correti et al., for $B\geq 3$.
\end{itemize}
Overall, our results yield the state-of-the-art security bounds for finding short collisions, and fully characterize the power of the multi-instance technique in the sponge setting.
\keywords{Collision \and hash functions \and Sponge \and multi-instance \and pre-computation \and auxiliary input} |
