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 International Symposium on Information Theory (ISIT)

Optimally-secure Coin-tossing against a Byzantine Adversary

Hamidreza Amini Khorasgani, Hemanta K. Maji, Mingyuan Wang

Published Jul 12, 2021• 2 citations
Publisher

Abstract

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. For most adversarial settings, the characterization of the exact or asymptotically optimal protocols remains open. Furthermore, even for the settings where near-optimal asymptotic constructions are known, the exact constants or poly-logarithmic multiplicative factors involved are not entirely well-understood. This work studies$n$-processor coin-tossing protocols where every processor broadcasts an arbitrary-length message once. An adaptive Byzantine adversary, based on the messages broadcast so far, can corrupt$k=1$processor. 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 a Byzantine adversary can cause. Our objective is to identify bias-$X$coin-tossing protocols achieving near-optimal minimum insecurity for every$X\in[0,1]$. Lichtenstein, Linial, and Saks (1989) studied bias-$X$coin-tossing protocols in this adversarial model where each party broadcasts an independent and uniformly random bit. They proved that the elegant “threshold coin-tossing protocols” are optimal for all$n$and$k$. Furthermore, Goldwasser, Kalai, and Park (2015), Kalai, Komargodski, and Raz (2018), and Haitner and Karidi-Heller (2020) prove that$k=\mathcal{O}(\sqrt{n} \cdot \mathsf{polylog}(n)$) corruptions suffice to fix the output of any bias-$X$coin-tossing protocol. These results encompass parties who send arbitrary-length messages, and each processor has multiple turns to reveal its entire message. We use an inductive approach to constructing coin-tossing protocols using a potential function as a proxy for measuring any bias-$X$coin-tossing protocol's susceptibility to attacks in our adversarial model. Our technique is inherently constructive and yields protocols that minimize the potential function. It is incidentally the case that the threshold protocols minimize the potential function, even for arbitrary-length messages. We demonstrate that these coin-tossing protocols' insecurity is a 2-approximation of the optimal protocol in our adversarial model. For any other$X\in[0,1]$that threshold protocols cannot realize, we prove that an appropriate (convex) combination of the threshold protocols is a 4-approximation of the optimal protocol. Finally, these results entail new (vertex) isoperimetric inequalities for density-$X$subsets of product spaces of arbitrary-size alphabets.

DOI
10.1109/isit45174.2021.9518276

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

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

Adaptively Secure Coin-Flipping, Revisited

Shafi Goldwasser, Yael Tauman Kalai, Sunoo Park

The full-information model was introduced by Ben-Or and Linial in 1985 to study collective coin-flipping: the problem of generating a common bounded-bias bit in a network of $n$ players with $t=t(n)$ faults. They showed that the majority protocol can tolerate $t=O(\sqrt n)$ adaptive corruptions, and conjectured that this is optimal in the adaptive setting. Lichtenstein, Linial, and Saks proved that the conjecture holds for protocols in which each player sends a single bit. Their result has been the main progress on the conjecture in the last 30 years. In this work we revisit this question and ask: what about protocols involving longer messages? Can increased communication allow for a larger fraction of faulty players? We introduce a model of strong adaptive corruptions, where in each round, the adversary sees all messages sent by honest parties and, based on the message content, decides whether to corrupt a party (and intercept his message) or not. We prove that any one-round coin-flipping protocol, regardless of message length, is secure against at most $\tilde{O}(\sqrt n)$ strong adaptive corruptions. Thus, increased message length does not help in this setting. We then shed light on the connection between adaptive and strongly adaptive adversaries, by proving that for any symmetric one-round coin-flipping protocol secure against $t$ adaptive corruptions, there is a symmetric one-round coin-flipping protocol secure against $t$ strongly adaptive corruptions. Returning to the standard adaptive model, we can now prove that any symmetric one-round protocol with arbitrarily long messages can tolerate at most $\tilde{O}(\sqrt n)$ adaptive corruptions. At the heart of our results lies a novel use of the Minimax Theorem and a new technique for converting any one-round secure protocol into a protocol with messages of $polylog(n)$ bits. This technique may be of independent interest.

arXiv:1503.01588•Mar 5, 2015•0 citations

Computational Hardness of Collective Coin-Tossing Protocols

Hemanta K. Maji

Ben-Or and Linial, in a seminal work, introduced the full information model to study collective coin-tossing protocols. Collective coin-tossing is an elegant functionality providing uncluttered access to the primary bottlenecks to achieve security in a specific adversarial model. Additionally, the research outcomes for this versatile functionality has direct consequences on diverse topics in mathematics and computer science. This survey summarizes the current state-of-the-art of coin-tossing protocols in the full information model and recent advances in this field. In particular, it elaborates on a new proof technique that identifies the minimum insecurity incurred by any coin-tossing protocol and, simultaneously, constructs the coin-tossing protocol achieving that insecurity bound. The combinatorial perspective into this new proof-technique yields new coin-tossing protocols that are more secure than well-known existing coin-tossing protocols, leading to new isoperimetric inequalities over product spaces. Furthermore, this proof-technique's algebraic reimagination resolves several long-standing fundamental hardness-of-computation problems in cryptography. This survey presents one representative application of each of these two perspectives.

