Powers of Tau in Asynchrony

Powers of Tau in Asynchrony

Speakers: Sourav Das

Conference: NDSS Symposium

YouTube: (no public video)

Overview

Sourav Das’s talk, "Powers of Tau in Asynchrony," introduces a groundbreaking distributed protocol for securely and robustly generating q-Strong Diffie-Hellman (q-SDH) parameters in an asynchronous network. These parameters, often referred to as "powers of tau," are a fundamental building block in modern cryptography, essential for the efficient construction of zero-knowledge succinct non-interactive arguments of knowledge (SNARKs), polynomial and vector commitments, verifiable secret sharing, and distributed randomness beacons. The core challenge lies in generating these parameters—a vector of group elements g, τg, τ²g, ..., τºg, where 'g' is an elliptic curve generator and 'τ' is a hidden, random field element—while ensuring 'τ' remains secret from any adversary.

Existing methods for generating q-SDH parameters suffer from critical limitations. They are highly sequential, rely on strong synchrony assumptions, and incur prohibitive communication and computation costs, often scaling as O(nq) communication and O(n) rounds for 'n' parties and 'q' parameters. Such costs can translate to days of computation for practical 'q' values (e.g., 2^28). Furthermore, current deployments frequently depend on a trusted third party to sample 'τ' and compute the powers, creating a single point of failure. The lack of robustness in asynchronous environments, where parties might time out or an adversary could exploit temporary network disruptions, further exacerbates these issues. This paper directly addresses these challenges, presenting the first distributed protocol capable of generating these critical parameters efficiently and securely under realistic asynchronous network conditions, thereby enhancing the security and resilience of cryptographic systems.

Background

[▶ Watch: Introduction: Importance of q-SDH and existing protocol limitations. (0:00)]()

The security of many advanced cryptographic constructions hinges on the q-Strong Diffie-Hellman (q-SDH) assumption. Defined as the intractability for any Probabilistic Polynomial Time (PPT) adversary to compute (τ+c)⁻¹g for any c ≠ -τ, given the q-SDH parameters g, τg, τ²g, ..., τºg, this assumption underscores the necessity of keeping 'τ' secret. Existing protocols for q-SDH parameter generation, notably those by Ben-Sasson et al., Kohlweiss et al., Bowe et al., and Nikolaenko et al., generally follow a blueprint established in Ben-Sasson et al. These methods are designed for synchronous networks and typically rely on a Byzantine broadcast channel. They operate in a round-robin fashion, where each party contributes its private randomness to update the parameters, with the security intuition that at least one honest party's contribution will keep 'τ' hidden.

However, adapting these synchronous, round-robin protocols to an asynchronous setting introduces fundamental difficulties. A Byzantine broadcast channel, which guarantees that all honest parties deliver the same message from a sender, cannot be reliably implemented in asynchrony. The core problem is the inability to distinguish between a malicious party intentionally withholding a message and an honest party experiencing network delays. Standard reliable broadcast definitions are insufficient, and even stronger notions like atomic broadcast cannot ensure the sequential, round-robin contribution of specific parties in an asynchronous environment.

To overcome these challenges, the proposed protocol builds upon several advanced cryptographic primitives. It leverages Threshold Secret Sharing, specifically Shamir's scheme, where a secret is distributed among parties such that a threshold 'k' shares can reconstruct it, while fewer reveal no information. For practical efficiency, the protocol assumes the existence of a Public Key Infrastructure (PKI), though it can be instantiated without it at higher costs. A crucial building block is Asynchronous Distributed Key Generation (ADKG), utilizing a protocol from Cachin et al. (2001). This ADKG generates an (n, t+1) Shamir secret sharing of a random value 'τ', along with its public key τg and threshold public keys τjg, with O(n²) communication and O(log n) expected rounds. The protocol also relies on Asynchronous Double Sharing of Random Values, again drawing from Cachin et al., which provides secret shares of a random field element 'z' using both degree 't' and degree '2t' polynomials, along with public group elements zg and z2tg. These modifications facilitate simulation-based security proofs while maintaining O(n²) communication and O(log n) round complexity. For verification, the protocol employs Bilinear Pairings, efficiently computable functions (e: G1 x G2 → GT) with bilinear and non-degenerate properties. Finally, Zero-Knowledge Proofs for Equality of Discrete Logarithm are essential, specifically the Chaum-Pedersen Σ-protocol, which proves knowledge of a witness 'a' such that 'a = ag' and 'b = ah', and can be made non-interactive using the Fiat-Shamir heuristic in the Random Oracle model.

