Secure Multiparty Computation of Threshold Signatures Made More Efficient

Secure Multiparty Computation of Threshold Signatures Made More Efficient

Speakers: Harry W. H. Wong

Conference: NDSS Symposium

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

Overview

This article delves into Harry W. H. Wong's presentation on enhancing the efficiency of secure multiparty computation (SMC) for threshold signatures, a critical cryptographic primitive for securing decentralized applications. The talk introduces novel protocols designed to address long-standing challenges in existing threshold signature schemes, particularly for ECDSA and BBS+ signatures. These challenges include the necessity for fixed "roll call" groups, a lack of robustness against participant failures, inadequate public verifiability and fault recovery mechanisms, and overall inefficiency due to high communication overhead.

Wong's work revisits the Cramer-Damgård-Nielsen (CDN) paradigm of SMC, leveraging Threshold Linearly Homomorphic Encryption (TLHE) to construct more robust and efficient protocols. The core innovation lies in the development of robust Distributed Key Generation (DKG) protocols for both discrete-logarithm-based and class-group-based cryptosystems, along with an optimized threshold variant of Castagnos-Laguillaumie (CL) encryption. By focusing on constant communication overhead and minimal rounds, this research aims to provide a foundational cryptographic layer that can support the dynamic and resilient nature required by modern decentralized services, such as blockchains and decentralized social networks.

The significance of this research lies in its practical implications for security and availability. By enabling threshold signatures that are secure against a dishonest majority, allow dynamic participant inclusion, offer constant communication overhead, and achieve state-of-the-art round complexity without roll calls, the presented protocols mitigate critical denial-of-service vulnerabilities and simplify fault attribution. Empirical results demonstrate substantial performance gains, halving computation and communication costs compared to prior robust schemes, thereby paving the way for wider adoption of secure and resilient decentralized systems.

Background

▶ Watch: Introduction and limitations of existing threshold signatures (0:00)

The internet's fundamental reliance on trust, authenticity, and integrity makes robust cryptographic solutions indispensable. Critical services like public-key infrastructures and DNS servers, if compromised, can lead to severe consequences such as phishing and exploitation of trust. The recent surge in decentralized technologies, propelled by blockchain and the demand for high availability in services like decentralized social networks, underscores the need for advanced cryptographic primitives. Threshold signatures, which allow a subset of t out of n participants to collaboratively produce a signature, are foundational to securing these applications. While widely adopted, existing threshold ECDSA schemes suffer from several critical drawbacks that limit their utility in dynamic, decentralized environments.

A primary issue is Roll Call Necessity, where many schemes mandate an initial, often unaccounted-for, communication round to form a fixed group of t signers. This group must remain constant throughout the signing process, severely hindering applications where participants may dynamically join or leave. Secondly, Non-robust Threshold Signing plagues schemes that prioritize best-case performance using t-out-of-t additive secret sharing. In such setups, the absence or fault of even a single participant can irrecoverably destroy computations, leading to a critical denial-of-service vulnerability, particularly problematic for time-sensitive operations. Furthermore, a pervasive Lack of Public Verifiability or Fault Recovery means that many schemes rely on private verifiability, requiring additional communication rounds for an identifying party to generate and distribute evidence of a fault. Even when public verifiability is supported, robust fault recovery is often absent, frequently necessitating a complete restart after minor faults. Finally, Inefficiency is a common thread, with prior schemes often exhibiting high signing costs due to pairwise interactions. Popular approaches, such as multiplicative-to-additive (MtA) protocols, typically require O(t) messages per party, and fault identification can incur O(t²) verification costs.

To address these shortcomings, Wong's work significantly departs from recent trends by revisiting the Cramer-Damgård-Nielsen (CDN) paradigm of Secure Multi-party Computation (SMC), which is based on Threshold Linearly Homomorphic Encryption (TLHE). TLHE offers two crucial functionalities: homomorphic operations, allowing computations on encrypted messages without decryption, and threshold decryption, enabling any t participants to decrypt. In the context of threshold signatures, participants can encrypt signature components and homomorphically compute the final signature without revealing their underlying values. This paradigm, when instantiated with robust building blocks, provides strong robustness guarantees. Should fewer than t participants be present, the signing process merely pauses, seamlessly resuming once enough participants rejoin, as intermediate values or the final signature can be recovered by decrypting broadcasted and verifiably encrypted results.

