Three-property preserving iterations of keyless compression functions

Ref: Elena Andreeva, Gregory Neven, Bart Preneel and Thomas Shrimpton. ECRYPT Workshop on Hash Functions 2007, electronically available from

Abstract: Almost all hash functions are based on the Merkle-Damgard iteration of a finite-domain compression function. It has been shown that this iteration preserves collision resistance, but it does not preserve other properties such as preimage or second preimage resistance. The recently proposed ROX construction provably preserves all seven security notions put forward by Rogaway and Shrimpton at FSE 2004, but it does so for families of hash functions, that is, the compression function is indexed by a public parameter known as a key. Practical hash functions however do not have such a parameter, so it is not entirely clear how to instantiate these schemes. We use Rogaway’s human-ignorance approach to resolve this situation, and present four different iterations (two of them chaining-based, two of them tree-based) that provably preserve all three notions of collision, preimage and second preimage resistance.