Name
Abstract | ||
|---|---|---|
At CRYPTO 2008 Stam [7] made the following conjecture: 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. For example, a 2n-bit to n-bit compression function making two calls to a random function of n-bit input cannot have collision security exceeding 2n/3. We prove this conjecture up to a constant multiplicative factor and under the condition m′ :=(2m−n(r−1))/(r+1)≥log2(17). This covers nearly all cases r=1 of the conjecture and the aforementioned example of a 2n-bit to n-bit compression function making two calls to a primitive of n-bit input. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-13190-5_30 | EUROCRYPT |
Keywords | Field | DocType |
random function | Discrete mathematics,Combinatorics,Multiplicative function,Collision resistance,Collision,Hash function,Conjecture,Mathematics,Random function | Conference |
Volume | Issue | ISSN |
6110 LNCS | null | 0302-9743 |
ISBN | Citations | PageRank |
3-642-13189-1 | 10 | 0.56 |
References | Authors | |
6 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| John P. Steinberger | 1 | 329 | 18.30 |