**Stam's Conjecture and Threshold Phenomena in Collision Resistance**

*John Steinberger, Xiaoming Sun, Zhe Yang*

**Abstract: **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.)

**Category / Keywords: **

**Publication Info: **CRYPTO 2012

**Date: **received 7 Aug 2012

**Contact author: **jpsteinb at gmail com

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20120808:060716 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]