{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,25]],"date-time":"2024-04-25T21:53:50Z","timestamp":1714082030858},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T00:00:00Z","timestamp":1694563200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T00:00:00Z","timestamp":1694563200000},"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":["comput. complex."],"published-print":{"date-parts":[[2023,12]]},"DOI":"10.1007\/s00037-023-00243-y","type":"journal-article","created":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T17:02:01Z","timestamp":1694624521000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Time-Space Tradeoffs for Bounded-Length Collisions in Merkle-Damg\u00e5rd Hashing"],"prefix":"10.1007","volume":"32","author":[{"given":"Ashrujit","family":"Ghoshal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilan","family":"Komargodski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,13]]},"reference":[{"key":"243_CR1","doi-asserted-by":"crossref","unstructured":"Hamza Abusalah, Jo\u00ebl Alwen, Bram Cohen, Danylo Khilko,\nKrzysztof Pietrzak & Leonid Reyzin (2017). Beyond Hellman\u2019s\nTime-Memory Trade-Offs with Applications to Proofs of Space. In Advances\nin Cryptology - ASIACRYPT, 357\u2013379.","DOI":"10.1007\/978-3-319-70697-9_13"},{"key":"243_CR2","doi-asserted-by":"crossref","unstructured":"Leonard Adleman (1978). Two theorems on random polynomial\ntime. In Symposium on Foundations of Computer Science, SFCS, 75\u2013\n83.","DOI":"10.1109\/SFCS.1978.37"},{"key":"243_CR3","doi-asserted-by":"crossref","unstructured":"Akshima, David Cash, Andrew Drucker & Hoeteck Wee (2020).\nTime-Space Tradeoffs and Short Collisions in Merkle-Damg\u00e5rd Hash\nFunctions. In Advances in Cryptology - CRYPTO, 157\u2013186.","DOI":"10.1007\/978-3-030-56784-2_6"},{"key":"243_CR4","doi-asserted-by":"crossref","unstructured":"Akshima, Siyao Guo & Qipeng Liu (2022). Time-Space Lower\nBounds for Finding Collisions in Merkle-Damg\u00e5rd Hash Functions. In\nAdvances in Cryptology - CRYPTO, 192\u2013221.","DOI":"10.1007\/978-3-031-15982-4_7"},{"key":"243_CR5","doi-asserted-by":"crossref","unstructured":"Elad Barkan, Eli Biham & Adi Shamir (2006). Rigorous Bounds\non Cryptanalytic Time\/Memory Tradeoffs. In Advances in Cryptology\n- CRYPTO, 1\u201321.","DOI":"10.1007\/11818175_1"},{"key":"243_CR6","doi-asserted-by":"crossref","unstructured":"Itay Berman, Akshay Degwekar, Ron D. Rothblum &\nPrashant Nalini Vasudevan (2018). Multi-Collision Resistant Hash\nFunctions and Their Applications. In Advances in Cryptology - EUROCRYPT,\n133\u2013161.","DOI":"10.1007\/978-3-319-78375-8_5"},{"key":"243_CR7","doi-asserted-by":"crossref","unstructured":"Nir Bitansky, Yael Tauman Kalai & Omer Paneth (2018). Multicollision\nresistance: a paradigm for keyless hash functions. In STOC,\n671\u2013684.","DOI":"10.1145\/3188745.3188870"},{"key":"243_CR8","doi-asserted-by":"crossref","unstructured":"Dror Chawin, Iftach Haitner & Noam Mazor (2020). Lower\nBounds on the Time\/Memory Tradeoff of Function Inversion. In Theory\nof Cryptography - TCC, 305\u2013334.","DOI":"10.1007\/978-3-030-64381-2_11"},{"key":"243_CR9","doi-asserted-by":"crossref","unstructured":"Kai-Min Chung, Siyao Guo, Qipeng Liu & Luowen Qian (2020).\nTight Quantum Time-Space Tradeoffs for Function Inversion. In FOCS,\n673\u2013684.","DOI":"10.1109\/FOCS46700.2020.00068"},{"key":"243_CR10","doi-asserted-by":"crossref","unstructured":"Sandro Coretti, Yevgeniy Dodis & Siyao Guo (2018a). Non-\nUniform Bounds in the Random-Permutation, Ideal-Cipher, and\nGeneric-Group Models. In Advances in Cryptology - CRYPTO, 693\u2013721.","DOI":"10.1007\/978-3-319-96884-1_23"},{"key":"243_CR11","doi-asserted-by":"crossref","unstructured":"Sandro Coretti, Yevgeniy Dodis, Siyao Guo & John P. Steinberger\n(2018b). Random Oracles and Non-uniformity. In Advances in\nCryptology - EUROCRYPT, 227\u2013258.","DOI":"10.1007\/978-3-319-78381-9_9"},{"key":"243_CR12","doi-asserted-by":"crossref","unstructured":"Henry Corrigan-Gibbs & Dmitry Kogan (2018). The Discrete-\nLogarithm Problem with Preprocessing. In Advances in Cryptology -\nEUROCRYPT, 415\u2013447.","DOI":"10.1007\/978-3-319-78375-8_14"},{"key":"243_CR13","doi-asserted-by":"crossref","unstructured":"Henry Corrigan-Gibbs & Dmitry Kogan (2019). The Function-\nInversion Problem: Barriers and Opportunities. In Theory of Cryptography\n- TCC, 393\u2013421.","DOI":"10.1007\/978-3-030-36030-6_16"},{"key":"243_CR14","doi-asserted-by":"crossref","unstructured":"Ivan Damg\u00e5rd (1987). Collision Free Hash Functions and Public Key\nSignature Schemes. In Advances in Cryptology - EUROCRYPT, 203\u2013\n216.","DOI":"10.1007\/3-540-39118-5_19"},{"key":"243_CR15","doi-asserted-by":"crossref","unstructured":"Anindya De, Luca Trevisan & Madhur Tulsiani (2010). Time\nSpace Tradeoffs for Attacks against One-Way Functions and PRGs. In\nAdvances in Cryptology - CRYPTO, 649\u2013665.","DOI":"10.1007\/978-3-642-14623-7_35"},{"key":"243_CR16","doi-asserted-by":"crossref","unstructured":"Itai Dinur (2020). Tight Time-Space Lower Bounds for Finding Multiple\nCollision Pairs and Their Applications. In Advances in Cryptology\n- EUROCRYPT, 405\u2013434.","DOI":"10.1007\/978-3-030-45721-1_15"},{"key":"243_CR17","doi-asserted-by":"crossref","unstructured":"Yevgeniy Dodis, Siyao Guo & Jonathan Katz (2017). Fixing\nCracks in the Concrete: Random Oracles with Auxiliary Input, Revisited.\nIn Advances in Cryptology - EUROCRYPT, 473\u2013495.","DOI":"10.1007\/978-3-319-56614-6_16"},{"key":"243_CR18","doi-asserted-by":"crossref","unstructured":"Amos Fiat & Moni Naor (1999). Rigorous Time\/Space Trade-offs\nfor Inverting Functions. SIAM J. Comput. 29(3), 790\u2013803.","DOI":"10.1137\/S0097539795280512"},{"key":"243_CR19","doi-asserted-by":"crossref","unstructured":"Cody Freitag, Ashrujit Ghoshal & Ilan Komargodski (2022).\nTime-Space Tradeoffs for Sponge Hashing: Attacks and Limitations for\nShort Collisions. In Advances in Cryptology - CRYPTO, 131\u2013160.","DOI":"10.1007\/978-3-031-15982-4_5"},{"key":"243_CR20","unstructured":"Rosario Gennaro & Luca Trevisan (2000). Lower Bounds on the\nEfficiency of Generic Cryptographic Constructions. In FOCS, 305\u2013313."},{"key":"243_CR21","doi-asserted-by":"crossref","unstructured":"Ashrujit Ghoshal & Stefano Tessaro (2020). On the Memory-\nTightness of Hashed ElGamal. In Advances in Cryptology - EUROCRYPT,\n33\u201362.","DOI":"10.1007\/978-3-030-45724-2_2"},{"key":"243_CR22","doi-asserted-by":"crossref","unstructured":"Martin E. Hellman (1980). A cryptanalytic time-memory trade-off.\nIEEE Trans. Inf. Theory 26(4), 401\u2013406.","DOI":"10.1109\/TIT.1980.1056220"},{"key":"243_CR23","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo & Valentine Kabanets (2010). Constructive\nproofs of concentration bounds. In Approximation, Randomization,\nand Combinatorial Optimization. Algorithms and Techniques, 617\u2013631.\nSpringer.","DOI":"10.1007\/978-3-642-15369-3_46"},{"key":"243_CR24","doi-asserted-by":"crossref","unstructured":"Antoine Joux (2004). Multicollisions in Iterated Hash Functions.\nApplication to Cascaded Constructions. In Advances in Cryptology -\nCRYPTO, 306\u2013316.","DOI":"10.1007\/978-3-540-28628-8_19"},{"key":"243_CR25","doi-asserted-by":"crossref","unstructured":"Ilan Komargodski, Moni Naor & Eylon Yogev (2018). Collision\nResistant Hashing for Paranoids: Dealing with Multiple Collisions. In\nAdvances in Cryptology - EUROCRYPT, 162\u2013194.","DOI":"10.1007\/978-3-319-78375-8_6"},{"key":"243_CR26","unstructured":"Ralph C. Merkle (1982). Secrecy, Authentication and Public Key\nSystems. Ph.D. thesis, UMI Research Press, Ann Arbor, Michigan."},{"key":"243_CR27","doi-asserted-by":"crossref","unstructured":"Ralph C. Merkle (1987). A Digital Signature Based on a Conventional\nEncryption Function. In Advances in Cryptology - CRYPTO,\n369\u2013378.","DOI":"10.1007\/3-540-48184-2_32"},{"key":"243_CR28","doi-asserted-by":"crossref","unstructured":"Ralph C. Merkle (1989). A Certified Digital Signature. In Advances\nin Cryptology - CRYPTO, 218\u2013238.","DOI":"10.1007\/0-387-34805-0_21"},{"key":"243_CR29","doi-asserted-by":"crossref","unstructured":"Robert H. Morris Sr. & Ken Thompson (1979). Password Security\n- A Case History. Commun. ACM 22(11), 594\u2013597.","DOI":"10.1145\/359168.359172"},{"key":"243_CR30","doi-asserted-by":"crossref","unstructured":"Robin A. Moser & G\u00e1bor Tardos (2010). A constructive proof of\nthe general lov\u00e1sz local lemma. J. ACM 57(2), 11:1\u201311:15.","DOI":"10.1145\/1667053.1667060"},{"key":"243_CR31","doi-asserted-by":"crossref","unstructured":"Philippe Oechslin (2003). Making a Faster Cryptanalytic Time-\nMemory Trade-Off. In Advances in Cryptology - CRYPTO, 617\u2013630.","DOI":"10.1007\/978-3-540-45146-4_36"},{"key":"243_CR32","doi-asserted-by":"crossref","unstructured":"Dominique Unruh (2007). Random Oracles and Auxiliary Input. In\nAdvances in Cryptology - CRYPTO, 205\u2013223.","DOI":"10.1007\/978-3-540-74143-5_12"},{"key":"243_CR33","unstructured":"Andrew Chi-Chih Yao (1990). Coherent Functions and Program\nCheckers (Extended Abstract). In STOC, 84\u201394."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00243-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-023-00243-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00243-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,26]],"date-time":"2023-12-26T19:04:13Z","timestamp":1703617453000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-023-00243-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,13]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["243"],"URL":"https:\/\/doi.org\/10.1007\/s00037-023-00243-y","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,13]]},"assertion":[{"value":"4 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 September 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"9"}}