International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Thomas Shrimpton
Martijn Stam
Download:
URL: http://eprint.iacr.org/2007/409
Search ePrint
Search Google
Abstract: We consider how to build an efficient compression function from a small number of random, non-compressing primitives (fixed-key blockciphers were our original motivation). 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 (i.e., modelled as random oracles), finding collisions requires $\Theta(2^{n/2}/n^c)$ queries for $c\approx 1$. 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.
BibTeX
@misc{eprint-2007-13689,
  title={Building a Collision-Resistant Compression Function from Non-Compressing Primitives},
  booktitle={IACR Eprint archive},
  keywords={Hash Functions, Random Oracle Model, Compression Functions, Collision Resistance},
  url={http://eprint.iacr.org/2007/409},
  note={ martijn.stam@epfl.ch 13811 received 25 Oct 2007},
  author={Thomas Shrimpton and Martijn Stam},
  year=2007
}