Collision Resistance from Multi-collision Resistance

Collision-resistant hash functions ( \(\textsf{CRH}\) $\mathsf{CRH}$ ) are a fundamental and ubiquitous cryptographic primitive. Several recent works have studied a relaxation of \(\textsf{CRH}\) $\mathsf{CRH}$ called t-way multi-collision-resistant hash functions ( \(t\text {-}\textsf{MCRH}\) $t\text{-}\mathsf{MCRH}$ ). These are families of functions for which it is computationally hard to find a t-way collision, even though such collisions are abundant (and even \((t-1)\) $(t-1)$ -way collisions may be easy to find). The case of \(t=2\) $t=2$ corresponds to standard \(\textsf{CRH}\) $\mathsf{CRH}$ , but it is natural to study t- \(\textsf{MCRH}\) $\mathsf{MCRH}$ for larger values of t. Multi-collision resistance seems to be a qualitatively weaker property than standard collision resistance. Nevertheless, in this work we show a non-blackbox transformation of any moderately shrinking t- \(\textsf{MCRH}\) $\mathsf{MCRH}$ , for \(t \in \{3,4\}\) $t\in \{3,4\}$ , into an (infinitely often secure) \(\textsf{CRH}\) $\mathsf{CRH}$ . This transformation is non-constructive—we can prove the existence of a \(\textsf{CRH}\) $\mathsf{CRH}$ but cannot explicitly point out a construction. Our result partially extends to larger values of t. In particular, we show that for suitable values of \(t>t'\) $t>t^{\prime }$ , we can transform a t- \(\textsf{MCRH}\) $\mathsf{MCRH}$ into a \(t'\) $t^{\prime }$ - \(\textsf{MCRH}\) $\mathsf{MCRH}$ , at the cost of reducing the shrinkage of the resulting hash function family and settling for infinitely often security. This result utilizes the list-decodability properties of Reed–Solomon codes.