View article

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 then finding collisions requires Θ(2^n/2/n ^c ) queries for c ≈ 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) ⊕ 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 …