Unforgeability of Blind Schnorr in the Limited Concurrency Setting

Franklin Harding; Jiayu Xu

doi:10.62056/a3qj5w7sf

Unforgeability of Blind Schnorr in the Limited Concurrency Setting

Authors

Franklin Harding, Jiayu Xu

Franklin Harding

Brown University, USA
fharding1 at protonmail dot com

Jiayu Xu

Oregon State University, USA
xujiay at oregonstate dot edu

Keywords: Schnorr signatures blind signatures algebraic group model ROS

Abstract

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.

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.

References

[BFP21]

Balthazar Bauer, Georg Fuchsbauer, and Antoine Plouviez. The One-More Discrete Logarithm Assumption in the Generic Group Model. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part IV, volume 13093 of LNCS, pages 587–617. December 2021. Springer, Cham. DOI: 10.1007/978-3-030-92068-5_20

Google Scholar ePrint

[BL13]

Foteini Baldimtsi and Anna Lysyanskaya. Anonymous credentials light. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, ACM CCS 2013, pages 1087–1098. November 2013. ACM Press. DOI: 10.1145/2508859.2516687

Google Scholar ePrint

[BLL⁺22]

Fabrice Benhamouda, Tancrède Lepoint, Julian Loss, Michele Orrù, and Mariana Raykova. On the (in)Security of ROS. Journal of Cryptology, 35(4):25, October 2022. DOI: 10.1007/s00145-022-09436-0

Google Scholar ePrint

[CATZ24]

Rutchathon Chairattana-Apirom, Stefano Tessaro, and Chenzhi Zhu. Pairing-Free Blind Signatures from CDH Assumptions. In Leonid Reyzin and Douglas Stebila, editors, CRYPTO 2024, Part I, volume 14920 of LNCS, pages 174–209. August 2024. Springer, Cham. DOI: 10.1007/978-3-031-68376-3_6

Google Scholar ePrint

[Cha82]

David Chaum. Blind Signatures for Untraceable Payments. In David Chaum, Ronald L. Rivest, and Alan T. Sherman, editors, CRYPTO'82, pages 199–203. 1982. Plenum Press, New York, USA. DOI: 10.1007/978-1-4757-0602-4_18

Google Scholar ePrint

[CKM⁺23]

Elizabeth C. Crites, Chelsea Komlo, Mary Maller, Stefano Tessaro, and Chenzhi Zhu. Snowblind: A Threshold Blind Signature in Pairing-Free Groups. In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part I, volume 14081 of LNCS, pages 710–742. August 2023. Springer, Cham. DOI: 10.1007/978-3-031-38557-5_23

Google Scholar ePrint

[CP93]

David Chaum and Torben P. Pedersen. Wallet Databases with Observers. In Ernest F. Brickell, editor, CRYPTO'92, volume 740 of LNCS, pages 89–105. August 1993. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48071-4_7

Google Scholar ePrint

[DH22]

Gian Demarmels and Lucien Heuzeveldt. Accessed: 2024-04-11. 2022.

Google Scholar ePrint

[FKL18]

Georg Fuchsbauer, Eike Kiltz, and Julian Loss. The Algebraic Group Model and its Applications. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part II, volume 10992 of LNCS, pages 33–62. August 2018. Springer, Cham. DOI: 10.1007/978-3-319-96881-0_2

Google Scholar ePrint

[FOO92]

Atsushi Fujioka, Tatsuaki Okamoto, and Kazuo Ohta. A Practical Secret Voting Scheme for Large Scale Elections. In Jennifer Seberry and Yuliang Zheng, editors, Advances in Cryptology - AUSCRYPT '92, volume 718 of Lecture Notes in Computer Science, pages 244–251. 1992. Springer. DOI: 10.1007/3-540-57220-1_66

Google Scholar ePrint

[FPS20]

Georg Fuchsbauer, Antoine Plouviez, and Yannick Seurin. Blind Schnorr Signatures and Signed ElGamal Encryption in the Algebraic Group Model. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part II, volume 12106 of LNCS, pages 63–95. May 2020. Springer, Cham. DOI: 10.1007/978-3-030-45724-2_3

Google Scholar ePrint

[FW24]

