{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T12:49:00Z","timestamp":1770900540504,"version":"3.50.1"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031486203","type":"print"},{"value":"9783031486210","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-48621-0_9","type":"book-chapter","created":{"date-parts":[[2023,11,26]],"date-time":"2023-11-26T18:02:21Z","timestamp":1701021741000},"page":"237-270","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On Time-Space Lower Bounds for\u00a0Finding Short Collisions in\u00a0Sponge Hash Functions"],"prefix":"10.1007","author":[{"family":"Akshima","sequence":"first","affiliation":[]},{"given":"Xiaoqi","family":"Duan","sequence":"additional","affiliation":[]},{"given":"Siyao","family":"Guo","sequence":"additional","affiliation":[]},{"given":"Qipeng","family":"Liu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,11,27]]},"reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/978-3-030-56784-2_6","volume-title":"Advances in Cryptology - CRYPTO 2020","author":"CD Akshima","year":"2020","unstructured":"Akshima, C.D., Drucker, A., Wee, H.: Time-space tradeoffs and short collisions in merkle-damg\u00e5rd hash functions. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12170, pp. 157\u2013186. Springer, Heidelberg (2020). https:\/\/doi.org\/10.1007\/978-3-030-56784-2_6"},{"key":"9_CR2","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/978-3-031-15982-4_7","volume-title":"Advances in Cryptology - CRYPTO 2022","author":"GS Akshima","year":"2022","unstructured":"Akshima, G.S., Liu, Q.: Time-space lower bounds for finding collisions in merkle-damg\u00e5rd hash functions. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13509, pp. 192\u2013221. Springer, Heidelberg (2022). https:\/\/doi.org\/10.1007\/978-3-031-15982-4_7"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: On the indifferentiability of the sponge construction. In: ECRYPT Hash Workshop, vol. 2007. Citeseer (2007)","DOI":"10.1007\/978-3-540-78967-3_11"},{"key":"9_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/978-3-540-78967-3_11","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2008","author":"G Bertoni","year":"2008","unstructured":"Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: On the indifferentiability of the sponge construction. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 181\u2013197. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78967-3_11"},{"key":"9_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/978-3-319-96884-1_23","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"S Coretti","year":"2018","unstructured":"Coretti, S., Dodis, Y., Guo, S.: Non-uniform bounds in the random-permutation, ideal-cipher, and generic-group models. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 693\u2013721. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96884-1_23"},{"key":"9_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/978-3-319-78381-9_9","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"S Coretti","year":"2018","unstructured":"Coretti, S., Dodis, Y., Guo, S., Steinberger, J.: Random oracles and non-uniformity. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 227\u2013258. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78381-9_9"},{"key":"9_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/978-3-319-78375-8_14","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"H Corrigan-Gibbs","year":"2018","unstructured":"Corrigan-Gibbs, H., Kogan, D.: The discrete-logarithm problem with\u00a0preprocessing. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 415\u2013447. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78375-8_14"},{"key":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/978-3-030-36030-6_16","volume-title":"Theory of Cryptography","author":"H Corrigan-Gibbs","year":"2019","unstructured":"Corrigan-Gibbs, H., Kogan, D.: The function-inversion problem: barriers and opportunities. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019. LNCS, vol. 11891, pp. 393\u2013421. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-36030-6_16"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Chung, K.M., Guo, S., Liu, Q., Qian, L.: Tight quantum time-space tradeoffs for function inversion. In: Irani, S. (ed.) 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, 16\u201319 November 2020, pp. 673\u2013684. IEEE (2020)","DOI":"10.1109\/FOCS46700.2020.00068"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Chawin, D., Haitner, I., Mazor, N.: Lower bounds on the time\/memory tradeoff of function inversion. In: Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, USA, 16\u201319 November 2020, Proceedings, Part III, pp. 305\u2013334 (2020)","DOI":"10.1007\/978-3-030-64381-2_11"},{"key":"9_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/0-387-34805-0_39","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 89 Proceedings","author":"IB Damg\u00e5rd","year":"1990","unstructured":"Damg\u00e5rd, I.B.: A design principle for hash functions. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 416\u2013427. Springer, New York (1990). https:\/\/doi.org\/10.1007\/0-387-34805-0_39"},{"key":"9_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/978-3-319-56614-6_16","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"Y Dodis","year":"2017","unstructured":"Dodis, Y., Guo, S., Katz, J.: Fixing cracks in the concrete: random oracles with auxiliary input, revisited. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 473\u2013495. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56614-6_16"},{"key":"9_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1007\/978-3-642-14623-7_35","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"A De","year":"2010","unstructured":"De, A., Trevisan, L., Tulsiani, M.: Time space tradeoffs for attacks against one-way functions and PRGs. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 649\u2013665. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14623-7_35"},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/978-3-031-15982-4_5","volume-title":"Advances in Cryptology - CRYPTO 2022","author":"C Freitag","year":"2022","unstructured":"Freitag, C., Ghoshal, A., Komargodski, I.: Time-space tradeoffs for sponge hashing: attacks and limitations for short collisions. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13509, pp. 131\u2013160. Springer, Heidelberg (2022). https:\/\/doi.org\/10.1007\/978-3-031-15982-4_5"},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1007\/978-3-031-30634-1_15","volume-title":"Advances in Cryptology - EUROCRYPT 2023","author":"C Freitag","year":"2023","unstructured":"Freitag, C., Ghoshal, A., Komargodski, I.: Optimal security for keyed hash functions: avoiding time-space tradeoffs for finding collisions. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023. LNCS, vol. 14007, pp. 440\u2013469. Springer, Heidelberg (2023). https:\/\/doi.org\/10.1007\/978-3-031-30634-1_15"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Gravin, N., Guo, S., Kwok, T.C., Lu, P.: Concentration bounds for almost k-wise independence with applications to non-uniform security. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, 10\u201313 January 2021, pp. 2404\u20132423 (2021)","DOI":"10.1137\/1.9781611976465.143"},{"key":"9_CR17","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/978-3-031-38545-2_15","volume-title":"Advances in Cryptology - CRYPTO 2023","author":"A Golovnev","year":"2023","unstructured":"Golovnev, A., Guo, S., Peters, S., Stephens-Davidowitz, N.: Revisiting time-space tradeoffs for function inversion. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, vol. 14082, pp. 453\u2013481. Springer, Heidelberg (2023). https:\/\/doi.org\/10.1007\/978-3-031-38545-2_15"},{"key":"9_CR18","first-page":"161","volume-title":"Advances in Cryptology - CRYPTO 202","author":"A Ghoshal","year":"2022","unstructured":"Ghoshal, A., Komargodski, I.: On time-space tradeoffs for bounded-length collisions in merkle-damg\u00e5rd hashing. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 202. LNCS, vol. 13509, pp. 161\u2013191. Springer, Heidelberg (2022)"},{"key":"9_CR19","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1007\/978-3-031-38545-2_16","volume-title":"Advances in Cryptology - CRYPTO 2023","author":"A Ghoshal","year":"2023","unstructured":"Ghoshal, A., Tessaro, S.: The Query-Complexity of Preprocessing Attacks. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, vol. 14082, pp. 482\u2013513. Springer, Heidelberg (2023). https:\/\/doi.org\/10.1007\/978-3-031-38545-2_16"},{"issue":"4","key":"9_CR20","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1109\/TIT.1980.1056220","volume":"26","author":"M Hellman","year":"1980","unstructured":"Hellman, M.: A cryptanalytic time-memory trade-off. IEEE Trans. Inf. Theory 26(4), 401\u2013406 (1980)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1007\/978-3-642-15369-3_46","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"R Impagliazzo","year":"2010","unstructured":"Impagliazzo, R., Kabanets, V.: Constructive proofs of concentration bounds. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX\/RANDOM -2010. LNCS, vol. 6302, pp. 617\u2013631. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15369-3_46"},{"key":"9_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/0-387-34805-0_21","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 89 Proceedings","author":"RC Merkle","year":"1990","unstructured":"Merkle, R.C.: A certified digital signature. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 218\u2013238. Springer, New York (1990). https:\/\/doi.org\/10.1007\/0-387-34805-0_21"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-48621-0_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T01:03:03Z","timestamp":1764118983000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-48621-0_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031486203","9783031486210"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-48621-0_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"27 November 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Taipei","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Taiwan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 November 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 December 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcc.iacr.org\/2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}