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

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

Presentation

A Multiparty Computation Approach to Threshold ECDSA

November 6, 2020

Presenters

Jack Doerner - Northeastern University

Description

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

Location

    
                            

Related Topics

Security and Privacy: cryptography

Created May 04, 2021, Updated June 07, 2021