Entropy•Dec 30, 2020•0 citations

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

Niv Buchbinder, Iftach Haitner, Nissan Levi +1 more

Abstract In a multi-party fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some adversarial parties try to bias the output. In this work, we focus on the case of an arbitrary number of corrupted parties. Cleve [20] [STOC 1986] has shown that in any such m -round coin-flipping protocol, the corrupted parties can bias the honest parties’ common output bit by $$\Theta (1/m)$$ Θ ( 1 / m ) . For more than two decades, however, the best-known coin-flipping protocol was the one of Awerbuch, Blum, Chor, Goldwasser, and Micali [10] [Manuscript 1985], who presented a t -party, m -round protocol with bias $$\Theta (t/\sqrt{m})$$ Θ ( t / m ) . This was changed by the breakthrough result of Moran, Naor, and Segev [51] [Journal of Cryptology 2016], who constructed an m -round, two -party coin-flipping protocol with optimal bias $$\Theta (1/m)$$ Θ ( 1 / m ) . More recently, Haitner and Tsfadia [37] [SIAM Journal on Computing 2017] constructed an m -round, three -party coin-flipping protocol with bias $$O(\log ^3m / m)$$ O ( log 3 m / m ) . Still for the case of more than three parties, the best-known protocol remained the $$\Theta (t/\sqrt{m})$$ Θ ( t / m ) -bias protocol of [10]. We make a step toward eliminating the above gap, presenting a t -party, m -round coin-flipping protocol, with bias $$O\left( \frac{t^4 \cdot 2^t \cdot \sqrt{\log m}}{m^{1/2+1/(2^{t-1}-2)}}\right) $$ O t 4 · 2 t · log m m 1 / 2 + 1 / ( 2 t - 1 - 2 ) for any $$t\le \tfrac{1}{2} \cdot \operatorname {loglog}m$$ t ≤ 1 2 · loglog m . This improves upon the

