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
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
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 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 [in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1986, pp. 364--369] 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 Ω(m1). For more than two decades the best known coin-flipping protocols against dishonest majority had bias Θ(mℓ), where ℓ is the number of corrupted parties. This was changed by a recent breakthrough result of Moran, Naor, and Segev [in Theory of Cryptography, Lecture Notes in Comput. Sci. 5444, Springer, Berlin, 2009, pp. 1--18], who constructed an m-round, two-party coin-flipping protocol with optimal bias Θ(m1). In a subsequent work, Beimel, Omri, and Orlov [in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1990, pp. 503--513] extended this result to the multiparty case in which less than 32 of the parties can be corrupted. Still, for the case of 32 (or more) corrupted parties, the best known protocol had bias Θ(mℓ). In particular, this was the state of affairs for the natural three-party case. We take a step toward eliminating the above gap, presenting an m-round, three-party coin-flipping protocol, with bias mO(log3m). Our approach (which we also apply to the two-party case) does not follow the “threshold round" paradigm used in the work of Moran, Naor, and Segev and Beimel, Omri, and Orlov but rather is a variation of the majority protocol of Cleve used to obtain the aforementioned Θ(mℓ)-bias protocol.
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.
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) Θ ( 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) Θ ( 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) Θ ( 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(log3m/m) O ( log 3 m / m ) . Still for the case of more than three parties, the best-known protocol remained the Θ(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(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≤21⋅loglogm t ≤ 1 2 · loglog m . This improves upon the
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.
Abstract. In this paper we show that any two-party functionality can be securely computed in a constant number of rounds, where security is obtained against malicious adversaries that may arbitrarily deviate from the protocol specification. This is in contrast to Yao’s constant-round protocol that ensures security only in the face of semi-honest adversaries, and to its malicious adversary version that requires a polynomial number of rounds. In order to obtain our result, we present a constant-round protocol for secure coin-tossing of polynomially many coins (in parallel). We then show how this protocol can be used in conjunction with other existing constructions in order to obtain a constant-round protocol for securely computing any two-party functionality. On the subject of coin-tossing, we also present a constant-round perfect coin-tossing protocol, where by “perfect ” we mean that the resulting coins are guaranteed to be statistically close to uniform (and not just pseudorandom). 1