{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:51:03Z","timestamp":1781077863482,"version":"3.54.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,3,6]],"date-time":"2024-03-06T00:00:00Z","timestamp":1709683200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,6]],"date-time":"2024-03-06T00:00:00Z","timestamp":1709683200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006260","name":"Technion - Israel Institute of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006260","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2024,4]]},"abstract":"Abstract<\/jats:title>Collision-resistant hash functions ($$\\textsf{CRH}$$<\/jats:tex-math>\n CRH<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>) are a fundamental and ubiquitous cryptographic primitive. Several recent works have studied a relaxation of $$\\textsf{CRH}$$<\/jats:tex-math>\n CRH<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> called t<\/jats:italic>-way multi-collision-resistant hash functions<\/jats:italic> ($$t\\text {-}\\textsf{MCRH}$$<\/jats:tex-math>\n \n t<\/mml:mi>\n -<\/mml:mtext>\n MCRH<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>). These are families of functions for which it is computationally hard to find a t<\/jats:italic>-way collision, even though such collisions are abundant (and even $$(t-1)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n t<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-way collisions may be easy to find). The case of $$t=2$$<\/jats:tex-math>\n \n t<\/mml:mi>\n =<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> corresponds to standard $$\\textsf{CRH}$$<\/jats:tex-math>\n CRH<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, but it is natural to study t<\/jats:italic>-$$\\textsf{MCRH}$$<\/jats:tex-math>\n MCRH<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for larger values of t<\/jats:italic>. Multi-collision resistance seems to be a qualitatively weaker property than standard collision resistance. Nevertheless, in this work we show a non-blackbox<\/jats:italic> transformation of any moderately shrinking t<\/jats:italic>-$$\\textsf{MCRH}$$<\/jats:tex-math>\n MCRH<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, for $$t \\in \\{3,4\\}$$<\/jats:tex-math>\n \n t<\/mml:mi>\n \u2208<\/mml:mo>\n {<\/mml:mo>\n 3<\/mml:mn>\n ,<\/mml:mo>\n 4<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, into an (infinitely often secure) $$\\textsf{CRH}$$<\/jats:tex-math>\n CRH<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This transformation is non-constructive\u2014we can prove the existence of a $$\\textsf{CRH}$$<\/jats:tex-math>\n CRH<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> but cannot explicitly point out a construction. Our result partially extends to larger values of t<\/jats:italic>. In particular, we show that for suitable values of $$t>t'$$<\/jats:tex-math>\n \n t<\/mml:mi>\n ><\/mml:mo>\n \n t<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we can transform a t<\/jats:italic>-$$\\textsf{MCRH}$$<\/jats:tex-math>\n MCRH<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> into a $$t'$$<\/jats:tex-math>\n \n t<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-$$\\textsf{MCRH}$$<\/jats:tex-math>\n MCRH<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, 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\u2013Solomon codes.<\/jats:p>","DOI":"10.1007\/s00145-024-09495-5","type":"journal-article","created":{"date-parts":[[2024,3,6]],"date-time":"2024-03-06T22:01:26Z","timestamp":1709762486000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Collision Resistance from Multi-collision Resistance"],"prefix":"10.1007","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5481-7276","authenticated-orcid":false,"given":"Ron D.","family":"Rothblum","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6880-795X","authenticated-orcid":false,"given":"Prashant Nalini","family":"Vasudevan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,3,6]]},"reference":[{"key":"9495_CR1","doi-asserted-by":"crossref","unstructured":"N. Bitansky, A. Degwekar, On the complexity of collision resistant hash functions: new and old black-box separations, in D. Hofheinz, A. Rosen, editors, Theory of Cryptography\u201417th International Conference, TCC 2019, Nuremberg, Germany, December 1\u20135, 2019, Proceedings, Part I. Lecture Notes in Computer Science, vol. 11891 (Springer, 2019), pp. 422\u2013450.","DOI":"10.1007\/978-3-030-36030-6_17"},{"key":"9495_CR2","doi-asserted-by":"crossref","unstructured":"I. Berman, A. Degwekar, R.D. Rothblum, P.N. Vasudevan, Multi-collision resistant hash functions and their applications, in J.B. Nielsen, V. Rijmen, editors, Advances in Cryptology-EUROCRYPT 2018-37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29-May 3, 2018 Proceedings, Part II. Lecture Notes in Computer Science, vol. 10821. (Springer, 2018), pp. 133\u2013161","DOI":"10.1007\/978-3-319-78375-8_5"},{"key":"9495_CR3","doi-asserted-by":"crossref","unstructured":"N. Bitansky, I. Haitner, I. Komargodski, E. Yogev, Distributional collision resistance beyond one-way functions, in: Y. Ishai, V. Rijmen, editors, Advances in Cryptology\u2014EUROCRYPT 2019\u201438th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part III. Lecture Notes in Computer Science, vol. 11478. (Springer, 2019), pp. 667\u2013695","DOI":"10.1007\/978-3-030-17659-4_23"},{"key":"9495_CR4","doi-asserted-by":"crossref","unstructured":"N. Bitansky, Y.T. Kalai, O. Paneth, Multi-collision resistance: A paradigm for keyless hash functions, in I. Diakonikolas, D. Kempe, M. Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25\u201329, 2018. (ACM, 2018), pp. 671\u2013684","DOI":"10.1145\/3188745.3188870"},{"key":"9495_CR5","doi-asserted-by":"crossref","unstructured":"N. Bitansky, V. Vaikuntanathan, A note on perfect correctness by derandomization, in J.-S. Coron, J.B. Nielsen, editors, Advances in Cryptology\u2014EUROCRYPT 2017\u201436th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30\u2013May 4, 2017, Proceedings, Part II. Lecture Notes in Computer Science, vol. 10211 (2017), pp. 592\u2013606","DOI":"10.1007\/978-3-319-56614-6_20"},{"key":"9495_CR6","unstructured":"Z. Dvir, D. Gutfreund, G.N. Rothblum, S.P. Vadhan, On approximating the entropy of polynomial mappings, in B. Chazelle, editor, Innovations in Computer Science\u2014ICS 2011, Tsinghua University, Beijing, China, January 7\u20139, 2011. Proceedings. (Tsinghua University Press, 2011), pp. 460\u2013475"},{"key":"9495_CR7","doi-asserted-by":"crossref","unstructured":"B. Dubrov, Y. Ishai, On the randomness complexity of efficient sampling, in J.M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21\u201323, 2006. (ACM, 2006), pp. 711\u2013720","DOI":"10.1145\/1132516.1132615"},{"issue":"6","key":"9495_CR8","doi-asserted-by":"publisher","first-page":"1513","DOI":"10.1137\/S0097539703426817","volume":"36","author":"Cynthia Dwork","year":"2007","unstructured":"C. Dwork, M. Naor, Zaps and their applications. SIAM J. Comput. 36(6), 1513\u20131543 (2007)","journal-title":"SIAM J. Comput."},{"key":"9495_CR9","doi-asserted-by":"crossref","unstructured":"C. Dwork, M. Naor, O. Reingold, Immunizing encryption schemes from decryption errors, in C. Cachin and J. Camenisch, editors, Advances in Cryptology\u2014EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2\u20136, 2004, Proceedings. Lecture Notes in Computer Science, vol. 3027. (Springer, 2004), pp. 342\u2013360","DOI":"10.1007\/978-3-540-24676-3_21"},{"key":"9495_CR10","doi-asserted-by":"crossref","unstructured":"O. Goldreich, The Foundations of Cryptography\u2014Volume 2: Basic Applications. (Cambridge University Press, 2004)","DOI":"10.1017\/CBO9780511721656"},{"issue":"4","key":"9495_CR11","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1137\/S0895480198344540","volume":"13","author":"Oded Goldreich","year":"2000","unstructured":"O. Goldreich, R. Rubinfeld, M. Sudan, Learning polynomials with queries: The highly noisy case. SIAM J. Discret. Math. 13(4), 535\u2013570 (2000)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"9495_CR12","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/130938438","volume":"44","author":"Iftach Haitner","year":"2015","unstructured":"I. Haitner, J.J. Hoch, O. Reingold, G. Segev, Finding collisions in interactive protocols: Tight lower bounds on the round and communication complexities of statistically hiding commitments. SIAM J. Comput. 44(1), 193\u2013242 (2015)","journal-title":"SIAM J. Comput."},{"key":"9495_CR13","doi-asserted-by":"crossref","unstructured":"J. Holmgren, A. Lombardi, Cryptographic hashing from strong one-way functions (or: One-way product functions and their applications), in M. Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7\u20139, 2018. (IEEE Computer Society, 2018), pp. 850\u2013858","DOI":"10.1109\/FOCS.2018.00085"},{"key":"9495_CR14","doi-asserted-by":"crossref","unstructured":"C.-Y. Hsiao, L. Reyzin, Finding collisions on a public road, or do secure hash functions need secret coins?, in M.K. Franklin, editor, Advances in Cryptology\u2014CRYPTO 2004, 24th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15\u201319, 2004, Proceedings. Lecture Notes in Computer Science, vol. 3152. (Springer, 2004), pp. 92\u2013105","DOI":"10.1007\/978-3-540-28628-8_6"},{"key":"9495_CR15","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, M. Luby, One-way functions are essential for complexity based cryptography (extended abstract), in 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October\u20131 November 1989. (IEEE Computer Society, 1989), pp. 230\u2013235","DOI":"10.1109\/SFCS.1989.63483"},{"key":"9495_CR16","doi-asserted-by":"crossref","unstructured":"A. Joux, Multicollisions in iterated hash functions: application to cascaded constructions, in M.K. Franklin, editor, Advances in Cryptology\u2014CRYPTO 2004, 24th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15\u201319, 2004, Proceedings. Lecture Notes in Computer Science, vol. 3152. (Springer, 2004), pp. 306\u2013316","DOI":"10.1007\/978-3-540-28628-8_19"},{"key":"9495_CR17","doi-asserted-by":"crossref","unstructured":"I. Komargodski, M. Naor, E. Yogev, White-box vs. black-box complexity of search problems: Ramsey and graph property testing, in C. Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15\u201317, 2017. (IEEE Computer Society, 2017), pp. 622\u2013632","DOI":"10.1109\/FOCS.2017.63"},{"key":"9495_CR18","doi-asserted-by":"crossref","unstructured":"I. Komargodski, M. Naor, E. Yogev, Collision resistant hashing for paranoids: dealing with multiple collisions, in J.B. Nielsen, V. Rijmen, editors, Advances in Cryptology-EUROCRYPT 2018-37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29-May 3, 2018 Proceedings, Part II. Lecture Notes in Computer Science, vol. 10821. (Springer, 2018), pp. 162\u2013194","DOI":"10.1007\/978-3-319-78375-8_6"},{"key":"9495_CR19","doi-asserted-by":"crossref","unstructured":"I. Komargodski, E. Yogev, On distributional collision resistant hashing, in H. Shacham, A. Boldyreva, editors, Advances in Cryptology\u2014CRYPTO 2018\u201438th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19\u201323, 2018, Proceedings, Part II. Lecture Notes in Computer Science, vol. 10992. (Springer, 2018), pp. 303\u2013327","DOI":"10.1007\/978-3-319-96881-0_11"},{"issue":"4","key":"9495_CR20","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","volume":"17","author":"Clemens Lautemann","year":"1983","unstructured":"C. Lautemann, BPP and the polynomial hierarchy. Inf. Process. Lett. 17(4), 215\u2013217 (1983)","journal-title":"Inf. Process. Lett."},{"key":"9495_CR21","doi-asserted-by":"crossref","unstructured":"M. Naor, Bit commitment using pseudo-randomness, in G. Brassard, editor, Advances in Cryptology\u2014CRYPTO \u201989, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20\u201324, 1989, Proceedings. Lecture Notes in Computer Science, vol. 435. (Springer, 1989), pp. 128\u2013136","DOI":"10.1007\/0-387-34805-0_13"},{"issue":"2","key":"9495_CR22","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1109\/TIT.2006.889721","volume":"53","author":"Mridul Nandi","year":"2007","unstructured":"M. Nandi, D.R. Stinson, Multicollision attacks on some generalized sequential hash functions. IEEE Trans. Inf. Theory. 53(2), 759\u2013767 (2007)","journal-title":"IEEE Trans. Inf. Theory."},{"key":"9495_CR23","unstructured":"Personal communication with the authors of [18]"},{"key":"9495_CR24","doi-asserted-by":"crossref","unstructured":"V. Shoup, New algorithms for finding irreducible polynomials over finite fields, in 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988, pp. 283\u2013290 (1988)","DOI":"10.1109\/SFCS.1988.21944"},{"key":"9495_CR25","doi-asserted-by":"crossref","unstructured":"D.R. Simon, Finding collisions on a one-way street: Can secure hash functions be based on general assumptions?, in K. Nyberg, editor, Advances in Cryptology\u2014EUROCRYPT \u201998, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31\u2013June 4, 1998, Proceeding. Lecture Notes in Computer Science, vol. 1403. (Springer, 1998), pp. 334\u2013345","DOI":"10.1007\/BFb0054137"},{"issue":"1","key":"9495_CR26","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/jcom.1997.0439","volume":"13","author":"Madhu Sudan","year":"1997","unstructured":"M. Sudan, Decoding of Reed Solomon codes beyond the error-correction bound. J. Complex., 13(1), 180\u2013193 (1997)","journal-title":"J. Complex."},{"key":"9495_CR27","doi-asserted-by":"crossref","unstructured":"H. Yu, X. Wang, Multi-collision attack on the compression functions of MD4 and 3-pass HAVAL, in K.-H. Nam, G. Rhee, editors, Information Security and Cryptology - ICISC 2007, 10th International Conference, Seoul, Korea, November 29\u201330, 2007, Proceedings. Lecture Notes in Computer Science, vol. 4817. (Springer, 2007), pp. 206\u2013226","DOI":"10.1007\/978-3-540-76788-6_17"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-024-09495-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-024-09495-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-024-09495-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,25]],"date-time":"2024-04-25T21:02:21Z","timestamp":1714078941000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-024-09495-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,6]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["9495"],"URL":"https:\/\/doi.org\/10.1007\/s00145-024-09495-5","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,6]]},"assertion":[{"value":"23 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 January 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 January 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 March 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"14"}}