Paper 2018/480

On Distributional Collision Resistant Hashing

Ilan Komargodski and Eylon Yogev

Abstract

Collision resistant hashing is a fundamental concept that is the basis for many of the important cryptographic primitives and protocols. Collision resistant hashing is a family of compressing functions such that no efficient adversary can find any collision given a random function in the family. In this work we study a relaxation of collision resistance called distributional collision resistance, introduced by Dubrov and Ishai (STOC '06). This relaxation of collision resistance only guarantees that no efficient adversary, given a random function in the family, can sample a pair $(x,y)$ where $x$ is uniformly random and $y$ is uniformly random conditioned on colliding with $x$. Our first result shows that distributional collision resistance can be based on the existence of multi-collision resistance hash (with no additional assumptions). Multi-collision resistance is another relaxation of collision resistance which guarantees that an efficient adversary cannot find any tuple of $k>2$ inputs that collide relative to a random function in the family. The construction is non-explicit, non-black-box, and yields an infinitely-often secure family. This partially resolves a question of Berman et al. (EUROCRYPT '18). We further observe that in a black-box model such an implication (from multi-collision resistance to distributional collision resistance) does not exist. Our second result is a construction of a distributional collision resistant hash from the average-case hardness of SZK. Previously, this assumption was not known to imply any form of collision resistance (other than the ones implied by one-way functions).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in CRYPTO 2018
Keywords
Collision Resistant HashingDistributional HashingMulti-Collision ResistanceStatistical Zero-KnowledgeNon-Black-Box Construction
Contact author(s)
komargodski @ cornell edu
eylon yogev @ weizmann ac il
History
2018-09-03: revised
2018-05-23: received
See all versions
Short URL
https://ia.cr/2018/480
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/480,
      author = {Ilan Komargodski and Eylon Yogev},
      title = {On Distributional Collision Resistant Hashing},
      howpublished = {Cryptology ePrint Archive, Paper 2018/480},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/480}},
      url = {https://eprint.iacr.org/2018/480}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.