Fast Multiparty Threshold ECDSA with Fast Trustless Setup

ABSTRACT

A threshold signature scheme enables distributed signing among n players such that any subgroup of size $t+1$ can sign, whereas any group with t or fewer players cannot. While there exist previous threshold schemes for the ECDSA signature scheme, we are the first protocol that supports multiparty signatures for any $t łeq n$ with an efficient dealerless key generation. Our protocol is faster than previous solutions and significantly reduces the communication complexity as well. We prove our scheme secure against malicious adversaries with a dishonest majority. We implemented our protocol, demonstrating its efficiency and suitability to be deployed in practice.

References

1. Judit Bar-Ilan and Donald Beaver. 1989. Non-cryptographic fault-tolerant computing in constant number of rounds of interaction. In Proceedings of the eighth annual ACM Symposium on Principles of distributed computing. ACM, 201--209.
2. Niko Barić and Birgit Pfitzmann. 1997. Collision-free accumulators and fail-stop signature schemes without trees. In International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 480--494.
3. Dan Boneh. 2011. Digital signature standard. Encyclopedia of cryptography and security. Springer, 347--347.
4. Dan Boneh, Rosario Gennaro, and Steven Goldfeder. 2017. Using level-1 homomorphic encryption to improve threshold dsa signatures for bitcoin wallet security. In Latincrypt .
5. Fabrice Boudot. 2000. Efficient proofs that a committed number lies in an interval. In International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 431--444.
6. Ran Canetti, Rosario Gennaro, Stanisław Jarecki, Hugo Krawczyk, and Tal Rabin. 1999. Adaptive security for threshold cryptosystems. In Annual International Cryptology Conference . Springer, 98--116.
7. Ran Canetti and Shafi Goldwasser. 1999. An Efficient Threshold Public Key Cryptosystem Secure Against Adaptive Chosen Ciphertext Attack. In Advances in Cryptology - EUROCRYPT '99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, May 2--6, 1999, Proceeding . 90--106.
8. Ivan Damgard and Jens Groth. 2003. Non-interactive and reusable non-malleable commitment schemes. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing. ACM, 426--437.
9. Ivan Damgård, Marcel Keller, Enrique Larraia, Christian Miles, and Nigel P Smart. 2012. Implementing AES via an actively/covertly secure dishonest-majority MPC protocol. In International Conference on Security and Cryptography for Networks. Springer, 241--263.
10. Giovanni Di Crescenzo, Yuval Ishai, and Rafail Ostrovsky. 1998. Non-interactive and non-malleable commitment. In Proceedings of the thirtieth annual ACM symposium on Theory of computing. ACM, 141--150.
11. Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky, and Adam Smith. 2001. Efficient and non-interactive non-malleable commitment. In International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 40--59.
12. Jack Doerner, Yashvanth Kondi, Eysa Lee, et almbox. 2018. Secure Two-party Threshold ECDSA from ECDSA Assumptions. In IEEE Symposium on Security and Privacy. IEEE, 0.
13. D Dolev, C Dwork, and M Naor. 1991. Non-malleable cryptography,". In Proceedings of the 23rd Annual Symposium on the Theory of Computing, ACM .
14. Paul Feldman. 1987. A practical scheme for non-interactive verifiable secret sharing. In Foundations of Computer Science, 1987., 28th Annual Symposium on. IEEE, 427--438.
15. Eiichiro Fujisaki and Tatsuaki Okamoto. 1997. Statistical zero knowledge protocols to prove modular polynomial relations. In Annual International Cryptology Conference. Springer, 16--30.
16. Rosario Gennaro. 2004. Multi-trapdoor commitments and their applications to proofs of knowledge secure under concurrent man-in-the-middle attacks. In Annual International Cryptology Conference . Springer, 220--236.
17. Rosario Gennaro, Steven Goldfeder, and Arvind Narayanan. 2016. Threshold-optimal DSA/ECDSA signatures and an application to Bitcoin wallet security. In International Conference on Applied Cryptography and Network Security . Springer, 156--174.
18. Rosario Gennaro, Stanisław Jarecki, Hugo Krawczyk, and Tal Rabin. 1996. Robust threshold DSS signatures. In International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 354--371.
19. Rosario Gennaro, Stanisław Jarecki, Hugo Krawczyk, and Tal Rabin. 2001. Robust threshold DSS signatures. Information and Computation , Vol. 164, 1 (2001), 54--84.
20. Rosario Gennaro and Silvio Micali. 2006. Independent zero-knowledge sets. In International Colloquium on Automata, Languages, and Programming. Springer, 34--45.
21. Shafi Goldwasser, Silvio Micali, and Ronald L Rivest. 1988. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. , Vol. 17, 2 (1988), 281--308.
22. Carmit Hazay, Gert Læssøe Mikkelsen, Tal Rabin, and Tomas Toft. 2012. Efficient RSA key generation and threshold paillier in the two-party setting. In Cryptographers' Track at the RSA Conference. Springer, 313--331.
23. Stanisław Jarecki and Anna Lysyanskaya. 2000. Adaptively secure threshold cryptography: Introducing concurrency, removing erasures. In International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 221--242.
24. Marcel Keller, Valerio Pastro, and Dragos Rotaru. 2018. Overdrive: making SPDZ great again. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 158--189.
25. David W Kravitz. 1993. Digital signature algorithm. (July 27 1993). US Patent 5,231,668.
26. Yehuda Lindell. 2017. Fast Secure Two-Party ECDSA Signing. In Annual International Cryptology Conference . Springer, 613--644.
27. Philip MacKenzie and Michael K Reiter. 2001. Two-party generation of DSA signatures. In Annual International Cryptology Conference . Springer, 137--154.
28. Philip MacKenzie and Ke Yang. 2004. On simulation-sound trapdoor commitments. In International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 382--400.
29. Pascal Paillier. 1999. Public-key cryptosystems based on composite degree residuosity classes. In International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 223--238.
30. Guillaume Poupard and Jacques Stern. 2000. Short Proofs of Knowledge for Factoring. In Public Key Cryptography, Third International Workshop on Practice and Theory in Public Key Cryptography, PKC 2000, Melbourne, Victoria, Australia, January 18--20, 2000, Proceedings . 147--166.
31. Ronald L Rivest, Adi Shamir, and Leonard Adleman. 1978. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM , Vol. 21, 2 (1978), 120--126.
32. Claus-Peter Schnorr. 1991. Efficient Signature Generation by Smart Cards. J. Cryptology , Vol. 4, 3 (1991), 161--174.
33. Adi Shamir. 1979. How to share a secret. Commun. ACM , Vol. 22, 11 (1979), 612--613.

Index Terms

• Security and privacy

  • Cryptography

    • Public key (asymmetric) techniques

      • Digital signatures

  • Network security

    • Security protocols

• Theory of computation

  • Computational complexity and cryptography

    • Cryptographic primitives

    • Cryptographic protocols