Cryptology ePrint Archive: Report 2017/489

Multi Collision Resistant Hash Functions and their Applications

Itay Berman and Akshay Degwekar and Ron D. Rothblum and Prashant Nalini Vasudevan

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

- 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

Category / Keywords: foundations / collision resistant hashing, entropy approximation

Date: received 29 May 2017, last revised 29 May 2017

Contact author: ronr at mit edu

Available format(s): PDF | BibTeX Citation

Version: 20170531:181725 (All versions of this report)

Short URL: ia.cr/2017/489

Discussion forum: Show discussion | Start new discussion