Georg Fuchsbauer and Mathias Wolf. Concurrently Secure Blind Schnorr Signatures. In Marc Joye and Gregor Leander, editors, EUROCRYPT 2024, Part II, volume 14652 of LNCS, pages 124–160. May 2024. Springer, Cham. DOI: 10.1007/978-3-031-58723-8_5

Google Scholar ePrint

[JLO97]

Ari Juels, Michael Luby, and Rafail Ostrovsky. Security of Blind Digital Signatures (Extended Abstract). In Burton S. Kaliski Jr., editor, CRYPTO'97, volume 1294 of LNCS, pages 150–164. August 1997. Springer, Berlin, Heidelberg. DOI: 10.1007/BFb0052233

Google Scholar ePrint

[KLX22]

Julia Kastner, Julian Loss, and Jiayu Xu. On Pairing-Free Blind Signature Schemes in the Algebraic Group Model. In Goichiro Hanaoka, Junji Shikata, and Yohei Watanabe, editors, PKC 2022, Part II, volume 13178 of LNCS, pages 468–497. March 2022. Springer, Cham. DOI: 10.1007/978-3-030-97131-1_16

Google Scholar ePrint

[KNR24]

Julia Kastner, Ky Nguyen, and Michael Reichle. Pairing-Free Blind Signatures from Standard Assumptions in the ROM. In Leonid Reyzin and Douglas Stebila, editors, CRYPTO 2024, Part I, volume 14920 of LNCS, pages 210–245. August 2024. Springer, Cham. DOI: 10.1007/978-3-031-68376-3_7

Google Scholar ePrint

[Nic19]

Jonas Nick. Blind signatures in scriptless scripts. Accessed: 2024-04-11. 2019.

Google Scholar ePrint

[NS01]

Phong Q. Nguyen and Igor Shparlinski. On the Insecurity of a Server-Aided RSA Protocol. In Colin Boyd, editor, ASIACRYPT 2001, volume 2248 of LNCS, pages 21–35. December 2001. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-45682-1_2

Google Scholar ePrint

[Sch01]

Claus-Peter Schnorr. Security of Blind Discrete Log Signatures against Interactive Attacks. In Sihan Qing, Tatsuaki Okamoto, and Jianying Zhou, editors, ICICS 01, volume 2229 of LNCS, pages 1–12. November 2001. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-45600-7_1

Google Scholar ePrint

[Sho97]

Victor Shoup. Lower Bounds for Discrete Logarithms and Related Problems. In Walter Fumy, editor, EUROCRYPT'97, volume 1233 of LNCS, pages 256–266. May 1997. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-69053-0_18

Google Scholar ePrint

[SPMS02]

Jacques Stern, David Pointcheval, John Malone-Lee, and Nigel P. Smart. Flaws in Applying Proof Methodologies to Signature Schemes. In Moti Yung, editor, CRYPTO 2002, volume 2442 of LNCS, pages 93–110. August 2002. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-45708-9_7

Google Scholar ePrint

[Wag02]

David Wagner. A Generalized Birthday Problem. In Moti Yung, editor, CRYPTO 2002, volume 2442 of LNCS, pages 288–303. August 2002. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-45708-9_19

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a3qj5w7sf

History

Submitted: 2024-07-05
Accepted: 2024-09-02
Published: 2024-10-07

How to cite

Franklin Harding and Jiayu Xu, Unforgeability of Blind Schnorr in the Limited Concurrency Setting. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/a3qj5w7sf.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-3-16,
    author = "Harding, Franklin and Xu, Jiayu",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Unforgeability of Blind Schnorr in the Limited Concurrency Setting",
    volume = "1",
    number = "3",
    date = "2024-10-07",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/a3qj5w7sf"
}

TY - JOUR
AU - Harding, Franklin
AU - Xu, Jiayu
PY  - 2024
TI  - Unforgeability of Blind Schnorr in the Limited Concurrency Setting
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 3
DO  - 10.62056/a3qj5w7sf
UR  - https://doi.org/10.62056/a3qj5w7sf
AB  - <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.</p><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. </p>
ER  -

Franklin Harding and Jiayu Xu, Unforgeability of Blind Schnorr in the Limited Concurrency Setting. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/a3qj5w7sf.