Welcome to the resource topic for 2024/380
Title:
Collision Resistance from Multi-Collision Resistance for all Constant Parameters
Authors: Jan Buzek, Stefano Tessaro
Abstract:A t-multi-collision-resistant hash function (t-MCRH) is a family of shrinking functions for which it is computationally hard to find t distinct inputs mapping to the same output for a function sampled from this family. Several works have shown that t-MCRHs are sufficient for many of the applications of collision-resistant hash functions (CRHs), which correspond to the special case of t = 2.
An important question is hence whether t-MCRHs for t > 2 are fundamentally weaker objects than CRHs. As a first step towards resolving this question, Rothblum and Vasudevan (CRYPTO '22) recently gave non-black-box constructions of infinitely-often secure CRHs from t-MCRHs for t \in \{3,4\} assuming the MCRH is sufficiently shrinking. Earlier on, Komargodski and Yogev (CRYPTO '18) also showed that t-MCRHs for any constant t imply the weaker notion of a distributional CRH.
In this paper, we remove the limitations of prior works, and completely resolve the question of the power of t-MCRHs for constant t in the infinitely-often regime, showing that the existence of such a function family always implies the existence of an infinitely-often secure CRH. As in the works mentioned above, our construction is non-blackbox and non-constructive. We further give a new domain extension result for MCRHs that enables us to show that the underlying MCRH need only have arbitrarily small linear shrinkage (mapping (1 + \epsilon)n bits to n bits for any fixed \epsilon > 0) to imply the existence of CRHs.
ePrint: https://eprint.iacr.org/2024/380
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 .