Multi Collision Resistant Hash Functions and their Applications

Oded's comments

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).

The original abstract

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:

1. The existence of MCRH follows from the average case hardness of a variant of Entropy Approximation, a problem known to be complete for the class NISZK.
2. MCRH imply the existence of constant-round statistically hiding (and computationally binding) commitment schemes.

See ECCC TR17-097.