Almost-Optimally Fair Multiparty Coin-Tossing with Nearly Three-Quarters Malicious

An α -fair coin-tossing protocol allows a set of mutually distrustful parties to generate a uniform bit, such that no efficient adversary can bias the output bit by more than α . Cleve (in: Proceedings of the 18th annual ACM symposium on theory of computing (STOC), 1986) has shown that if half of the parties can be corrupted, then no r -round coin-tossing protocol is o(1 / r) -fair. For over two decades, the best-known m-party protocols, tolerating up to t≥ m/ 2 corrupted parties, were only O(t/r) -fair. In a surprising result, Moran et al. (in: Theory of cryptography, sixth theory of cryptography conference, TCC, 2009) constructed an r -round two-party O(1 / r) -fair coin-tossing protocol, i.e., an optimally fair protocol. Beimel et al. (in: Rabin (ed) Advances in cryptology—CRYPTO 2010, volume 6223 of lecture notes in computer science, Springer, 2010) extended the result of Moran et al. to the multiparty setting where strictly fewer than 2/3 of the parties are corrupted. They constructed a 22k/r -fair r-round m-party protocol, tolerating up to t=m+k2 corrupted parties. In a breakthrough result, Haitner and Tsfadia (in: Symposium on theory of computing, STOC, 2014) constructed an O(log ³(r) / r) -fair (almost optimal) three-party coin-tossing protocol. Their work brought forth a combination of novel techniques for coping with the difficulties of constructing fair coin-tossing protocols. Still, the best coin-tossing protocols for the case where more than 2/3 of the parties may be corrupted (and even when t= 2 m/ 3 , where m> 3) were θ(1/r) -fair. We construct an O(log ³(r) / r) -fair m-party coin-tossing protocol, tolerating up to t corrupted parties, whenever m is constant and t< 3 m/ 4 .