Suppose we are given a perfect na??+a??c-to-n bit compression function f and we want to construct a larger ma??+a??s-to-s bit compression function H instead. What level of security, in particular collision resistance, can we expect from H if it makes r calls to f? We conjecture that typically collisions can be found in 2(nra??+a??cra??a??a??m)/(ra??+a??1) queries. This bound is also relevant for building a ma??+a??s-to-s bit compression function based on a blockcipher with k-bit keys and n-bit blocks: simply set ca??=a??k, or ca??=a??0 in case of fixed keys. We also exhibit a number of (conceptual) compression functions whose collision resistance is close to this bound. In particular, we consider the following four scenarios:
* A 2n-to-n bit compression function making two calls to an n-to-n bit primitive, providing collision resistance up to 2 n/3/n queries. This beats a recent bound by Rogaway and Steinberger that 2 n/4 queries to the underlying random n-to-n bit function suffice to find collisions in any rate-1/2 compression function. In particular, this shows that Rogaway and Steinbergera??s recent bound of 2(nra??a??a??ma??a??a??s/2)/r) queries (for ca??=a??0) crucially relies upon a uniformity assumption; a blanket generalization to arbitrary compression functions would be incorrect.
* A 3n-to-2n bit compression function making a single call to a 3n-to-n bit primitive, providing collision resistance up to 2 n queries.
* A 3n-to-2n bit compression function making two calls to a 2n-to-n bit primitive, providing collision resistance up to 2 n queries.
* A single call compression function with parameters satisfying ma??a??a??na??+a??c, na??a??a??s, ca??a??a??m. This result provides a tradeoff between how many bits you can compress for what level of security given a single call to an na??+a??c-to-n bit random function.