Name
Abstract | ||
|---|---|---|
At CRYPTO 2008 Stam [8] 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 [9] 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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-32009-5_23 | ADVANCES IN CRYPTOLOGY - CRYPTO 2012 |
DocType | Volume | Issue |
Journal | 7417 | null |
ISSN | Citations | PageRank |
0302-9743 | 6 | 0.42 |
References | Authors | |
9 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| John P. Steinberger | 1 | 329 | 18.30 |
| Xiaoming Sun | 2 | 280 | 41.19 |
| Zhe Yang | 3 | 6 | 0.42 |