{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihixuxb53uuuspffccwi5fcin4mnbe6ssxjn3ypvmrbrf6snj3hpy",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mis73mydnrq2"
  },
  "path": "/report/2026/046",
  "publishedAt": "2026-04-05T09:53:40.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "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.",
  "title": "TR26-046 |  Black-Box Separation Between Multi-Collision Resistance and Collision Resistance | \n\n\tXinyu Mao, \n\n\tJiapeng Zhang"
}