{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:16:10Z","timestamp":1778040970978,"version":"3.51.4"},"reference-count":36,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T00:00:00Z","timestamp":1770076800000},"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,24]]},"abstract":"\n Quantum computers may soon be able to compute discrete logarithms, but the high resource cost will likely restrict attackers to only a limited number of such computations. Traditional digital signature schemes \u2014such as\n \n \n \\Schnorr<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n ,\n \n \n \\ECDSA<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n , and\n \n \n \\BLS<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n \u2014 are easy targets for such restricted attackers: a single discrete logarithm computation suffices to recover the secret key, enabling the attacker to forge an arbitrary number of signatures.\n <\/jats:p>\n \n This work explores whether signature schemes can be designed in such a way that forging multiple signatures is significantly harder than a single discrete logarithm computation. To formalize this, we introduce the notion of multi-unforgeability, where a signature scheme is said to be\n \n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n -unforgeable if it is computationally infeasible for an adversary to produce valid signatures on\n \n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n distinct messages.\n <\/jats:p>\n \n Our main technical contribution is to propose two novel digital signature schemes, both featuring constant-size signatures. The first scheme builds upon the\n \n \n \\BLS<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n signature scheme in bilinear groups, and we show that breaking\n \n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n -unforgeability requires solving\n \n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n independent Diffie-Hellman instances. The second scheme is based on the Chevallier-Mames signature scheme over prime-order groups without pairings; in this case, breaking\n \n \n \n k<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n -unforgeability is as hard as solving\n \n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n many Diffie-Hellman instances.\n <\/jats:p>\n Both schemes significantly raise the difficulty of large-scale forgery, offering enhanced security in scenarios where multiple signatures may be targeted.<\/jats:p>","DOI":"10.62056\/a3c0l5w4e-","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":["Signatures in the Multi-Unforgeability Setting"],"prefix":"10.62056","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1178-048X","authenticated-orcid":false,"given":"Eike","family":"Kiltz","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/04tsk2644","id-type":"ROR","asserted-by":"publisher"}],"name":"Ruhr University Bochum","place":["Germany"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-7112-1878","authenticated-orcid":false,"given":"Samin","family":"Nooripoor","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/04tsk2644","id-type":"ROR","asserted-by":"publisher"}],"name":"Ruhr University Bochum","place":["Germany"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2026,5,4]]},"reference":[{"key":"ref1:CCS:ABDGGH15","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/2810103.2813707","article-title":"Imperfect Forward Secrecy: How Diffie-Hellman Fails in\n Practice","author":"David Adrian","year":"2015"},{"key":"ref2:PKC:BelRieShe25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/978-3-031-91829-2_5","article-title":"Intermundium-DL: Assessing the Resilience of Current\n Schemes to Discrete-Log-Computation Attacks on Public Parameters","volume":"15677","author":"Mihir Bellare","year":"2025"},{"key":"ref3:C:BelRisTes12","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/978-3-642-32009-5_19","article-title":"Multi-instance Security and Its Application to\n Password-Based Cryptography","volume":"7417","author":"Mihir Bellare","year":"2012"},{"key":"ref4:EC:AueGiaKil20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/978-3-030-45727-3_16","article-title":"Everybody's a Target: Scalability in Public-Key Encryption","volume":"12107","author":"Benedikt Auerbach","year":"2020"},{"key":"ref5:EC:FarTes21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/978-3-030-77886-6_3","article-title":"Password Hashing and Preprocessing","volume":"12697","author":"Pooya Farshim","year":"2021"},{"key":"ref6:PQ:EatSteb21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-030-81293-5_9","article-title":"The \"Quantum Annoying\" Property of Password-Authenticated\n Key Exchange Protocols","volume":"12841","author":"Edward Eaton","year":"2021"},{"key":"ref7:ESORICS:TieEatSte23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/978-3-031-50594-2_9","article-title":"Making an Asymmetric PAKE Quantum-Annoying by Hiding Group\n Elements","volume":"14344","author":"Marcel Tiepelt","year":"2023"},{"key":"ref8:PKC:BruHeuSta23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/978-3-031-31371-4_12","article-title":"Multi-instance Secure Public-Key Encryption","volume":"13941","author":"Carlo Brunetta","year":"2023"},{"key":"ref9:EC:BelRog96","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/3-540-68339-9_34","article-title":"The Exact Security of Digital Signatures: How to Sign with\n RSA and Rabin","volume":"1070","author":"Mihir Bellare","year":"1996"},{"key":"ref10:AC:BonLynSha01","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1007\/3-540-45682-1_30","article-title":"Short Signatures from the Weil Pairing","volume":"2248","author":"Dan Boneh","year":"2001"},{"key":"ref11:TCC:DHHKSU21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/978-3-030-90456-2_11","article-title":"On the Impossibility of Purely Algebraic Signatures","volume":"13044","author":"Nico D\u00f6ttling","year":"2021"},{"key":"ref12:C:Chevallier-Mames05","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/11535218_31","article-title":"An Efficient CDH-Based Signature Scheme with a Tight\n Security Reduction","volume":"3621","author":"Beno\u00eet Chevallier-Mames","year":"2005"},{"key":"ref13:EC:BelRis09","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/978-3-642-01001-9_24","article-title":"Simulation without the Artificial Abort: Simplified Proof\n and Improved Concrete Security for Waters' IBE Scheme","volume":"5479","author":"Mihir Bellare","year":"2009"},{"key":"ref14:EC:BGLS03","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/3-540-39200-9_26","article-title":"Aggregate and Verifiably Encrypted Signatures from Bilinear\n Maps","volume":"2656","author":"Dan Boneh","year":"2003"},{"key":"ref15:EC:GohJar03","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/3-540-39200-9_25","article-title":"A Signature Scheme as Secure as the Diffie-Hellman\n Problem","volume":"2656","author":"Eu-Jin Goh","year":"2003"},{"key":"ref16:AC:KilLosPan17","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/978-3-319-70700-6_3","article-title":"Tightly-Secure Signatures from Five-Move Identification\n Protocols","volume":"10626","author":"Eike Kiltz","year":"2017"},{"key":"ref17:C:Schnorr89","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/0-387-34805-0_22","article-title":"Efficient Identification and Signatures for Smart Cards","volume":"435","author":"Claus-Peter Schnorr","year":"1990"},{"key":"ref18:C:FiaSha86","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-47721-7_12","article-title":"How to Prove Yourself: Practical Solutions to\n Identification and Signature Problems","volume":"263","author":"Amos Fiat","year":"1987"},{"key":"ref19:EC:CasKilSho08","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-540-78967-3_8","article-title":"The Twin Diffie-Hellman Problem and Applications","volume":"4965","author":"David Cash","year":"2008"},{"key":"ref20:CCS:BacLos22","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1145\/3548606.3560656","article-title":"On the Adaptive Security of the Threshold BLS Signature\n Scheme","author":"Renas Bacho","year":"2022"},{"key":"ref21:EC:TesZhu23a","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1007\/978-3-031-30589-4_22","article-title":"Threshold and Multi-signature Schemes from Linear Hash\n Functions","volume":"14008","author":"Stefano Tessaro","year":"2023"},{"key":"ref22:EC:PoiSte96","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/3-540-68339-9_33","article-title":"Security Proofs for Signature Schemes","volume":"1070","author":"David Pointcheval","year":"1996"},{"key":"ref23:CCS:BelNev06","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1145\/1180405.1180453","article-title":"Multi-signatures in the plain public-Key model and a general\n forking lemma","author":"Mihir Bellare","year":"2006"},{"key":"ref24:C:FucKilLos18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-319-96881-0_2","article-title":"The Algebraic Group Model and its Applications","volume":"10992","author":"Georg Fuchsbauer","year":"2018"},{"key":"ref25:C:CraSho98","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BFb0055717","article-title":"A Practical Public Key Cryptosystem Provably Secure Against\n Adaptive Chosen Ciphertext Attack","volume":"1462","author":"Ronald Cramer","year":"1998"},{"key":"ref26:EC:CraSho02","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/3-540-46035-7_4","article-title":"Universal Hash Proofs and a Paradigm for Adaptive Chosen\n Ciphertext Secure Public-Key Encryption","volume":"2332","author":"Ronald Cramer","year":"2002"},{"key":"ref27:EC:BelRog06","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/11761679_25","article-title":"The Security of Triple Encryption and a Framework for\n Code-Based Game-Playing Proofs","volume":"4004","author":"Mihir Bellare","year":"2006"},{"key":"ref28:RSA:AbdBelRog01","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/3-540-45353-9_12","article-title":"The Oracle Diffie-Hellman Assumptions and an Analysis of\n DHIES","volume":"2020","author":"Michel Abdalla","year":"2001"},{"key":"ref29:EC:Yun15","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"817","DOI":"10.1007\/978-3-662-46803-6_27","article-title":"Generic Hardness of the Multiple Discrete Logarithm\n Problem","volume":"9057","author":"Aaram Yun","year":"2015"},{"key":"ref30:SAC:KuhStr01","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/3-540-45537-X_17","article-title":"Random Walks Revisited: Extensions of Pollard's Rho\n Algorithm for Computing Multiple Discrete Logarithms","volume":"2259","author":"Fabian Kuhn","year":"2001"},{"key":"ref31:ACNS:YinKun17","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1007\/978-3-319-61204-1_25","article-title":"Bounds in Various Generalized Settings of the Discrete\n Logarithm Problem","volume":"10355","author":"Jason H. M. Ying","year":"2017"},{"key":"ref32:EC:Hhan25","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/978-3-031-91098-2_13","article-title":"A New Approach to Generic Lower Bounds - Classical\/Quantum\n MDL, Quantum Factoring, and More","author":"Minki Hhan","year":"2025"},{"key":"ref33:C:KilMasPan16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-662-53008-5_2","article-title":"Optimal Security Proofs for Signatures from Identification\n Schemes","volume":"9815","author":"Eike Kiltz","year":"2016"},{"key":"ref34:CCS:KatWan03","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/948109.948132","article-title":"Efficiency Improvements for Signature Schemes with Tight\n Security Reductions","author":"Jonathan Katz","year":"2003"},{"key":"ref35:King1975GeneralisedVandermonde","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1090\/S0002-9939-1975-0371919-0","article-title":"Generalised Vandermonde Determinants and Schur Functions","volume":"48","author":"R. C. King","year":"1975","journal-title":"Proceedings of the American Mathematical Society"},{"key":"ref36:EPRINT:Shoup04","volume-title":"Sequences of games: a tool for taming complexity in security\n proofs","author":"Victor Shoup","year":"2004"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:04:29Z","timestamp":1778040269000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/3\/1\/33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,4]]},"references-count":36,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,5,4]]}},"URL":"https:\/\/doi.org\/10.62056\/a3c0l5w4e-","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-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc3-1-122"}}