U.S. flag   An official website of the United States government
Dot gov

Official websites use .gov
A .gov website belongs to an official government organization in the United States.


Secure .gov websites use HTTPS
A lock (Dot gov) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


A Multiparty Computation Approach to Threshold ECDSA

November 6, 2020


Jack Doerner - Northeastern University


Abstract: 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. Standardizing a design for a threshold variant of ECDSA will be significant progress toward standardizing building blocks for threshold cryptosystems at large. However, the design of ECDSA 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 and primitives such as the Paillier cryptosystem. We introduce new protocols for multi-party ECDSA key-generation and signing with arbitrary thresholds that are secure against malicious adversaries in the Random Oracle Model assuming only the Computational Diffie-Hellman Assumption. We instantiate our protocols using the same hash function and elliptic curve group used by the ECDSA signature being computed. Our threshold t scheme requires log(t)+6 rounds of communication with scope for adjustment to constant rounds if desired, and when t = 2 we provide an optimized two message protocol. Furthermore, our protocols are non-interactive in the preprocessing model. We evaluate our implementations and find that the wall-clock time for computing a signature through our two-party protocol comes to within a factor of 18 of local signatures. Concretely, two parties can jointly sign a message in just over three milliseconds. We also demonstrate the feasibility of signing with a low-power device (as in the setting of 2-factor authentication) by computing a signature between two Raspberry Pi devices in under 60 milliseconds.

Presented at

NIST Workshop on Multi-Party Threshold Schemes (MPTS) 2020. https://csrc.nist.gov/events/2020/mpts2020

Based on joint work with Yashvanth Kondi, Eysa Lee, and abhi shelat.

Event Details



Related Topics

Security and Privacy: cryptography

Created May 04, 2021, Updated June 07, 2021