Robust Threshold ECDSA with Online-Friendly Design in Three Rounds

Robust Threshold ECDSA with Online-Friendly Design in Three Rounds

Speakers: Guofeng Tang; Haiyang Xue

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=rxyQUYYsS74

Overview

This talk, presented by Guofeng Tang and Haiyang Xue from Simple Management University, introduces a groundbreaking advancement in threshold ECDSA (Elliptic Curve Digital Signature Algorithm). The work focuses on developing a scheme that is both robust and online-friendly, while achieving a minimal communication overhead of just three rounds. This combination of properties addresses significant challenges in deploying secure and efficient distributed signature systems, particularly for high-value applications like cryptocurrency.

The significance of this research stems from the widespread adoption of ECDSA as a standard signature scheme, critical for everything from securing Bitcoin and Ethereum transactions to TLS protocols. However, traditional ECDSA implementations suffer from the inherent risk of a single point of failure – the private key. Threshold ECDSA mitigates this by distributing the private key among multiple parties, requiring a threshold number of them to cooperate for a signature. This work not only enhances the security guarantees by ensuring robustness against malicious participants but also optimizes the protocol for practical, real-world deployment by making its online phase exceptionally fast.

The core contribution is the design of the first three-round robust threshold ECDSA scheme that maintains online-friendliness, meaning its most time-sensitive operations rely solely on efficient elliptic curve group computations. By innovatively restructuring the secret sharing and multiplication processes, the authors have achieved a protocol that significantly outperforms prior robust schemes in terms of communication rounds and online execution speed, marking a substantial step forward for distributed cryptographic key management.

Background

▶ Watch: Introduction to Threshold ECDSA and its importance (0:00)

The concept of threshold signatures is a fundamental cryptographic primitive designed to enhance the security and resilience of private keys. Instead of entrusting a single entity with a secret key, threshold signature schemes distribute shares of the key among N parties. A signature can only be generated if at least T+1 parties cooperate, while T or fewer parties cannot reconstruct the key or forge a signature. This distributed approach eliminates the single point of failure inherent in traditional signature schemes, protecting against key loss due to compromise, negligence, or malicious insiders.

ECDSA (Elliptic Curve Digital Signature Algorithm) is a widely adopted digital signature standard, mandated by NIST and extensively used across various critical applications. Its prominence is particularly notable in the cryptocurrency domain, where it underpins the security of transactions in major blockchain networks like Bitcoin and Ethereum. The private key in these systems directly controls ownership of digital assets, making its protection paramount. The loss or compromise of an ECDSA private key can lead to irreversible financial losses. Threshold ECDSA directly addresses this vulnerability by distributing control over these critical keys, making it a highly sought-after solution for exchanges, custodians, and decentralized applications.

Research in threshold ECDSA has traditionally focused on two main directions: enhancing security and improving efficiency.

• Security requirements have evolved from basic security with abort (where malicious parties can cause the protocol to fail) to identifiable abort (where misbehaving parties can be identified) and, finally, to robustness. Robustness, also known as Guaranteed Output Delivery (GOD) in the context of generic Multi-Party Computation (MPC), ensures that the honest majority of parties can successfully complete the signing process even in the presence of malicious adversaries.
• Efficiency considerations primarily revolve around minimizing communication rounds (a critical factor for network latency) and optimizing online cost. An "online-friendly" protocol is one where the real-time, online phase operations primarily consist of computationally inexpensive elliptic curve group operations, avoiding more expensive primitives like homomorphic encryption/decryption, which can introduce significant delays.

Previous constructions in the field have made various trade-offs:

• DKLS24 achieved three-round communication and online-friendliness but only offered security with abort, lacking robustness or identifiable abort.
• CDKS24 introduced identifiable abort and maintained online-friendliness but required seven communication rounds.
• WMY+23 was a pioneering work, presenting the first robust and online-friendly scheme, but it incurred a higher communication cost of five rounds, plus an additional two rounds for traitor identification.
• WMC24 also achieved robustness with four communication rounds but was not online-friendly, meaning its online phase involved more computationally intensive operations.

