International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Collision Resistance from Multi-collision Resistance

Authors:
Ron D. Rothblum
Prashant Nalini Vasudevan
Download:
DOI: 10.1007/s00145-024-09495-5
Search ePrint
Search Google
Abstract: AbstractCollision-resistant hash functions ($$\textsf{CRH}$$ CRH ) are a fundamental and ubiquitous cryptographic primitive. Several recent works have studied a relaxation of $$\textsf{CRH}$$ CRH called t-way multi-collision-resistant hash functions ($$t\text {-}\textsf{MCRH}$$ t - MCRH ). These are families of functions for which it is computationally hard to find a t-way collision, even though such collisions are abundant (and even $$(t-1)$$ ( t - 1 ) -way collisions may be easy to find). The case of $$t=2$$ t = 2 corresponds to standard $$\textsf{CRH}$$ CRH , but it is natural to study t-$$\textsf{MCRH}$$ MCRH for larger values of t. Multi-collision resistance seems to be a qualitatively weaker property than standard collision resistance. Nevertheless, in this work we show a non-blackbox transformation of any moderately shrinking t-$$\textsf{MCRH}$$ MCRH , for $$t \in \{3,4\}$$ t ∈ { 3 , 4 } , into an (infinitely often secure) $$\textsf{CRH}$$ CRH . This transformation is non-constructive—we can prove the existence of a $$\textsf{CRH}$$ CRH but cannot explicitly point out a construction. Our result partially extends to larger values of t. In particular, we show that for suitable values of $$t>t'$$ t > t ′ , we can transform a t-$$\textsf{MCRH}$$ MCRH into a $$t'$$ t ′ -$$\textsf{MCRH}$$ MCRH , at the cost of reducing the shrinkage of the resulting hash function family and settling for infinitely often security. This result utilizes the list-decodability properties of Reed–Solomon codes.
BibTeX
@article{jofc-2024-34417,
  title={Collision Resistance from Multi-collision Resistance},
  journal={Journal of Cryptology},
  publisher={Springer},
  volume={37},
  pages={14},
  doi={10.1007/s00145-024-09495-5},
  author={Ron D. Rothblum and Prashant Nalini Vasudevan},
  year=2024
}