Journal of Cryptology•Nov 6, 2025•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
Ben-Or and Linial (1985) introduced the full information model for coin-tossing protocols involvingnnnprocessors with unbounded computational power using a common broadcast channel for all their communications. For most adversarial settings, the characterization of the exact or asymptotically optimal protocols remains open. Furthermore, even for the settings where near-optimal asymptotic constructions are known, the exact constants or poly-logarithmic multiplicative factors involved are not entirely well-understood. This work studiesnnn-processor coin-tossing protocols where every processor broadcasts an arbitrary-length message once. An adaptive Byzantine adversary, based on the messages broadcast so far, can corruptk=1k=1k=1processor. 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 a Byzantine adversary can cause. Our objective is to identify bias-XXXcoin-tossing protocols achieving near-optimal minimum insecurity for everyX∈[0,1]X\in[0,1]X∈[0,1]. Lichtenstein, Linial, and Saks (1989) studied bias-XXXcoin-tossing protocols in this adversarial model where each party broadcasts an independent and uniformly random bit. They proved that the elegant “threshold coin-tossing protocols” are optimal for allnnnandkkk. Furthermore, Goldwasser, Kalai, and Park (2015), Kalai, Komargodski, and Raz (2018), and Haitner and Karidi-Heller (2020) prove thatk=O(n⋅polylog(n)k=\mathcal{O}(\sqrt{n} \cdot \mathsf{polylog}(n)k=O(n​⋅polylog(n)) corruptions suffice to fix the output of any bias-XXXcoin-tossing protocol. These results encompass parties who send arbitrary-length messages, and each processor has multiple turns to reveal its entire message. We use an inductive approach to constructing coin-tossing protocols using a potential function as a proxy for measuring any bias-XXXcoin-tossing protocol's susceptibility to attacks in our adversarial model. Our technique is inherently constructive and yields protocols that minimize the potential function. It is incidentally the case that the threshold protocols minimize the potential function, even for arbitrary-length messages. We demonstrate that these coin-tossing protocols' insecurity is a 2-approximation of the optimal protocol in our adversarial model. For any otherX∈[0,1]X\in[0,1]X∈[0,1]that threshold protocols cannot realize, we prove that an appropriate (convex) combination of the threshold protocols is a 4-approximation of the optimal protocol. Finally, these results entail new (vertex) isoperimetric inequalities for density-XXXsubsets of product spaces of arbitrary-size alphabets.
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.
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).
The full-information model was introduced by Ben-Or and Linial in 1985 to study collective coin-flipping: the problem of generating a common bounded-bias bit in a network of nnn players with t=t(n)t=t(n)t=t(n) faults. They showed that the majority protocol can tolerate t=O(n)t=O(\sqrt n)t=O(n​) adaptive corruptions, and conjectured that this is optimal in the adaptive setting. Lichtenstein, Linial, and Saks proved that the conjecture holds for protocols in which each player sends a single bit. Their result has been the main progress on the conjecture in the last 30 years. In this work we revisit this question and ask: what about protocols involving longer messages? Can increased communication allow for a larger fraction of faulty players? We introduce a model of strong adaptive corruptions, where in each round, the adversary sees all messages sent by honest parties and, based on the message content, decides whether to corrupt a party (and intercept his message) or not. We prove that any one-round coin-flipping protocol, regardless of message length, is secure against at most O~(n)\tilde{O}(\sqrt n)O~(n​) strong adaptive corruptions. Thus, increased message length does not help in this setting. We then shed light on the connection between adaptive and strongly adaptive adversaries, by proving that for any symmetric one-round coin-flipping protocol secure against ttt adaptive corruptions, there is a symmetric one-round coin-flipping protocol secure against ttt strongly adaptive corruptions. Returning to the standard adaptive model, we can now prove that any symmetric one-round protocol with arbitrarily long messages can tolerate at most O~(n)\tilde{O}(\sqrt n)O~(n​) adaptive corruptions. At the heart of our results lies a novel use of the Minimax Theorem and a new technique for converting any one-round secure protocol into a protocol with messages of polylog(n)polylog(n)polylog(n) bits. This technique may be of independent interest.
Ben-Or and Linial, in a seminal work, introduced the full information model to study collective coin-tossing protocols. Collective coin-tossing is an elegant functionality providing uncluttered access to the primary bottlenecks to achieve security in a specific adversarial model. Additionally, the research outcomes for this versatile functionality has direct consequences on diverse topics in mathematics and computer science. This survey summarizes the current state-of-the-art of coin-tossing protocols in the full information model and recent advances in this field. In particular, it elaborates on a new proof technique that identifies the minimum insecurity incurred by any coin-tossing protocol and, simultaneously, constructs the coin-tossing protocol achieving that insecurity bound. The combinatorial perspective into this new proof-technique yields new coin-tossing protocols that are more secure than well-known existing coin-tossing protocols, leading to new isoperimetric inequalities over product spaces. Furthermore, this proof-technique's algebraic reimagination resolves several long-standing fundamental hardness-of-computation problems in cryptography. This survey presents one representative application of each of these two perspectives.
Abstract In a multi-party fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some adversarial parties try to bias the output. In this work, we focus on the case of an arbitrary number of corrupted parties. Cleve [20] [STOC 1986] has shown that in any such m -round coin-flipping protocol, the corrupted parties can bias the honest parties’ common output bit by Θ(1/m)\Theta (1/m)Θ(1/m) Θ ( 1 / m ) . For more than two decades, however, the best-known coin-flipping protocol was the one of Awerbuch, Blum, Chor, Goldwasser, and Micali [10] [Manuscript 1985], who presented a t -party, m -round protocol with bias Θ(t/m)\Theta (t/\sqrt{m})Θ(t/m​) Θ ( t / m ) . This was changed by the breakthrough result of Moran, Naor, and Segev [51] [Journal of Cryptology 2016], who constructed an m -round, two -party coin-flipping protocol with optimal bias Θ(1/m)\Theta (1/m)Θ(1/m) Θ ( 1 / m ) . More recently, Haitner and Tsfadia [37] [SIAM Journal on Computing 2017] constructed an m -round, three -party coin-flipping protocol with bias O(log⁡3m/m)O(\log ^3m / m)O(log3m/m) O ( log 3 m / m ) . Still for the case of more than three parties, the best-known protocol remained the Θ(t/m)\Theta (t/\sqrt{m})Θ(t/m​) Θ ( t / m ) -bias protocol of [10]. We make a step toward eliminating the above gap, presenting a t -party, m -round coin-flipping protocol, with bias O(t4⋅2t⋅log⁡mm1/2+1/(2t−1−2))O\left( \frac{t^4 \cdot 2^t \cdot \sqrt{\log m}}{m^{1/2+1/(2^{t-1}-2)}}\right) O(m1/2+1/(2t−1−2)t4⋅2t⋅logm​​) O t 4 · 2 t · log m m 1 / 2 + 1 / ( 2 t - 1 - 2 ) for any t≤12⋅loglog⁡mt\le \tfrac{1}{2} \cdot \operatorname {loglog}mt≤21​⋅loglogm t ≤ 1 2 · loglog m . This improves upon the
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.