Secure Multi-party Threshold ECDSA from ECDSA Assumptions

@inproceedings{wtstw17,
 title = {Secure Multi-party Threshold ECDSA from ECDSA Assumptions},
 author = {Jack Doerner and Yashvanth Kondi and Eysa Lee and abhi shelat},
 booktitle = {To appear Oakland S&P'2018},
 year = {2018},
}

The Elliptic Curve Digital Signature Algorithm (ECDSA) is one of the most widely used schemes in deployed cryptography. Through its applications in code and binary authentication, web security, and cryptocurrency, it is likely one of the few cryptographic algorithms encountered on a daily basis by the average person. However, its design is such that executing multi-party or threshold signatures in a secure manner is challenging: unlike other, less widespread signature schemes, secure multi-party ECDSA requires custom protocols, which has heretofore implied reliance upon additional cryptographic assumptions such as the Paillier encryption scheme.

We propose new multi-party threshold ECDSA key-generation and signing protocols, which we prove secure against malicious adversaries in the observable, non-programmable random oracle model using only the Computational Diffie-Hellman Assumption and the assumptions already required by ECDSA. Our scheme incurs a number of rounds logarithmic in the number of parties, and only two rounds in the two-party case. Via implementation we find that our scheme outperforms the best prior results in practice by a factor of roughly 100 for key generation and more than 20 for signing, coming to within a factor of 10 of local signatures. Concetely, two parties can jointly sign a message in 1.77 milliseconds.