Key Findings

[▶ Watch: Asynchronous network challenges for existing q-SDH protocols. (2:00)]()

The "Powers of Tau in Asynchrony" talk presents several significant advancements in the field of distributed cryptography:

• First Asynchronous Protocol for q-SDH: The most prominent contribution is the design and implementation of the first distributed protocol capable of generating q-SDH parameters in an asynchronous network. This directly addresses a critical gap in existing cryptographic infrastructure, which previously relied on synchronous assumptions or trusted third parties.
• Optimal Fault Tolerance: The protocol is robust against a powerful malicious adversary that can corrupt up to 't' parties, operating under the assumption that n ≥ 3t + 1. This threshold is optimal for achieving consensus and security in asynchronous network models, ensuring high resilience even with significant adversarial control.
• Substantial Performance Improvements: The protocol achieves remarkable efficiency gains over state-of-the-art synchronous protocols. Benchmarking demonstrates that it is 2 to 6 times faster in terms of runtime and utilizes 4 to 13 times less per-party bandwidth. For instance, with 128 parties and q = 2^18, the protocol was 6.1 times faster and used 13 times less bandwidth than the baseline.
• Efficient Complexity Metrics: The theoretical analysis confirms its efficiency:
• Expected Round Complexity: O(log q + log n).
• Per-Party Communication Cost: O(q + n² log q), which is optimal when q ≥ n² log q.
• Per-Party Computation Cost: O(q log n) group multiplications and O(n log q) bilinear pairings.
• Responsiveness: Unlike synchronous protocols tied to fixed-time rounds, this protocol is responsive, meaning it makes progress at the actual speed of the network, adapting dynamically to varying network conditions.
• Rigorous Security and Practicality: The protocol is backed by a rigorous security analysis based on simulatability in the asynchronous setting. Furthermore, its practical implementation and extensive evaluation on up to 128 geographically distributed parties on AWS demonstrate its real-world viability and scalability.

Technical Deep Dive

[▶ Watch: Foundation: Asynchronous Distributed Key Generation (ADKG) protocol. (3:15)]()

The core innovation of this protocol lies in its two-phase approach to computing the q-SDH parameters (g, τg, ..., τºg) in an asynchronous network. The fundamental idea is to first securely establish τg and secret shares τi for each party, and then leverage these to efficiently compute higher powers of τ. A naive approach, where each party computes τiτkg and multicasts it for reconstruction, would be highly inefficient (O(q) rounds, O(nq) communication) and vulnerable to malicious parties sending inconsistent messages.

To ensure correctness and robustness, the protocol introduces a validation mechanism using Non-Interactive Zero-Knowledge (NIZK) proofs. When a party sends a computed value like τiτkg, it attaches a NIZK proof (πi) demonstrating the correct computation from τkg and τig. The overall protocol, IqSDH (Algorithm 1), orchestrates three main phases:

1. Setup Phase: This phase establishes the foundational cryptographic elements.

• ADKG Execution: Parties run an Asynchronous Distributed Key Generation (ADKG) protocol. This yields an (n, t+1) Shamir secret sharing of a uniformly random secret 'τ' (where each party 'i' holds τi), the public key τg, and threshold public keys τjg.
• Double Sharing Execution: Concurrently, parties execute the FDou protocol to generate random double sharings for log q uniform secrets. For each k from 0 to log q - 1, this provides Zkg, Zk2tg, and their corresponding secret shares Zki, Zk2ti. These are vital for the subsequent squaring protocol.

2. Powers-of-Two Phase: This phase iteratively computes powers of τ that are powers of two, i.e., τ(2k)g.

