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

IEEE Symposium on Security and Privacy (S&P)

Practical Asynchronous Distributed Key Generation

Sourav Das, Thomas Yurek, Zhuolun Xiang, Andrew K. Miller, Lefteris Kokoris-Kogias, Ling Ren

Published May 1, 2022• 108 citations
Publisher

Abstract

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.

DOI
10.1109/sp46214.2022.9833584

Related papers

Asynchronous Distributed Key Generation for Computationally-Secure Randomness, Consensus, and Threshold Signatures.

Eleftherios Kokoris Kogias, Dahlia Malkhi, Alexander Spiegelman

In this paper, we present the first Asynchronous Distributed Key Generation (ADKG) algorithm which is also the first distributed key generation algorithm that can generate cryptographic keys with a dual (f,2f+1)-threshold (where f is the number of faulty parties). As a result, using our ADKG we remove the trusted setup assumption that the most scalable consensus algorithms make. In order to create a DKG with a dual (f,2f+1)- threshold we first answer in the affirmative the open question posed by Cachin et al. [7] on how to create an Asynchronous Verifiable Secret Sharing (AVSS) protocol with a reconstruction threshold of f+1<k łe 2f+1, which is of independent interest. Our High-threshold-AVSS (HAVSS) uses an asymmetric bivariate polynomial to encode the secret. This enables the reconstruction of the secret only if a set of k nodes contribute while allowing an honest node that did not participate in the sharing phase to recover his share with the help of f+1 honest parties. Once we have HAVSS we can use it to bootstrap scalable partially synchronous consensus protocols, but the question on how to get a DKG in asynchrony remains as we need a way to produce common randomness. The solution comes from a novelEventually Perfect Common Coin (EPCC) abstraction that enables the generation of a common coin from n concurrent HAVSS invocations. EPCC's key property is that it is eventually reliable, as it might fail to agree at most f times (even if invoked a polynomial number of times). UsingEPCC we implement anEventually Efficient Asynchronous Binary Agreement (EEABA) which is optimal when the EPCC agrees and protects safety when EPCC fails. Finally, using EEABA we construct the first ADKG which has the same overhead and expected runtime as the best partially-synchronous DKG (O(n4) words, O(f) rounds). As a corollary of our ADKG, we can also create the first Validated Asynchronous Byzantine Agreement (VABA) that does not need a trusted dealer to setup threshold signatures of degree n-f. Our VABA has an overhead of expected O(n2) words and O(1) time per instance, after an initial O(n4) words and O(f) time bootstrap via ADKG.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 30, 2020•118 citations

Distributed Key Generation in the Wild.

Aniket Kate, Yizhou Huang, Ian Goldberg

Distributed key generation (DKG) has been studied extensively in the cryptographic literature. However, it has never been examined outside of the synchronous setting, and the known DKG protocols cannot guarantee safety or liveness over the Internet. In this work, we present the first realistic DKG protocol for use over the Internet. We propose a practical system model for the Internet and define an efficient verifiable secret sharing (VSS) scheme in it. We observe the necessity of Byzantine agreement for asynchronous DKG and analyze the difficulty of using a randomized protocol for it. Using our VSS scheme and a leader-based agreement protocol, we then design a provably secure DKG protocol. We also consider and achieve cryptographic properties such as uniform randomness of the shared secret and compare static versus adaptive adversary models. Finally, we implement our DKG protocol, and establish its efficiency and reliability by extensively testing it on the PlanetLab platform. Counter to a general non-scalability perception about asynchronous systems, our experiments demonstrate that our asynchronous DKG protocol scales well with the system size and it is suitable for realizing multiparty computation and threshold cryptography over the Internet.

•Jan 1, 2012•52 citations

Powers of Tau in Asynchrony

Sourav Das, Zhuolun Xiang, Ling Ren

The q-Strong Diffie-Hellman (q-SDH) parameters are foundational to efficient constructions of many cryptographic primitives such as zero-knowledge succinct non-interactive arguments of knowledge, polynomial/vector commitments, verifiable secret sharing, and randomness beacon.The only existing method to generate these parameters securely is highly sequential, requires synchrony assumptions, and has very high communication and computation costs.For example, to generate parameters for any given q, each party incurs a communication cost of Ω(nq) and requires Ω(n) rounds.Here n is the number of parties in the secure multiparty computation protocol.Since q is typically large, i.e., on the order of billions, the cost is highly prohibitive.In this paper, we present a distributed protocol to generate q-SDH parameters in an asynchronous network.In a network of n parties, our protocol tolerates up to one-third of malicious parties.Each party incurs a communication cost of O(q+n 2 log q) and the protocol finishes in O(log q + log n) expected rounds.We provide a rigorous security analysis of our protocol.We implement our protocol and evaluate it with up to 128 geographically distributed parties.Our evaluation illustrates that our protocol is highly scalable and results in a 2-6× better runtime and 4-13× better per-party bandwidth usage compared to the state-of-theart synchronous protocol for generating q-SDH parameters.

Network and Distributed System Security Symposium•Jan 1, 2024•5 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•4 citations

Quantum Entanglement-Based Distributed Key Generation Protocol

Jincheng Zhang

This paper presents a novel protocol for distributed key generation (DKG) leveraging quantum entanglement. The core claim is to demonstrate the secure and efficient generation of a shared secret key among multiple parties using the unique properties of entangled quantum states. The protocol utilizes a specifically designed entangled state shared between the participating nodes. This shared state facilitates the synchronous generation of keys across the distributed network. The key innovation lies in the enhanced security provided by the fundamental laws of quantum mechanics, eliminating the vulnerabilities inherent in classical DKG protocols susceptible to eavesdropping attacks. Furthermore, the protocol aims to improve key generation efficiency by utilizing the inherent correlations present within the entangled state. We detail the mathematical formulation of the protocol, including the state preparation, entanglement distribution, and key extraction phases. The proposed approach offers a promising direction for secure communication in quantum networks.

•Sep 3, 2026•0 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•10 citations
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.
In this paper, we present the first Asynchronous Distributed Key Generation (ADKG) algorithm which is also the first distributed key generation algorithm that can generate cryptographic keys with a dual (f,2f+1)-threshold (where f is the number of faulty parties). As a result, using our ADKG we remove the trusted setup assumption that the most scalable consensus algorithms make. In order to create a DKG with a dual (f,2f+1)- threshold we first answer in the affirmative the open question posed by Cachin et al. [7] on how to create an Asynchronous Verifiable Secret Sharing (AVSS) protocol with a reconstruction threshold of f+1<k łe 2f+1, which is of independent interest. Our High-threshold-AVSS (HAVSS) uses an asymmetric bivariate polynomial to encode the secret. This enables the reconstruction of the secret only if a set of k nodes contribute while allowing an honest node that did not participate in the sharing phase to recover his share with the help of f+1 honest parties. Once we have HAVSS we can use it to bootstrap scalable partially synchronous consensus protocols, but the question on how to get a DKG in asynchrony remains as we need a way to produce common randomness. The solution comes from a novelEventually Perfect Common Coin (EPCC) abstraction that enables the generation of a common coin from n concurrent HAVSS invocations. EPCC's key property is that it is eventually reliable, as it might fail to agree at most f times (even if invoked a polynomial number of times). UsingEPCC we implement anEventually Efficient Asynchronous Binary Agreement (EEABA) which is optimal when the EPCC agrees and protects safety when EPCC fails. Finally, using EEABA we construct the first ADKG which has the same overhead and expected runtime as the best partially-synchronous DKG (O(n4) words, O(f) rounds). As a corollary of our ADKG, we can also create the first Validated Asynchronous Byzantine Agreement (VABA) that does not need a trusted dealer to setup threshold signatures of degree n-f. Our VABA has an overhead of expected O(n2) words and O(1) time per instance, after an initial O(n4) words and O(f) time bootstrap via ADKG.
Distributed key generation (DKG) has been studied extensively in the cryptographic literature. However, it has never been examined outside of the synchronous setting, and the known DKG protocols cannot guarantee safety or liveness over the Internet. In this work, we present the first realistic DKG protocol for use over the Internet. We propose a practical system model for the Internet and define an efficient verifiable secret sharing (VSS) scheme in it. We observe the necessity of Byzantine agreement for asynchronous DKG and analyze the difficulty of using a randomized protocol for it. Using our VSS scheme and a leader-based agreement protocol, we then design a provably secure DKG protocol. We also consider and achieve cryptographic properties such as uniform randomness of the shared secret and compare static versus adaptive adversary models. Finally, we implement our DKG protocol, and establish its efficiency and reliability by extensively testing it on the PlanetLab platform. Counter to a general non-scalability perception about asynchronous systems, our experiments demonstrate that our asynchronous DKG protocol scales well with the system size and it is suitable for realizing multiparty computation and threshold cryptography over the Internet.
The q-Strong Diffie-Hellman (q-SDH) parameters are foundational to efficient constructions of many cryptographic primitives such as zero-knowledge succinct non-interactive arguments of knowledge, polynomial/vector commitments, verifiable secret sharing, and randomness beacon.The only existing method to generate these parameters securely is highly sequential, requires synchrony assumptions, and has very high communication and computation costs.For example, to generate parameters for any given q, each party incurs a communication cost of Ω(nq) and requires Ω(n) rounds.Here n is the number of parties in the secure multiparty computation protocol.Since q is typically large, i.e., on the order of billions, the cost is highly prohibitive.In this paper, we present a distributed protocol to generate q-SDH parameters in an asynchronous network.In a network of n parties, our protocol tolerates up to one-third of malicious parties.Each party incurs a communication cost of O(q+n 2 log q) and the protocol finishes in O(log q + log n) expected rounds.We provide a rigorous security analysis of our protocol.We implement our protocol and evaluate it with up to 128 geographically distributed parties.Our evaluation illustrates that our protocol is highly scalable and results in a 2-6× better runtime and 4-13× better per-party bandwidth usage compared to the state-of-theart synchronous protocol for generating q-SDH parameters.
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.
This paper presents a novel protocol for distributed key generation (DKG) leveraging quantum entanglement. The core claim is to demonstrate the secure and efficient generation of a shared secret key among multiple parties using the unique properties of entangled quantum states. The protocol utilizes a specifically designed entangled state shared between the participating nodes. This shared state facilitates the synchronous generation of keys across the distributed network. The key innovation lies in the enhanced security provided by the fundamental laws of quantum mechanics, eliminating the vulnerabilities inherent in classical DKG protocols susceptible to eavesdropping attacks. Furthermore, the protocol aims to improve key generation efficiency by utilizing the inherent correlations present within the entangled state. We detail the mathematical formulation of the protocol, including the state preparation, entanglement distribution, and key extraction phases. The proposed approach offers a promising direction for secure communication in quantum networks.
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.