International Association
for Cryptologic Research

At CRYPTO 2008 Stam conjectured that if an $(m\\!+\\!s)$-bit

to $s$-bit compression function $F$ makes $r$ calls to a primitive $f$

of $n$-bit input, then a collision for $F$ can be obtained (with high

probability) using $r2^{(nr-m)/(r+1)}$ queries to $f$, which is sometimes

less than the birthday bound. Steinberger (Eurocrypt 2010) proved Stam\'s

conjecture up to a constant multiplicative factor for most cases in

which $r = 1$ and for certain other cases that reduce to the case

$r = 1$. In this paper we prove the general case of Stam\'s conjecture

(also up to a constant multiplicative factor). Our result is

qualitatively different from Steinberger\'s, moreover, as we show the

following novel threshold phenomenon: that exponentially many (more

exactly, $2^{s-2(m-n)/(r+1)}$) collisions are obtained with high

probability after $O(1)r2^{(nr-m)/(r+1)}$ queries. This in particular

shows that threshold phenomena observed in practical compression

functions such as JH are, in fact, unavoidable for compression

functions with those parameters. (This is the full version of the

same-titled article that appeared at CRYPTO 2012.)