Paper 2019/523

Threshold ECDSA from ECDSA Assumptions: The Multiparty Case

Jack Doerner, Yashvanth Kondi, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.IEEE S&P 2019
DOI
10.1109/SP.2019.00024
Keywords
threshold cryptographyelliptic curve cryptographymulti-party computationECDSAconcrete efficiency
Contact author(s)
j @ ckdoerner net
History
2020-05-22: revised
2019-05-20: received
See all versions
Short URL
https://ia.cr/2019/523
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/523,
      author = {Jack Doerner and Yashvanth Kondi and Eysa Lee and abhi shelat},
      title = {Threshold ECDSA from ECDSA Assumptions: The Multiparty Case},
      howpublished = {Cryptology ePrint Archive, Paper 2019/523},
      year = {2019},
      doi = {10.1109/SP.2019.00024},
      note = {\url{https://eprint.iacr.org/2019/523}},
      url = {https://eprint.iacr.org/2019/523}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.