Welcome to the resource topic for 2023/1444
Title:
On Time-Space Lower Bounds for Finding Short Collisions in Sponge Hash Functions
Authors: Akshima, Xiaoqi Duan, Siyao Guo, Qipeng Liu
Abstract: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.
ePrint: https://eprint.iacr.org/2023/1444
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .