It may be worthy to highlight some facts regarding the two main results stated in the abstract. The first result presents a construction of MCRH based on an assumption that is not known to imply standard CRH. The second result shows that general MCRH imply constant-round statistically hiding commitment schemes, whereas arbitrary one-way functions are only known to imply statistically hiding commitment schemes of a large number of rounds. Hence, these results demonstrate that MCRH may be a useful relaxation of CRH; on the one hand, MCRH may be constructable under weaker conditions (than CRH) and on the other hand they may yield similar applications.
Note (by Ron): The two related (concurrent and independent) works mentioned at the very end of Section 1.2 have been posted (see BKP and KNY).
Collision resistant hash functions (CRH) are functions that shrink their input, but for which it is computationally infeasible to find a collision, namely two strings that hash to the same value (although collisions are abundant).
In this work we study multi-collision resistant hash functions (MCRH) a natural relaxation of collision resistant hash functions in which it is difficult to find a t-way collision (i.e., t strings that hash to the same value) although finding (t-1)-way collisions could be easy. We show the following:
See ECCC TR17-097.