A Collision-Resistant Rate-1 Double-Block-Length Hash Function

This paper proposes a construction for collision resistant $2n$-bit hash functions, based on $n$-bit block ciphers with $2n$-bit keys. The construction is analysed in the ideal cipher model; for $n=128$ an adversary would need roughly $2^{122}$ units of time to find a collision. The construction employs ``combinatorial\u27\u27 hashing as an underlying building block (like Universal Hashing for cryptographic message authentication by Wegman and Carter). The construction runs at rate~1, thus improving on a similar rate~1/2 approach by Hirose (FSE 2006)