Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Leibniz international proceedings in informatics

Quadratic Asynchronous DKG from Plain Setup

Ittai Abraham, Renas Bacho, Gilad Stern

Published Jan 1, 2026• 0 citations
Publisher

Abstract

Asynchronous distributed key generation (ADKG) is a fundamental primitive for building threshold cryptosystems and fault-tolerant distributed protocols in adversarial network settings. A central objective in this line of work is to achieve ADKG with O(n²) communication and constant round complexity under minimal setup assumptions. Recent progress has led to subcubic-communication ADKG protocols under different trade-offs. Feng and Tang (CRYPTO 2025) presented an ADKG protocol with O(n²) communication and O(1) rounds, but at the cost of a cubic-communication setup phase in which each party posts a linear-sized public key on a public bulletin board. In contrast, Abraham et al. (PODC 2026) achieved an ADKG protocol with a standard setup phase, where each party posts only a constant-sized public key, but with O(n^{2+1/k}) communication and O(k) rounds for a tunable parameter k ≤ log{n}. These results leave open whether one can simultaneously obtain constant-round complexity and quadratic communication under a standard setup phase. In this work, we resolve this open problem by presenting the first ADKG protocol that achieves O(n²) communication and O(1) rounds while requiring only a standard setup phase in which each party posts a constant-sized public key on a public bulletin board. Our protocol is resilient to a strongly adaptive adversary corrupting up to f < n/3 parties and assumes only random oracles and secure erasures, both of which are also assumed by prior subcubic-communication ADKG constructions.

DOI
10.4230/lipics.disc.2026.9

Related papers

Practical Asynchronous Distributed Key Reconfiguration and Its Applications

Hanwen Feng, Ya Gao, Yuan Lu +2 more

In this paper, we study practical constructions of asynchronous distributed key reconfiguration (ADKR), which enables an asynchronous fault-tolerant system with an existing threshold cryptosystem to efficiently generate a new threshold cryptosystem for a reconfigured set of participants. While existing asynchronous distributed threshold key generation (ADKG) protocols theoretically solve ADKR, they fail to deliver satisfactory scalability due to cubic communication overhead, even with simplifications to the reconfiguration setting. We introduce an efficient share-dispersal-then-agree-andrecast paradigm for constructing efficient ADKR while preserving adaptive security. Our method reduces the total overhead to$O\left(\kappa n^{2}\right)$from$O\left(n^{3}\right)$, where$\kappa$is a small constant (typically$\sim 30$or less). And our further optimizations in PVSS minimize redundant computations across different parties and reduce the dominating PVSS verification cost by about one-third. Our techniques developed for ADKR can also be leveraged to improve the asymptotic efficiency of various other asynchronous protocols: (i) it implies the first (coin-assisted) quadratic-communication ADKG; and (ii) it can be extended to realize the first quadratic-communication asynchronous dynamic proactive secret sharing (ADPSS) with adaptive security. Experimental evaluations on a global network of 256 AWS servers show up to 40 % lower latency compared to the state-of-the-art ADKG protocols that are simplified to the reconfiguration setting, highlighting the practicality of our ADKR in large-scale asynchronous systems.

IEEE Symposium on Security and Privacy (S&P)•May 18, 2026•1 citation

Practical Asynchronous Distributed Key Generation

Sourav Das, Thomas Yurek, Zhuolun Xiang +3 more

Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a trusted third party and is a building block to decentralized protocols such as randomness beacons, threshold signatures, and general multiparty computation. Until recently, DKG protocols have assumed the synchronous model and thus are vulnerable when their underlying network assumptions do not hold. The recent advancements in asynchronous DKG protocols are insufficient as they either have poor efficiency or limited functionality, resulting in a lack of concrete implementations. In this paper, we present a simple and concretely efficient asynchronous DKG (ADKG) protocol. In a network of n nodes, our ADKG protocol can tolerate up to $t\lt n/3$ malicious nodes and have an expected $O(\kappa n^{3})$ communication cost, where $\kappa$ is the security parameter. Our ADKG protocol produces a field element as the secret and is thus compatible with off-the-shelf threshold cryptosystems. We implement our ADKG protocol and evaluate it using a network of up to 128 nodes in geographically distributed AWS instances. Our evaluation shows that our protocol takes as low as 3 and 9.5 seconds to terminate for 32 and 64 nodes, respectively. Also, each node sends only 0.7 Megabytes and 2.9 Megabytes of data during the two experiments, respectively.

IEEE Symposium on Security and Privacy (S&P)•May 1, 2022•119 citations