The homomorphic signing process for deriving an ECDSA signature (R, σ) using TLHE involves several steps: first, distributively generating randomness k in ciphertext; second, distributively generating gy for a random y, and (ky, kx) in ciphertext via homomorphic evaluation on encrypted k; third, threshold-decrypting ky and gy to compute R as (gy)(1/ky); and finally, threshold-decrypting σ := km + rkx, which is homomorphically generated from encrypted (k, kx) and plain (r, m). A key advantage of this approach is that each party P_i requires only O(1) messages and 3 rounds to compute ky (and similarly kx), a stark contrast to the O(t) messages needed for MtA protocols. The use of zero-knowledge proofs (ZKPs) over the computation also requires only O(1) messages, and public verifiability is achieved asymptotically for free, enabling immediate, non-interactive fault attribution without an extra ZKP round for secrets.

This approach relies on two key TLHE extensions: a distributed key generation (DKG) protocol for LHE, and ZKPs of knowledge for public verifiability that allow witness extraction. The researchers specifically build upon Castagnos-Laguillaumie (CL) encryption 17 due to its decentralized setup and message space (a group Zq of prime order q), which aligns perfectly with the modulus used by ECDSA. This avoids the need for additional ZKPs, such as range proofs, which would be necessary with other LHE schemes like threshold Paillier encryption. However, CL encryption operates in an unknown-order group, which introduces complexities for division in the exponent and witness extraction.

Compared to prior work, most threshold ECDSA proposals like Abram et al. 2, 11, 16, 35, and 48 use MtA protocols, focusing on optimizing communication. Schemes such as 11, 15, 16, 28, 31, 41, 48 still require a fixed roll call group, leading to restarts upon faults. While Wong et al. 48 achieved self-healing, it still required two extra rounds in worst-case scenarios, and Bouez and Singh 8 achieved 1-round online signing but deferred fault identification. For threshold BBS+ signatures, Doerner et al. 26 adapted SMC techniques, but their approach was computationally lighter than LHE. This work distinguishes itself by prioritizing communication efficiency over computation, acknowledging that computation is often more readily optimizable, while offering robust, non-interactive cheat identification and allowing any party to contribute to recovery. Furthermore, it addresses the heavy overhead of threshold LHE schemes under malicious settings, like Castagnos et al. 19, by building a robust DKG for TLHE over Zq. Concurrent work by Braun et al. 10 revisited the CDN paradigm in a You-Only-Speak-Once (YOSO) setting but assumed an honest majority, thus not considering witness extraction or dual-code-based verification, and yielded a biased key. Wong's DKG, following Gennaro et al. 34, produces a uniformly distributed public key.

Key Findings

▶ Watch: Detailed homomorphic ECDSA signature derivation process (2:30)

The research presents several pivotal contributions that significantly advance the state of the art in secure multiparty computation for threshold signatures:

• Robust DKG Protocol for CL Encryption: The work introduces a novel, robust Distributed Key Generation (DKG) protocol specifically designed for Castagnos-Laguillaumie (CL) encryption that operates effectively in a dishonest majority setting. This protocol ensures the generation of a uniformly-distributed public key, extending the security guarantees of threshold CL encryption beyond what was previously tailored for an honest majority. Its public verification machinery enables a 2-round construction, marking a significant improvement in efficiency and practicality.
• Dual-Code-based Verification for Class Groups: A groundbreaking application of dual-code-based verification is introduced for class groups within a (t, n)-threshold setting. This technique dramatically reduces the computational cost for ensuring share consistency from O(tn²) (typical for pairwise approaches) to a more scalable O(n²) for public verification, thereby making the DKG process significantly more efficient and practical for larger participant groups.
• Superior Threshold ECDSA Protocol: The proposed threshold ECDSA protocol demonstrates measurable superiority over existing state-of-the-art robust schemes. It offers inherent robustness, allowing participants to dynamically join or leave without disrupting the protocol. Operating in just 3 communication rounds, it eliminates the need for extra rounds dedicated to conflict resolution or recovery by relying solely on publicly verifiable shares. Furthermore, it achieves an O(1) communication overhead for verifying all other parties during threshold signing. Empirical results confirm substantial performance gains, including approximately 50% savings in both runtime and communication costs compared to the robust threshold ECDSA scheme by Wong et al. 48, while maintaining equivalent security guarantees.
• Robust Threshold BBS+ Signature Design: The research provides an alternative and more robust design and realization for threshold BBS+ signatures. Previous attempts, such as Doerner et al. 28, largely followed the blueprint of MtA-based ECDSA, which suffered from relative weaknesses in public verifiability and robustness. The new approach offers a more resilient and efficient alternative for signing vectors of messages.
• Broad Applicability of Technical Contributions: Beyond the specific signature schemes, the developed technical contributions, including the DKG protocols and dual-code-based verification, hold independent interest. These techniques are broadly applicable to other cryptosystems that can be thresholdized with public verifiability, leveraging CL encryption's compatibility, or to general SMC tasks in dishonest majority settings, paving the way for wider cryptographic innovation.
• Resolution of Open Problems: The work successfully closes two out of three previously identified open problems from the earlier work by Wong et al. 48, underscoring its significant impact on advancing the field.

Technical Deep Dive

▶ Watch: Achieving O(1) messages and public verifiability (3:05)

The core of this research revolves around constructing robust and efficient threshold signature schemes by leveraging Threshold Linearly Homomorphic Encryption (TLHE), specifically an optimized variant of Castagnos-Laguillaumie (CL) encryption, and novel Distributed Key Generation (DKG) protocols.

Distributed Key Generation (DKG)

The central technical contribution is the design of two robust DKG protocols: one for CL encryption (DKG-CL) and another for discrete-logarithm-based cryptosystems (DKG-DL). The general outline of these DKG protocols is as follows:

Each party P_i first sets up its own CL encryption key pair. They then distribute CL-encrypted shares of their secret, along with committed shares, using Zero-Knowledge Proofs (ZKPs) to demonstrate well-formedness. After verifying all received shares and excluding any invalid ones, each party broadcasts their share in the exponent. ZKPs are again used to prove that the decryption of the homomorphically-evaluated ciphertext returns the correct share. Crucially, the public key, which is a shared secret in the exponent, is uniformly distributed and can be constructed from the broadcasted shares without further interaction.

A critical component of the DKG is Dual-Code-based Verification. Standard ZKPs alone are insufficient to prevent a malicious party from distributing inconsistent shares to different participants, which could lead to system inconsistency. The traditional remedy involves generating a committed polynomial corresponding to the shares, but this incurs O(tn²) computation for verification and requires an extra communication round for complaints. The presented work extends the dual-code-based verification technique 12 (originally for public attestation of uniform randomness beacons under an honest majority assumption) for use in ECDSA. This adaptation leverages a dual vector such that its inner product with a vector of inconsistent shares would be non-zero, allowing public verification of all shares in the exponent with only O(n²) computation. This technique is further extended to commitments of shares, specifically Pedersen commitments, which eliminates information leakage during the first communication round and thwarts rushing adversaries, ensuring robustness and uniform key distribution.

For Recovery of Shares for Dishonest Majority via Extraction, a significant challenge in DKG is extracting shares of the secret key for simulation-based security proofs. In this approach, all shares are encrypted and broadcasted, enabling the simulator to extract shares by decryption, with the decryption key being the only element extracted via ZKP of knowledge. This enhances extendibility to concurrent settings. However, the secret key in CL encryption resides in integers over an unknown modulus. Standard E-protocols in unknown-order groups have a 1/2 soundness lower bound. To address this, the protocols rely on the 2-fractional-root assumption 21, a computational assumption that tackles the challenges posed by division in the class group.

