Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR17-097 | 31st May 2017 19:49

Multi Collision Resistant Hash Functions and their Applications



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.

ISSN 1433-8092 | Imprint