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.
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) 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/3 malicious nodes and have an expected O(κn3) communication cost, where κ 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) 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.
Randomisation is a critical tool in designing distributed systems. The common coin primitive, enabling the system members to agree on an unpredictable random number, has proven to be particularly useful. We observe, however, that it is impossible to implement a truly random common coin protocol in a fault-prone asynchronous system. To circumvent this impossibility, we introduce two relaxations of the perfect common coin: (1) approximate common coin generating random numbers that are close to each other; and (2) Monte Carlo common coin generating a common random number with an arbitrarily small, but non-zero, probability of failure. Building atop the approximate agreement primitive, we obtain efficient asynchronous implementations of the two abstractions, tolerating up to one third of Byzantine processes. Our protocols do not assume trusted setup or public key infrastructure and converge to the perfect coin exponentially fast in the protocol running time. By plugging one of our protocols for Monte Carlo common coin in a well-known consensus algorithm, we manage to get a binary Byzantine agreement protocol with O(n³ log n) communication complexity, resilient against an adaptive adversary, and tolerating the optimal number f < n/3 of failures without trusted setup or PKI. To the best of our knowledge, the best communication complexity for binary Byzantine agreement achieved so far in this setting is O(n⁴). We also show how the approximate common coin, combined with a variant of Gray code, can be used to solve an interesting problem of Intersecting Random Subsets, which we introduce in this paper.
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.
Abstract. Verifiable Secret Sharing (VSS) is a fundamental primitive used in many distributed cryptographic tasks, such as Multiparty Computation (MPC) and Byzantine Agreement (BA). It is a two phase (sharing, reconstruction) protocol. The VSS and MPC protocols are carried out among n parties, where t out of n parties can be under the influence of a Byzantine (active) adversary, having unbounded computing power. It is well known that protocols for perfectly secure VSS and perfectly secure MPC exist in an asynchronous network iff n ≥ 4t+1. Hence, we call any perfectly secure VSS (MPC) protocol designed over an asynchronous network with n = 4t + 1 as optimally resilient VSS (MPC) protocol. A secret is d-shared among the parties if there exists a random degreed polynomial whose constant term is the secret and each honest party possesses a distinct point on the degree-d polynomial. Typically VSS is used as a primary tool to generate t-sharing of secret(s). In this paper, we present an optimally resilient, perfectly secure Asynchronous VSS (AVSS)
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.