Simple Three-Round Multiparty Schnorr Signing with Full Simulatability

Yehuda Lindell

doi:10.62056/a36c0l5vt

Simple Three-Round Multiparty Schnorr Signing with Full Simulatability

Authors

Yehuda Lindell

Coinbase, USA
yehuda dot lindell at gmail dot com

Abstract

In a multiparty signing protocol, also known as a threshold signature scheme, the private signing key is shared amongst a set of parties and only a quorum of those parties can generate a signature. Research on multiparty signing has been growing in popularity recently due to its application to cryptocurrencies. Most work has focused on reducing the number of rounds to two, and as a result: (a) are not fully simulatable in the sense of MPC real/ideal security definitions, and/or (b) are not secure under concurrent composition, and/or (c) utilize non-standard assumptions of different types in their proofs of security. In this paper, we describe a simple three-round multiparty protocol for Schnorr signatures that is secure for any number of corrupted parties; i.e., in the setting of a dishonest majority. The protocol is fully simulatable, secure under concurrent composition, and proven secure in the standard model or random-oracle model (depending on the instantiations of the commitment and zero-knowledge primitives). The protocol realizes an ideal Schnorr signing functionality with perfect security in the ideal commitment and zero-knowledge hybrid model (and thus the only assumptions needed are for realizing these functionalities).

In our presentation, we do not assume that all parties begin with the message to be signed, the identities of the participating parties and a unique common session identifier, since this is often not the case in practice. Rather, the parties achieve consensus on these parameters as the protocol progresses.

References

[AB21]

Handan Kilinç Alper and Jeffrey Burdges. Two-round trip schnorr multi-signatures via delinearized witnesses. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part I, volume 12825 of Lecture Notes in Computer Science, 157–188. Springer, 2021. https://doi.org/10.1007/978-3-030-84242-0_7.

Google Scholar ePrint

[BCPV13]

Olivier Blazy, Céline Chevalier, David Pointcheval, and Damien Vergnaud. Analysis and improvement of lindell's uc-secure commitment schemes. In Michael J. Jacobson Jr., Michael E. Locasto, Payman Mohassel, and Reihaneh Safavi-Naini, editors, Applied Cryptography and Network Security - 11th International Conference, ACNS 2013, Banff, AB, Canada, June 25-28, 2013. Proceedings, volume 7954 of Lecture Notes in Computer Science, 534–551. Springer, 2013. https://doi.org/10.1007/978-3-642-38980-1_34.

Google Scholar ePrint

[BDL⁺12]

Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. High-speed high-security signatures. J. Cryptogr. Eng., 2(2):77–89, 2012. https://doi.org/10.1007/S13389-012-0027-1.

Google Scholar ePrint

[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. https://doi.org/10.1007/S00145-022-09436-0.

Google Scholar ePrint

[BN06]

Mihir Bellare and Gregory Neven. Multi-signatures in the plain public-key model and a general forking lemma. In Ari Juels, Rebecca N. Wright, and Sabrina De Capitani di Vimercati, editors, Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS 2006, Alexandria, VA, USA, October 30 - November 3, 2006, 390–399. ACM, 2006. https://doi.org/10.1145/1180405.1180453.

Google Scholar ePrint

[Boy89]

Colin Boyd. Digital multisignatures. Proc. IMA Conf. Crypto. Coding, 1989, pages 241–246, 1989.

Google Scholar ePrint

[Can00]

Ran Canetti. Security and composition of multiparty cryptographic protocols. J. Cryptol., 13(1):143–202, 2000. https://doi.org/10.1007/S001459910006.

Google Scholar ePrint

[Can01]

Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, 136–145. IEEE Computer Society, 2001. https://doi.org/10.1109/SFCS.2001.959888.

Google Scholar ePrint

[CCL15]

Ran Canetti, Asaf Cohen, and Yehuda Lindell. A simpler variant of universally composable security for standard multiparty computation. In Rosario Gennaro and Matthew Robshaw, editors, Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II, volume 9216 of Lecture Notes in Computer Science, 3–22. Springer, 2015. https://doi.org/10.1007/978-3-662-48000-7_1.

Google Scholar ePrint

[CKM21]

Elizabeth C. Crites, Chelsea Komlo, and Mary Maller. How to prove schnorr assuming schnorr: security of multi- and threshold signatures. IACR Cryptol. ePrint Arch., pages 1375, 2021.

Google Scholar ePrint

[CKM23]

Elizabeth C. Crites, Chelsea Komlo, and Mary Maller. Fully adaptive schnorr threshold signatures. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part I, volume 14081 of Lecture Notes in Computer Science, 678–709. Springer, 2023. https://doi.org/10.1007/978-3-031-38557-5_22.

Google Scholar ePrint

[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, 1084–1101. IEEE, 2019. https://doi.org/10.1109/SP.2019.00050.

Google Scholar ePrint

[Des87]

Yvo Desmedt. Society and group oriented cryptography: A new concept. In Carl Pomerance, editor, Advances in Cryptology - CRYPTO '87, A Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, California, USA, August 16-20, 1987, Proceedings, volume 293 of Lecture Notes in Computer Science, 120–127. Springer, 1987. https://doi.org/10.1007/3-540-48184-2_8.

Google Scholar ePrint

[DF89]

Yvo Desmedt and Yair Frankel. Threshold cryptosystems. In Gilles Brassard, editor, Advances in Cryptology - CRYPTO '89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings, volume 435 of Lecture Notes in Computer Science, 307–315. Springer, 1989. https://doi.org/10.1007/0-387-34805-0_28.

Google Scholar ePrint

[Fel87]

Paul Feldman. A practical scheme for non-interactive verifiable secret sharing. In 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987, 427–437. IEEE Computer Society, 1987. https://doi.org/10.1109/SFCS.1987.4.

Google Scholar ePrint

[Fis05]

Marc Fischlin. Communication-efficient non-interactive proofs of knowledge with online extractors. In Victor Shoup, editor, Advances in Cryptology - CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings, volume 3621 of Lecture Notes in Computer Science, 152–168. Springer, 2005. https://doi.org/10.1007/11535218_10.

Google Scholar ePrint

[Fuj16]

Eiichiro Fujisaki. Improving practical uc-secure commitments based on the DDH assumption. In Vassilis Zikas and Roberto De Prisco, editors, Security and Cryptography for Networks - 10th International Conference, SCN 2016, Amalfi, Italy, August 31 - September 2, 2016, Proceedings, volume 9841 of Lecture Notes in Computer Science, 257–272. Springer, 2016. https://doi.org/10.1007/978-3-319-44618-9_14.

Google Scholar ePrint

[GGN16]

Rosario Gennaro, Steven Goldfeder, and Arvind Narayanan. Threshold-optimal DSA/ECDSA signatures and an application to bitcoin wallet security. In Mark Manulis, Ahmad-Reza Sadeghi, and Steve A. Schneider, editors, Applied Cryptography and Network Security - 14th International Conference, ACNS 2016, Guildford, UK, June 19-22, 2016. Proceedings, volume 9696 of Lecture Notes in Computer Science, 156–174. Springer, 2016. https://doi.org/10.1007/978-3-319-39555-5_9.

Google Scholar ePrint

[GJKR96]

Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin. Robust threshold DSS signatures. In Ueli M. Maurer, editor, Advances in Cryptology - EUROCRYPT '96, International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, May 12-16, 1996, Proceeding, volume 1070 of Lecture Notes in Computer Science, 354–371. Springer, 1996. https://doi.org/10.1007/3-540-68339-9_31.

Google Scholar ePrint

[GL05]

Shafi Goldwasser and Yehuda Lindell. Secure multi-party computation without agreement. J. Cryptol., 18(3):247–287, 2005. https://doi.org/10.1007/S00145-005-0319-Z.

Google Scholar ePrint

[GLSY04]

Rosario Gennaro, Darren Leigh, Ravi Sundaram, and William S. Yerazunis. Batching schnorr identification scheme with applications to privacy-preserving authorization and low-bandwidth communication devices. In Pil Joong Lee, editor, Advances in Cryptology - ASIACRYPT 2004, 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, December 5-9, 2004, Proceedings, volume 3329 of Lecture Notes in Computer Science, 276–292. Springer, 2004. https://doi.org/10.1007/978-3-540-30539-2_20.

Google Scholar ePrint

[Gol04]

Oded Goldreich. The Foundations of Cryptography - Volume 2: Basic Applications. Cambridge University Press, 2004. ISBN 0-521-83084-2. https://doi.org/10.1017/CBO9780511721656.

Google Scholar ePrint

[HL10]

Carmit Hazay and Yehuda Lindell. Efficient Secure Two-Party Protocols - Techniques and Constructions. Information Security and Cryptography. Springer, 2010. ISBN 978-3-642-14302-1. https://doi.org/10.1007/978-3-642-14303-8.

Google Scholar ePrint

[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, 34–65. Springer, 2020. https://doi.org/10.1007/978-3-030-81652-0_2.

Google Scholar ePrint

[KLR10]

Eyal Kushilevitz, Yehuda Lindell, and Tal Rabin. Information-theoretically secure protocols and security under composition. SIAM J. Comput., 39(5):2090–2112, 2010. https://doi.org/10.1137/090755886.

Google Scholar ePrint

[Lin11]

Yehuda Lindell. Highly-efficient universally-composable commitments based on the DDH assumption. In Kenneth G. Paterson, editor, Advances in Cryptology - EUROCRYPT 2011 - 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15-19, 2011. Proceedings, volume 6632 of Lecture Notes in Computer Science, 446–466. Springer, 2011. https://doi.org/10.1007/978-3-642-20465-4_25.

Google Scholar ePrint

[Lin17]

Yehuda Lindell. Fast secure two-party ECDSA signing. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part II, volume 10402 of Lecture Notes in Computer Science, 613–644. Springer, 2017. https://doi.org/10.1007/978-3-319-63715-0_21.

Google Scholar ePrint

[Mak22]

Nikolaos Makriyannis. On the classic protocol for MPC schnorr signatures. IACR Cryptol. ePrint Arch., pages 1332, 2022.

Google Scholar ePrint

[MOR01]

Silvio Micali, Kazuo Ohta, and Leonid Reyzin. Accountable-subgroup multisignatures. In Michael K. Reiter and Pierangela Samarati, editors, CCS 2001, Proceedings of the 8th ACM Conference on Computer and Communications Security, Philadelphia, Pennsylvania, USA, November 6-8, 2001, 245–254. ACM, 2001. https://doi.org/10.1145/501983.502017.

Google Scholar ePrint

[MR01]

Philip D. MacKenzie and Michael K. Reiter. Two-party generation of DSA signatures. In Joe Kilian, editor, Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19-23, 2001, Proceedings, volume 2139 of Lecture Notes in Computer Science, 137–154. Springer, 2001. https://doi.org/10.1007/3-540-44647-8_8.

Google Scholar ePrint

[NKDM03]

Antonio Nicolosi, Maxwell N. Krohn, Yevgeniy Dodis, and David Mazières. Proactive two-party signatures for user authentication. In Proceedings of the Network and Distributed System Security Symposium, NDSS 2003, San Diego, California, USA. The Internet Society, 2003.

Google Scholar ePrint

[NRS21]

Jonas Nick, Tim Ruffing, and Yannick Seurin. Musig2: simple two-round schnorr multi-signatures. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part I, volume 12825 of Lecture Notes in Computer Science, 189–221. Springer, 2021. https://doi.org/10.1007/978-3-030-84242-0_8.

Google Scholar ePrint

[Sch89]

Claus-Peter Schnorr. Efficient identification and signatures for smart cards. In Gilles Brassard, editor, Advances in Cryptology - CRYPTO '89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings, volume 435 of Lecture Notes in Computer Science, 239–252. Springer, 1989. https://doi.org/10.1007/0-387-34805-0_22.

Google Scholar ePrint

[SG02]

Victor Shoup and Rosario Gennaro. Securing threshold cryptosystems against chosen ciphertext attack. J. Cryptol., 15(2):75–96, 2002. https://doi.org/10.1007/S00145-001-0020-9.

Google Scholar ePrint

[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, 207–220. Springer, 2000. https://doi.org/10.1007/3-540-45539-6_15.

Google Scholar ePrint

[SS01]

Douglas R. Stinson and Reto Strobl. Provably secure distributed schnorr signatures and a (t, n) threshold scheme for implicit certificates. In Vijay Varadharajan and Yi Mu, editors, Information Security and Privacy, 6th Australasian Conference, ACISP 2001, Sydney, Australia, July 11-13, 2001, Proceedings, volume 2119 of Lecture Notes in Computer Science, 417–434. Springer, 2001. https://doi.org/10.1007/3-540-47719-5_33.

Google Scholar ePrint

[Wui12]

Pieter Wuille. Bip32 – hierarchical deterministic wallets. 2012.

Google Scholar ePrint

PDF Open access

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

History

Submitted: 2024-01-08
Accepted: 2024-03-05
Published: 2024-04-09

How to cite

Yehuda Lindell, "Simple Three-Round Multiparty Schnorr Signing with Full Simulatability," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/a36c0l5vt.

License

Copyright is held by the author(s)

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

@article{CiC-1-1-25,
    author = "Lindell, Yehuda",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Simple Three-Round Multiparty Schnorr Signing with Full Simulatability",
    volume = "1",
    number = "1",
    date = "2024-04-09",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/a36c0l5vt"
}

TY - JOUR
AU - Lindell, Yehuda
PY  - 2024
TI  - Simple Three-Round Multiparty Schnorr Signing with Full Simulatability
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 1
DO  - 10.62056/a36c0l5vt
UR  - https://doi.org/10.62056/a36c0l5vt
AB  - <p>In a multiparty signing protocol, also known as a threshold signature scheme, the private signing key is shared amongst a set of parties and only a quorum of those parties can generate a signature. Research on multiparty signing has been growing in popularity recently due to its application to cryptocurrencies. Most work has focused on reducing the number of rounds to two, and as a result: (a) are not fully simulatable in the sense of MPC real/ideal security definitions, and/or (b) are not secure under concurrent composition, and/or (c) utilize non-standard assumptions of different types in their proofs of security. In this paper, we describe a simple three-round multiparty protocol for Schnorr signatures that is secure for any number of corrupted parties; i.e., in the setting of a dishonest majority. The protocol is fully simulatable, secure under concurrent composition, and proven secure in the standard model or random-oracle model (depending on the instantiations of the commitment and zero-knowledge primitives). The protocol realizes an ideal Schnorr signing functionality with perfect security in the ideal commitment and zero-knowledge hybrid model (and thus the only assumptions needed are for realizing these functionalities).</p><p>In our presentation, we do not assume that all parties begin with the message to be signed, the identities of the participating parties and a unique common session identifier, since this is often not the case in practice. Rather, the parties achieve consensus on these parameters as the protocol progresses. </p>
ER  -

Yehuda Lindell, "Simple Three-Round Multiparty Schnorr Signing with Full Simulatability," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/a36c0l5vt.