These prior works highlight the existing gap: a robust, online-friendly threshold ECDSA scheme that also achieves minimal communication rounds remained an open challenge. The presented work directly addresses this by providing a solution that simultaneously satisfies all three highly desirable properties.

Key Findings

▶ Watch: Review of existing robust and online-friendly ECDSA schemes (4:00)

The central contribution of Tang and Xue's work is the development of the first three-round robust threshold ECDSA scheme that is also demonstrably online-friendly. This achievement represents a significant breakthrough by combining properties previously only attainable through trade-offs.

The core innovations enabling this breakthrough include:

1. Novel Protocol Design for Efficiency: The scheme re-architects the secret sharing and multiplication phases of ECDSA to drastically reduce communication rounds. This is primarily achieved by introducing the concept of an "undetermined gamma" and concurrently sharing other secret values (k and x) within the initial round of the Multi-Party Computation for Two-Party Multiplication (MTE) protocol. This innovative approach allows the entire signing process to complete in just three rounds (two offline, one online), making it the most round-efficient robust scheme to date.
2. Robustness with Public Checking: To ensure robustness, the protocol incorporates a mechanism to identify and exclude misbehaving parties. Crucially, the authors found a vulnerability in previous robust schemes (specifically WMY+23), which utilized MTE without sufficient public checking. Their solution involves constructing an IMT (Interactive Multi-Party Computation for Two-Party Multiplication) with public checking, integrating zero-knowledge proofs into the two-round MT protocol. These proofs can be aggregated across multiple parties, maintaining efficiency.
3. Online-Friendly Performance: The online phase of their protocol is designed to be highly efficient, relying exclusively on fast elliptic curve group operations. This is achieved through the construction of an efficient DDH (Decisional Diffie-Hellman) relation zero-knowledge proof specifically tailored for elliptic curves, ensuring that the real-time signing process imposes minimal computational overhead.
4. Extensibility: Beyond ECDSA, the techniques developed for adding robustness, particularly the IMT with public checking, are shown to be generalizable. The authors demonstrate that these methods can be extended to construct other robust threshold signature schemes, specifically mentioning threshold BBS+, indicating a broader impact of their cryptographic primitives.

In direct comparison to prior robust schemes, their protocol demonstrates clear superiority in key metrics: it achieves a reduction from five or four rounds down to three, and its online phase is orders of magnitude faster (e.g., 0.5 milliseconds vs. 38 milliseconds in a two-party setting compared to WMC24). While the overall cost might be superior primarily in small-scale cases, the speakers emphasize that such scenarios are highly common in practical deployments, underscoring the immediate applicability and impact of their work.

Technical Deep Dive

▶ Watch: Introducing a 3-round robust and online-friendly ECDSA scheme (4:40)

At its core, ECDSA signature generation involves computing a signature (r, s) based on a message hash, a private key x, and a randomly chosen ephemeral nonce k. In a threshold setting, the private key x and the nonce k (or components derived from it, such as gamma) are shared among multiple parties. The challenge for threshold ECDSA is to perform the necessary multiplications and inversions securely and collaboratively without any party learning the full private key or nonce. Specifically, the computation of sigma often involves terms like k gamma and x gamma where k, gamma, and x are all shared secret values.

Previous robust threshold ECDSA schemes typically relied on Shamir secret sharing to distribute k, gamma, and x among the parties. To compute the necessary products, they would then employ an MTE (Multi-Party Computation for Two-Party Multiplication) protocol. A standard two-round MTE protocol operates by using one secret value (e.g., gamma) in the first round and the other two (e.g., k and x) in the second round. However, before these MTE operations could even begin, additional rounds were required to establish the initial secret shares of k, gamma, and x. This setup typically led to an offline phase requiring at least three rounds for sharing, followed by the two-round MTE, and then one more online round to open the shares, resulting in a minimum of four total communication rounds for the signing process.

