Beyond uniformity: Better security/efficiency tradeoffs for compression functions
Suppose we are given a perfect n + c-to-n bit compression function f and we want to construct a larger m + 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((nr+cr-m)/(r+1)) queries. This bound is also relevant for building a m + s-to-s bit compression function based on a blockcipher with k-bit keys and n-bit blocks: simply set c = k, or c = 0 in case of fixed keys.