The DKG protocols are Rushing-Resilient and operate in two rounds. A 1-round construction is insufficient to defend against rushing adversaries who can bias the key distribution. The design employs the 2-stage paradigm 34, where the first stage fixes an initial secret, and the second reveals lifted initial secrets for computing the resultant key. The protocol follows the distributed randomness generation (DRG) construction of Wong et al. 48 but integrates dual-code-based verification for committed shares, with Non-Interactive Zero-Knowledge (NIZK) proofs maintaining correspondence with encrypted shares.

The Security Definition of DKG mandates three conditions: (C1) all sufficiently large subsets of shares from honest parties define the same unique secret key; (C2) all honest parties have the same public key value; and (C3) the secret key is uniformly distributed. Robustness ensures successful completion with t honest parties, and secrecy requires a simulator to produce an indistinguishable view for any adversary.

DKG-DL (Discrete-Log Keys) is presented as a two-phase protocol:

• Generation Phase (Round 1): Each party P_i samples an initial secret X_i, shares it using Shamir Secret Sharing (SS), encrypts X_ij for each P_j using P_j's encryption key (ek_j), commits to X_ij with Pedersen commitments (PC_Xij), and proves well-formedness with Z_enc-PC. All these are broadcast. The GenVf step verifies Z_enc-PC and uses dual code verification to ensure consistency, removing faulty parties and fixing the qualified set Q.
• Revelation Phase (Round 2): P_i decrypts the homomorphically-added ciphertext C_xi to obtain their share x_i. They then assert the correctness of their lifted share X_i against C_xi using Z_Dec-DL and broadcast X_i and its proof. RevealVf verifies these proofs, and the public key X is computed via interpolation in the exponent.

DKG-CL (Class Groups) is similar but adapted for integers over an unknown modulus s. The initial secret X_i is a large integer, requiring integer Shamir SS. Since CL encryption's plaintext space is F_q, X_ij is decomposed in base q, leading to multiple ciphertexts. A ZKP for big integers (Z_BInt) is used. The Gen and GenVf phases involve O(n len) and O(n² len) operations, respectively.

Threshold LHE (t-CL)

Building upon the DKG-CL protocol, a threshold variant of CL encryption, termed t-CL, is introduced. This scheme comprises Setup, Key Generation (KGen), Encryption (Enc), Partial Decryption (PartDec), and Final Decryption (FinDec). The DKG-CL protocol ensures a uniformly distributed key for t-CL. A key optimization is the reduction of the exponent for decryption from Δ³ to Δ², where Δ = n!, significantly improving efficiency, especially in an unknown-order group with large exponents.

The Construction of t-CL is detailed as follows:

• Setup: This phase is distributed. First, a class group for CL encryption is initialized. Each P_i picks a random q_i, broadcasts its hash H(q_i), then q_i. After verification, a new prime q' is derived, and P_i runs CLE.Setup(q, q', λ). Second, a random base element h for class-group commitments is sampled distributively. Each P_i picks h_i, broadcasts H(h_i), then h_i. After verification, h is formed as the product of valid h_j. Third, each P_i runs CLE.KGen (with ZKP) to obtain their CL encryption key pair (CLE.ek_i, CLE.dk_i). Finally, all parties return the public parameters pp, including class group parameters, h, and all CLE.ek_j.
• KGen: This invokes the DKG-CL protocol to generate the threshold key pair (X; X_i). The public key ek is X, individual public keys ek_j are gX_i, and the secret key share dk_i is X_i.
• Encryption (Enc): For t-CL, this slightly differs from standard CL encryption. It uses g(Δ2) as the base element to generate the c_0 component of the ciphertext, specifically c_0 = (g(Δ2))r.
• Partial Decryption (PartDec): Performed by P_i, it returns a share cpd_i = c_0(dk_i), along with a proof T_cpd.
• Final Decryption (FinDec): Invalid partial decryptions are discarded. The correct shares cpd_j are interpolated to reconstruct c(Δ2dk) = (ekΔ2*)r. Given that c_1 = fm (ekΔ2)r, the message m is recovered as Dlog(f(Δ2)m)/Δ2 mod q.

