Paper 2012/451

Stam's Conjecture and Threshold Phenomena in Collision Resistance

John Steinberger, Xiaoming Sun, and 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.)

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. CRYPTO 2012
Contact author(s)
jpsteinb @ gmail com
History
2012-08-08: received
Short URL
https://ia.cr/2012/451
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/451,
      author = {John Steinberger and Xiaoming Sun and Zhe Yang},
      title = {Stam's Conjecture and Threshold Phenomena in Collision Resistance},
      howpublished = {Cryptology ePrint Archive, Paper 2012/451},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/451}},
      url = {https://eprint.iacr.org/2012/451}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.