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

Authors:
Mihir Bellare and Thomas Ristenpart

Abstract:
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.

References:
An extended abstract appears in Advances in Cryptology - ASIACRYPT 2006, Lecture Notes in Computer Science Vol. 4284, pp. 299-314, X. Lai and K. Chen eds., Springer-Verlag, 2006.

An earlier version of this work appeared in the Second Cryptographic Hash Workshop in 2006.

Full Version:
Full version of the Asiacrypt paper: pdf.

Presentations:
The slides from my presentation at Asiacrypt 2006 can be found here (pdf).

List of Updates:
October 18, 2007 (Thanks to Elena Andreeva for pointing out an error in the proof of Theorem 5.2. Corrected version is now posted.)
December 28, 2006 (Thanks, again, to Donghoon Chang for pointing out an error in the final case analysis of the proof of Lemma 5.1 which lead to a too-tight bound. Corrected version is now posted.)
December 11, 2006 (typo fix in Asiacrypt full version. Thanks to Donghoon Chang for pointing out a typo in Theorem 5.2)
December 6, 2006 (put up Asiacrypt slides)
November 8, 2006 (put up full version of Asiacrypt paper)
August 26, 2006