Synchronous Distributed Key Generation without Broadcasts

Nibesh Shrestha, Adithya Bhat, Aniket Kate +1 more

Distributed key generation (DKG) is a key building block in developing many efficient threshold cryptosystems. This work initiates the study of communication complexity and round complexity of DKG protocols over a point-to-point (bounded) synchronous network. Our key result is the first synchronous DKG protocol for discrete log-based cryptosystems with O ( κ n 3 ) communication complexity ( κ denotes a security parameter) that tolerates any t < n / 2 Byzantine faults among n parties. We present two variants of the protocol: (i) a protocol with worst-case O ( κ n 3 ) communication and O ( t ) rounds, and (ii) a protocol with expected O ( κ n 3 ) communication and expected constant rounds. In the process of achieving our results, we design (1) a novel weak gradecast protocol with a communication complexity of O ( κ n 2 ) for linear-sized inputs and constant rounds, (2) a protocol called “recoverable-set-of-shares” for ensuring recovery of shared secrets, (3) an oblivious leader election protocol with O ( κ n 3 ) communication and constant rounds, and (4) a multi-valued validated Byzantine agreement (MVBA) protocol with O ( κ n 3 ) communication complexity for linear-sized inputs and expected constant rounds. Each of these primitives is of independent interest.

IACR Communications in Cryptology•Jul 8, 2024•5 citations

GRandLine: Adaptively Secure DKG and Randomness Beacon with (Log-)Quadratic Communication Complexity

Renas Bacho, Christoph Lenzen, Julian Loss +2 more

A randomness beacon is a source of continuous and publicly verifiable randomness which is of crucial importance for many applications. Existing works on randomness beacons suffer from at least one of the following drawbacks: (i) security only against static (i.e., non-adaptive) adversaries, (ii) each epoch takes many rounds of communication, or (iii) computationally expensive tools such as proof-of-work (PoW) or verifiable delay functions (VDF). In this work, we introduce GRandLine, the first adaptively secure randomness beacon protocol that overcomes all these limitations while preserving simplicity and optimal resilience in the synchronous network setting. We achieve our result in two steps. First, we design a novel distributed key generation (DKG) protocol GRand that runs in O(λ n2 log n ) bits of communication but, unlike most conventional DKG protocols, outputs both secret and public keys as group elements. Here, λ denotes the security parameter. Second, following termination of GRand, parties can use their keys to derive a sequence of randomness beacon values, where each random value costs only a single asynchronous round and O(λ n2) bits of communication. We implement GRandLine and evaluate it using a network of up to 64 parties running in geographically distributed AWS instances. Our evaluation shows that GRandLine can produce about 2 beacon outputs per second in a network of 64 parties. We compare our protocol to the state-of-the-art randomness beacon protocols OptRand (NDSS '23), BRandPiper (CCS '21), and Drand, in the same setting and observe that it vastly outperforms them.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Dec 2, 2024•12 citations

Constant-Round YOSO MPC Without Setup

Sebastian Kolby, Divya Ravi, Sophia Yakoubov

YOSO MPC (Gentry et al., Crypto 2021) is a new MPC framework where each participant can speak at most once. This models an adaptive adversary’s ability to watch the network and corrupt or destroy parties it deems significant based on their communication. By using private channels to anonymous receivers (e.g. by encrypting to a public key whose owner is unknown), the communication complexity of YOSO MPC can scale sublinearly with the total number N of available parties, even when the adversary’s corruption threshold is linear in N (e.g. just under N/2). It was previously an open problem whether YOSO MPC can achieve guaranteed output delivery in a constant number of rounds without relying on trusted setup. In this work, we show that this can indeed be accomplished. We demonstrate three different approaches: the first two (which we call YaOSO and YOSO-GLS) use two and three rounds of communication, respectively. Our third approach (which we call YOSO-LHSS) uses O(d) rounds, where d is the multiplicative depth of the circuit being evaluated; however, it can be used to bootstrap any constant-round YOSO protocol that requires setup, by generating that setup within YOSO-LHSS. Though YOSO-LHSS requires more rounds than our first two approaches, it may be more practical, since the zero knowledge proofs it employs are more efficient to instantiate. As a contribution of independent interest, we introduce a verifiable state propagation UC functionality, which allows parties to send private message which are verifiably derived in the “correct” way (according to the protocol in question) to anonymous receivers. This is a natural functionality to build YOSO protocols on top of.

IACR Communications in Cryptology•Oct 7, 2024•3 citations

Balanced and Adaptively Secure Asynchronous Common Coin and Byzantine Agreement With Sub-Quadratic Communication

Hanwen Feng, Tiancheng Mai, Qiang Tang

Distributed common randomness generation (i.e., the common coin problem) is a cornerstone of randomized distributed computing. While a long line of research has sought scalable solutions, the asynchronous setting remains a challenge. Specifically, while Blum et al. (TCC'21) achieved sub-quadratic communication complexity, their approach lacks “balance”: certain nodes must still send Ω(n) messages, creating a scalability bottleneck. Furthermore, their solution only tolerates a 1/3 - ε fraction of corrupted nodes, whereas the classic construction by Cachin et al. (PODC'00) tolerates up to 1/2 under the same setup assumptions.

ACM Symposium on Principles of Distributed Computing (PODC)•Jul 1, 2026•1 citation
Asynchronous distributed key generation (ADKG) is a fundamental primitive for building threshold cryptosystems and fault-tolerant distributed protocols in adversarial network settings. A central objective in this line of work is to achieve ADKG with O(n²) communication and constant round complexity under minimal setup assumptions. Recent progress has led to subcubic-communication ADKG protocols under different trade-offs. Feng and Tang (CRYPTO 2025) presented an ADKG protocol with O(n²) communication and O(1) rounds, but at the cost of a cubic-communication setup phase in which each party posts a linear-sized public key on a public bulletin board. In contrast, Abraham et al. (PODC 2026) achieved an ADKG protocol with a standard setup phase, where each party posts only a constant-sized public key, but with O(n^{2+1/k}) communication and O(k) rounds for a tunable parameter k ≤ log{n}. These results leave open whether one can simultaneously obtain constant-round complexity and quadratic communication under a standard setup phase. In this work, we resolve this open problem by presenting the first ADKG protocol that achieves O(n²) communication and O(1) rounds while requiring only a standard setup phase in which each party posts a constant-sized public key on a public bulletin board. Our protocol is resilient to a strongly adaptive adversary corrupting up to f < n/3 parties and assumes only random oracles and secure erasures, both of which are also assumed by prior subcubic-communication ADKG constructions.
In this paper, we study practical constructions of asynchronous distributed key reconfiguration (ADKR), which enables an asynchronous fault-tolerant system with an existing threshold cryptosystem to efficiently generate a new threshold cryptosystem for a reconfigured set of participants. While existing asynchronous distributed threshold key generation (ADKG) protocols theoretically solve ADKR, they fail to deliver satisfactory scalability due to cubic communication overhead, even with simplifications to the reconfiguration setting. We introduce an efficient share-dispersal-then-agree-andrecast paradigm for constructing efficient ADKR while preserving adaptive security. Our method reduces the total overhead toO(κn2)O\left(\kappa n^{2}\right)O(κn2)fromO(n3)O\left(n^{3}\right)O(n3), whereκ\kappaκis a small constant (typically∼30\sim 30∼30or less). And our further optimizations in PVSS minimize redundant computations across different parties and reduce the dominating PVSS verification cost by about one-third. Our techniques developed for ADKR can also be leveraged to improve the asymptotic efficiency of various other asynchronous protocols: (i) it implies the first (coin-assisted) quadratic-communication ADKG; and (ii) it can be extended to realize the first quadratic-communication asynchronous dynamic proactive secret sharing (ADPSS) with adaptive security. Experimental evaluations on a global network of 256 AWS servers show up to 40 % lower latency compared to the state-of-the-art ADKG protocols that are simplified to the reconfiguration setting, highlighting the practicality of our ADKR in large-scale asynchronous systems.
Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a trusted third party and is a building block to decentralized protocols such as randomness beacons, threshold signatures, and general multiparty computation. Until recently, DKG protocols have assumed the synchronous model and thus are vulnerable when their underlying network assumptions do not hold. The recent advancements in asynchronous DKG protocols are insufficient as they either have poor efficiency or limited functionality, resulting in a lack of concrete implementations. In this paper, we present a simple and concretely efficient asynchronous DKG (ADKG) protocol. In a network of n nodes, our ADKG protocol can tolerate up to t<n/3t\lt n/3t<n/3 malicious nodes and have an expected O(κn3)O(\kappa n^{3})O(κn3) communication cost, where κ\kappaκ is the security parameter. Our ADKG protocol produces a field element as the secret and is thus compatible with off-the-shelf threshold cryptosystems. We implement our ADKG protocol and evaluate it using a network of up to 128 nodes in geographically distributed AWS instances. Our evaluation shows that our protocol takes as low as 3 and 9.5 seconds to terminate for 32 and 64 nodes, respectively. Also, each node sends only 0.7 Megabytes and 2.9 Megabytes of data during the two experiments, respectively.
Distributed key generation (DKG) is a key building block in developing many efficient threshold cryptosystems. This work initiates the study of communication complexity and round complexity of DKG protocols over a point-to-point (bounded) synchronous network. Our key result is the first synchronous DKG protocol for discrete log-based cryptosystems with O ( κ n 3 ) communication complexity ( κ denotes a security parameter) that tolerates any t < n / 2 Byzantine faults among n parties. We present two variants of the protocol: (i) a protocol with worst-case O ( κ n 3 ) communication and O ( t ) rounds, and (ii) a protocol with expected O ( κ n 3 ) communication and expected constant rounds. In the process of achieving our results, we design (1) a novel weak gradecast protocol with a communication complexity of O ( κ n 2 ) for linear-sized inputs and constant rounds, (2) a protocol called “recoverable-set-of-shares” for ensuring recovery of shared secrets, (3) an oblivious leader election protocol with O ( κ n 3 ) communication and constant rounds, and (4) a multi-valued validated Byzantine agreement (MVBA) protocol with O ( κ n 3 ) communication complexity for linear-sized inputs and expected constant rounds. Each of these primitives is of independent interest.
A randomness beacon is a source of continuous and publicly verifiable randomness which is of crucial importance for many applications. Existing works on randomness beacons suffer from at least one of the following drawbacks: (i) security only against static (i.e., non-adaptive) adversaries, (ii) each epoch takes many rounds of communication, or (iii) computationally expensive tools such as proof-of-work (PoW) or verifiable delay functions (VDF). In this work, we introduce GRandLine, the first adaptively secure randomness beacon protocol that overcomes all these limitations while preserving simplicity and optimal resilience in the synchronous network setting. We achieve our result in two steps. First, we design a novel distributed key generation (DKG) protocol GRand that runs in O(λ n2 log n ) bits of communication but, unlike most conventional DKG protocols, outputs both secret and public keys as group elements. Here, λ denotes the security parameter. Second, following termination of GRand, parties can use their keys to derive a sequence of randomness beacon values, where each random value costs only a single asynchronous round and O(λ n2) bits of communication. We implement GRandLine and evaluate it using a network of up to 64 parties running in geographically distributed AWS instances. Our evaluation shows that GRandLine can produce about 2 beacon outputs per second in a network of 64 parties. We compare our protocol to the state-of-the-art randomness beacon protocols OptRand (NDSS '23), BRandPiper (CCS '21), and Drand, in the same setting and observe that it vastly outperforms them.
YOSO MPC (Gentry et al., Crypto 2021) is a new MPC framework where each participant can speak at most once. This models an adaptive adversary’s ability to watch the network and corrupt or destroy parties it deems significant based on their communication. By using private channels to anonymous receivers (e.g. by encrypting to a public key whose owner is unknown), the communication complexity of YOSO MPC can scale sublinearly with the total number N of available parties, even when the adversary’s corruption threshold is linear in N (e.g. just under N/2). It was previously an open problem whether YOSO MPC can achieve guaranteed output delivery in a constant number of rounds without relying on trusted setup. In this work, we show that this can indeed be accomplished. We demonstrate three different approaches: the first two (which we call YaOSO and YOSO-GLS) use two and three rounds of communication, respectively. Our third approach (which we call YOSO-LHSS) uses O(d) rounds, where d is the multiplicative depth of the circuit being evaluated; however, it can be used to bootstrap any constant-round YOSO protocol that requires setup, by generating that setup within YOSO-LHSS. Though YOSO-LHSS requires more rounds than our first two approaches, it may be more practical, since the zero knowledge proofs it employs are more efficient to instantiate. As a contribution of independent interest, we introduce a verifiable state propagation UC functionality, which allows parties to send private message which are verifiably derived in the “correct” way (according to the protocol in question) to anonymous receivers. This is a natural functionality to build YOSO protocols on top of.
Distributed common randomness generation (i.e., the common coin problem) is a cornerstone of randomized distributed computing. While a long line of research has sought scalable solutions, the asynchronous setting remains a challenge. Specifically, while Blum et al. (TCC'21) achieved sub-quadratic communication complexity, their approach lacks “balance”: certain nodes must still send Ω(n) messages, creating a scalability bottleneck. Furthermore, their solution only tolerates a 1/3 - ε fraction of corrupted nodes, whereas the classic construction by Cachin et al. (PODC'00) tolerates up to 1/2 under the same setup assumptions.