Paper 2023/1444

On Time-Space Lower Bounds for Finding Short Collisions in Sponge Hash Functions

Akshima, NYU Shanghai
Xiaoqi Duan, ETH Zürich
Siyao Guo, NYU Shanghai
Qipeng Liu, UC San Diego

Sponge paradigm, used in the design of SHA-3, is an alternative hashing technique to the popular Merkle-Damgård 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ård 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 $\tilde{\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 $\tilde{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 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, - For $B=1$, we prove an improved $\tilde{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., and is optimal for $ST^2\leq 2^c$. - For $B=2$, we give a considerably simpler and more modular proof, recovering the bound obtained by Freitag et al. - We obtain our bounds by adapting the recent multi-instance technique of Akshima, Guo and Liu (CRYPTO 2022) which bypasses the limitations of prior techniques in the Merkle-Damgård 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 bound by Correti et al., for $B\geq 3$. Overall, our results yield state-of-the-art security bounds for finding short collisions and fully characterize the power of the multi-instance technique in the sponge setting.

Available format(s)
Publication info
A minor revision of an IACR publication in TCC 2023
Collisionhash functionsSpongemulti-instancepre-computationauxiliary input
Contact author(s)
akshima @ nyu edu
dogther66 @ gmail com
siyao guo 41 @ gmail com
qipengliu0 @ gmail com
2023-11-15: revised
2023-09-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Akshima and Xiaoqi Duan and Siyao Guo and Qipeng Liu},
      title = {On Time-Space Lower Bounds for Finding Short Collisions in Sponge Hash Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1444},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.