Paper 2025/2049
Black-Box Separation Between Multi-Collision Resistance and Collision Resistance
, University of Southern California, University of Southern CaliforniaAbstract
A $K$-multi-collision-resistant hash function ($K$-MCRH) is a shrinking keyed function for which it is computationally infeasible to find $K$ distinct inputs that map to the same output under a randomly chosen hash key; the case $K = 2$ coincides with the standard definition of collision-resistant hash function (CRH). A natural question is whether $K$-MCRH implies CRH for $K \geq 3$, as noted by Komargodski, Naor, and Yogev (EUROCRYPT 2018) and also by Jain, Li, Robere, and Xun (FOCS 2024). We resolve this question for all constant $K$, showing that there is no black-box construction of $K$-MCRH from $(K + 1)$-MCRH for all constant $K \geq 2$. We also show that there is no black-box construction of distributional CRH (which is another relaxation of CRH) from 3-MCRH, answering an open question posed by Komargodski and Yogev (CRYPTO 2018) and also by Berman, Degwekar, Rothblum, and Vasudevan (EUROCRYPT 2018). Besides applications in cryptography, our separation also implies black-box separations between TFNP search problems, which are related to problems in proof complexity and other areas.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- collision resistanceblack-box separation
- Contact author(s)
-
xinyumao @ usc edu
jiapengz @ usc edu - History
- 2026-03-29: revised
- 2025-11-06: received
- See all versions
- Short URL
- https://ia.cr/2025/2049
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/2049,
author = {Xinyu Mao and Jiapeng Zhang},
title = {Black-Box Separation Between Multi-Collision Resistance and Collision Resistance},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/2049},
year = {2025},
url = {https://eprint.iacr.org/2025/2049}
}
