A Boolean function f is monotone if and only if there exists a monotone Boolean circuit (consisting exclusively of AND or OR gates) which computes f . The study of monotone cryptography was initiated by Goldreich and Izsak (TOC '12) who showed that one-way functions (OWF) can be monotone, but no monotone pseudo-random generator (PRG) exists. Incidentally, many cryptographic primitives cannot be monotone, by the work of Guo, Malkin, Oliveira and Rosen (TCC'15). Not long after, Miller, Scrivener, Stern and Venkitasubramaniam (INDOCRYPT'16) showed that collision resistant hash functions (CRH) (and even the weaker notion of target CRH) cannot be monotone. Distributional collision resistant hash functions (dCRH) are a relaxation of the usual CRH notion. In particular, a hash function h has distributional collision resistance if there does not exist any efficient adversary that produces collisions that are statistically close to ( x 1 , x 2 ) where x 1 is a random input and x 2 is sampled uniformly from the set of pre-images of h ( x 1 ) . Despite being a weaker notion of collision resistance, dCRH have applications to e.g. constant round statistically-hiding commitment schemes, and (these commitment schemes) are not known to be constructible from OWF alone. In this work we show the existence of a monotone dCRH, assuming any CRH exists. To prove our result, we observe that the proof technique of Goldreich and Izsak for the existence of monotone OWF can be extended analogously to dCRH. As a result, dCRH joins the rather small list of primitives known to also be monotone, namely (surjective or injective, but not bijective) OWF, and certain list decodable codes (decoders).
Kirthivaasan Puniamurthy (Mon,) studied this question.