International Association
for Cryptologic Research

We 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). Despite showing the feasibility of realizing PRIO and NIRP

objects in theory-using ideal ciphers and (trapdoor) one-way permutations- these constructions suffer from several

efficiency and implementation issues as pointed out by their designers and briefly reviewed in this paper.

In contrast to the previous constructions, we show that constructing a DMS hash function does not require any

PRIO or NIRP, and hence there is no need for additional (trapdoor) one-way permutations. In fact, Ristenpart and

Shrimpton posed the question of whether MCM is secure under easy-to-invert mixing steps as an open problem in

their paper.We resolve this question in the affirmative in the fixed-input-length (FIL) hash setting. More precisely,

we show that one can sandwich a provably CR function, which is sufficiently compressing, between two random

invertible permutations to build a provably DMS compression function. Any multi-property-preserving (MPP)

domain extender that preserves CR and PRO can then be used to convert such a DMS compression function

to a full-fledged DMS hash function. Interestingly, there are efficient off-the-shelf candidates for all the three

ingredients (provably CR compression functions, random invertible permutations, and MPP domain extenders)

from which one can choose to implement such a DMS hash function in practice. Further, we also explain the

implementation options as well as a concrete instantiation.