Stam's
Conjecture and Threshold Phenomena in Collision Resistance
John
Steinberger (
Xiaoming Sun
(Chinese
Zhe Yang (Hulu,
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 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 phenomenona
observed in practical compression functions such as JHash
are, in fact, unavoidable for compression functions with those parameters.