Collision Resistance from Multi-collision Resistance for All Constant Parameters

A t-multi-collision-resistant hash function (t-MCRH) is a family of shrinking functions for which it is computationally hard to find t distinct inputs mapped to the same output by a function sampled from this family. Several works have shown that t-MCRHs are sufficient for many of the applications of collision-resistant hash functions (CRHs), which correspond to the special case of  \(t = 2\) . An important question is hence whether t-MCRHs for \(t > 2\) are fundamentally weaker objects than CRHs. As a first step towards resolving this question, Rothblum and Vasudevan (CRYPTO ’22) recently gave non-black-box constructions of infinitely-often secure CRHs from t-MCRHs for \(t \in \{3,4\}\) assuming the MCRH is sufficiently shrinking. Earlier on, Komargodski and Yogev (CRYPTO ’18) also showed that t-MCRHs for any constant t imply the weaker notion of a distributional CRH. In this paper, we remove the limitations of prior works, and completely resolve the question of the power of t-MCRHs for constant t in the infinitely-often regime, showing that the existence of such a function family always implies the existence of an infinitely-often secure CRH. As in the works mentioned above, our proof is non-black-box and non-constructive. We further give a new domain extension result for MCRHs that enables us to show that the underlying MCRH need only have arbitrarily small linear shrinkage (mapping \((1 + \epsilon )n\) bits to n bits for any fixed \(\epsilon > 0\) ) to imply the existence of CRHs.