Paper 2017/486

Collision Resistant Hashing for Paranoids: Dealing with Multiple Collisions

Ilan Komargodski, Moni Naor, and Eylon Yogev

Abstract

A collision resistant hash (CRH) function is one that compresses its input, yet it is hard to find a collision, i.e. a $x_1 \neq x_2$ s.t. $h(x_1) = h(x_2)$. Collision resistant hash functions are one of the more useful cryptographic primitives both in theory and in practice and two prominent applications are in signature schemes and succinct zero-knowledge arguments. In this work we consider a relaxation of the above requirement that we call Multi-CRH: a function where it is hard to find $x_1, x_2, \ldots, x_k$ which are all distinct, yet $ h(x_1) = h(x_2) = \cdots = h(x_k)$. We show that for some of the major applications of CRH functions it is possible to replace them by the weaker notion of an Multi-CRH, albeit at the price of adding interaction: we show a statistically hiding commitment schemes with succinct interaction (committing to $\mathsf{poly}(n)$ bits requires exchanging $O(n)$ bits) that can be opened locally (without revealing the full string). This in turn can be used to provide succinct arguments for any statement. On the other hand we show black-box separation results from standard CRH and a hierarchy of such Multi-CRHs.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
collision resistancemulti collisionscommitmentsshort commitmentsstatistically-hiding commitmentsuniversal one-way hashing
Contact author(s)
ilan komargodski @ weizmann ac il
History
2017-05-31: received
Short URL
https://ia.cr/2017/486
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/486,
      author = {Ilan Komargodski and Moni Naor and Eylon Yogev},
      title = {Collision Resistant Hashing for Paranoids: Dealing with Multiple Collisions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/486},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/486}},
      url = {https://eprint.iacr.org/2017/486}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.