The Security Analysis for t-CL is formalized through several lemmas: Lemma 5 guarantees evaluation correctness if CLE and DKG-CL satisfy correctness. Lemma 6 establishes t-ind-cpa-security (ciphertext indistinguishability under chosen plaintext attacks) if DKG-CL has secrecy and CLE is IND-CPA-secure. Lemma 7 ensures simulation security, meaning dk cannot be learned from partial decryptions, contingent on DKG-CL secrecy and Z_PartDec being honest-verifier zero-knowledge. The proof strategy aligns with classic threshold ElGamal encryption due to structural similarity, and the threshold decryption process is robust, succeeding with t or more honest parties. A Property for Simple Security Proof (Section V.C) notes that t-ind-cpa-security allows the simulator for threshold decryption to simulate partial decryptions with knowledge of the final decryption result m, which is crucial for building larger protocols.

System Design and Architecture - Threshold Signatures

Leveraging the threshold CL encryption, efficient threshold signing protocols for both ECDSA and BBS+ signatures are proposed. These protocols are designed to defend against rushing adversaries by using threshold lifted ElGamal encryption to commit to group elements within the same elliptic-curve group as the signature.

Threshold ECDSA Construction

The protocol integrates DKG-DL, DKG-CL, and t-CL.

• Setup:

1. Run t-CL.Setup to set up a class group.
2. Invoke two instances of DKG-DL to generate key pairs for threshold ECDSA (X, X_i) and threshold ElGamal (t-EIG) (elek, eldk_i).
3. Concurrently, invoke DKG-CL to generate a key pair for threshold CL encryption (clek, cldk_i).

• Offline Signing Phase (3 rounds, executed before message is known):
• Round 1: Each party P_i encrypts its share k_i using t-CL.Enc, proves well-formedness with Z_enc, and broadcasts (k_i, π_ki). Homomorphically compute the LHE of k := Σ_j k_j.
• Round 2: P_i encrypts gy_i, generates LHE of x_ik and y_ik. Proves these with Z_DL-CL and Z_EI-CL, and broadcasts (x_ik, π_xik, gy_i, π_yik). Homomorphically compute encrypted xk := Σ_j x_jk, yk := Σ_j y_jk, and gy := Π_j gy_j.
• Round 3: P_i partially decrypts yk and gy using t-CL.PartDec and t-EIG.PartDec, then broadcasts the partial decryptions. P_i fully decrypts yk and gy using t-CL.FinDec and t-EIG.FinDec. It then computes R := (gy)(1/yk) and returns (R, k, xk).
• Online Signing Phase (non-interactive):
• Step 1: P_i homomorphically derives the encryption of km + rkx as (m k) (r xk).
• Step 2-3: P_i partially decrypts km + rkx using t-CL.PartDec, broadcasts the result, and then fully decrypts it using t-CL.FinDec. It returns (r, s := km + rkx). An optimization is to conduct partial decryption verification only if the final ECDSA verification fails.

Theorem 1 asserts correctness and robustness if DKG-DL, DKG-CL, t-CL, and t-EIG are correct and ZKPs are sound. Theorem 2 guarantees simulatability if DKG-DL, DKG-CL satisfy secrecy, and t-CL, t-EIG satisfy simulation security and t-ind-cpa.

Threshold BBS+ Signatures

An alternative design and realization for Threshold BBS+ Signatures (Section VI.C) is also provided. This scheme signs on vectors of l messages. Its setup involves DKG-CL for t-CL, DKG-DL over G2 for BBS+, and DKG-DL over G1 for t-EIG. The offline phase is 4-round, similar to ECDSA, involving distributed generation and extraction of encrypted components. The online phase then computes the signature A = (Dy)(1/(x+e)). Similar theorems 3 and 4 confirm its robustness and simulatability.

Demo / Proof of Concept

▶ Watch: Distinctions from prior threshold ECDSA and BBS+ schemes (4:00)

