MJH: a faster alternative to MDC-2

Abstract

In this paper, we introduce a new class of double-block-length hash functions. Using the ideal cipher model, we prove that these hash functions, dubbed MJH, are asymptotically collision resistant up to query complexity for any in the iteration, where is the block size of the underlying blockcipher. When based on -bit key blockciphers, our construction, being of rate 1/2, provides better provable security than MDC-2, the only known construction of a rate-1/2 double-length hash function based on an -bit key blockcipher with non-trivial provable security. Moreover, since key scheduling is performed only once per message block for MJH, our proposal significantly outperforms MDC-2 in efficiency. When based on a -bit key blockcipher, we can use the extra bits of key to increase the amount of payload accordingly. Thus we get a rate-1 hash function that is much faster than existing proposals, such as Tandem-DM with comparable provable security. This is the full version of Lee and Stam (A faster alternative to MDC-2, 2011).