• Starting with τg (from ADKG), parties compute τ(2k)g for k from 1 to log q.
• This is achieved by sequentially invoking a customized Secure Multiparty Computation (MPC) functionality for squaring, Fsq, which is realized by the Isq protocol (Algorithm 2).
• Isq Protocol (Fsq Realization): Isq takes as input the secret sharing of a value 'a' (ai) and its public group element (ag), and outputs the secret sharing of a² (a²i) and its public group element (a²g). Each party 'i' locally computes aiai. To hide intermediate values and ensure correctness, parties add a random double share z2t (obtained from FDou) to get a² + z. Each party then computes a NIZK proof πi for the equality of discrete logarithms between g, aig, aig, aiaig. These values, along with aiai + z2t, are then multicast. Upon receiving 2t+1 valid messages, parties reconstruct a² + z using Lagrange interpolation. Finally, each party 'i' computes its share of a² as a²i = a² + z - zi, and for each party 'j', computes a²jg = (a² + z)g - zjg. This Isq protocol incurs a communication cost of O(n²) per invocation. By invoking Isq sequentially log q times, all powers of two (τg, τ²g, τ⁴g, ..., τ(2^log q)g) are computed.

3. All Powers Phase (Hall Protocol, Algorithm 3): This final phase computes all remaining powers τag for any a ≤ q.

• Memoization (Binary Tree): The key insight is that any integer 'a' can be expressed in binary as a sum of powers of two. For example, if a = 2^k1 + 2^k2, then τag = τ(2^k1)g * τ(2^k2)g. To optimize this, a binary tree structure (Figure 3) is employed, where leaves represent each 'a' from 0 to 'q'. Each node 's' is associated with val(s) = τsg. Traversing the tree from the root allows computation of τag by multiplying corresponding powers of two. While this reduces exponent multiplications to O(q), a naive application would still result in O(nq) per-party communication.
• Batched Multiplication in the Exponent (BatMul, Algorithm 4): To drastically reduce communication and computation, the BatMul protocol is introduced. It takes secret shares αi, public αg, and a vector of public group elements β1g, ..., βmg, and efficiently computes αβ1g, ..., αβmg.
• Instead of separate computations for each αβkg, BatMul divides the 'm' inputs into 'l' batches, where l = m/(n-t).
• Crucially, BatMul batches NIZK proofs for SHARE messages. Instead of sending 'l' individual proofs, parties send a single proof for a random linear combination of all batches.
• Similarly, EVAL messages are batched, combining multiple checks into a single bilinear pairing check.
• This batching strategy reduces per-party communication to O(n+m) and computation to O(m log n) group multiplications and O(n) pairings.
• When applied to the Hall protocol, BatMul computes values at each height 'h' of the binary tree by multiplying with τ(2^h) and the node values βkg. This brings the total per-party communication cost down to O(q + n log q) and computation cost to O(q log n) group multiplications and O(n log q) bilinear pairings.

