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

IEICE Transactions on Information and Systems

An Unbiased Global Coin Flipping Protocol on Synchronous Distributed Systems

Kunikazu Yoda, Yasuo Okabe, Masanori Kanazawa

Published Jan 1, 2001• 1 citation
OpenAlex

Abstract

We present a distributed protocol for achieving totally unbiased global coin flipping in the presence of an adversary.We consider a synchronous system of $n$ processors at most $t$ of which may be corrupted and manipu- lated by a malicious adversary.We assume a complete network where every two processors are connected via a private channel.Our protocol is deterministic and assumes a very powerful adversary.Although it cannot eavesdrop, it is computationally unbounded, capable of rushing and dynamic.This is the same model that is adopted in Yao's global coin flipping protocol [Yao84], which we use as the base of our pro- tocol.Our protocol tolerates almost $n/3$ processor failures and terminates in $t+4$ rounds.The resilience of our protocol is greatly improved from that of Yao's protocol at the expense of running time, which is only added just two rounds.

Related papers

Efficient Distributed Coin-tossing Protocols

Hamidreza Amini Khorasgani, Hemanta K. Maji, Himanshi K. Mehta +1 more

Ben-Or and Linial (1985) introduced the full information model for coin-tossing protocols involving$n$-processors with unbounded computational power using a common broadcast channel for all their communications. A bias-$X$coin-tossing protocol outputs 1 with probability$X$; otherwise, it outputs 0 with probability ($1-X$). A coin-tossing protocol's insecurity is the maximum change in the output distribution (in the statistical distance) that an adversary can cause. This work considers an adversary who monitors the protocol's communication and intervenes at most once by restarting the processor who just broadcast her message. For a given tolerance$\varepsilon$, our objective is to use the minimum number of processors, ensuring that this adversary can only change the output distribution by at most$\epsilon$. Historically, the “threshold coin-tossing protocols” have been optimal or asymptotically optimal against various adversary models. However, for our model, Khorasgani, Maji, and Mukherjee (2019) prove the existence of coin-tossing protocols that achieve the same tolerance as the threshold protocols using a smaller number of processors. Unfortunately, their protocol is not computationally efficient. Towards this objective, for any$x\in(0,1)$and$n\in \mathbb{N}$, this paper presents computationally efficient coin-tossing protocols approximating the new protocols of Khorasgani, Maji, and Mukherjee (2019). This protocol's running time is linear in the inverse of the accuracy parameter of this approximation, which can be set arbitrarily small.

IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•1 citation

Impossibility of Black-Box Reduction from Non-Adaptively to Adaptively Secure Coin-Flipping

Yevgeniy Dodis

Collective Coin-Flipping is a classical problem where n computationally unbounded processors are trying to generate a random bit in a setting where only a single broadcast channel is available for communication. The protocol is said to be b(n)-resilient if any adversary that can corrupt up to b(n) players, still cannot bias the coin to some desired outcome almost certainly. The problem is extensively studied for the case of non-adaptive adversaries who have to decide which players to corrupt before the protocol starts. In particular, it is well-known that the optimum resilience threshold is n=2 in this case. However, none of these protocols is resilient against an adaptive adversary who can corrupt just a single player in the course of the execution. In fact, Ben-Or and Linial [BL90] conjectured that the adaptive adversary is much more powerful than the non-adaptive adversary. More specically, that the optimal resilience threshold for adaptive adversaries is only O( p n) (which is achieved by a simple "majority " protocol). We give strong evidence towards this conjecture by showing that no black-box transformation from any statically secure coin-flipping protocol can yield an adaptively secure protocol tolerating

Electronic colloquium on computational complexity•Jan 1, 2000•9 citations

Limits on the security of coin flips when half the processors are faulty

Richard Cleve

