ECCC-Report TR17-097https://eccc.weizmann.ac.il/report/2017/097Comments and Revisions published for TR17-097en-usTue, 26 Sep 2017 22:41:50 +0300
Revision 1
| Multi Collision Resistant Hash Functions and their Applications |
Itay Berman,
Akshay Degwekar,
Ron Rothblum,
Prashant Nalini Vasudevan
https://eccc.weizmann.ac.il/report/2017/097#revision1Collision 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. Tue, 26 Sep 2017 22:41:50 +0300https://eccc.weizmann.ac.il/report/2017/097#revision1
Paper TR17-097
| Multi Collision Resistant Hash Functions and their Applications |
Ron Rothblum,
Itay Berman,
Akshay Degwekar,
Prashant Nalini Vasudevan
https://eccc.weizmann.ac.il/report/2017/097Collision 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.Wed, 31 May 2017 21:30:37 +0300https://eccc.weizmann.ac.il/report/2017/097