Threat Model and Security Analysis: The protocol operates under a standard asynchronous network model with pairwise authenticated channels. The adversary is a Probabilistic Polynomial Time (PPT) malicious adversary that can corrupt up to 't' parties, with the optimal threshold n ≥ 3t + 1. The security definition requires both Correctness (honest parties eventually terminate and output identical, uniformly random q-SDH parameters) and Security (simulatability: an adversary's view in the real protocol is indistinguishable from its view when interacting with an ideal functionality, implying that breaking q-SDH with generated parameters means breaking it for ideal parameters). The proof of correctness relies on a hybrid model, leveraging the ideal functionalities of ADKG and Double Sharing, and the secure realization of Fsq by Isq, combined with NIZK proofs. The proof of security involves constructing a PPT simulator, SqSDH (Figure 4), that simulates the adversary's view using simulators for underlying primitives (SADKG, SDou, Ssq, Sdleq) and hybrid arguments, leveraging the perfect zero-knowledge of Chaum-Pedersen and perfect hiding of Pedersen commitments.

Demo / Proof of Concept

[▶ Watch: Verification tools: Bilinear pairings and zero-knowledge proofs. (4:00)]()

To validate the practical performance and scalability of the protocol, a robust implementation and extensive evaluation were conducted.

Implementation Details:

• The protocol was implemented in Python 3.7.13, leveraging Rust libraries for computationally intensive cryptographic operations to ensure efficiency.
• asyncio was used for concurrency, although the prototype maintained a single-threaded architecture per party.
• The codebase was built upon an existing open-source asynchronous DKG codebase from Cachin et al. (2001), with the random double-sharing protocol implemented as described in Appendix C of their paper.
• Cryptographic Primitives:
• Elliptic Curve: The widely used BLS12381 elliptic curve was chosen, utilizing an implementation from Zcash (wrapped in Python). This pairing-friendly curve involves three groups (G1, G2, GT). q-SDH parameters were generated in G1, which is more efficient. A G1 group element, after point compression, occupies 48 Bytes, while a G2 element is 96 Bytes.
• Zero-Knowledge Proofs: For equality of discrete logarithm, the Chaum-Pedersen Σ-protocol (18) was employed. Benchmarking confirmed its efficiency, being approximately 2.75 times more computationally efficient than a pairing-based check.
• Polynomial Operations: For computing polynomial coefficients (degree n-t-1), an FNT-based NTT implementation from Soro and Lacan (51) was used, offering O(n log n) time complexity. While both quadratic and FNT-based approaches were implemented, the quadratic one surprisingly performed better for smaller numbers of parties in microbenchmarks.
• External Verification: For an external verifier 'V' to confirm the correctness and security of the generated q-SDH parameters, a PKI is assumed. Each participating party signs the final output using its private key and sends this signature to 'V'. The verifier then waits for t+1 valid signatures on the matching output, ensuring integrity and authenticity.

Evaluation and Results:

The evaluation setup was designed to simulate realistic distributed environments.

• Number of Parties (n): Tested with 16, 32, 64, and 128 parties.
• Degree of q (q): Evaluated for q values of 2^14, 2^16, and 2^18.
• Infrastructure: All parties were deployed on Amazon Web Services (AWS) t3x.large virtual machines, with one party per VM (4 vCPUs, 16GB RAM, Ubuntu 20.04).
• Network: Parties were geographically distributed across eight different AWS regions (Canada, Ireland, N. California, N. Virginia, Oregon, Ohio, Singapore, and Tokyo), forming a complete graph overlay network.
• Metrics: Measured runtime (protocol start to output) and per-party bandwidth usage (total data sent by a party, in Megabytes).

Baseline Comparison: The protocol was benchmarked against a state-of-the-art sequential synchronous protocol (Section I, incorporating update verification from Nikolaenko et al. (46)). This baseline's verification cost was optimized from 2q pairings to 2q group multiplications and 2 pairings, with a pipelined verification step. Baseline runtime was approximated as 3nq group multiplications, and bandwidth as nq G1 group elements (48 Bytes each), which actually favored the baseline by not accounting for synchronous broadcast overhead.

Evaluation Results:

• Runtime (Figure 6, Table IV):
• The asynchronous protocol demonstrated significant speed improvements. For 64 parties and q = 2^16, it took approximately 1037 seconds, compared to 3580 seconds for the baseline, making it 3.4 times faster.
• For 128 parties and q = 2^18, the protocol completed in approximately 4721 seconds, while the baseline took 28883 seconds (not shown in figure), a 6.1 times speedup.
• Runtime scaled logarithmically with 'n' and linearly with 'q' (for large 'q'). Smaller 'n' showed linear growth with 'n' due to smaller constants in the O(nq) term.
• Runtime Breakdown: The Powers-of-Two phase consistently took less than 2% of total runtime. The Setup phase's contribution varied from 4.3% (n=16, q=2^14) to 41% (n=128, q=2^14). The All Powers phase dominated for smaller 'n' and larger 'q', contributing 57.7% (n=128, q=2^14) to 99.5% (n=16, q=2^18). For larger 'n', the Setup phase's computation cost became more significant.

• Bandwidth Usage (Figure 5, Table V):
• The protocol achieved substantial bandwidth reductions. With 32 parties and q = 2^16, each party sent 13.57 Megabytes (MB), compared to 96 MB for the baseline, a 7 times reduction.
• For 128 parties and q = 2^18, our protocol used 118.17 MB, versus 1536 MB for the baseline, a 13 times reduction.
• Bandwidth usage scaled quadratically with 'n' and linearly with 'q'.
• Bandwidth Breakdown: The Powers-of-Two phase used less than 3% of bandwidth. The Setup phase's bandwidth usage was significant, especially for large 'n' and small 'q' (e.g., n=128, q=2^14, setup accounted for 95% of bandwidth), due to the O((n² log q)/q) ratio of setup bandwidth to all-powers bandwidth.

Overall Findings: The evaluation results strongly corroborated the theoretical analysis, confirming the protocol's practicality, scalability, and efficiency. Computation cost was identified as the primary bottleneck for the protocol, and while the Setup phase contributed a large portion of bandwidth in some configurations, its runtime impact was comparatively small, indicating efficient computation within that phase.

Defensive Implications

[▶ Watch: Core technical approach: secure τg and NIZK-validated updates. (4:30)]()

The "Powers of Tau in Asynchrony" protocol offers profound implications for defenders and developers building systems reliant on advanced cryptographic primitives like SNARKs, polynomial commitments, and verifiable secret sharing.

Firstly, it provides a robust, distributed alternative to the prevailing practice of relying on a trusted third party (TTP) for generating q-SDH parameters. The TTP model inherently introduces a single point of failure and requires significant trust, which is often undesirable in security-critical applications. By enabling distributed generation in an asynchronous setting, this protocol eliminates the need for a TTP, thereby significantly reducing the attack surface and enhancing the overall security posture of systems that consume these parameters. Defenders can now advocate for and implement TTP-free setups for their SNARK-based systems.

Secondly, the protocol's resilience to an asynchronous network model addresses a critical vulnerability in prior synchronous approaches. Real-world networks are inherently asynchronous and prone to delays, packet loss, and temporary outages. Synchronous protocols break down under such conditions, potentially leading to reduced fault tolerance or even security compromises if an adversary can exploit network timing. This asynchronous design ensures that the parameter generation process remains robust even when parties experience varying network speeds or temporary disconnections, making it suitable for geographically distributed deployments and enhancing system reliability. Defenders can now deploy q-SDH generation processes with greater confidence in dynamic and unpredictable network environments.

Finally, the substantial performance gains in both runtime (2-6x faster) and bandwidth usage (4-13x reduction) mean that secure, distributed generation of q-SDH parameters is no longer a prohibitively expensive operation. This efficiency makes it practical to regenerate these parameters more frequently if needed, or to support larger 'q' values (e.g., for more complex SNARKs), without incurring excessive operational costs. For organizations deploying systems that require these parameters, this translates to more efficient resource utilization and the ability to scale their cryptographic applications effectively, while maintaining optimal fault tolerance (n >= 3t+1) against malicious actors. The protocol empowers developers to build more secure, resilient, and performant cryptographic systems by providing a foundational component that is both trustworthy and efficient.

Key Takeaways

• The talk introduces the first distributed protocol for generating q-Strong Diffie-Hellman (q-SDH) parameters in an asynchronous network, eliminating reliance on synchronous assumptions or trusted third parties.
• The protocol achieves optimal fault tolerance, securely operating even with up to one-third of participating parties being malicious (n ≥ 3t + 1).
• It demonstrates significant performance improvements over state-of-the-art synchronous methods, being 2 to 6 times faster in runtime and using 4 to 13 times less per-party bandwidth.
• Novel technical approaches include a custom Isq protocol for efficient computation of powers-of-two (τ(2k)g) and a Batched Multiplication (BatMul) protocol with memoization for computing all remaining powers (τag), which drastically reduces communication and computation costs.
• The protocol boasts efficient complexity metrics: O(log q + log n) expected rounds, O(q + n² log q) per-party communication, and O(q log n) group multiplications plus O(n log q) bilinear pairings per party.
• Backed by rigorous security analysis (simulatability) and a practical implementation evaluated on geographically distributed AWS instances, this work paves the way for more secure, efficient, and resilient cryptographic systems, particularly for SNARKs and related primitives.

About the Speaker(s)

Sourav Das is a researcher in the field of cryptography, specializing in distributed protocols and secure multiparty computation. His work, as presented in "Powers of Tau in Asynchrony," demonstrates deep expertise in the design and analysis of cryptographic primitives, particularly those related to asynchronous networks and fault tolerance. He is adept at leveraging advanced cryptographic techniques such as Asynchronous Distributed Key Generation (ADKG), Threshold Secret Sharing, Bilinear Pairings, and Zero-Knowledge Proofs to build robust and efficient systems. Furthermore, his presentation highlights a strong understanding of practical implementation challenges, evident in his use of Python and Rust, and his extensive evaluation of the protocol on cloud infrastructure (AWS) with geographically distributed parties, underscoring a commitment to both theoretical rigor and real-world applicability.