Protocols which allow an asynchronous network of processors to agree on a r andom (unbiased) bit are proposed in [1] and [4]. It is claimed tha t (assuming a t rapdoor funct ion exists), if less than half of the processors are faulty then the correct processors will still agree on a bit whose bias is negligibly small (when the running t ime of the processors is poly(n) the bias is smaller than O(~r) for all k). If half the processors are faulty then these protocols are no longer effective: the bits ou tpu t by the correct processors may be heavily biased. We prove tha t the above protocols are opt imal in the sense tha t no protocol exists which tolerates faults in at least half of the processors. The result is very general because few restr ict ions are made on the types of communicat ion allowed between correct processors (such as pr ivate channels and global channels) and the correct processors only need to agree on a bit in a weak probabil ist ic sense. Also, the faulty processors do not require very much power. They can privately communicate wi th each other but they cannot read messages which are exchanged pr ivately between two correct processors. An interest ing instance of the problem arises when the number of processors is fixed at two and one of t hem

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1986•458 citations

A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip

Iftach Haitner, Yonatan Karidi-Heller

In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems ’83], the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS ’85], the parties communicate over a broadcast channel, and a computationally unbounded adversary can choose which parties to corrupt along the protocol execution. Ben-Or and Linial proved that the n -party majority protocol is resilient to \(O(\sqrt {n})\) corruptions, and conjectured this is a tight upper bound for any n -party protocol (of any round complexity). Their conjecture was proved to be correct, up to polylogarithmic factors, for single-turn (each party sends a single message) single-bit (a message is one bit) protocols Lichtenstein et al. [Combinatorica ’89], symmetric protocols Goldwasser et al. [ICALP ’15], and recently for (arbitrary message length) single-turn protocols Tauman Kalai et al. [DISC ’18]. Yet, the question of many-turn protocols was left entirely open. In this work, we close the above gap, proving that no n -party protocol (of any round complexity) is resilient to \(\Omega (\sqrt {n} \cdot \log ^3 n)\) adaptive corruptions. Namely, majority is the optimal coin-flipping protocol against adaptive adversaries (up to polylogarithmic factors).

arXiv:2005.01565•Annual Symposium on Foundations of Computer Science•Nov 1, 2020•13 citations

An Optimally Fair Coin Toss.

Tal Moran, Moni Naor, Gil Segev

