Short Collisions Separate Sponge from Merkle-Damgård

What it is

Ashrujit Ghoshal's ePrint 2026/2695 (received 30 October 2026, approved 4 November 2026, preprint) compares short-collision finding in salted Merkle-Damgård (MD) and Sponge. It works in the query-bounded preprocessing model of Ghoshal and Tessaro (CRYPTO '23). The adversary makes at most T1 queries before the salt is revealed and at most T2 afterwards, and must output two colliding messages of at most B blocks.

How it works

The separation holds in one parameter regime: N = 2^n, matching n-bit salts, blocks and outputs for both constructions, T1 = Θ(N/T2), and T2 = o(√N). In that regime the two constructions behave differently.

• Sponge: a three-block attack uses inverse permutation queries to make one precomputed collision useful from many different capacities. It succeeds with constant probability.
• MD: any adversary with B = o(T2) blocks succeeds with probability at most O(B/T2 + T2²/N), which is o(1). The proof is a graph argument. It separates collisions already present in the preprocessing transcript from those reachable by a short computation starting from the newly sampled salt.

The MD bound holds for arbitrary B. Earlier analyses covered only the one- and two-block cases.

Caveats

• Sponge also has a matching upper bound in a range that contains the separation. There, longer messages give no asymptotic gain, and the best preprocessing advantage is already reached with at most three blocks.
• The result concerns ideal primitives under matched query budgets and salt, block and output sizes. The page does not map it to any deployed hash function or give concrete parameters.
• The page gives no implementation, and no guidance for choosing between constructions in practice.