{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T17:04:51Z","timestamp":1753895091579,"version":"3.41.2"},"reference-count":21,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,7,5]],"date-time":"2024-07-05T00:00:00Z","timestamp":1720137600000},"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>Blind signature schemes enable a user to obtain a digital signature on a message from a signer without revealing the message itself. Among the most fundamental examples of such a scheme is blind Schnorr, but recent results show that it does not satisfy the standard notion of security against malicious users, One-More Unforgeability (OMUF), as it is vulnerable to the ROS attack. However, blind Schnorr does satisfy the weaker notion of sequential OMUF, in which only one signing session is open at a time, in the Algebraic Group Model (AGM) + Random Oracle Model (ROM), assuming the hardness of the Discrete Logarithm (DL) problem.<\/jats:p>\n          <jats:p>This paper serves as a first step towards characterizing the security of blind Schnorr in the limited concurrency setting. Specifically, we show that blind Schnorr satisfies OMUF when at most two signing sessions can be concurrently open (in the AGM+ROM, assuming DL). Our argument suggests that it is plausible that blind Schnorr satisfies OMUF for up to polylogarithmically many concurrent signing sessions. Our security proof involves interesting techniques from linear algebra and combinatorics. <\/jats:p>","DOI":"10.62056\/a3qj5w7sf","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":["Unforgeability of Blind Schnorr in the Limited Concurrency Setting"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-9811-1610","authenticated-orcid":false,"given":"Franklin","family":"Harding","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05gq02987","id-type":"ROR","asserted-by":"publisher"}],"name":"Brown University","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0881-9980","authenticated-orcid":false,"given":"Jiayu","family":"Xu","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00ysfqy60","id-type":"ROR","asserted-by":"publisher"}],"name":"Oregon State University","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"ref1:C:Chaum82","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/978-1-4757-0602-4_18","article-title":"Blind Signatures for Untraceable Payments","author":"David Chaum","year":"1982"},{"volume-title":"Adding Schnorr\u2019s Blind Signature in Taler","year":"2022","author":"Gian Demarmels","key":"ref2:Demarmels22"},{"key":"ref3:CCS:BalLys13","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1145\/2508859.2516687","article-title":"Anonymous credentials light","author":"Foteini Baldimtsi","year":"2013"},{"key":"ref4:Fujioka05","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/3-540-57220-1_66","article-title":"A Practical Secret Voting Scheme for Large Scale Elections","volume":"718","author":"Atsushi Fujioka","year":"1992"},{"volume-title":"Blind signatures in scriptless scripts","year":"2019","author":"Jonas Nick","key":"ref5:Nick19"},{"key":"ref6:C:ChaPed92","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/3-540-48071-4_7","article-title":"Wallet Databases with Observers","volume":"740","author":"David Chaum","year":"1993"},{"key":"ref7:ICICS:Schnorr01","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45600-7_1","article-title":"Security of Blind Discrete Log Signatures against\n  Interactive Attacks","volume":"2229","author":"Claus-Peter Schnorr","year":"2001"},{"key":"ref8:EC:Shoup97","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/3-540-69053-0_18","article-title":"Lower Bounds for Discrete Logarithms and Related Problems","volume":"1233","author":"Victor Shoup","year":"1997"},{"key":"ref9:AC:NguShp01","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/3-540-45682-1_2","article-title":"On the Insecurity of a Server-Aided RSA Protocol","volume":"2248","author":"Phong Q. Nguyen","year":"2001"},{"key":"ref10:C:SPMS02","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/3-540-45708-9_7","article-title":"Flaws in Applying Proof Methodologies to Signature Schemes","volume":"2442","author":"Jacques Stern","year":"2002"},{"key":"ref11: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":"ref12:EC:FucPloSeu20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/978-3-030-45724-2_3","article-title":"Blind Schnorr Signatures and Signed ElGamal Encryption\n  in the Algebraic Group Model","volume":"12106","author":"Georg Fuchsbauer","year":"2020"},{"key":"ref13:AC:BauFucPlo21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1007\/978-3-030-92068-5_20","article-title":"The One-More Discrete Logarithm Assumption in the Generic\n  Group Model","volume":"13093","author":"Balthazar Bauer","year":"2021"},{"key":"ref14:C:Wagner02","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/3-540-45708-9_19","article-title":"A Generalized Birthday Problem","volume":"2442","author":"David Wagner","year":"2002"},{"key":"ref15:JC:BLLOR22","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s00145-022-09436-0","article-title":"On the (in)Security of ROS","volume":"35","author":"Fabrice Benhamouda","year":"2022","journal-title":"Journal of Cryptology"},{"key":"ref16:PKC:KasLosXu22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1007\/978-3-030-97131-1_16","article-title":"On Pairing-Free Blind Signature Schemes in the Algebraic\n  Group Model","volume":"13178","author":"Julia Kastner","year":"2022"},{"key":"ref17:C:JueLubOst97","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/BFb0052233","article-title":"Security of Blind Digital Signatures (Extended Abstract)","volume":"1294","author":"Ari Juels","year":"1997"},{"key":"ref18:C:CKMTZ23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1007\/978-3-031-38557-5_23","article-title":"Snowblind: A Threshold Blind Signature in Pairing-Free\n  Groups","volume":"14081","author":"Elizabeth C. Crites","year":"2023"},{"key":"ref19:C:ChaTesZhu24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/978-3-031-68376-3_6","article-title":"Pairing-Free Blind Signatures from CDH Assumptions","volume":"14920","author":"Rutchathon Chairattana-Apirom","year":"2024"},{"key":"ref20:C:KasNguRei24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/978-3-031-68376-3_7","article-title":"Pairing-Free Blind Signatures from Standard Assumptions in\n  the ROM","volume":"14920","author":"Julia Kastner","year":"2024"},{"key":"ref21:EC:FucWol24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1007\/978-3-031-58723-8_5","article-title":"Concurrently Secure Blind Schnorr Signatures","volume":"14652","author":"Georg Fuchsbauer","year":"2024"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:28:17Z","timestamp":1733866097000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/3\/16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":21,"URL":"https:\/\/doi.org\/10.62056\/a3qj5w7sf","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-05","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-52"}}