{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T04:11:52Z","timestamp":1767931912453,"version":"3.49.0"},"reference-count":19,"publisher":"International Association for Cryptologic Research","issue":"4","license":[{"start":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T00:00:00Z","timestamp":1759795200000},"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":[[2025,12,2]]},"abstract":"We study additive positive accumulators, which maintain a short digest of a growing set such that each value in the set can prove membership via a generated witness. Due to the compactness of the digest, previously added values may require updated witnesses as the set grows.<\/jats:p>\n \n In this paper, we establish a trade-off between the bit-length of the accumulator value and the number of witness updates. Specifically, we show that if the accumulator value has bit-length\n \n \n \n p<\/mml:mi>\n o<\/mml:mi>\n l<\/mml:mi>\n y<\/mml:mi>\n <\/mml:mrow>\n (<\/mml:mo>\n log<\/mml:mi>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n , where\n \n \n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n is the number of accumulated values, then some values must incur\n \n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mi>\n n<\/mml:mi>\n \/<\/mml:mo>\n log<\/mml:mi>\n log<\/mml:mi>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n witness updates. This improves upon the recent\n \n \n \u03c9<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n lower bound of [BCCK25] and matches the upper bound in [MQ23].\n <\/jats:p>\n Building on the framework of [MQR22], we introduce a new combinatorial structure that removes the fixed-update-time assumption. Our approach also applies to Registration-based Encryption [GHMR18], thereby resolving the open problem left in [MQR22]: it shows that the tight lower bound on decryption-update frequency continues to hold even without any fixed-update-time assumption.<\/jats:p>","DOI":"10.62056\/av7t7ta5v","type":"journal-article","created":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T23:39:47Z","timestamp":1767915587000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Tight Lower Bound on Witness Update Frequency in Additive Positive Accumulators"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-8510-4675","authenticated-orcid":false,"given":"Wei","family":"Qi","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05crjpb27","id-type":"ROR","asserted-by":"publisher"}],"name":"Bocconi University","place":["Via Roentgen, 1, Milan, MI, 20136, Italy"],"department":["Department of Computing Sciences"]}]}],"member":"48349","published-online":{"date-parts":[[2026,1,8]]},"reference":[{"key":"ref1:merkle-moutain-range","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/978-3-032-01878-6_6","article-title":"Merkle Mountain Ranges are Optimal: On Witness Update\n Frequency for Cryptographic Accumulators","volume":"16001","author":"Joseph Bonneau","year":"2025","ISBN":"https:\/\/id.crossref.org\/isbn\/9783032018779"},{"key":"ref2:upper-bound","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITC.2023.15","article-title":"Online Mergers and Applications to Registration-Based\n Encryption and Accumulators","volume":"267","author":"Mohammad Mahmoody","year":"2023","ISBN":"https:\/\/id.crossref.org\/isbn\/9783959772716","ISSN":"https:\/\/id.crossref.org\/issn\/1868-8969","issn-type":"electronic"},{"key":"ref3:lower-bound","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/978-3-031-22318-1_20","article-title":"Lower Bounds for the Number of Decryption Updates in\n Registration-Based Encryption","author":"Mohammad Mahmoody","year":"2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031223181"},{"key":"ref4:rbe","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1007\/978-3-030-03807-6_25","article-title":"Registration-Based Encryption: Removing Private-Key\n Generator from IBE","volume":"11239","author":"Sanjam Garg","year":"2018","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030038069"},{"key":"ref5:acc-1","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/3-540-48285-7_24","article-title":"One-Way Accumulators: A Decentralized Alternative to Digital\n Signatures","volume":"765","author":"Josh Benaloh","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540482857"},{"key":"ref6:acc-2","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/3-540-45708-9_5","article-title":"Dynamic Accumulators and Application to Efficient Revocation\n of Anonymous Credentials","volume":"2442","author":"Jan Camenisch","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540457084"},{"key":"ref7:acc-3","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-540-30574-3_19","article-title":"Accumulators from Bilinear Pairings and Applications","volume":"3376","author":"Lan Nguyen","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540305743"},{"key":"ref8:acc-4","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1007\/3-540-69053-0_33","article-title":"Collision-Free Accumulators and Fail-Stop Signature Schemes\n Without Trees","volume":"1233","author":"Niko Bari\u0107","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540690535"},{"key":"ref9:merkle","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/3-540-48184-2_32","article-title":"A Digital Signature Based on a Conventional Encryption\n Function","volume":"293","author":"Ralph C. Merkle","year":"1988","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540481843"},{"key":"ref10:PKI","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/978-3-319-44618-9_16","article-title":"Efficient Asynchronous Accumulators for Distributed PKI","volume":"9841","author":"Leonid Reyzin","year":"2016","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319446189"},{"key":"ref11:rbe-1","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/978-3-030-17259-6_3","article-title":"Registration-Based Encryption from Standard Assumptions","volume":"11443","author":"Sanjam Garg","year":"2019","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030172596"},{"key":"ref12:RBE-2","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1007\/978-3-030-56784-2_21","article-title":"Verifiable Registration-Based Encryption","volume":"12170","author":"Rishab Goyal","year":"2020","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030567842"},{"key":"ref13:RBE-3","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-030-92641-0_7","article-title":"Optimizing Registration Based Encryption","volume":"13129","author":"Kelong Cong","year":"2021","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030926410"},{"key":"ref14:RBE-4","series-title":"CCS '23","isbn-type":"print","doi-asserted-by":"publisher","first-page":"1065","DOI":"10.1145\/3576915.3616596","article-title":"Efficient Registration-Based Encryption","author":"Noemi Glaeser","year":"2023","ISBN":"https:\/\/id.crossref.org\/isbn\/9798400700507"},{"key":"ref15:RBE-5","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/978-981-99-8733-7_6","article-title":"Cuckoo Commitments: Registration-Based Encryption and\n Key-Value Map Commitments for Large Spaces","volume":"14442","author":"Dario Fiore","year":"2023","ISBN":"https:\/\/id.crossref.org\/isbn\/9789819987337"},{"key":"ref16:RBE-6","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/978-3-031-30620-4_14","article-title":"Efficient Laconic Cryptography from\u00a0Learning with\u00a0Errors","volume":"14006","author":"Nico D\u00f6ttling","year":"2023","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031306204"},{"key":"ref17:RBE-7","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-031-91820-9_7","article-title":"Registration-Based Encryption in the Plain Model","volume":"15674","author":"Jesko Dujmovic","year":"2025","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031918209"},{"key":"ref18:lower-bound-2","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1109\/EuroSP.2017.13","article-title":"Accumulators with Applications to Anonymity-Preserving\n Revocation","author":"Foteini Baldimtsi","year":"2017"},{"key":"ref19:acc-5","doi-asserted-by":"publisher","DOI":"10.1109\/CSF51468.2021.00033","article-title":"Efficient Constructions of Pairing Based Accumulators","author":"Ioanna Karantaidou","year":"2021","journal-title":"2021 IEEE 34th Computer Security Foundations Symposium\n (CSF)"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T23:41:08Z","timestamp":1767915668000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/4\/14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,8]]},"references-count":19,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2026,1,8]]}},"URL":"https:\/\/doi.org\/10.62056\/av7t7ta5v","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,8]]},"assertion":[{"value":"2025-10-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-4-28"}}