We address one of the foundational problems in cryptography: the bias of coin-\nipping pro-tocols. Coin-\nipping protocols allow mutually distrustful parties to generate a common unbiased random bit, guaranteeing that even if one of the parties is malicious, it cannot signicantly bias the output of the honest party. A classical result by Cleve [STOC '86] showed that for any two-party r-round coin-\nipping protocol there exists an efficient adversary that can bias the output of the honest party by Ω(1=r). However, the best previously known protocol only guarantees O(1= p r) bias, and the question of whether Cleve's bound is tight has remained open for more than twenty years. In this paper we establish the optimal trade-off between the round complexity and the bias of two-party coin-\nipping protocols. Under standard assumptions (the existence of oblivious transfer), we show that Cleve's lower bound is tight: we construct an r-round protocol with bias O(1=r).

•Jan 1, 2009•0 citations

Fair Coin Flipping: Tighter Analysis and the Many-Party Case

Niv Buchbinder, Iftach Haitner, Nissan Levi +1 more

In a multi-party fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. In this work we focus on the case of dishonest majority, ie at least half of the parties can be corrupted. [19] [STOC 1986] has shown that in any m-round coin-flipping protocol the corrupted parties can bias the honest parties’ common output bit by Θ(1/m). For more than two decades the best known coin-flipping protocols against majority was the protocol of [9] [Manuscript 1985], who presented a t-party, m-round protocol with bias This was changed by the breakthrough result of [42] [TCC 2009], who constructed an m-round, two-party coin-flipping protocol with optimal bias Θ(1/m). Recently, [32] [STOC 14] constructed an m-round, three-party coin-flipping protocol with bias O(log3 m/m). Still for the case of more than three parties, against arbitrary number of corruptions, the best known protocol remained the protocol of [9]. We make a step towards eliminating the above gap, presenting a t-party, m-round coin-flipping protocol, with bias This improves upon the protocol of [9] for any t ≤ 1/2 · log log m, and in particular for t ∊ O(1), this yields an protocol. For the three-party case, this yields an protocol, improving over the the O(log3 m/m)-bias protocol of [32]. Our protocol generalizes that of [32], by presenting an appropriate “defense protocols” for the remaining parties to interact in, in the case that some parties abort or caught cheating ([32] only presented a two-party defense protocol, which limits their final protocol to handle three parties). We analyze our new protocols by presenting a new paradigm for analyzing fairness of coin-flipping protocols. We map the set of adversarial strategies that try to bias the honest parties outcome in the protocol to the set of the feasible solutions of a linear program. The gain each strategy achieves is the value of the corresponding solution. We then bound the the optimal value of the linear program by constructing a feasible solution to its dual.

arXiv:2104.08820•ACM-SIAM Symposium on Discrete Algorithms (SODA)•Jan 1, 2017•24 citations
We present a distributed protocol for achieving totally unbiased global coin flipping in the presence of an adversary.We consider a synchronous system of nnn processors at most ttt of which may be corrupted and manipu- lated by a malicious adversary.We assume a complete network where every two processors are connected via a private channel.Our protocol is deterministic and assumes a very powerful adversary.Although it cannot eavesdrop, it is computationally unbounded, capable of rushing and dynamic.This is the same model that is adopted in Yao's global coin flipping protocol [Yao84], which we use as the base of our pro- tocol.Our protocol tolerates almost n/3n/3n/3 processor failures and terminates in t+4t+4t+4 rounds.The resilience of our protocol is greatly improved from that of Yao's protocol at the expense of running time, which is only added just two rounds.
Ben-Or and Linial (1985) introduced the full information model for coin-tossing protocols involvingnnn-processors with unbounded computational power using a common broadcast channel for all their communications. A bias-XXXcoin-tossing protocol outputs 1 with probabilityXXX; otherwise, it outputs 0 with probability (1−X1-X1−X). A coin-tossing protocol's insecurity is the maximum change in the output distribution (in the statistical distance) that an adversary can cause. This work considers an adversary who monitors the protocol's communication and intervenes at most once by restarting the processor who just broadcast her message. For a given toleranceε\varepsilonε, our objective is to use the minimum number of processors, ensuring that this adversary can only change the output distribution by at mostϵ\epsilonϵ. Historically, the “threshold coin-tossing protocols” have been optimal or asymptotically optimal against various adversary models. However, for our model, Khorasgani, Maji, and Mukherjee (2019) prove the existence of coin-tossing protocols that achieve the same tolerance as the threshold protocols using a smaller number of processors. Unfortunately, their protocol is not computationally efficient. Towards this objective, for anyx∈(0,1)x\in(0,1)x∈(0,1)andn∈Nn\in \mathbb{N}n∈N, this paper presents computationally efficient coin-tossing protocols approximating the new protocols of Khorasgani, Maji, and Mukherjee (2019). This protocol's running time is linear in the inverse of the accuracy parameter of this approximation, which can be set arbitrarily small.
Collective Coin-Flipping is a classical problem where n computationally unbounded processors are trying to generate a random bit in a setting where only a single broadcast channel is available for communication. The protocol is said to be b(n)-resilient if any adversary that can corrupt up to b(n) players, still cannot bias the coin to some desired outcome almost certainly. The problem is extensively studied for the case of non-adaptive adversaries who have to decide which players to corrupt before the protocol starts. In particular, it is well-known that the optimum resilience threshold is n=2 in this case. However, none of these protocols is resilient against an adaptive adversary who can corrupt just a single player in the course of the execution. In fact, Ben-Or and Linial [BL90] conjectured that the adaptive adversary is much more powerful than the non-adaptive adversary. More specically, that the optimal resilience threshold for adaptive adversaries is only O( p n) (which is achieved by a simple "majority " protocol). We give strong evidence towards this conjecture by showing that no black-box transformation from any statically secure coin-flipping protocol can yield an adaptively secure protocol tolerating
Protocols which allow an asynchronous network of processors to agree on a r andom (unbiased) bit are proposed in [1] and [4]. It is claimed tha t (assuming a t rapdoor funct ion exists), if less than half of the processors are faulty then the correct processors will still agree on a bit whose bias is negligibly small (when the running t ime of the processors is poly(n) the bias is smaller than O(~r) for all k). If half the processors are faulty then these protocols are no longer effective: the bits ou tpu t by the correct processors may be heavily biased. We prove tha t the above protocols are opt imal in the sense tha t no protocol exists which tolerates faults in at least half of the processors. The result is very general because few restr ict ions are made on the types of communicat ion allowed between correct processors (such as pr ivate channels and global channels) and the correct processors only need to agree on a bit in a weak probabil ist ic sense. Also, the faulty processors do not require very much power. They can privately communicate wi th each other but they cannot read messages which are exchanged pr ivately between two correct processors. An interest ing instance of the problem arises when the number of processors is fixed at two and one of t hem
In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems ’83], the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS ’85], the parties communicate over a broadcast channel, and a computationally unbounded adversary can choose which parties to corrupt along the protocol execution. Ben-Or and Linial proved that the n -party majority protocol is resilient to O(n)O(\sqrt {n})O(n​) corruptions, and conjectured this is a tight upper bound for any n -party protocol (of any round complexity). Their conjecture was proved to be correct, up to polylogarithmic factors, for single-turn (each party sends a single message) single-bit (a message is one bit) protocols Lichtenstein et al. [Combinatorica ’89], symmetric protocols Goldwasser et al. [ICALP ’15], and recently for (arbitrary message length) single-turn protocols Tauman Kalai et al. [DISC ’18]. Yet, the question of many-turn protocols was left entirely open. In this work, we close the above gap, proving that no n -party protocol (of any round complexity) is resilient to Ω(n⋅log⁡3n)\Omega (\sqrt {n} \cdot \log ^3 n)Ω(n​⋅log3n) adaptive corruptions. Namely, majority is the optimal coin-flipping protocol against adaptive adversaries (up to polylogarithmic factors).
We address one of the foundational problems in cryptography: the bias of coin-\nipping pro-tocols. Coin-\nipping protocols allow mutually distrustful parties to generate a common unbiased random bit, guaranteeing that even if one of the parties is malicious, it cannot signicantly bias the output of the honest party. A classical result by Cleve [STOC '86] showed that for any two-party r-round coin-\nipping protocol there exists an efficient adversary that can bias the output of the honest party by Ω(1=r). However, the best previously known protocol only guarantees O(1= p r) bias, and the question of whether Cleve's bound is tight has remained open for more than twenty years. In this paper we establish the optimal trade-off between the round complexity and the bias of two-party coin-\nipping protocols. Under standard assumptions (the existence of oblivious transfer), we show that Cleve's lower bound is tight: we construct an r-round protocol with bias O(1=r).
In a multi-party fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. In this work we focus on the case of dishonest majority, ie at least half of the parties can be corrupted. [19] [STOC 1986] has shown that in any m-round coin-flipping protocol the corrupted parties can bias the honest parties’ common output bit by Θ(1/m). For more than two decades the best known coin-flipping protocols against majority was the protocol of [9] [Manuscript 1985], who presented a t-party, m-round protocol with bias This was changed by the breakthrough result of [42] [TCC 2009], who constructed an m-round, two-party coin-flipping protocol with optimal bias Θ(1/m). Recently, [32] [STOC 14] constructed an m-round, three-party coin-flipping protocol with bias O(log3 m/m). Still for the case of more than three parties, against arbitrary number of corruptions, the best known protocol remained the protocol of [9]. We make a step towards eliminating the above gap, presenting a t-party, m-round coin-flipping protocol, with bias This improves upon the protocol of [9] for any t ≤ 1/2 · log log m, and in particular for t ∊ O(1), this yields an protocol. For the three-party case, this yields an protocol, improving over the the O(log3 m/m)-bias protocol of [32]. Our protocol generalizes that of [32], by presenting an appropriate “defense protocols” for the remaining parties to interact in, in the case that some parties abort or caught cheating ([32] only presented a two-party defense protocol, which limits their final protocol to handle three parties). We analyze our new protocols by presenting a new paradigm for analyzing fairness of coin-flipping protocols. We map the set of adversarial strategies that try to bias the honest parties outcome in the protocol to the set of the feasible solutions of a linear program. The gain each strategy achieves is the value of the corresponding solution. We then bound the the optimal value of the linear program by constructing a feasible solution to its dual.