Summary: 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 a Multi-CRH, albeit at the price of adding interaction: we show a constant-round statistically-hiding commitment scheme with succinct interaction (committing to \(\mathsf{poly}(n)\) bits requires exchanging \(\tilde{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 \({\mathsf {NP}}\) statement.{ }We formulate four possible worlds of hashing-related assumptions (in the spirit of Impagliazzo’s worlds). They are (1) Nocrypt, where no one-way functions exist, (2) Unihash, where one-way functions exist, and hence also UOWHFs and signature schemes, but no Multi-CRH functions exist, (3) Minihash, where Multi-CRH functions exist but no CRH functions exist, and (4) Hashomania, where CRH functions exist. We show that these four worlds are distinct in a black-box model: we show a separation of CRH from Multi-CRH and a separation of Multi-CRH from one-way functions.
For the entire collection see [Zbl 1387.94007].