{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T09:32:25Z","timestamp":1751275945992},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,2,13]],"date-time":"2024-02-13T00:00:00Z","timestamp":1707782400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,2,13]],"date-time":"2024-02-13T00:00:00Z","timestamp":1707782400000},"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":["J Cryptol"],"published-print":{"date-parts":[[2024,4]]},"DOI":"10.1007\/s00145-024-09491-9","type":"journal-article","created":{"date-parts":[[2024,2,13]],"date-time":"2024-02-13T22:02:23Z","timestamp":1707861743000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Time-Space Lower Bounds for Finding Collisions in Merkle\u2013Damg\u00e5rd Hash Functions"],"prefix":"10.1007","volume":"37","author":[{"family":"Akshima","sequence":"first","affiliation":[]},{"given":"Siyao","family":"Guo","sequence":"additional","affiliation":[]},{"given":"Qipeng","family":"Liu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,2,13]]},"reference":[{"key":"9491_CR1","doi-asserted-by":"crossref","unstructured":"D.C. Akshima, A. Drucker, H. Wee, Time-space tradeoffs and short collisions in Merkle\u2013Damg\u00e5rd hash functions, in D. Micciancio, T. Ristenpart (eds.) Advances in Cryptology - CRYPTO 2020, volume 12170 of Lecture Notes in Computer Science (Springer, 2020), pp. 157\u2013186","DOI":"10.1007\/978-3-030-56784-2_6"},{"key":"9491_CR2","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 IACR Cryptol. ePrint Arch., 2023, p. 1444","DOI":"10.1007\/978-3-031-48621-0_9"},{"key":"9491_CR3","doi-asserted-by":"crossref","unstructured":"M. Bellare, P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, in Proceedings of the 1st ACM Conference on Computer and Communications Security (1993), pp. 62\u201373","DOI":"10.1145\/168588.168596"},{"key":"9491_CR4","doi-asserted-by":"crossref","unstructured":"S. Coretti, Y. Dodis, S. Guo, Non-uniform bounds in the random-permutation, ideal-cipher, and generic-group models, in H. Shacham, A. Boldyreva (eds.) Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part I. Lecture Notes in Computer Science, vol. 10991 (Springer, 2018), pp. 693\u2013721","DOI":"10.1007\/978-3-319-96884-1_23"},{"key":"9491_CR5","doi-asserted-by":"crossref","unstructured":"S. Coretti, Y. Dodis, S. Guo, J.P. Steinberger, Random oracles and non-uniformity, in J.B. Nielsen, V. Rijmen (eds.) 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 I. Lecture Notes in Computer Science, vol. 10820 (Springer, 2018), pp. 227\u2013258","DOI":"10.1007\/978-3-319-78381-9_9"},{"key":"9491_CR6","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 (Springer, 2018), pp. 415\u2013447","DOI":"10.1007\/978-3-319-78375-8_14"},{"key":"9491_CR7","doi-asserted-by":"crossref","unstructured":"H. Corrigan-Gibbs, D. Kogan, The function-inversion problem: barriers and opportunities, in Theory of Cryptography Conference (Springer, 2019), pp. 393\u2013421","DOI":"10.1007\/978-3-030-36030-6_16"},{"key":"9491_CR8","doi-asserted-by":"crossref","unstructured":"K.-M. Chung, S. Guo, Q. Liu, L. Qian, Tight quantum time-space tradeoffs for function inversion, in S. Irani (ed.) 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020 (IEEE, 2020), pp. 673\u2013684","DOI":"10.1109\/FOCS46700.2020.00068"},{"key":"9491_CR9","doi-asserted-by":"crossref","unstructured":"D. Chawin, I. Haitner, N. Mazor, Lower bounds on the time\/memory tradeoff of function inversion, in Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part III (2020), pp. 305\u2013334","DOI":"10.1007\/978-3-030-64381-2_11"},{"key":"9491_CR10","doi-asserted-by":"crossref","unstructured":"I. Damg\u00e5rd, A design principle for hash functions, in Advances in Cryptology - CRYPTO \u201989, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings (1989), pp. 416\u2013427","DOI":"10.1007\/0-387-34805-0_39"},{"key":"9491_CR11","doi-asserted-by":"crossref","unstructured":"Y. Dodis, S. Guo, J. Katz, Fixing cracks in the concrete: random oracles with auxiliary input, revisited, in J.-S. Coron, J.B. Nielsen (eds.) Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part II. Lecture Notes in Computer Science, vol. 10211 (2017), pp. 473\u2013495","DOI":"10.1007\/978-3-319-56614-6_16"},{"key":"9491_CR12","doi-asserted-by":"crossref","unstructured":"A. De, L. Trevisan, M. Tulsiani, Time space tradeoffs for attacks against one-way functions and prgs, in Annual Cryptology Conference (Springer, 2010), pp. 649\u2013665","DOI":"10.1007\/978-3-642-14623-7_35"},{"key":"9491_CR13","doi-asserted-by":"crossref","unstructured":"C. Freitag, A. Ghoshal, I. Komargodski, Time-space tradeoffs for sponge hashing: attacks and limitations for short collisions, in Y. Dodis, T, Shrimpton (eds.) Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part III. Lecture Notes in Computer Science, vol. 13509 (Springer, 2022), pp. 131\u2013160","DOI":"10.1007\/978-3-031-15982-4_5"},{"key":"9491_CR14","doi-asserted-by":"crossref","unstructured":"C. Freitag, A. Ghoshal, I. Komargodski, Optimal security for keyed hash functions: avoiding time-space tradeoffs for finding collisions, in C. Hazay, M. Stam (eds.) Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part IV. Lecture Notes in Computer Science, vol. 14007 (Springer, 2023), pp. 440\u2013469","DOI":"10.1007\/978-3-031-30634-1_15"},{"key":"9491_CR15","doi-asserted-by":"crossref","unstructured":"N. Gravin, S. Guo, T.C. Kwok, P. Lu, 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, January 10 - 13, 2021 (2021), pp. 2404\u20132423","DOI":"10.1137\/1.9781611976465.143"},{"key":"9491_CR16","doi-asserted-by":"crossref","unstructured":"A. Golovnev, S. Guo, S. Peters, N. Stephens-Davidowitz, Revisiting time-space tradeoffs for function inversion, in H. Handschuh, A. Lysyanskaya (eds.) Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part II. Lecture Notes in Computer Science, vol. 14082 (Springer, 2023), pp. 453\u2013481","DOI":"10.1007\/978-3-031-38545-2_15"},{"key":"9491_CR17","doi-asserted-by":"crossref","unstructured":"A. Ghoshal, I. Komargodski, On time-space tradeoffs for bounded-length collisions in Merkle\u2013Damg\u00e5rd hashing, in Annual International Cryptology Conference (Springer, 2022)","DOI":"10.1007\/s00037-023-00243-y"},{"key":"9491_CR18","doi-asserted-by":"crossref","unstructured":"S. Guo, Q. Li, Q. Liu, J. Zhang, Unifying presampling via concentration bounds, in Theory of Cryptography - 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8-11, 2021, Proceedings, Part I (2021), pp. 177\u2013208","DOI":"10.1007\/978-3-030-90459-3_7"},{"key":"9491_CR19","doi-asserted-by":"crossref","unstructured":"A. Ghoshal, S. Tessaro, The query-complexity of preprocessing attacks, in H. Handschuh, A. Lysyanskaya (eds.) Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part II. Lecture Notes in Computer Science, vol. 14082 (Springer, 2023), pp. 482\u2013513","DOI":"10.1007\/978-3-031-38545-2_16"},{"key":"9491_CR20","doi-asserted-by":"crossref","unstructured":"M.E. Hellman, A cryptanalytic time-memory trade-off. IEEE Trans. Inf. Theory, 26(4), 401\u2013406 (1980)","DOI":"10.1109\/TIT.1980.1056220"},{"key":"9491_CR21","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, V. Kabanets, Constructive proofs of concentration bounds, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings (2010), pp. 617\u2013631","DOI":"10.1007\/978-3-642-15369-3_46"},{"key":"9491_CR22","doi-asserted-by":"crossref","unstructured":"R.C. Merkle, A certified digital signature, in Advances in Cryptology - CRYPTO \u201989, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings (1989), pp. 218\u2013238","DOI":"10.1007\/0-387-34805-0_21"},{"key":"9491_CR23","doi-asserted-by":"crossref","unstructured":"D. Unruh, Random oracles and auxiliary input, in A. Menezes (ed.) Advances in Cryptology - CRYPTO 2007, 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007, Proceedings. Lecture Notes in Computer Science, vol. 4622 (Springer 2007), pp. 205\u2013223","DOI":"10.1007\/978-3-540-74143-5_12"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-024-09491-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-024-09491-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-024-09491-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,25]],"date-time":"2024-04-25T21:02:31Z","timestamp":1714078951000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-024-09491-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,13]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["9491"],"URL":"https:\/\/doi.org\/10.1007\/s00145-024-09491-9","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,13]]},"assertion":[{"value":"5 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 November 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"10"}}