EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Collision Resistance from Multi-collision Resistance

Ron D. Rothblum, Prashant Nalini Vasudevan

Journal of Cryptology · 2024-04 · 37 (2)

DOI: 10.1007/s00145-024-09495-5 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Cryptology, online erschienen am 06.03.2024. Verfasst von Ron D. Rothblum und 1 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 27 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Technion - Israel Institute of Technology.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Collision-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.

Förderung

  • Technion - Israel Institute of Technology

Zitieren

APA

Rothblum, R. D., & Vasudevan, P. N. (2024). Collision Resistance from Multi-collision Resistance. Journal of Cryptology, 37(2). https://doi.org/10.1007/s00145-024-09495-5

Vancouver

Rothblum RD, Vasudevan PN. Collision Resistance from Multi-collision Resistance. Journal of Cryptology. 2024;37(2). doi:10.1007/s00145-024-09495-5

BibTeX
@article{Rothblum2024,
  author = {Rothblum, Ron D. and Vasudevan, Prashant Nalini},
  title = {Collision Resistance from Multi-collision Resistance},
  journal = {Journal of Cryptology},
  year = {2024},
  volume = {37},
  number = {2},
  doi = {10.1007/s00145-024-09495-5}
}
Kostenlos starten →