To empirically validate the theoretical claims, the proposed constructions were implemented using BICYCL 9, an open-source C++ library specifically designed for class-group arithmetic. For cryptographic parameters, the CL-HSMq class group was utilized, offering a 256-bit plaintext space and an 1827-bit λ, achieving a 128-bit security level. The SHA-3 hash function was employed to instantiate the Fiat-Shamir transform within the ZKPs. All experiments were conducted 100 times on a desktop computer equipped with an AMD Ryzen 5 2600 CPU and 64GB RAM. For performance comparisons with state-of-the-art schemes, the number of parties n was set to t-1, representing a worst-case scenario for threshold decryption utilization.

Performance of DKG Protocols

The performance evaluation of the DKG protocols (Figure 3 in the presentation) revealed key insights into their computational and communication costs:

• Runtime per Party (Figure 3a and 3b): The generation phase of both DKG-CL and DKG-DL proved to be the most time-consuming component. For DKG-CL, this phase scales with n len and n² len, taking approximately 150 seconds for n=20 parties. In contrast, the revelation phase for both DKG-CL and DKG-DL exhibited constant runtime, completing within a few seconds, indicating its efficiency once the initial setup is done.
• Communication Cost per Party (Figure 3c): The revelation phase of DKG-CL demonstrated a constant-size communication cost of 1.31 KBytes per party, while DKG-DL was even more compact at 0.77 KBytes per party. This highlights the protocols' efficiency in terms of network bandwidth during the critical revelation stage.

Performance of Threshold CL Encryption (t-CL)

• A partial decryption (PartDec) operation for t-CL took approximately 93 ms, with each party broadcasting 0.8 KBytes of data.
• Final decryption (FinDec) scaled with n, requiring 443 ms for n=5 parties and 1704 ms for n=20 parties.
• Homomorphic evaluation within t-CL followed the basic CLE scheme, costing 24ms (or less than 1ms if ciphertext re-randomization was not required).
• The t-CL.KGen protocol is essentially the DKG-CL protocol itself, emphasizing that its relatively high initial cost is a one-time trade-off for significant efficiency gains in subsequent online phases.

Performance of Threshold ECDSA Protocol

The threshold ECDSA protocol, instantiated on the secp256k1 elliptic curve, showed compelling performance improvements compared to existing robust schemes (Figure 4 in the presentation):

• Offline Stage Runtime (Figure 4a): The proposed scheme achieved significant efficiency gains, demonstrating approximately 50% savings in runtime compared to Wong et al. 48, which offers weaker self-healing properties. When compared to Castagnos et al. 16, which provides identifiable abort, the new scheme still achieved about 20% savings in runtime.
• Offline Stage Communication Cost (Figure 4b): Similar substantial improvements were observed in communication costs. The protocol saved over half the communication costs compared to Wong et al. 48 and approximately 20% compared to Castagnos et al. 16. For context, a Paillier-based threshold ECDSA scheme (e.g., 11) incurred 153 KBytes for n=5 and 613 KBytes for n=20, which is at least twice the communication cost of the presented work. Furthermore, CLE encryption/decryption was found to be faster than Paillier for the 128-bit security level.
• Comparisons to OT-based instantiations, such as Gagol et al. 35, revealed a trade-off: while OT-based schemes might achieve half the runtime, they incur significantly higher communication costs (e.g., 400 KBytes for 15 parties and 700 KBytes for 20 parties), underscoring the communication efficiency of Wong's approach.

These empirical results strongly substantiate the claims of efficiency and robustness, positioning the new threshold signature protocols as a superior choice for decentralized applications.

Defensive Implications

▶ Watch: Core technical contribution: Robust DKG for CL encryption (4:50)

The advancements presented in this work have profound implications for security practitioners and developers building decentralized systems. Understanding and adopting these new techniques can significantly bolster the resilience, availability, and trustworthiness of cryptographic operations.

