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 Reconfiguration and Its Applications

Hanwen Feng, Ya Gao, Yuan Lu, Qiang Tang, J Q Xu

Published May 18, 2026• 1 citation
Publisher

Abstract

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.

DOI
10.1109/sp63933.2026.00033

Related papers

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

Quadratic Asynchronous DKG from Plain Setup

Ittai Abraham, Renas Bacho, Gilad Stern

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.

Leibniz international proceedings in informatics•Jan 1, 2026•0 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•50 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•5 citations

An Improved Threshold Homomorphic Cryptosystem Based on Class Groups

Lennart Braun, Guilhem Castagnos, Ivan Damgård +4 more

We present distributed key generation and decryption protocols for an additively homomorphic cryptosystem based on class groups, improving on a similar system proposed by Braun, Damgård, and Orlandi at CRYPTO ‘23. Our key generation is similarly constant round but achieves lower communication complexity than the previous work. This improvement is in part the result of relaxing the reconstruction property required of the underlying integer verifiable secret sharing scheme. This eliminates the reliance on potentially costly proofs of knowledge in unknown order groups. We present a new method to batch zero-knowledge proofs in unknown order groups which strengthens these improvements. We also present a protocol which is proven secure against adaptive adversaries in the single inconsistent player (SIP) model. Our protocols are secure in the universal composability (UC) framework and provide guaranteed output delivery. We demonstrate the relative efficiency of our techniques by presenting the running times and communication costs associated with our implementation of the statically secure protocol and provide a direct comparison with alternate state of the art constructions.

Lecture notes in computer science•Jan 1, 2024•9 citations
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.
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.
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.
We present distributed key generation and decryption protocols for an additively homomorphic cryptosystem based on class groups, improving on a similar system proposed by Braun, Damgård, and Orlandi at CRYPTO ‘23. Our key generation is similarly constant round but achieves lower communication complexity than the previous work. This improvement is in part the result of relaxing the reconstruction property required of the underlying integer verifiable secret sharing scheme. This eliminates the reliance on potentially costly proofs of knowledge in unknown order groups. We present a new method to batch zero-knowledge proofs in unknown order groups which strengthens these improvements. We also present a protocol which is proven secure against adaptive adversaries in the single inconsistent player (SIP) model. Our protocols are secure in the universal composability (UC) framework and provide guaranteed output delivery. We demonstrate the relative efficiency of our techniques by presenting the running times and communication costs associated with our implementation of the statically secure protocol and provide a direct comparison with alternate state of the art constructions.