Mix-Compress-Mix Revisited: Dispensing with Non-invertible Random Injection Oracles

The authors revisit the problem of building Dual-Model Secure (DMS) hash functions that are simultaneously provably Collision Resistant (CR) in the standard model and provably PseudoRandom Oracle (PRO) in an idealized model. Designing a DMS hash function was first investigated by Ristenpart and Shrimpton (ASIACRYPT 2007); they put forth a generic approach, called Mix-Compress-Mix (MCM), and showed the feasibility of the MCM approach with a secure (but inefficient) construction. An improved construction was later presented by Lehmann and Tessaro (ASIACRYPT 2009). The proposed construction by Ristenpart and Shrimpton requires a non-invertible (Pseudo-) Random Injection Oracle (PRIO) and the Lehmann-Tessaro construction requires a Non-Invertible Random Permutation oracle (NIRP).