Paper 2007/409

Building a Collision-Resistant Compression Function from Non-Compressing Primitives

Thomas Shrimpton and Martijn Stam


We consider how to build an efficient compression function from a small number of random, non-compressing primitives. Our main goal is to achieve a level of collision resistance as close as possible to the optimal birthday bound. We present a $2n$-to-$n$ bit compression function based on three independent $n$-to-$n$ bit random functions, each called only once. We show that if the three random functions are treated as black boxes finding collisions requires $\Theta(2^{n/2}/n^c)$ queries for $c\approx 1$. This result remains valid if two of the three random functions are replaced by a fixed-key ideal cipher in Davies-Meyer mode (i.e., $E_K(x)\xor x$ for permutation $E_K$). We also give a heuristic, backed by experimental results, suggesting that the security loss is at most four bits for block sizes up to 256 bits. We believe this is the best result to date on the matter of building a collision resistant compression function from non-compressing functions. It also relates to an open question from Black et al. (Eurocrypt'05), who showed that compression functions that invoke a single non-compressing random function cannot suffice. We also explore the relationship of our problem with that of doubling the output of a hash function and we show how our compression function can be used to double the output length of ideal hashes.

Available format(s)
Publication info
Published elsewhere. Full version of paper appearing at ICALP'08
Hash FunctionsRandom Oracle ModelCompression FunctionsCollision Resistance
Contact author(s)
martijn stam @ epfl ch
2008-07-06: last of 2 revisions
2007-10-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Thomas Shrimpton and Martijn Stam},
      title = {Building a Collision-Resistant Compression Function from Non-Compressing Primitives},
      howpublished = {Cryptology ePrint Archive, Paper 2007/409},
      year = {2007},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.