Paper 2017/489

Multi Collision Resistant Hash Functions and their Applications

Itay Berman, Akshay Degwekar, 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: 1. The existence of MCRH follows from the average case hardness of a variant of the Entropy Approximation problem. The goal in the entropy approximation problem (Goldreich, Sahai and Vadhan, CRYPTO '99) is to distinguish circuits whose output distribution has high entropy from those having low entropy. 2. MCRH imply the existence of constant-round statistically hiding (and computationally binding) commitment schemes. As a corollary, using a result of Haitner et-al (SICOMP, 2015), we obtain a blackbox separation of MCRH from any one-way permutation.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
collision resistant hashingentropy approximation
Contact author(s)
ronr @ mit edu
History
2017-09-26: revised
2017-05-31: received
See all versions
Short URL
https://ia.cr/2017/489
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/489,
      author = {Itay Berman and Akshay Degwekar and Ron D.  Rothblum and Prashant Nalini Vasudevan},
      title = {Multi Collision Resistant Hash Functions and their Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/489},
      year = {2017},
      url = {https://eprint.iacr.org/2017/489}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.