The many faces of Schnorr: a toolkit for the modular design of threshold Schnorr signatures
Authors
Victor Shoup
Victor Shoup
Offchain Labs, USA
victor at shoup dot net
victor at shoup dot net
Abstract
Recently, a number of highly optimized threshold signing protocols for Schnorr signatures have been proposed. While these proposals contain important new techniques, some of them present and analyze these techniques in very specific contexts, making it less than obvious how these techniques can be adapted to other contexts, or combined with one another. The main goal of this paper is to abstract out and extend in various ways some of these techniques, building a toolbox of techniques that can be easily combined in different ways and in different contexts. To this end, we present security results for various “enhanced” modes of attack on the Schnorr signature scheme in the non-distributed setting, and we demonstrate how to reduce the security in the distributed threshold setting to these enhanced modes of attack in the non-distributed setting. This results in a very modular approach to protocol design and analysis, which can be used to easily design new threshold Schnorr protocols that enjoy better security and/or performance properties than existing ones.
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, Advances in Cryptology - ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6-10, 2021, Proceedings, Part IV, volume 13093 of Lecture Notes in Computer Science, pages 587–617. 2021. Springer. DOI: 10.1007/978-3-030-92068-5_20 Also at https://eprint.iacr.org/2021/866
[BHK+24]
Fabrice Benhamouda, Shai Halevi, Hugo Krawczyk, Yiping Ma, and Tal Rabin. SPRINT: High-Throughput Robust Distributed Schnorr Signatures. In Marc Joye and Gregor Leander, editors, Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part V, volume 14655 of Lecture Notes in Computer Science, pages 62–91. 2024. Springer. DOI: 10.1007/978-3-031-58740-5_3 Also at https://eprint.iacr.org/2023/427
[BL22]
Jeremiah Blocki and Seunghoon Lee. On the Multi-user Security of Short Schnorr Signatures with Preprocessing. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part II, volume 13276 of Lecture Notes in Computer Science, pages 614–643. 2022. Springer. DOI: 10.1007/978-3-031-07085-3_21 Also at https://eprint.iacr.org/2019/1105
[BLL+22]
Fabrice Benhamouda, Tancrède Lepoint, Julian Loss, Michele Orrù, and Mariana Raykova. On the (in)Security of ROS. J. Cryptol., 35(4):25, 2022. Also at https://eprint.iacr.org/2020/945 DOI: 10.1007/s00145-022-09436-0
[BLS01]
Dan Boneh, Ben Lynn, and Hovav Shacham. Short Signatures from the Weil Pairing. In Colin Boyd, editor, Advances in Cryptology - ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, December 9-13, 2001, Proceedings, volume 2248 of Lecture Notes in Computer Science, pages 514–532. 2001. Springer. DOI: 10.1007/3-540-45682-1_30
[Bol03]
Alexandra Boldyreva. Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme. In Yvo Desmedt, editor, Public Key Cryptography - PKC 2003, 6th International Workshop on Theory and Practice in Public Key Cryptography, Miami, FL, USA, January 6-8, 2003, Proceedings, volume 2567 of Lecture Notes in Computer Science, pages 31–46. 2003. Springer. DOI: 10.1007/3-540-36288-6_3
[BS23]
Dan Boneh and Victor Shoup. A Graduate Course in Applied Cryptography (v0.6). 2023. Available at https://toc.cryptobook.us/
[BTZ22]
Mihir Bellare, Stefano Tessaro, and Chenzhi Zhu. Stronger Security for Non-Interactive Threshold Signatures: BLS and FROST. https://eprint.iacr.org/2022/833. Cryptology ePrint Archive, Paper 2022/833. 2022.
[Can20]
Ran Canetti. Universally Composable Security. J. ACM, 67(5):28:1–28:94, 2020. Also at https://eprint.iacr.org/2000/067 DOI: 10.1145/3402457
[CDH+21]
Jan Camenisch, Manu Drijvers, Timo Hanke, Yvonne-Anne Pignolet, Victor Shoup, and Dominic Williams. Internet Computer Consensus. https://eprint.iacr.org/2021/632. Cryptology ePrint Archive, Report 2021/632. 2021.
[{Cer}10]
Certicom Research. SEC 2: Recommended Elliptic Curve Domain Parameters. Version 2.0, http://www.secg.org/sec2-v2.pdf. 2010.
[CGG+20]
Ran Canetti, Rosario Gennaro, Steven Goldfeder, Nikolaos Makriyannis, and Udi Peled. UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts. In Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna, editors, CCS '20: 2020 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, USA, November 9-13, 2020, pages 1769–1787. 2020. ACM. DOI: 10.1145/3372297.3423367 Also at https://eprint.iacr.org/2021/060
[CKM21]
Elizabeth Crites, Chelsea Komlo, and Mary Maller. How to Prove Schnorr Assuming Schnorr: Security of Multi- and Threshold Signatures. https://eprint.iacr.org/2021/1375. Cryptology ePrint Archive, Paper 2021/1375. 2021.
[CL99]
Miguel Castro and Barbara Liskov. Practical Byzantine Fault Tolerance. In Margo I. Seltzer and Paul J. Leach, editors, Proceedings of the Third USENIX Symposium on Operating Systems Design and Implementation (OSDI), New Orleans, Louisiana, USA, February 22-25, 1999, pages 173–186. 1999. USENIX Association.
[CP17]
Ashish Choudhury and Arpita Patra. An Efficient Framework for Unconditionally Secure Multiparty Computation. IEEE Trans. Inf. Theory, 63(1):428–468, 2017. DOI: 10.1109/TIT.2016.2614685
[CP23]
Benjamin Y. Chan and Rafael Pass. Simplex Consensus: A Simple and Fast Consensus Protocol. In Guy N. Rothblum and Hoeteck Wee, editors, Theory of Cryptography - 21st International Conference, TCC 2023, volume 14372 of Lecture Notes in Computer Science, pages 452–479. 2023. Springer. DOI: 10.1007/978-3-031-48624-1_17 Also at https://eprint.iacr.org/2023/463
[DDL+24]
Sourav Das, Sisi Duan, Shengqi Liu, Atsuki Momose, Ling Ren, and Victor Shoup. Asynchronous Consensus without Trusted Setup or Public-Key Cryptography. In Bo Luo, Xiaojing Liao, Jun Xu, Engin Kirda, and David Lie, editors, Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, CCS 2024, Salt Lake City, UT, USA, October 14-18, 2024, pages 3242–3256. 2024. ACM. DOI: 10.1145/3658644.3670327 Also at https://eprint.iacr.org/2024/677
[DEF+19]
Manu Drijvers, Kasra Edalatnejad, Bryan Ford, Eike Kiltz, Julian Loss, Gregory Neven, and Igors Stepanovs. On the Security of Two-Round Multi-Signatures. In 2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019, pages 1084–1101. 2019. IEEE. DOI: 10.1109/SP.2019.00050 Also at https://eprint.iacr.org/2018/417
[DT22]
The DFINITY Team. The Internet Computer for Geeks. https://ia.cr/2022/087. Cryptology ePrint Archive, Report 2022/087. 2022.
[GJKR07]
Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin. Secure Distributed Key Generation for Discrete-Log Based Cryptosystems. J. Cryptol., 20(1):51–83, 2007. DOI: 10.1007/s00145-006-0347-3
[Gro21]
Jens Groth. Non-interactive distributed key generation and key resharing. https://eprint.iacr.org/2021/339. Cryptology ePrint Archive, Report 2021/339. 2021.
[GS22a]
Jens Groth and Victor Shoup. Design and analysis of a distributed ECDSA signing service. https://eprint.iacr.org/2022/506. Cryptology ePrint Archive, Report 2022/506. 2022.
[GS22b]
Jens Groth and Victor Shoup. On the Security of ECDSA with Additive Key Derivation and Presignatures. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part I, volume 13275 of Lecture Notes in Computer Science, pages 365–396. 2022. Springer. DOI: 10.1109/SP.2019.00050 Full version in Cryptology ePrint Archive, Report 2021/1330, https://eprint.iacr.org/2021/1330
[GS24]
Jens Groth and Victor Shoup. Fast Batched Asynchronous Distributed Key Generation. In Marc Joye and Gregor Leander, editors, Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part V, volume 14655 of Lecture Notes in Computer Science, pages 370–400. 2024. Springer. DOI: 10.1007/978-3-031-58740-5_13 Also at https://eprint.iacr.org/2023/1175
[HN06]
Martin Hirt and Jesper Buus Nielsen. Robust Multiparty Computation with Linear Communication Complexity. In Cynthia Dwork, editor, Advances in Cryptology - CRYPTO 2006, 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2006, Proceedings, volume 4117 of Lecture Notes in Computer Science, pages 463–482. 2006. Springer. DOI: 10.1007/11818175_28
[KG20]
Chelsea Komlo and Ian Goldberg. FROST: Flexible Round-Optimized Schnorr Threshold Signatures. In Orr Dunkelman, Michael J. Jacobson Jr., and Colin O'Flynn, editors, Selected Areas in Cryptography - SAC 2020 - 27th International Conference, Halifax, NS, Canada (Virtual Event), October 21-23, 2020, Revised Selected Papers, volume 12804 of Lecture Notes in Computer Science, pages 34–65. 2020. Springer. DOI: 10.1007/978-3-030-81652-0_2 Also at https://eprint.iacr.org/2020/852
[Mau05]
Ueli M. Maurer. Abstract Models of Computation in Cryptography. In Nigel P. Smart, editor, Cryptography and Coding, 10th IMA International Conference, Cirencester, UK, December 19-21, 2005, Proceedings, volume 3796 of Lecture Notes in Computer Science, pages 1–12. 2005. Springer. DOI: 10.1007/11586821_1
[NSW09]
Gregory Neven, Nigel P. Smart, and Bogdan Warinschi. Hash function requirements for Schnorr signatures. J. Math. Cryptol., 3(1):69–87, 2009. DOI: 10.1515/JMC.2009.004
[PS00]
David Pointcheval and Jacques Stern. Security Arguments for Digital Signatures and Blind Signatures. J. Cryptol., 13(3):361–396, 2000. DOI: 10.1007/S001450010003
[RRJ+22]
Tim Ruffing, Viktoria Ronge, Elliott Jin, Jonas Schneider-Bensch, and Dominique Schröder. ROAST: Robust Asynchronous Schnorr Threshold Signatures. https://eprint.iacr.org/2022/550. Cryptology ePrint Archive, Paper 2022/550. 2022.
[Sho97]
Victor Shoup. Lower Bounds for Discrete Logarithms and Related Problems. In Walter Fumy, editor, Advances in Cryptology - EUROCRYPT '97, International Conference on the Theory and Application of Cryptographic Techniques, Konstanz, Germany, May 11-15, 1997, Proceeding, volume 1233 of Lecture Notes in Computer Science, pages 256–266. 1997. Springer. DOI: 10.1007/3-540-69053-0_18
[Sho00]
Victor Shoup. Practical Threshold Signatures. In Bart Preneel, editor, Advances in Cryptology - EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000, Proceeding, volume 1807 of Lecture Notes in Computer Science, pages 207–220. 2000. Springer. DOI: 10.1007/3-540-45539-6_15 Also at https://eprint.iacr.org/1999/011
[Sho24]
Victor Shoup. A Theoretical Take on a Practical Consensus Protocol. Cryptology ePrint Archive, Paper 2024/696. 2024.
[SS24]
Victor Shoup and Nigel P. Smart. Lightweight Asynchronous Verifiable Secret Sharing with Optimal Resilience. J. Cryptol., 37(3):27, 2024. Also at https://eprint.iacr.org/2023/536 DOI: 10.1007/S00145-024-09505-6
[Wag02]
David A. Wagner. A Generalized Birthday Problem. In Moti Yung, editor, Advances in Cryptology - CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002, Proceedings, volume 2442 of Lecture Notes in Computer Science, pages 288–303. 2002. Springer. DOI: 10.1007/3-540-45708-9_19
[Wui20]
P. Wuille. BIP32: Hierarchical deterministic wallets. https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki. 2020.
[Zha22]
Mark Zhandry. To Label, or Not To Label (in Generic Groups). In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part III, volume 13509 of Lecture Notes in Computer Science, pages 66–96. 2022. Springer. DOI: 10.1007/978-3-031-15982-4_3 Also at https://eprint.iacr.org/2022/226
PDF
History
Submitted: 2025-01-13
Accepted: 2025-03-11
Published: 2025-04-08
Accepted: 2025-03-11
Published: 2025-04-08
How to cite
Victor Shoup, The many faces of Schnorr: a toolkit for the modular design of threshold Schnorr signatures. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/ahsgvurzn.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.