TR17-097 Authors: Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan

Publication: 31st May 2017 21:30

Downloads: 103

Keywords:

Collision resistant hash functions 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.

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