The innovation in Tang and Xue's scheme lies in a radical re-thinking of how gamma is handled and how the secret shares are managed. They introduce the concept of an "undetermined gamma." Instead of pre-sharing gamma in a dedicated round before the MTE, gamma's value is effectively determined during the execution of the MTE protocol itself. This eliminates the need for a separate initial round solely for sharing gamma. Furthermore, by recognizing that k and x are only utilized in the second round of the MTE, their sharing can be cleverly integrated and run together with the first round of the MTE protocol. This concurrent sharing and computation collapses the offline phase from three rounds down to just two. When combined with the single online phase round required to open the shares, the entire protocol achieves an unprecedented three-round communication structure for robust threshold ECDSA.

Achieving robustness – the guarantee that an honest majority can always complete the protocol – necessitates mechanisms to identify and exclude malicious parties. The speakers identified a critical vulnerability in prior robust schemes, such as WMY+23, which used MTE without adequate public checking. Without public verifiability of intermediate computations, a malicious party could inject incorrect values, causing the protocol to abort or produce an invalid signature without being identified. To counter this, their scheme constructs an IMT (Interactive Multi-Party Computation for Two-Party Multiplication) with public checking. This is achieved by augmenting the standard two-round MTE with zero-knowledge proofs (ZKPs). These ZKPs allow parties to prove the correctness of their contributions to the MTE without revealing the underlying secret shares. A key design consideration was to ensure these proofs could be efficiently aggregated in multi-party settings, preventing the overhead from scaling linearly with the number of participants.

For the online phase, where speed is paramount, the protocol employs an efficient DDH (Decisional Diffie-Hellman) relation zero-knowledge proof specifically tailored for elliptic curves. The choice of DDH-based proofs ensures that the online computations are truly online-friendly, meaning they primarily involve fast elliptic curve group operations. This is crucial because elliptic curve operations are significantly less computationally intensive than other cryptographic operations like homomorphic encryption or decryption, which often plague the online phases of less efficient MPC protocols. By restricting the online phase to these optimized operations, the scheme achieves its remarkable speed, making it suitable for applications requiring high throughput and low latency.

Demo / Proof of Concept

▶ Watch: Ensuring robustness through public checking and zero-knowledge proofs (6:40)

While the talk did not detail a specific live demonstration or a publicly available proof-of-concept implementation, the speakers presented compelling performance benchmarks to validate the efficiency and superiority of their proposed robust threshold ECDSA scheme. These comparisons highlight the practical advantages over existing state-of-the-art protocols.

The performance evaluation specifically contrasted their three-round scheme with two prominent robust threshold ECDSA constructions: WMY+23 and WMC24.

• Compared to WMY+23 (2023): Their protocol significantly reduces communication overhead. WMY+23 requires five communication rounds for signing, plus an additional two rounds for traitor identification, totaling seven rounds in some scenarios. In contrast, the new scheme completes the entire signing process in just three rounds. Furthermore, the new protocol is cited as being more efficient in both its offline and online phases, implying lower computational costs per round in addition to fewer rounds overall.
• Compared to WMC24 (2024): The new scheme also demonstrates a notable improvement in communication rounds, requiring one less round than WMC24's four-round structure. The most striking difference, however, lies in the online phase performance. For a two-party setting, WMC24's online phase requires approximately 38 milliseconds, whereas the new protocol achieves an online phase completion in a mere 0.5 milliseconds. This represents an improvement of over 70 times, making the online phase significantly faster and reinforcing its "online-friendly" design.

The speakers acknowledged that while their overall cost is superior, this advantage is particularly pronounced in small-scale cases. They emphasized that these smaller-scale deployments (e.g., two to three parties) are, in fact, "more common in practice" for critical applications like cryptocurrency custody or multi-signature wallets. This practical relevance underscores the immediate utility and impact of their highly optimized, robust, and efficient threshold ECDSA scheme.

Defensive Implications

▶ Watch: Comparative analysis: superior performance against previous robust schemes (8:20)

