{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:15:27Z","timestamp":1778040927597,"version":"3.51.4"},"reference-count":29,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T00:00:00Z","timestamp":1769990400000},"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":[[2026,4,16]]},"abstract":"\n A Boolean function\n \n \n f<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n is monotone if and only if there exists a monotone Boolean circuit (consisting exclusively of AND or OR gates) which computes\n \n \n f<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n . The study of monotone cryptography was initiated by Goldreich and Izsak (TOC '12) who showed that one-way functions (OWF) can be monotone, but no monotone pseudo-random generator (PRG) exists. Incidentally, many cryptographic primitives cannot be monotone, by the work of Guo, Malkin, Oliveira and Rosen (TCC'15). Not long after, Miller, Scrivener, Stern and Venkitasubramaniam (INDOCRYPT'16) showed that collision resistant hash functions (CRH) (and even the weaker notion of target CRH) cannot be monotone.\n <\/jats:p>\n \n Distributional collision resistant hash functions (dCRH) are a relaxation of the usual CRH notion. In particular, a hash function\n \n \n h<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n has distributional collision resistance if there does not exist any efficient adversary that produces collisions that are statistically close to\n \n \n (<\/mml:mo>\n \n x<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n x<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n where\n \n \n \n x<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n is a random input and\n \n \n \n x<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n is sampled uniformly from the set of pre-images of\n \n \n h<\/mml:mi>\n (<\/mml:mo>\n \n x<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n . Despite being a weaker notion of collision resistance, dCRH have applications to e.g. constant round statistically-hiding commitment schemes, and (these commitment schemes) are not known to be constructible from OWF alone.\n <\/jats:p>\n In this work we show the existence of a monotone dCRH, assuming any CRH exists. To prove our result, we observe that the proof technique of Goldreich and Izsak for the existence of monotone OWF can be extended analogously to dCRH. As a result, dCRH joins the rather small list of primitives known to also be monotone, namely (surjective or injective, but not bijective) OWF, and certain list decodable codes (decoders).<\/jats:p>","DOI":"10.62056\/akp2fh888","type":"journal-article","created":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T18:09:08Z","timestamp":1777918148000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["A Note on the Existence of Monotone Distributional Collision Resistant Hash Functions"],"prefix":"10.62056","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2468-9151","authenticated-orcid":false,"given":"Kirthivaasan","family":"Puniamurthy","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/020hwjq30","id-type":"ROR","asserted-by":"publisher"}],"name":"Aalto University","place":["Finland"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2026,5,4]]},"reference":[{"key":"ref1:alon1987monotone","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/bf02579196","article-title":"The monotone circuit complexity of Boolean functions","volume":"7","author":"Noga Alon","year":"1987","journal-title":"Combinatorica"},{"key":"ref2:pitassi2017strongly","doi-asserted-by":"publisher","first-page":"1246","DOI":"10.1145\/3055399.3055478","article-title":"Strongly exponential lower bounds for monotone computation","author":"Toniann Pitassi","year":"2017"},{"key":"ref3:garg2018monotone","doi-asserted-by":"publisher","first-page":"902","DOI":"10.1145\/3188745.3188838","article-title":"Monotone circuit lower bounds from resolution","author":"Ankit Garg","year":"2018"},{"key":"ref4:goldreich2012monotone","doi-asserted-by":"publisher","first-page":"231","DOI":"10.4086\/toc.2012.v008a010","article-title":"Monotone circuits: One-way functions versus pseudorandom\n generators","volume":"8","author":"Oded Goldreich","year":"2012","journal-title":"Theory of Computing"},{"key":"ref5:TCC:GMOR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/978-3-662-46494-6_3","article-title":"The Power of Negations in Cryptography","volume":"9014","author":"Siyao Guo","year":"2015"},{"key":"ref6:INDOCRYPT:MSSV16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/978-3-319-49890-4_19","article-title":"On Negation Complexity of Injections, Surjections and\n Collision-Resistance in Cryptography","volume":"10095","author":"Douglas Miller","year":"2016"},{"key":"ref7:markov1958inversion","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1145\/320941.320945","article-title":"On the inversion complexity of a system of functions","volume":"5","author":"Andrey A Markov","year":"1958","journal-title":"Journal of the ACM (JACM)"},{"key":"ref8:fischer1975complexity","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/3-540-07407-4_9","article-title":"The complexity of negation-limited networks\u2014A brief\n survey","author":"Michael Fischer","year":"1975"},{"key":"ref9:TCC:ReiTreVad04","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-24638-1_1","article-title":"Notions of Reducibility between Cryptographic Primitives","volume":"2951","author":"Omer Reingold","year":"2004"},{"key":"ref10:AC:BaeBrzFis13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/978-3-642-42033-7_16","article-title":"Notions of Black-Box Reductions, Revisited","volume":"8269","author":"Paul Baecher","year":"2013"},{"key":"ref11:rudich1988limits","volume-title":"Limits on the provable consequences of one-way functions","author":"Steven Rudich","year":"1988"},{"key":"ref12:EC:BHKY19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1007\/978-3-030-17659-4_23","article-title":"Distributional Collision Resistance Beyond One-Way\n Functions","volume":"11478","author":"Nir Bitansky","year":"2019"},{"key":"ref13:EC:Simon98","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/BFb0054137","article-title":"Finding Collisions on a One-Way Street: Can Secure Hash\n Functions Be Based on General Assumptions?","volume":"1403","author":"Daniel R. Simon","year":"1998"},{"key":"ref14:FOCS:Yao82a","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1109\/SFCS.1982.45","article-title":"Theory and Applications of Trapdoor Functions (Extended\n Abstract)","author":"Andrew Chi-Chih Yao","year":"1982"},{"key":"ref15:guo2017negation","doi-asserted-by":"publisher","first-page":"75","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2015.850","article-title":"Negation-limited formulas","volume":"660","author":"Siyao Guo","year":"2017","journal-title":"Theoretical Computer Science"},{"key":"ref16:FOCS:AppIshKus04","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1109\/FOCS.2004.20","article-title":"Cryptography in NC$^0$","author":"Benny Applebaum","year":"2004"},{"key":"ref17:ITCS:ABGKR14","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1145\/2554797.2554821","article-title":"Candidate weak pseudorandom functions in $\\mathsf{AC}^0$\n $o$ MOD$_2$","author":"Adi Akavia","year":"2014"},{"key":"ref18:TCC:BIPSW18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1007\/978-3-030-03810-6_25","article-title":"Exploring Crypto Dark Matter: New Simple PRF Candidates\n and Their Applications","volume":"11240","author":"Dan Boneh","year":"2018"},{"key":"ref19:C:BCGIKS21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/978-3-030-84259-8_17","article-title":"Low-Complexity Weak Pseudorandom Functions in\n $\\mathtt{AC}0[\\mathtt{MOD}2]$","volume":"12828","author":"Elette Boyle","year":"2021"},{"key":"ref20:EPRINT:Goldreich00b","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22670-0_10","volume-title":"Candidate One-Way Functions Based on Expander Graphs","author":"Oded Goldreich","year":"2000"},{"key":"ref21:C:Merkle89b","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/0-387-34805-0_40","article-title":"One Way Hash Functions and DES","volume":"435","author":"Ralph C. Merkle","year":"1990"},{"key":"ref22:C:Damgaard89b","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":"1990"},{"key":"ref23:merkle1979secrecy","volume-title":"Secrecy, authentication, and public key systems.","author":"Ralph Charles Merkle","year":"1979"},{"key":"ref24:micciancio2020sis","article-title":"The sis problem and cryptographic applications","author":"Daniele Micciancio","year":"2020","journal-title":"Lecture slides from Simons Institute for the Theory of\n Computing"},{"key":"ref25:berkowitz1982some","volume-title":"On some relationships between monotone and nonmonotone\n circuit complexity","author":"S Berkowitz","year":"1982"},{"key":"ref26:rossman_notes","volume-title":"Lecture 1: Introduction to the Course and Basic\n Definitions","author":"Benjamin Rossman","year":"2019"},{"key":"ref27:ajtai19830","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/800061.808726","article-title":"An 0 (n log n) sorting network","author":"Mikl\u00f3s Ajtai","year":"1983"},{"key":"ref28:savage1972computational","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1145\/321724.321731","article-title":"Computational work and time on finite machines","volume":"19","author":"John E Savage","year":"1972","journal-title":"Journal of the ACM (JACM)"},{"key":"ref29:mittelbach2021theory","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-63287-8","article-title":"The theory of hash functions and random oracles","author":"Arno Mittelbach","year":"2021","journal-title":"An Approach to Modern Cryptography, Cham: Springer Nature"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:02:14Z","timestamp":1778040134000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/3\/1\/11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,4]]},"references-count":29,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,5,4]]}},"URL":"https:\/\/doi.org\/10.62056\/akp2fh888","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,4]]},"assertion":[{"value":"2026-02-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-16","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc3-1-13"}}