Black-Box Separation between Multi-Collision Resistance and Collision Resistance

Описание: Date: 2026-01-09
Speaker: Xinyu Mao (University of Southern California)
Abstract:
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 ≥ 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 ≥ 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 cryptography, our separation also implies black-box separations between TFNP search problems, which are related to problems in proof complexity and other areas.

This is joint work with Jiapeng Zhang. The paper is available at: https://ia.cr/2025/2049