Collision Resistance from Multi-collision Resistance.

Collision-resistant hash functions (CRH ) are a fundamental and ubiquitous cryptographic primitive. Several recent works have studied a relaxation of CRH called t-way multi-collision-resistant hash functions ( t - 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) -way collisions may be easy to find). The case of t = 2 corresponds to standard CRH , but it is natural to study t- 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- MCRH , for t ∈ { 3 , 4 } , into an (infinitely often secure) CRH . This transformation is non-constructive—we can prove the existence of a 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 ′ , we can transform a t- MCRH into a t ′ - 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. [ABSTRACT FROM AUTHOR]