## Multi Collision Resistant Hash Functions and their Applications

by Itay Berman, Akshay Degwekar, Ron Rothblum,
and Prashant Nalini Vasudevan

#### 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:

- 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.
- MCRH imply the existence of constant-round statistically hiding (and
computationally binding) commitment schemes.

In addition, we show a blackbox separation of MCRH from any one-way
permutation.
See ECCC TR17-097.

Back to
list of Oded's choices.