Cryptology ePrint Archive: Report 2019/523

Threshold ECDSA from ECDSA Assumptions: The Multiparty Case

Jack Doerner and Yashvanth Kondi and Eysa Lee and abhi shelat

Abstract: Cryptocurrency applications have spurred a resurgence of interest in the computation of ECDSA signatures using threshold protocols---that is, protocols in which the signing key is secret-shared among $n$ parties, of which any subset of size $t$ must interact in order to compute a signature. Among the resulting works to date, that of Doerner et al. requires the most natural assumptions while also achieving the best practical signing speed. It is, however, limited to the setting in which the threshold is two. We propose an extension of their scheme to arbitrary thresholds, and prove it secure against a malicious adversary corrupting up to one party less than the threshold under only the Computational Diffie-Hellman Assumption in the Global Random Oracle model, an assumption strictly weaker than those under which ECDSA is proven.

We implement our scheme and evaluate it among groups of up to 256 of co-located and geographically-distributed parties, and among small groups of embedded devices. In the LAN setting, our scheme outperforms all prior works by orders of magnitude, and that it is efficient enough for use even on smartphones or hardware tokens. In the WAN setting, our protocol outperforms the best constant-round protocols in realistic scenarios, despite its logarithmic round count.

Category / Keywords: cryptographic protocols / threshold cryptography, elliptic curve cryptography, multi-party computation, ECDSA, concrete efficiency

Original Publication (with major differences): IEEE S&P 2019

Date: received 18 May 2019, last revised 22 May 2020

Contact author: j at ckdoerner net

Available format(s): PDF | BibTeX Citation

Version: 20200522:174533 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]