{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T20:15:50Z","timestamp":1770840950459,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T00:00:00Z","timestamp":1764892800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T00:00:00Z","timestamp":1764892800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003483","name":"Hebrew University of Jerusalem","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003483","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2026,1]]},"abstract":"Abstract<\/jats:title>\n \n Sponge hashing is a novel alternative to the popular Merkle-Damg\u00e5rd hashing design. The sponge construction has become increasingly popular in various applications, perhaps most notably, it underlies the SHA-3 hashing standard. Sponge hashing is parametrized by two numbers,\n r<\/jats:italic>\n and\n c<\/jats:italic>\n (bitrate and capacity, respectively), and by a fixed-size permutation on\n \n \n $$r+c$$<\/jats:tex-math>\n \n \n r<\/mml:mi>\n +<\/mml:mo>\n c<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n bits. In this work, we study the collision resistance of sponge hashing instantiated with a random permutation by adversaries with arbitrary\n S<\/jats:italic>\n -bit auxiliary advice input about the random permutation that make\n T<\/jats:italic>\n online queries. Recent work by Coretti et al. (CRYPTO\u00a0\u201918) showed that such adversaries can find collisions (with respect to a random\n c<\/jats:italic>\n -bit initialization vector) with advantage\n \n \n $$\\Theta (ST^2\/2^c + T^2\/ 2^{r})$$<\/jats:tex-math>\n \n \n \u0398<\/mml:mi>\n (<\/mml:mo>\n S<\/mml:mi>\n \n T<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \/<\/mml:mo>\n \n 2<\/mml:mn>\n c<\/mml:mi>\n <\/mml:msup>\n +<\/mml:mo>\n \n T<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \/<\/mml:mo>\n \n 2<\/mml:mn>\n r<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Although the above attack formally breaks collision resistance in some range of parameters, its practical relevance is limited since the resulting collision is very long (on the order of\n T<\/jats:italic>\n blocks). Focusing on the task of finding\n short<\/jats:italic>\n collisions, we study the complexity of finding a\n B<\/jats:italic>\n -block collision for a given parameter\n \n \n $$B\\ge 1$$<\/jats:tex-math>\n \n \n B<\/mml:mi>\n \u2265<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . We give several new attacks and limitations. Most notably, we give a new attack that results in a single-block collision and has advantage\n \n \n $$\\begin{aligned} \\Omega \\left( \\left( \\frac{S^{2}T}{2^{2c}}\\right) ^{2\/3} + \\frac{T^2}{2^r}\\right) . \\end{aligned}$$<\/jats:tex-math>\n \n \n \n \n \n \n \u03a9<\/mml:mi>\n \n \n \n \n \n \n S<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n T<\/mml:mi>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n \n 2<\/mml:mn>\n c<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mfrac>\n <\/mml:mfenced>\n \n 2<\/mml:mn>\n \/<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n +<\/mml:mo>\n \n \n T<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n 2<\/mml:mn>\n r<\/mml:mi>\n <\/mml:msup>\n <\/mml:mfrac>\n <\/mml:mfenced>\n .<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:disp-formula>\n In certain range of parameters (e.g.,\n \n \n $$ST^2>2^c$$<\/jats:tex-math>\n \n \n S<\/mml:mi>\n \n T<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n ><\/mml:mo>\n \n 2<\/mml:mn>\n c<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ), our attack outperforms the previously-known best attack. To the best of our knowledge, this is the first natural application for which sponge hashing is\n provably less secure<\/jats:italic>\n than the corresponding instance of Merkle-Damg\u00e5rd hashing. Our attack relies on a novel connection between single-block collision finding in sponge hashing and the well-studied function inversion problem. We also give a general attack that works for any\n \n \n $$B\\ge 2$$<\/jats:tex-math>\n \n \n B<\/mml:mi>\n \u2265<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and has advantage\n \n \n $$\\Omega ({STB}\/{2^{c}} + {T^2}\/{2^{\\min \\{r,c\\}}})$$<\/jats:tex-math>\n \n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n \n STB<\/mml:mi>\n <\/mml:mrow>\n \/<\/mml:mo>\n \n 2<\/mml:mn>\n c<\/mml:mi>\n <\/mml:msup>\n +<\/mml:mo>\n \n T<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \/<\/mml:mo>\n \n 2<\/mml:mn>\n \n min<\/mml:mo>\n {<\/mml:mo>\n r<\/mml:mi>\n ,<\/mml:mo>\n c<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , adapting an idea of Akshima et al. (CRYPTO\u00a0\u201920). We complement the above attacks with bounds on the best possible attacks. Specifically, we prove that there is a qualitative jump in the advantage of best possible attacks for finding unbounded-length collisions and those for finding very short collisions. Most notably, we prove (via a highly non-trivial compression argument) that the above attack is optimal for\n \n \n $$B=2$$<\/jats:tex-math>\n \n \n B<\/mml:mi>\n =<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n in some range of parameters.\n <\/jats:p>","DOI":"10.1007\/s00145-025-09558-1","type":"journal-article","created":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T22:25:22Z","timestamp":1764973522000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Time-Space Tradeoffs for Sponge Hashing: Attacks and Limitations for Short Collisions"],"prefix":"10.1007","volume":"39","author":[{"given":"Cody","family":"Freitag","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashrujit","family":"Ghoshal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilan","family":"Komargodski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"9558_CR1","doi-asserted-by":"crossref","unstructured":"H. Abusalah, J. Alwen, B. Cohen, D. Khilko, K. Pietrzak, L. Reyzin. Beyond Hellman\u2019s time-memory trade-offs with applications to proofs of space. In Advances in Cryptology - ASIACRYPT, pages 357\u2013379, (2017).","DOI":"10.1007\/978-3-319-70697-9_13"},{"key":"9558_CR2","doi-asserted-by":"crossref","unstructured":"T. B. Akshima, S. Guo, Z. Xie, Y. Ye. Tight time-space tradeoffs for the decisional diffie-hellman problem. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1739\u20131749, 2024.","DOI":"10.1145\/3618260.3649752"},{"key":"9558_CR3","doi-asserted-by":"crossref","unstructured":"Akshima, D.C., A. Drucker, H. Wee. Time-space tradeoffs and short collisions in Merkle-Damg\u00e5rd hash functions. In Advances in Cryptology - CRYPTO, pages 157\u2013186, 2020.","DOI":"10.1007\/978-3-030-56784-2_6"},{"key":"9558_CR4","doi-asserted-by":"crossref","unstructured":"X.D. Akshima, S. Guo, Q. Liu. On time-space lower bounds for finding short collisions in sponge hash functions. In Theory of Cryptography Conference, pages 237\u2013270. Springer, 2023.","DOI":"10.1007\/978-3-031-48621-0_9"},{"key":"9558_CR5","doi-asserted-by":"crossref","unstructured":"Adleman, L. Two theorems on random polynomial time. In 19th Annual Symposium on Foundations of Computer Science (sfcs 1978), pages 75\u201383, 1978.","DOI":"10.1109\/SFCS.1978.37"},{"key":"9558_CR6","doi-asserted-by":"crossref","unstructured":"Akshima, S.G., and Q. Liu. Time-space lower bounds for finding collisions in Merkle-Damg\u00e5rd hash functions. In Advances in Cryptology - CRYPTO, pages 192\u2013221, 2022.","DOI":"10.1007\/978-3-031-15982-4_7"},{"key":"9558_CR7","doi-asserted-by":"crossref","unstructured":"E. Barkan, E. Biham, A. Shamir. Rigorous bounds on cryptanalytic time\/memory tradeoffs. In Advances in Cryptology - CRYPTO, pages 1\u201321, 2006.","DOI":"10.1007\/11818175_1"},{"key":"9558_CR8","doi-asserted-by":"crossref","unstructured":"G. Bertoni, J. Daemen, M. Peeters, G.\u00a0Van Assche. On the indifferentiability of the sponge construction. In Advances in Cryptology - EUROCRYPT, pages 181\u2013197, 2008.","DOI":"10.1007\/978-3-540-78967-3_11"},{"key":"9558_CR9","unstructured":"G. Bertoni, J. Daemen, M. Peeters, G. Van\u00a0Assche. Sponge functions. In ECRYPT hash workshop, volume 2007. Citeseer, 2007."},{"key":"9558_CR10","unstructured":"G. Bertoni, J. Daemen, M. Peeters, G. Van\u00a0Assche. On the security of the keyed sponge construction. In Symmetric Key Encryption Workshop, volume 2011, 2011."},{"key":"9558_CR11","doi-asserted-by":"crossref","unstructured":"Bernstein, D.J., Lange, T.: Non-uniform cracks in the concrete: The power of free precomputation. In Advances in Cryptology - ASIACRYPT, pages 321\u2013340, (2013).","DOI":"10.1007\/978-3-642-42045-0_17"},{"key":"9558_CR12","doi-asserted-by":"crossref","unstructured":"Coretti, S., Dodis, Y., Guo, S.: Non-uniform bounds in the random-permutation, ideal-cipher, and generic-group models. In Advances in Cryptology - CRYPTO, pages 693\u2013721, (2018).","DOI":"10.1007\/978-3-319-96884-1_23"},{"key":"9558_CR13","doi-asserted-by":"crossref","unstructured":"S. Coretti, Y. Dodis, S. Guo, J.P. Steinberger. Random oracles and non-uniformity. In Advances in Cryptology - EUROCRYPT, pages 227\u2013258, (2018).","DOI":"10.1007\/978-3-319-78381-9_9"},{"key":"9558_CR14","doi-asserted-by":"crossref","unstructured":"H. Corrigan-Gibbs, D. Kogan. The discrete-logarithm problem with preprocessing. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 415\u2013447, 2018.","DOI":"10.1007\/978-3-319-78375-8_14"},{"key":"9558_CR15","doi-asserted-by":"crossref","unstructured":"K.-M. Chung, S. Guo, Q. Liu, L. Qian. Tight quantum time-space tradeoffs for function inversion. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 673\u2013684. IEEE, 2020.","DOI":"10.1109\/FOCS46700.2020.00068"},{"key":"9558_CR16","doi-asserted-by":"crossref","unstructured":"H. Corrigan-Gibbs, D. Kogan. The function-inversion problem: Barriers and opportunities. In Theory of Cryptography - TCC, pages 393\u2013421, 2019.","DOI":"10.1007\/978-3-030-36030-6_16"},{"key":"9558_CR17","doi-asserted-by":"crossref","unstructured":"I. Damg\u00e5rd. Collision free hash functions and public key signature schemes. In Advances in Cryptology - EUROCRYPT, pages 203\u2013216, 1987.","DOI":"10.1007\/3-540-39118-5_19"},{"key":"9558_CR18","doi-asserted-by":"crossref","unstructured":"Y. Dodis, S. Guo, J. Katz. Fixing cracks in the concrete: Random oracles with auxiliary input, revisited. In Advances in Cryptology - EUROCRYPT, pages 473\u2013495, 2017.","DOI":"10.1007\/978-3-319-56614-6_16"},{"key":"9558_CR19","doi-asserted-by":"crossref","unstructured":"A. De, L. Trevisan, M. Tulsiani. Time space tradeoffs for attacks against one-way functions and PRGs. In Advances in Cryptology - CRYPTO, pages 157\u2013186, 2010.","DOI":"10.1007\/978-3-642-14623-7_35"},{"key":"9558_CR20","doi-asserted-by":"crossref","unstructured":"P.-A. Fouque, A. Joux,C. Mavromati. Multi-user collisions: Applications to discrete logarithm, even-mansour and PRINCE. In Advances in Cryptology - ASIACRYPT, pages 420\u2013438, 2014.","DOI":"10.1007\/978-3-662-45611-8_22"},{"issue":"3","key":"9558_CR21","doi-asserted-by":"publisher","first-page":"790","DOI":"10.1137\/S0097539795280512","volume":"29","author":"Amos Fiat","year":"1999","unstructured":"Amos Fiat and Moni Naor. Rigorous time\/space trade-offs for inverting functions. SIAM J. Comput., 29(3):790\u2013803, 1999.","journal-title":"SIAM J. Comput."},{"key":"9558_CR22","doi-asserted-by":"crossref","unstructured":"A. Golovnev, S. Guo, T. Horel, S. Park, V. Vaikuntanathan. Data structures meet cryptography: 3SUM with preprocessing. In 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 294\u2013307, 2020.","DOI":"10.1145\/3357713.3384342"},{"key":"9558_CR23","doi-asserted-by":"crossref","unstructured":"A. Ghoshal, I. Komargodski. On time-space tradeoffs for bounded-length collisions in Merkle-Damg\u00e5rd hashing. In Advances in Cryptology - CRYPTO, pages 161\u2013191, 2022.","DOI":"10.1007\/978-3-031-15982-4_6"},{"key":"9558_CR24","doi-asserted-by":"crossref","unstructured":"R. Gennaro, L. Trevisan. Lower bounds on the efficiency of generic cryptographic constructions. In 41st Annual Symposium on Foundations of Computer Science, FOCS, pages 305\u2013313. IEEE Computer Society, 2000.","DOI":"10.1109\/SFCS.2000.892119"},{"key":"9558_CR25","doi-asserted-by":"crossref","unstructured":"P. Gazi, S. Tessaro. Provably robust sponge-based PRNGs and KDFs. In Advances in Cryptology - EUROCRYPT, pages 87\u2013116, 2016.","DOI":"10.1007\/978-3-662-49890-3_4"},{"issue":"4","key":"9558_CR26","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1109\/TIT.1980.1056220","volume":"26","author":"Martin E Hellman","year":"1980","unstructured":"Martin\u00a0E. Hellman. A cryptanalytic time-memory trade-off. IEEE Trans. Inf. Theory, 26(4):401\u2013406, 1980.","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9558_CR27","unstructured":"R.C. Merkle. Secrecy, Authentication and Public Key Systems. PhD thesis, UMI Research Press, Ann Arbor, Michigan, 1982."},{"key":"9558_CR28","doi-asserted-by":"crossref","unstructured":"R.C. Merkle. A digital signature based on a conventional encryption function. In Advances in Cryptology - CRYPTO, pages 369\u2013378, 1987.","DOI":"10.1007\/3-540-48184-2_32"},{"key":"9558_CR29","doi-asserted-by":"crossref","unstructured":"R.C. Merkle. A certified digital signature. In Advances in Cryptology - CRYPTO, pages 218\u2013238, 1989.","DOI":"10.1007\/0-387-34805-0_21"},{"key":"9558_CR30","volume-title":"An analysis of algorithms for solving discrete logarithms in fixed groups","author":"Joseph Mihalcik","year":"2010","unstructured":"Joseph Mihalcik. An analysis of algorithms for solving discrete logarithms in fixed groups. Technical report, Naval Postgraduate School Monterey CA, 2010."},{"key":"9558_CR31","doi-asserted-by":"crossref","unstructured":"P. Morin, Wolfgang Mulzer, and Tommy Reddad. Encoding arguments. ACM Comput. Surv., 50(3):46:1\u201346:36, 2017.","DOI":"10.1145\/3084288"},{"key":"9558_CR32","doi-asserted-by":"crossref","unstructured":"P. Oechslin. Making a faster cryptanalytic time-memory trade-off. In Advances in Cryptology - CRYPTO, pages 617\u2013630, 2003.","DOI":"10.1007\/978-3-540-45146-4_36"},{"key":"9558_CR33","doi-asserted-by":"crossref","unstructured":"R.H.\u00a0Morris Sr. , K. Thompson. Password security - A case history. Commun. ACM, 22(11):594\u2013597, 1979.","DOI":"10.1145\/359168.359172"},{"key":"9558_CR34","doi-asserted-by":"crossref","unstructured":"D. Unruh. Random oracles and auxiliary input. In Advances in Cryptology - CRYPTO, pages 205\u2013223, 2007.","DOI":"10.1007\/978-3-540-74143-5_12"},{"key":"9558_CR35","doi-asserted-by":"crossref","unstructured":"H. Wee. On obfuscating point functions. In 37th Annual ACM Symposium on Theory of Computing, STOC, pages 523\u2013532, 2005.","DOI":"10.1145\/1060590.1060669"},{"key":"9558_CR36","doi-asserted-by":"crossref","unstructured":"A.\u00a0C.-C. Yao. Coherent functions and program checkers (extended abstract). In STOC, pages 84\u201394, 1990.","DOI":"10.1145\/100216.100226"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-025-09558-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-025-09558-1","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-025-09558-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T20:00:10Z","timestamp":1770840010000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-025-09558-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,5]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["9558"],"URL":"https:\/\/doi.org\/10.1007\/s00145-025-09558-1","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,5]]},"assertion":[{"value":"23 January 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 September 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 December 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"9"}}