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

Distributed Randomness from Approximate Agreement

Freitas, Luciano, Petr Kuznetsov, Andrei Tonkikh

Published Jan 1, 2022• 2 citations
Publisher

Abstract

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.

DOI
10.4230/lipics.disc.2022.24

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

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•0 citations

Resource-Efficient Common Randomness and Secret-Key Schemes

Badih Ghazi, T. S. Jayram

We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with connections to communication under uncertainty and locality sensitive hashing. We take the approach of treating correlated sources as a critical resource, and ask whether common randomness can be generated resource-efficiently. We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicit schemes that use only a polynomial number of samples (in the key length) so that the players can generate shared keys that agree with constant probability using optimal communication. The best previously known schemes were both non-constructive and used an exponential number of samples. In the amortized setting, we characterize the largest achievable ratio of key length to communication in terms of the external and internal information costs, two well-studied quantities in theoretical computer science. In the relaxed setting where the two parties merely wish to improve the correlation between the generated keys of length k, we show that there are no interactive protocols using o(k) bits of communication having agreement probability even as small as 2–o(k). For the related communication problem where the players wish to compute a joint function f of their inputs using i.i.d samples from a known source, we give a simultaneous message passing protocol using 2O(c) bits where c is the interactive randomized public-coin communication complexity of f. This matches the lower bound shown previously while the best previously known upper bound was doubly exponential in c. Our schemes reveal a new connection between common randomness and unbiased error-correcting codes, e.g., dual-BCH codes and their analogues in Euclidean space.

arXiv:1707.08086•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2018•14 citations

Fast quantum byzantine agreement

Michael Ben-Or, Avinatan Hassidim

We present a fast quantum Byzantine Agreement protocol that can reach agreement in O(1) expected communication rounds against a strong full information, dynamic adversary, tolerating up to the optimal t‹n3 faulty players in the synchronous setting, and up to t‹n4 faulty players for asynchronous systems. This should be contrasted with the known classical synchronous lower bound of Ω(√ nlog n) [3] when t=(n).

ACM Symposium on Theory of Computing (STOC)•May 22, 2005•120 citations

Practical generation of common random strings for secure multiparty computations over the Internet

István Vajda

It is known that most of the interesting multiparty cryptographic tasks cannot be implemented securely without trusted setup in a general concurrent network environment like the Internet. We need an appropriate trusted third party to solve this problem. An important trusted setup is a public random string shared by the parties. We present a practical n-bit coin toss protocol for provably secure implementation of such setup. Our idea is inviting external peers into the execution of the protocol to establish an honest majority among the parties. We guarantee security in the presence of an unconditional, static, malicious adversary. Additionally, we present an original practical idea of using live public radio broadcast channels for the generation of common physical random source.

Transactions on Networks and Communications•Dec 31, 2020•0 citations

Network Extractor Protocols

Yael Tauman Kalai, Xin Li, Anup Rao +1 more

We design efficient protocols for processors to extract private randomness over a network with Byzantine faults, when each processor has access to an independent weakly-random n-bit source of sufficient min-entropy.We give several such network extractor protocols in both the information theoretic and computational settings.For a computationally unbounded adversary, we construct protocols in both the synchronous and asynchronous settings.These network extractors imply efficient protocols for leader election (synchronous setting only) and Byzantine agreement which tolerate a linear fraction of faults,even when the min-entropy is only 2(logn)Omega(1).For larger min-entropy,in the synchronous setting the fraction of tolerable faults approaches the bounds in the perfect-randomness case.Our network extractors for a computationally bounded adversary work in the synchronous setting even when 99% of the parties are faulty, assuming trapdoor permutations exist. Further, assuming a strong variant of the Decisional Diffie-Hellman Assumption, we construct a network extractor in which all parties receive private randomness. This yields an efficient protocol for secure multi-party computation with imperfect randomness, when the number of parties is at least polylog (n) and where the parties only have access to an independent source with min-entropy nOmega(1).

Annual Symposium on Foundations of Computer Science•Oct 1, 2008•34 citations
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.
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 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.
We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with connections to communication under uncertainty and locality sensitive hashing. We take the approach of treating correlated sources as a critical resource, and ask whether common randomness can be generated resource-efficiently. We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicit schemes that use only a polynomial number of samples (in the key length) so that the players can generate shared keys that agree with constant probability using optimal communication. The best previously known schemes were both non-constructive and used an exponential number of samples. In the amortized setting, we characterize the largest achievable ratio of key length to communication in terms of the external and internal information costs, two well-studied quantities in theoretical computer science. In the relaxed setting where the two parties merely wish to improve the correlation between the generated keys of length k, we show that there are no interactive protocols using o(k) bits of communication having agreement probability even as small as 2–o(k). For the related communication problem where the players wish to compute a joint function f of their inputs using i.i.d samples from a known source, we give a simultaneous message passing protocol using 2O(c) bits where c is the interactive randomized public-coin communication complexity of f. This matches the lower bound shown previously while the best previously known upper bound was doubly exponential in c. Our schemes reveal a new connection between common randomness and unbiased error-correcting codes, e.g., dual-BCH codes and their analogues in Euclidean space.
It is known that most of the interesting multiparty cryptographic tasks cannot be implemented securely without trusted setup in a general concurrent network environment like the Internet. We need an appropriate trusted third party to solve this problem. An important trusted setup is a public random string shared by the parties. We present a practical n-bit coin toss protocol for provably secure implementation of such setup. Our idea is inviting external peers into the execution of the protocol to establish an honest majority among the parties. We guarantee security in the presence of an unconditional, static, malicious adversary. Additionally, we present an original practical idea of using live public radio broadcast channels for the generation of common physical random source.
We design efficient protocols for processors to extract private randomness over a network with Byzantine faults, when each processor has access to an independent weakly-random n-bit source of sufficient min-entropy.We give several such network extractor protocols in both the information theoretic and computational settings.For a computationally unbounded adversary, we construct protocols in both the synchronous and asynchronous settings.These network extractors imply efficient protocols for leader election (synchronous setting only) and Byzantine agreement which tolerate a linear fraction of faults,even when the min-entropy is only 2(logn)Omega(1).For larger min-entropy,in the synchronous setting the fraction of tolerable faults approaches the bounds in the perfect-randomness case.Our network extractors for a computationally bounded adversary work in the synchronous setting even when 99% of the parties are faulty, assuming trapdoor permutations exist. Further, assuming a strong variant of the Decisional Diffie-Hellman Assumption, we construct a network extractor in which all parties receive private randomness. This yields an efficient protocol for secure multi-party computation with imperfect randomness, when the number of parties is at least polylog (n) and where the parties only have access to an independent source with min-entropy nOmega(1).