The development of a three-round, robust, and online-friendly threshold ECDSA scheme has profound defensive implications for organizations and systems that rely on ECDSA for securing critical assets and communications.

1. Enhanced Private Key Protection: For institutions managing high-value digital assets (e.g., cryptocurrency exchanges, custodians, financial service providers), this protocol offers an unparalleled level of private key security. By distributing key control among multiple parties and ensuring robustness, it mitigates the risk of a single point of failure. Even if a subset of parties (up to the defined threshold T) becomes compromised or malicious, the honest majority can still successfully generate signatures, guaranteeing asset control and transaction finality. This significantly bolsters defenses against insider threats, targeted attacks, and system compromises.

1. Guaranteed Transaction Finality and Availability: The robustness property is a critical defensive advantage. In scenarios where timely signatures are essential (e.g., high-frequency trading, real-time settlement systems, or critical infrastructure control), the guarantee of output delivery ensures that malicious parties cannot indefinitely stall or disrupt operations by misbehaving. This leads to higher availability and reliability of services dependent on ECDSA signatures.

1. Improved Efficiency for High-Throughput Systems: The three-round communication and online-friendly design translate directly into practical benefits for systems requiring high throughput and low latency. Organizations no longer need to compromise between strong security guarantees and performance. The ability to complete a robust signature process in minimal rounds with exceptionally fast online computations makes this scheme ideal for integrating into performance-sensitive environments without introducing significant bottlenecks.

1. Accountability and Incident Response: The inherent capability to achieve identifiable abort within the robust framework provides crucial forensic value. If a signing attempt fails due to malicious activity, the protocol allows for the identification of the misbehaving parties. This accountability mechanism is vital for internal auditing, compliance, and informing incident response procedures, enabling organizations to pinpoint and address sources of compromise or malicious intent.

1. Broader Applicability for Secure Protocols: Beyond direct ECDSA use cases, the underlying techniques for constructing IMT with public checking and efficient zero-knowledge proofs are generalizable. This means other distributed cryptographic protocols, such as threshold BBS+ signatures, can leverage these innovations to enhance their robustness and efficiency. Defenders and protocol designers can adopt these principles to build more resilient and performant secure multi-party systems across a wider range of applications.

In essence, this work provides a cryptographic primitive that allows defenders to deploy highly secure, fault-tolerant, and performant distributed signature systems. It moves the needle on what's possible in practical MPC, enabling a stronger defensive posture against a spectrum of threats while maintaining operational efficiency.

Key Takeaways

• First of its Kind: This work introduces the first three-round, robust, and online-friendly threshold ECDSA scheme, achieving a critical balance of security and efficiency previously unreached.
• Innovative Round Reduction: The protocol's minimal three-round communication (two offline, one online) is enabled by novel techniques like "undetermined gamma" and concurrent sharing of secret values (k and x) within the MTE protocol.
• Robustness with Public Checking: Robustness is guaranteed through an IMT design incorporating public checking via aggregated zero-knowledge proofs, directly addressing vulnerabilities found in prior robust schemes without such mechanisms.
• Exceptional Online Performance: The online phase is highly efficient and "online-friendly," relying solely on fast elliptic curve group operations, demonstrated by a two-party online phase completing in just 0.5 milliseconds, significantly faster than previous robust schemes.
• Practical for Critical Applications: The scheme offers substantial advantages in communication rounds and online speed, particularly beneficial for small-scale deployments common in high-security, high-availability applications like cryptocurrency custody.
• Extensible Techniques: The developed techniques for adding robustness, particularly the IMT with public checking, are generalizable and can be extended to enhance other threshold signature schemes, such as BBS+.

About the Speaker(s)

Guofeng Tang and Haiyang Xue are the researchers behind this work, both affiliated with Simple Management University. Their presentation at IEEE S&P highlights their expertise in cryptography, particularly in the domain of threshold signature schemes and secure multi-party computation. Their collaboration has led to significant advancements in making complex cryptographic protocols more practical and robust for real-world deployment.