{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T17:05:01Z","timestamp":1753895101291,"version":"3.41.2"},"reference-count":29,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T00:00:00Z","timestamp":1720396800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,9,2]]},"abstract":"<jats:p>  The collision-resistant hash function is an early cryptographic primitive that finds extensive use in various applications. Remarkably, the Merkle-Damg\u00e5rd and Merkle tree hash structures possess the collision-resistance preserving property, meaning the hash function remains collision-resistant when the underlying compression function is collision-resistant. This raises the intriguing question of whether reducing the number of underlying compression function calls with the collision-resistance preserving property is possible. In pursuit of addressing these inquiries, we prove that for an <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mrow>\n                  <mml:mi>\u2113<\/mml:mi>\n                <\/mml:mrow>\n                <mml:mi>n<\/mml:mi>\n              <\/mml:mrow>\n            <\/mml:math>-to-<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>s<\/mml:mi>\n                <mml:mi>n<\/mml:mi>\n              <\/mml:mrow>\n            <\/mml:math>-bit collision-resistance preserving hash function designed using <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>r<\/mml:mi>\n              <\/mml:mrow>\n            <\/mml:math>\n            <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>t<\/mml:mi>\n                <mml:mi>n<\/mml:mi>\n              <\/mml:mrow>\n            <\/mml:math>-to-<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>n<\/mml:mi>\n              <\/mml:mrow>\n            <\/mml:math>-bit compression function calls, we must have <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>r<\/mml:mi>\n                <mml:mo>\u2265<\/mml:mo>\n                <mml:mi>\u2308<\/mml:mi>\n                <mml:mo stretchy=\"false\">(<\/mml:mo>\n                <mml:mi>\u2113<\/mml:mi>\n                <mml:mo>\u2212<\/mml:mo>\n                <mml:mi>s<\/mml:mi>\n                <mml:mo stretchy=\"false\">)<\/mml:mo>\n                <mml:mo>\/<\/mml:mo>\n                <mml:mo stretchy=\"false\">(<\/mml:mo>\n                <mml:mi>t<\/mml:mi>\n                <mml:mo>\u2212<\/mml:mo>\n                <mml:mn>1<\/mml:mn>\n                <mml:mo stretchy=\"false\">)<\/mml:mo>\n                <mml:mi>\u2309<\/mml:mi>\n              <\/mml:mrow>\n            <\/mml:math>. Throughout the paper, all operations other than the compression function are assumed to be linear (which we call linear hash mode). <\/jats:p>","DOI":"10.62056\/akgy11zn4","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T15:13:33Z","timestamp":1728314013000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Lower Bound on Number of Compression Calls of a Collision-Resistance Preserving Hash"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7240-5304","authenticated-orcid":false,"given":"Debasmita","family":"Chakraborty","sequence":"first","affiliation":[{"name":"Indian Statistical Institute","place":["Kolkata, 700108, India"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1029-6576","authenticated-orcid":false,"given":"Mridul","family":"Nandi","sequence":"additional","affiliation":[{"name":"Indian Statistical Institute","place":["Kolkata, 700108, India"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"article-title":"Sponge functions","year":"2007","author":"Guido Bertoni","key":"ref1:bertoni2007sponge"},{"key":"ref2:DBLP:conf\/crypto\/BierbrauerJKS93","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/3-540-48329-2_28","article-title":"On Families of Hash Functions via Geometric Codes and\n  Concatenation","volume":"773","author":"J\u00fcrgen Bierbrauer","year":"1993"},{"key":"ref3:DBLP:conf\/crypto\/BlackRS02","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/3-540-45708-9_21","article-title":"Black-Box Analysis of the Block-Cipher-Based Hash-Function\n  Constructions from PGV","volume":"2442","author":"John Black","year":"2002"},{"key":"ref4:DBLP:conf\/sacrypt\/BertoniDPA11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/978-3-642-28496-0_19","article-title":"Duplexing the Sponge: Single-Pass Authenticated Encryption\n  and Other Applications","volume":"7118","author":"Guido Bertoni","year":"2011"},{"key":"ref5:DBLP:conf\/crypto\/RogawayS08","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/978-3-540-85174-5_24","article-title":"Constructing Cryptographic Hash Functions from Fixed-Key\n  Blockciphers","volume":"5157","author":"Phillip Rogaway","year":"2008"},{"key":"ref6:DBLP:conf\/asiacrypt\/RistenpartS07","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-540-76900-2_9","article-title":"How to Build a Hash Function from Any Collision-Resistant\n  Function","volume":"4833","author":"Thomas Ristenpart","year":"2007"},{"key":"ref7:DBLP:journals\/joc\/BlackCS09","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s00145-008-9030-1","article-title":"On the Impossibility of Highly-Efficient Blockcipher-Based\n  Hash Functions","volume":"22","author":"John Black","year":"2009","journal-title":"J. Cryptol."},{"key":"ref8:DBLP:conf\/crypto\/Damgard89a","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/0-387-34805-0_39","article-title":"A Design Principle for Hash Functions","volume":"435","author":"Ivan Damg\u00e5rd","year":"1989"},{"key":"ref9:DBLP:conf\/crypto\/Merkle89","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/0-387-34805-0_21","article-title":"A Certified Digital Signature","volume":"435","author":"Ralph C. Merkle","year":"1989"},{"key":"ref10:DBLP:conf\/sp\/Merkle80","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1109\/SP.1980.10006","article-title":"Protocols for Public Key Cryptosystems","author":"Ralph C. Merkle","year":"1980"},{"volume-title":"Batch Signing for TLS","year":"2020","author":"David Benjamin","key":"ref11:ietf-tls-batch-signing-00"},{"key":"ref12:10.1007\/11941378_25","series-title":"INDOCRYPT'06","isbn-type":"print","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/11941378_25","article-title":"CMSS: an improved merkle signature scheme","author":"Johannes Buchmann","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/3540497676"},{"key":"ref13:10.1007\/978-3-540-72738-5_3","series-title":"ACNS '07","isbn-type":"print","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-540-72738-5_3","article-title":"Merkle Signatures with Virtually Unlimited Signature\n  Capacity","author":"Johannes Buchmann","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540727378"},{"key":"ref14:DBLP:conf\/ccs\/BernsteinHKNRS19","doi-asserted-by":"publisher","first-page":"2129","DOI":"10.1145\/3319535.3363229","article-title":"The SPHINCS\\({}^{\\mbox{+}}\\) Signature Framework","author":"Daniel J. Bernstein","year":"2019"},{"key":"ref15:DBLP:journals\/joc\/HaberS91","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF00196791","article-title":"How to Time-Stamp a Digital Document","volume":"3","author":"Stuart Haber","year":"1991","journal-title":"J. Cryptol."},{"key":"ref16:DBLP:conf\/eurocrypt\/GennaroGP013","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1007\/978-3-642-38348-9_37","article-title":"Quadratic Span Programs and Succinct NIZKs without PCPs","volume":"7881","author":"Rosario Gennaro","year":"2013"},{"key":"ref17:DBLP:conf\/uss\/Ben-SassonCTV14","first-page":"781","article-title":"Succinct Non-Interactive Zero Knowledge for a von Neumann\n  Architecture","author":"Eli Ben-Sasson","year":"2014"},{"key":"ref18:DBLP:journals\/iacr\/Ben-SassonCG0MTV14","first-page":"349","article-title":"Zerocash: Decentralized Anonymous Payments from Bitcoin","author":"Eli Ben-Sasson","year":"2014","journal-title":"IACR Cryptol. ePrint Arch."},{"volume-title":"DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS\n  INTRACTABLE AS FACTORIZATION","year":"1979","author":"M. O. Rabin","key":"ref19:10.5555\/889813"},{"key":"ref20:1573105973881933824","first-page":"155","article-title":"Digitalized Signatures","author":"Rabin M.O.","year":"1978","journal-title":"Foundations of Secure Computation"},{"key":"ref21:DBLP:journals\/iacr\/DodisKMN21","first-page":"373","article-title":"T5: Hashing Five Inputs with Three Compression Calls","author":"Yevgeniy Dodis","year":"2021","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref22:DBLP:conf\/eurocrypt\/0001B021","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/978-3-030-77886-6_4","article-title":"Compactness of Hashing Modes and Efficiency Beyond Merkle\n  Tree","volume":"12697","author":"Elena Andreeva","year":"2021"},{"key":"ref23:dhar_et_al:LIPIcs.ITC.2022.11","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITC.2022.11","article-title":"Revisiting Collision and Local Opening Analysis of ABR\n  Hash","volume":"230","author":"Chandranan Dhar","year":"2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9783959772389","ISSN":"https:\/\/id.crossref.org\/issn\/1868-8969","issn-type":"electronic"},{"key":"ref24:DBLP:conf\/crypto\/Stam08","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/978-3-540-85174-5_22","article-title":"Beyond Uniformity: Better Security\/Efficiency Tradeoffs for\n  Compression Functions","volume":"5157","author":"Martijn Stam","year":"2008"},{"key":"ref25:DBLP:conf\/eurocrypt\/Steinberger10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/978-3-642-13190-5_30","article-title":"Stam's Collision Resistance Conjecture","volume":"6110","author":"John P. Steinberger","year":"2010"},{"key":"ref26:DBLP:conf\/crypto\/SteinbergerSY12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/978-3-642-32009-5_23","article-title":"Stam's Conjecture and Threshold Phenomena in Collision\n  Resistance","volume":"7417","author":"John P. Steinberger","year":"2012"},{"key":"ref27:DBLP:conf\/icalp\/ShrimptonS08","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/978-3-540-70583-3_52","article-title":"Building a Collision-Resistant Compression Function from\n  Non-compressing Primitives","volume":"5126","author":"Thomas Shrimpton","year":"2008"},{"key":"ref28:DBLP:conf\/vietcrypt\/Rogaway06","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/11958239_14","article-title":"Formalizing Human Ignorance","volume":"4341","author":"Phillip Rogaway","year":"2006"},{"key":"ref29:2fd4d11a-229b-3d9f-b6ea-b8bdb72552e9","first-page":"565","article-title":"Sylvester's Identity and Multistep Integer-Preserving\n  Gaussian Elimination","volume":"22","author":"Erwin H. Bareiss","year":"1968","journal-title":"Mathematics of Computation"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:28:23Z","timestamp":1733866103000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/3\/22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":29,"URL":"https:\/\/doi.org\/10.62056\/akgy11zn4","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"type":"electronic","value":"3006-5496"}],"subject":[],"published":{"date-parts":[[2024,10,7]]},"assertion":[{"value":"2024-07-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-3-73"}}