Paper 2006/399

Multi-Property-Preserving Hash Domain Extension and the EMD Transform

Mihir Bellare and Thomas Ristenpart


We point out that the seemingly strong pseudorandom oracle preserving (PRO-Pr) property of hash function domain-extension transforms defined and implemented by Coron et. al. [12] can actually weaken our guarantees on the hash function, in particular producing a hash function that fails to be even collision-resistant (CR) even though the compression function to which the transform is applied is CR. Not only is this true in general, but we show that all the transforms presented in [12] have this weakness. We suggest that the appropriate goal of a domain extension transform for the next generation of hash functions is to be multi-property preserving, namely that one should have a single transform that is simultaneously at least collision-resistance preserving, pseudorandom function preserving and PRO-Pr. We present an efficient new transform that is proven to be multi-property preserving in this sense.

Note: New update (October 2007) includes fix for an error in the proof of Theorem 5.2. Previously: fixed an error in the proof of Lemma 5.1 (which lead to a too-tight bound).

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Preliminary version in Asiacrypt 2006. This is the full version.
Hash functionsrandom oracleMerkle-Damgardcollision-resistancepsuedorandom function
Contact author(s)
tristenp @ cs ucsd edu
2007-10-18: last of 4 revisions
2006-11-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mihir Bellare and Thomas Ristenpart},
      title = {Multi-Property-Preserving Hash Domain Extension and the EMD Transform},
      howpublished = {Cryptology ePrint Archive, Paper 2006/399},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.