Welcome to the resource topic for 2017/486
Title:
Collision Resistant Hashing for Paranoids: Dealing with Multiple Collisions
Authors: Ilan Komargodski, Moni Naor, 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.
ePrint: https://eprint.iacr.org/2017/486
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .