Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

SPRINT: High-Throughput Robust Distributed Schnorr Signatures

  • Conference paper
  • First Online:
Advances in Cryptology – EUROCRYPT 2024 (EUROCRYPT 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14655))

  • 714 Accesses

Abstract

We describe robust high-throughput threshold protocols for generating Schnorr signatures in an asynchronous setting with potentially hundreds of parties. The protocols run a single message-independent interactive ephemeral randomness generation procedure (i.e., DKG) followed by non-interactive signature generation for multiple messages, at a communication cost similar to one execution of a synchronous non-robust protocol in prior work (e.g., Gennaro et al.) and with a large number of parties (ranging from few tens to hundreds and more). Our protocols extend seamlessly to the dynamic/proactive setting where each run of the protocol uses a new committee with refreshed shares of the secret key; in particular, they support large committees periodically sampled from among the overall population of parties and the required secret state is transferred to the selected parties. The protocols work over a broadcast channel and are robust (provide guaranteed output delivery) even over asynchronous networks.

The combination of these features makes our protocols a good match for implementing a signature service over a public blockchain with many validators, where guaranteed output delivery is an absolute must. In that setting, there is a system-wide public key, where the corresponding secret signature key is distributed among the validators. Clients can submit messages (under suitable controls, e.g., smart contracts), and authorized messages are signed relative to the global public key.

Asymptotically, when running with committees of n parties, our protocols can generate \(\varOmega (n^2)\) signatures per run, while providing resilience against \(\varOmega (n)\) corrupted nodes and broadcasting only \(O(n^2)\) group elements and scalars (hence O(1) elements per signature).

We prove the security of our protocols via a reduction to the hardness of the discrete logarithm problem in the random oracle model.

F. Benhamouda, S. Halevi, H. Krawczyk and T. Rabin—Work done prior to joining Amazon, partially while at the Algorand Foundation.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 119.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 139.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    SPRINT is a permuted acronym for “Robust Threshold Schnorr with Super-INvertible Packing”.

  2. 2.

    Throughout the paper, we use a DKG protocol for different purposes, including ephemeral Schnorr randomness generation, long-term key generation, and proactive refreshment.

  3. 3.

    Our use of an underlying broadcast channel also obviates the need to find a biclique of dealers and shareholders, which is sometimes needed when giving up completeness, and which can be computationally hard (cf. [2]).

  4. 4.

    We also describe some optimizations related to faster multiplication by super-invertible matrices in our full version [4, Appendix B].

  5. 5.

    Since our techniques apply in the asynchronous setting, they inherently require \(n\ge 3t+1\); see our full version [4, Appendix H].

  6. 6.

    Recall we use DKG to refer to distributed key generation for long-term keys, for generating ephemeral randomness as needed in Schnorr signatures, and also for proactive refreshment.

  7. 7.

    Broadcasting messages of size \(\ell \ge n\lambda \) bits, as done in our protocol, can be achieved using a total point-to-point communication of \(O(\ell n)\) bits [14, 29].

  8. 8.

    We use additive notation for group operations, but sometimes use the traditional exponentiation terminology.

  9. 9.

    \(p= 2^{252} + 27742317777372353535851937790883648493\) and the factorization of \(p-1\) is \(2^2 \times 3 \times 11 \times 198211423230930754013084525763697 \times 276602624281642239937218680557139826668747\).

  10. 10.

    The ECFFT solution performs better for \(b=t\) is a power of two. But we show in the full version [4, Appendix B.2] that it also works for general b and t, with a cost depending on the smallest power of 2 larger or equal to \(\max (b,t)\).

  11. 11.

    We suppress here the index u, which is irrelevant for this discussion.

  12. 12.

    As described here, the protocol only works for resharing a packed vector of the form \((s,s,\ldots ,s)\). But it is not very hard to extend it to reshare arbitrary packed vectors (using somewhat higher-degree polynomials), see the full version [4, Appendix I].

  13. 13.

    Recall that in the dynamic setting we use an agreement protocol that provides stronger guarantees about the size of \(\textsf{QUAL}\), than in the static setting. Namely \(|\textsf{QUAL}| \ge d_1\) instead of just \(|\textsf{QUAL}| + |\textsf{BAD}| \ge d_1\). See Sect. 2.2.

  14. 14.

    More precisely, there is a public commitment \(\hat{\textbf{F}}\) of \(\textbf{F}\) from which anyone can derive a Feldman commitment \(\sigma _i \cdot G\) of \(\sigma _i\). See Sect. 2.1.

  15. 15.

    We need \(n \ge 657\) to get (statistical) safety failure \(<2^{-80}\) (and liveness failure \(< 2^{-11}\)), without packing (i.e., \(a = 1\)). Setting \(a=40\) only requires \(n \ge 992\) while multiplying the number of messages that can be signed by 40 and while providing the same safety guarantees. This is because we have less than \((n-1)/3\) corrupted parties selected in each committee with overwhelming probability. See details in the full version [4, Appendix D.1].

  16. 16.

    E.g., it assumes human intervention to replace or reboot servers, to export public keys from new servers or servers that choose new (encryption) keys, etc. (see [23]).

  17. 17.

    The proof-of-decryption can be very simple: a proof of equality of discrete logs if using ElGamal encryption for the shares, or showing an inverted RSA ciphertext if using RSA-based encryption.

References

  1. Abraham, I., Jovanovic, P., Maller, M., Meiklejohn, S., Stern, G.: Bingo: adaptivity and asynchrony in verifiable secret sharing and distributed key generation. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO (2023). https://doi.org/10.1007/978-3-031-38557-5_2

  2. Ben-Or, M., Canetti, R., Goldreich, O.: Asynchronous secure computation. In: 25th ACM STOC, pp. 52–61. ACM Press (May 1993). https://doi.org/10.1145/167088.167109

  3. Ben-Sasson, E., Carmon, D., Kopparty, S., Levit, D.: Elliptic curve fast Fourier transform (ECFFT) part I: low-degree extension in time O(n log n) over all finite fields. In: Bansal, N., Nagarajan, V. (eds.) SODA 2023, Florence, Italy, January 22–25, 2023, pp. 700–737. SIAM (2023). https://doi.org/10.1137/1.9781611977554.ch30

  4. Benhamouda, F., Halevi, S., Krawczyk, H., Ma, Y., Rabin, T.: SPRINT: high-throughput robust distributed Schnorr signatures. Cryptology ePrint Archive (2023). https://eprint.iacr.org/2023/427

  5. Benhamouda, F., Lepoint, T., Loss, J., Orrù, M., Raykova, M.: On the (in)security of ROS. J. Cryptol. 35(4), 25 (2022). https://doi.org/10.1007/s00145-022-09436-0

    Article  MathSciNet  Google Scholar 

  6. Borgeaud, W.: ECFFT algorithms on the BN254 base field (2023). https://github.com/wborgeaud/ecfft-bn254

  7. Chen, J., Micali, S.: Algorand: a secure and efficient distributed ledger. Theor. Comput. Sci. (2019). https://doi.org/10.1016/j.tcs.2019.02.001

    Article  MathSciNet  Google Scholar 

  8. Crites, E.C., Komlo, C., Maller, M.: How to prove Schnorr assuming schnorr: security of multi- and threshold signatures. Cryptology ePrint Archive (2021). https://eprint.iacr.org/2021/1375

  9. Das, S., Xiang, Z., Kokoris-Kogias, L., Ren, L.: Practical asynchronous high-threshold distributed key generation and distributed polynomial sampling. USENIX Security (2023)

    Google Scholar 

  10. Das, S., Yurek, T., Xiang, Z., Miller, A.K., Kokoris-Kogias, L., Ren, L.: Practical asynchronous distributed key generation. In: 2022 IEEE Symposium on Security and Privacy, pp. 2518–2534. IEEE Computer Society Press (May 2022). https://doi.org/10.1109/SP46214.2022.9833584

  11. Drijvers, M., Edalatnejad, K., Ford, B., Kiltz, E., Loss, J., Neven, G., Stepanovs, I.: On the security of two-round multi-signatures. In: 2019 IEEE Symposium on Security and Privacy (SP), pp. 1084–1101 (2019). https://doi.org/10.1109/SP.2019.00050

  12. Feldman, P.: A practical scheme for non-interactive verifiable secret sharing. In: 28th FOCS, pp. 427–437. IEEE Computer Society Press (Oct 1987). https://doi.org/10.1109/SFCS.1987.4

  13. Franklin, M.K., Yung, M.: Communication complexity of secure computation (extended abstract). In: 24th ACM STOC, pp. 699–710. ACM Press (May 1992). https://doi.org/10.1145/129712.129780

  14. Ganesh, C., Patra, A.: Optimal extension protocols for byzantine broadcast and agreement. Distributed Comput. 34(1), 59–77 (2021). https://doi.org/10.1007/s00446-020-00384-1

    Article  MathSciNet  Google Scholar 

  15. Garillot, F., Kondi, Y., Mohassel, P., Nikolaenko, V.: Threshold Schnorr with stateless deterministic signing from standard assumptions. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12825, pp. 127–156. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84242-0_6

    Chapter  Google Scholar 

  16. Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Secure distributed key generation for discrete-log based cryptosystems. J. Cryptol. 20(1), 51–83 (Jan 2007). https://doi.org/10.1007/s00145-006-0347-3

  17. Gennaro, R., Rabin, M.O., Rabin, T.: Simplified VSS and fast-track multiparty computations with applications to threshold cryptography. In: Coan, B.A., Afek, Y. (eds.) 17th ACM PODC, pp. 101–111. ACM (Jun / Jul 1998). https://doi.org/10.1145/277697.277716

  18. Goyal, V., Polychroniadou, A., Song, Y.: Sharing transformation and dishonest majority MPC with packed secret sharing. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO (2022). https://doi.org/10.1007/978-3-031-15985-5_1

  19. Groth, J., Shoup, V.: Design and analysis of a distributed ECDSA signing service. Cryptology ePrint Archive, Report 2022/506 (2022). https://eprint.iacr.org/2022/506

  20. Groth, J., Shoup, V.: On the security of ECDSA with additive key derivation and presignatures. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part I. LNCS, vol. 13275, pp. 365–396. Springer, Heidelberg (May / Jun 2022). https://doi.org/10.1007/978-3-031-06944-4_13

  21. Groth, J., Shoup, V.: Fast batched asynchronous distributed key generation. Cryptology ePrint Archive (2023). https://eprint.iacr.org/2023/1175

  22. Herzberg, A., Jakobsson, M., Jarecki, S., Krawczyk, H., Yung, M.: Proactive public key and signature systems. In: Graveman, R., Janson, P.A., Neuman, C., Gong, L. (eds.) ACM CCS 97, pp. 100–110. ACM Press (Apr 1997). https://doi.org/10.1145/266420.266442

  23. Herzberg, A., Jarecki, S., Krawczyk, H., Yung, M.: Proactive secret sharing or: how to cope with perpetual leakage. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 339–352. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-44750-4_27

    Chapter  Google Scholar 

  24. Hirt, M., Nielsen, J.B.: Robust multiparty computation with linear communication complexity. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 463–482. Springer, Heidelberg (2006). https://doi.org/10.1007/11818175_28

    Chapter  Google Scholar 

  25. Joshi, S., Pandey, D., Srinathan, K.: Atssia: asynchronous truly-threshold schnorr signing for inconsistent availability. In: Park, J.H., Seo, S.H. (eds.) Information Security and Cryptology - ICISC 2021, pp. 71–91. Springer International Publishing, Cham (2022)

    Chapter  Google Scholar 

  26. Kate, A., Zaverucha, G.M., Goldberg, I.: Constant-size commitments to polynomials and their applications. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 177–194. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_11

    Chapter  Google Scholar 

  27. Komlo, C., Goldberg, I.: FROST: flexible round-optimized schnorr threshold signatures. In: Dunkelman, O., Jacobson, Jr., M.J., O’Flynn, C. (eds.) SAC 2020. LNCS, vol. 12804, pp. 34–65. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-81652-0_2

    Chapter  Google Scholar 

  28. Lindell, Y.: Simple three-round multiparty schnorr signing with full simulatability. Cryptology ePrint Archive, Report 2022/374 (2022). https://eprint.iacr.org/2022/374

  29. Nayak, K., Ren, L., Shi, E., Vaidya, N.H., Xiang, Z.: Improved extension protocols for byzantine broadcast and agreement. In: Attiya, H. (ed.) 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference. LIPIcs, vol. 179, pp. 28:1–28:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020). https://doi.org/10.4230/LIPIcs.DISC.2020.28

  30. Neji, W., Blibech, K., Ben Rajeb, N.: Distributed key generation protocol with a new complaint management strategy. Security Commun. Netw. 9(17), 4585–4595 (2016). https://doi.org/10.1002/sec.1651

    Article  Google Scholar 

  31. Ostrovsky, R., Yung, M.: How to withstand mobile virus attacks (extended abstract). In: Logrippo, L. (ed.) 10th ACM PODC., pp. 51–59. ACM (Aug 1991). https://doi.org/10.1145/112600.112605

  32. Patra, A., Choudhary, A., Rangan, C.P.: Efficient statistical asynchronous verifiable secret sharing with optimal resilience. In: Kurosawa, K. (ed.) ICITS 09. LNCS, vol. 5973, pp. 74–92. Springer, Heidelberg (Dec 2010). https://doi.org/10.1007/978-3-642-14496-7_7

  33. Pedersen, T.P.: A threshold cryptosystem without a trusted party. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 522–526. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-46416-6_47

    Chapter  Google Scholar 

  34. Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_9

    Chapter  Google Scholar 

  35. Ruffing, T., Ronge, V., Jin, E., Schneider-Bensch, J., Schröder, D.: ROAST: robust asynchronous schnorr threshold signatures. In: Yin, H., Stavrou, A., Cremers, C., Shi, E. (eds.) ACM CCS 2022, pp. 2551–2564. ACM Press (Nov 2022). https://doi.org/10.1145/3548606.3560583

  36. Shoup, V.: The many faces of Schnorr. Cryptology ePrint Archive (2023). https://eprint.iacr.org/2023/1019

  37. Stinson, D.R., Strobl, R.: Provably secure distributed Schnorr signatures and a (t, n) threshold scheme for implicit certificates. In: Varadharajan, V., Mu, Y. (eds.) ACISP 2001. LNCS, vol. 2119, pp. 417–434. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-47719-5_33

    Chapter  Google Scholar 

  38. Yurek, T., Luo, L., Fairoze, J., Kate, A., Miller, A.K.: hbACSS: How to robustly share many secrets. In: 29th Annual Network and Distributed System Security Symposium, NDSS 2022, San Diego, California, USA, April 24-28, 2022 (2022)

    Google Scholar 

Download references

Acknowledgements

We thank Victor Shoup for mentioning to us the solution using a Vandermonde matrix for fast multiplication by a super-invertible matrix.

Author information

Authors and Affiliations

  1. AWS, New York, NY, USA

    Fabrice Benhamouda, Shai Halevi, Hugo Krawczyk & Tal Rabin

  2. University of Pennsylvania, Philadelphia, PA, USA

    Yiping Ma & Tal Rabin

Authors
  1. Fabrice Benhamouda
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shai Halevi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hugo Krawczyk
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Yiping Ma
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Tal Rabin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Fabrice Benhamouda .

Editor information

Editors and Affiliations

  1. Zama, Paris, France

    Marc Joye

  2. Ruhr University Bochum, Bochum, Germany

    Gregor Leander

Rights and permissions

Reprints and permissions

Copyright information

© 2024 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Benhamouda, F., Halevi, S., Krawczyk, H., Ma, Y., Rabin, T. (2024). SPRINT: High-Throughput Robust Distributed Schnorr Signatures. In: Joye, M., Leander, G. (eds) Advances in Cryptology – EUROCRYPT 2024. EUROCRYPT 2024. Lecture Notes in Computer Science, vol 14655. Springer, Cham. https://doi.org/10.1007/978-3-031-58740-5_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-58740-5_3

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-58739-9

  • Online ISBN: 978-3-031-58740-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation