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.
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 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.
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.
This paper introduces a novel Distributed Key Generation (DKG) protocol based on the Commutative Supersingular Isogeny Diffie-Hellman (CSIDH) framework for secure multi-party cryptography. Our proposed protocol is designed to address scalability and security concerns, particularly in post-quantum cryptographic systems. The main contributions include the introduction of Piecewise Verifiable Proofs (PVPs) for non-interactive zero-knowledge verification of secret shares, and the provision of rigorous security analysis, including resistance to quantum adversaries via Shor’s and Grover’s algorithms. We analyze the protocol’s efficiency, ensuring low computational overhead even in large-scale systems, and compare it with other distributed cryptographic protocols such as RSA-based and lattice-based schemes. Through mathematical proofs and complexity analysis, we demonstrate that our protocol offers enhanced security, efficiency, and scalability in a post-quantum environment. The results presented in this paper provide a strong foundation for implementing secure multi-party computations in quantum-resistant systems.
Abstract. Secure multiparty computation (MPC) allows a set of parties to securely evaluate any agreed function of their inputs, even when up to t of the n parties are faulty. Protocols for synchronous networks (where every sent message is assumed to arrive within a constant time) tolerate up to t < n/2 faulty parties, whereas in the more realistic asynchronous setting (with no a priory information on maximal message delay) only security against t < n/3 is possible. Note that even asynchronous Byzantine agreement requires t < n/3. In this paper, we are interested in the minimal synchronicity assumption for achieving security against t < n/2. It turns out that the bottleneck of asynchronous MPC is the distribution of the inputs: Once the inputs are correctly distributed, any deterministic function can be computed over a fully asynchronous network with t < n/2. Furthermore, we show that the inputs can be verifiably distributed with t < n/2, if a single round of synchronous broadcast is available. Composing the above, we obtain the first MPC protocol that achieves security against t < n/2 without assuming a fully synchronous network. Actually our protocol guarantees security against any faulty minority in an almost asynchronous network, i.e. in a network with one single round of synchronous broadcast (followed by a fully asynchronous communication). Furthermore our protocol takes inputs of all parties (in a fully asynchronous network only inputs of n−t parties can be guaranteed), and so achieves everything that is possible in synchronous networks (but impossible in fully asynchronous networks) at the price of just one synchronous broadcast round. As tools for our protocol we introduce the notions of almost non-interactive verifiable secret-sharing and almost non-interactive zero-knowledge proof of knowledge, which are of independent interest as they can serve as efficient replacements for fully non-interactive verifiable secret-sharing and fully non-interactive zero-knowledge proof of knowledge.
Perfectly-secure verifiable secret sharing (VSS) and multi-party computation (MPC) protocols in asynchronous network tolerate only at most one-fourth of corruption, while their counterparts in synchronous network sustain against at most one-third corruption. Moreover property-wise, synchronous protocols provide much stronger guarantees than the asynchronous counterparts. Taking note of the fact that asynchronous network is more realistic on one hand and on the other, synchrony of a network has positive impact on several aspects of distributed protocols including properties and fault-tolerance, we explore the power of hybrid networks that combines best of both the worlds by supporting a few synchronous rounds at the onset of a protocol execution, before turning to asynchronous mode. In hybrid networks, we investigate various feasibility questions pertaining to protocols giving guarantees attainable in synchronous and asynchronous networks. For the asynchronous protocols in hybrid networks, we hope to leverage the initial synchronous rounds to bridge the gap in the fault-tolerance with the synchronous protocols under minimal synchrony assumption. We ask the following fundamental question of both theoretical and practical importance: What is the minimum number of initial synchronous rounds necessary and sufficient in a hybrid network to construct asynchronous perfectly-secure VSS and MPC protocols with the fault-tolerance of synchronous protocols? On the positive note, we show that the answer is one for VSS which is clearly optimal. Notably no broadcast oracle is invoked in the synchronous round of our proposed VSS protocol. On the negative side, we prove that one synchronous round is not enough for MPC, putting MPC on a higher pedestal than VSS in terms of difficulty. For synchronous protocols in hybrid networks, we hope to save on the synchronous rounds leveraging conveniently the available asynchronous phase. We settle the question for VSS in the negative showing that three rounds that are known to be necessary (and sufficient) for VSS in synchronous networks, are also required in hybrid networks. VSS being a special case of MPC, the lower bound holds true for MPC. We match the lower bound with a three-round protocol. Notably, synchronous MPC with cryptographic security is known to be achievable in hybrid networks with one synchronous round.
Multi-party computation (MPC) enables a set of mutually n distrusting parties to compute any function on their private inputs. Mainly, MPC facilitates agreement on the function's output while preserving the secrecy of honest inputs, even against a subset of t parties controlled by an adversary. With applications spanning from anonymous broadcast to private auctions, MPC is considered a cornerstone of distributed cryptography, and significant research efforts have been aimed at making MPC practical in the last decade. However, most libraries either make strong assumptions like the network being bounded synchronous, or incur high computation overhead from the extensive use of expensive public-key operations that prevent them from scaling beyond a few dozen parties. This work presents Velox, an asynchronous MPC protocol that offers fairness against an optimal adversary corrupting up to t < n/3 parties. Velox significantly enhances practicality by leveraging lightweight cryptographic primitives-such as symmetric-key encryption and hash functions-which are 2-3 orders of magnitude faster than public-key operations, resulting in substantial computational efficiency. Moreover, Velox is highly communication-efficient, with linear amortized communication relative to circuit size and only O(n3) field elements of additive overhead. Concretely, Velox requires just 9.33 field elements per party per multiplication gate, more than 10× reduction compared to the state of the art. Moreover, Velox also offers Post-Quantum Security as lightweight cryptographic primitives retain their security against a quantum adversary. We implement Velox comprehensively, covering both offline and online phases, and evaluate its performance on a geographically distributed testbed through a real-world application: anonymous broadcast. Our implementation securely shuffles a batch of k = 256 messages in 4 seconds with n = 16 parties and 18 seconds with n = 64 parties, a 36× and 28.6× reduction in latency compared to the prior best work. At scale with n = 112 parties, Velox is able to shuffle the same batch of messages in under 50 seconds from end to end, illustrating its effectiveness and scalability. Overall, our work removes significant barriers faced by prior asynchronous MPC solutions, making asynchronous MPC practical and efficient for large-scale deployments involving 100s of parties.