1. Enhance Robustness in Decentralized Applications: Developers of decentralized applications, including blockchain platforms, decentralized social networks, and critical infrastructure services, should prioritize the integration of robust threshold signature schemes. The presented protocols, with their inherent ability to withstand participant faults and dynamic changes without requiring restarts or fixed "roll call" groups, directly address critical denial-of-service vulnerabilities. This ensures higher availability and operational continuity for services reliant on collective cryptographic actions.
2. Facilitate Non-Interactive Fault Recovery: The public verifiability and non-interactive fault attribution mechanisms embedded in these protocols are crucial. Defenders can benefit from immediate identification of malicious or faulty participants without needing additional communication rounds for evidence generation. This streamlines incident response, reduces operational overhead associated with fault management, and enhances transparency in multi-party computations.
3. Leverage Efficiency for Scalability: The demonstrated significant reductions in computation and communication costs make robust threshold signatures more practical for real-world deployments. This efficiency allows for greater scalability in decentralized systems, enabling larger groups of participants to collaboratively sign without incurring prohibitive resource demands, thereby expanding the applicability of these cryptographic primitives.
4. Adopt Optimized DKG for Secure Setup: The robust, 2-round DKG protocols for CL encryption and discrete-logarithm-based cryptosystems provide a secure and efficient foundation for generating shared keys. Organizations should consider these DKG approaches for any multi-party cryptographic setup requiring high assurance, uniform key distribution, and resilience against dishonest majorities. The dual-code-based verification technique, reducing cost from O(tn²) to O(n²), is a significant enabler for practical DKG in larger n settings.
5. Consider Broader SMC Applications: The technical contributions, particularly the DKG protocols and the optimized t-CL encryption, are not limited to signature schemes. They represent valuable building blocks for other Secure Multiparty Computation (SMC) tasks in dishonest majority settings. Security architects should evaluate how these primitives can be adapted to enhance other distributed cryptographic protocols requiring robustness, efficiency, and public verifiability.
6. Mitigate Rushing Attacks: The 2-round design of the DKG protocols explicitly defends against rushing adversaries, who could otherwise bias key distributions in 1-round constructions. This ensures the integrity and security of the generated shared keys from sophisticated attacks.

In summary, this work provides concrete, empirically validated tools and methodologies for building more secure, resilient, and efficient decentralized systems. Defenders should actively explore integrating these advanced threshold signature and DKG protocols to future-proof their cryptographic architectures against evolving threats and operational complexities.

Key Takeaways

• Novel robust, 2-round Distributed Key Generation (DKG) protocols are introduced for both Castagnos-Laguillaumie (CL) encryption and discrete-logarithm-based cryptosystems, providing uniformly distributed public keys in a dishonest majority setting.
• The innovative use of dual-code-based verification for class groups significantly improves DKG scalability, reducing the cost of ensuring share consistency from O(tn²) to a practical O(n²) public verification.
• The proposed threshold ECDSA protocol offers state-of-the-art robustness, allowing dynamic participant changes and non-interactive fault recovery, while operating in just 3 communication rounds with an O(1) communication overhead for verification.
• Empirical results demonstrate substantial performance improvements, including approximately 50% savings in offline computation and communication costs compared to prior robust threshold ECDSA schemes (e.g., Wong et al. 48), making robust threshold signatures more practical for real-world deployment.
• The work addresses critical limitations of existing threshold signature schemes, such as the "roll call" necessity and non-robustness, thereby enabling the development of more resilient and available decentralized applications.
• The technical contributions, including the optimized threshold CL encryption and DKG protocols, hold independent interest and are broadly applicable as building blocks for other Secure Multiparty Computation (SMC) tasks in dishonest majority settings.

About the Speaker(s)

Harry W. H. Wong is the speaker for this presentation at the NDSS Symposium. Based on the technical depth and specific contributions outlined in the talk, Wong's research focuses on advancing the efficiency and robustness of secure multiparty computation, particularly in the context of threshold cryptography and decentralized applications. His work demonstrates expertise in cryptographic protocol design, distributed key generation, homomorphic encryption, and empirical performance analysis of cryptographic primitives. No further biographical details were provided in the transcript or metadata.