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)

Unfair coin tossing

Grégory Demay, Ueli M. Maurer

Published Jul 1, 2013• 5 citations
Publisher

Abstract

An ideal coin tossing resource for two parties outputs the same random bit to both parties. We introduce the notion of an unfair coin tossing resource by relaxing both the fairness and the non-influenceability guarantees that an ideal coin toss would provide. The presence of this non-ideal behavior is necessary in order to understand what coin tossing protocols really achieve in the setting of two distrustful parties, since it is known that such an ideal coin tossing resource cannot be constructed whenever a majority of players is dishonest.

DOI
10.1109/isit.2013.6620488

Related papers

A resource-fair protocol for two-party coin toss

Ou Ruan, Zhou Jing, Guohua Cui +1 more

Coin-flipping protocols allow mutually distrustful parties to generate a random bit with uniform distribution. Minimizing bias and keeping fairness are two key requirements in designing such protocols. However, the best previously known fair coin-flipping protocol only guarantees with bias O (1/ r ). In the paper, we introduce a new approach for fair coin-flipping protocol construction by using Garay et al ’s “resource fairness” technique and propose a resource-fair two-party coin-flipping protocol according to the standard real/ideal simulation paradigm. Compared with the other coin-flipping protocols, our protocol enjoys an important advantage that its bias is 0.

Wuhan University Journal of Natural Sciences•Jun 1, 2013•0 citations

Protocols for Multiparty Coin Toss With Dishonest Majority.

Amos Beimel, Eran Omri, Ilan Orlov

Abstract. Coin-tossing protocols are protocols that generate a random bit with uniform distribution. These protocols are used as a building block in many cryptographic protocols. Cleve [STOC 1986] has shown that if at least half of the parties can be malicious, then, in any r-round coin-tossing protocol, the malicious parties can cause a bias of Ω(1/r) to the bit that the honest parties output. However, for more than two t, where t is the number

•Jan 1, 2012•2 citations

AN INTRODUCTION TO QUANTUM COIN TOSSING

C. Doescher, Michael Keyl

We review the quantum version of a well known problem of cryptography called coin tossing ("flipping a coin via telephone"). It can be regarded as a game where two remote players (who distrust each other) try to generate a uniformly distributed random bit which is common to both parties. The only resource they can use to perform this task is a classical or quantum communication channel. In this paper we provide a general overview over such coin tossing protocols, concerning in particular their security.

arXiv:quant-ph/0206088•Fluctuation and Noise Letters•Dec 1, 2002•18 citations

An almost-optimally fair three-party coin-flipping protocol

Iftach Haitner, Eliad Tsfadia

In a multiparty fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. Cleve [STOC 1986] has shown that in the case of dishonest majority (i.e., at least half of the parties can be corrupted), 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 dishonest majority had bias [EQUATION], where ℓ is the number of corrupted parties. This was changed by a recent breakthrough result of Moran et al. [TCC 2009], who constructed an m-round, two-party coin-flipping protocol with optimal bias Θ(1/m). In a subsequent work, Beimel et al. [Crypto 2010] extended this result to the multiparty case in which less than 2/3 of the parties can be corrupted. Still for the case of 2/3 (or more) corrupted parties, the best known protocol had bias [EQUATION]. In particular, this was the state of affairs for the natural three-party case.

ACM Symposium on Theory of Computing (STOC)•May 31, 2014•22 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•27 citations

On the impossibility of information-theoretic composable coin toss extension

Gregor Seiler, Ueli M. Maurer

Shared randomness is an important resource in cryptography. It is well-known that in the information-theoretic setting there is no protocol that allows two parties who do not trust each other to obtain a uniformly distributed shared bit string solely by exchanging messages such that a dishonest party can not influence the result. On the other hand, in the situation where the two parties already share a random bit string and want to use it in order to construct a longer random bit string, it is only known to be impossible when the protocols are restricted in the number of messages to be exchanged. In this paper we prove that it is also impossible when arbitrarily many messages are allowed.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•1 citation
An ideal coin tossing resource for two parties outputs the same random bit to both parties. We introduce the notion of an unfair coin tossing resource by relaxing both the fairness and the non-influenceability guarantees that an ideal coin toss would provide. The presence of this non-ideal behavior is necessary in order to understand what coin tossing protocols really achieve in the setting of two distrustful parties, since it is known that such an ideal coin tossing resource cannot be constructed whenever a majority of players is dishonest.
Coin-flipping protocols allow mutually distrustful parties to generate a random bit with uniform distribution. Minimizing bias and keeping fairness are two key requirements in designing such protocols. However, the best previously known fair coin-flipping protocol only guarantees with bias O (1/ r ). In the paper, we introduce a new approach for fair coin-flipping protocol construction by using Garay et al ’s “resource fairness” technique and propose a resource-fair two-party coin-flipping protocol according to the standard real/ideal simulation paradigm. Compared with the other coin-flipping protocols, our protocol enjoys an important advantage that its bias is 0.
We review the quantum version of a well known problem of cryptography called coin tossing ("flipping a coin via telephone"). It can be regarded as a game where two remote players (who distrust each other) try to generate a uniformly distributed random bit which is common to both parties. The only resource they can use to perform this task is a classical or quantum communication channel. In this paper we provide a general overview over such coin tossing protocols, concerning in particular their security.
In a multiparty fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. Cleve [STOC 1986] has shown that in the case of dishonest majority (i.e., at least half of the parties can be corrupted), 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 dishonest majority had bias [EQUATION], where ℓ is the number of corrupted parties. This was changed by a recent breakthrough result of Moran et al. [TCC 2009], who constructed an m-round, two-party coin-flipping protocol with optimal bias Θ(1/m). In a subsequent work, Beimel et al. [Crypto 2010] extended this result to the multiparty case in which less than 2/3 of the parties can be corrupted. Still for the case of 2/3 (or more) corrupted parties, the best known protocol had bias [EQUATION]. In particular, this was the state of affairs for the natural three-party case.
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.
Shared randomness is an important resource in cryptography. It is well-known that in the information-theoretic setting there is no protocol that allows two parties who do not trust each other to obtain a uniformly distributed shared bit string solely by exchanging messages such that a dishonest party can not influence the result. On the other hand, in the situation where the two parties already share a random bit string and want to use it in order to construct a longer random bit string, it is only known to be impossible when the protocols are restricted in the number of messages to be exchanged. In this paper we prove that it is also impossible when arbitrarily many messages are allowed.