Paper 2016/800

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

Bar Alon and Eran Omri

Abstract

An $\alpha$-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 $\alpha$. Cleve [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 $$ corrupted parties, were only $$-fair. In a surprising result, Moran, Naor, and Segev [TCC 2009] constructed an $$-round two-party $$-fair coin-tossing protocol, i.e., an optimally fair protocol. Beimel, Omri, and Orlov [Crypto 2010] extended the results of Moran et al.~to the {\em multiparty setting} where strictly fewer than 2/3 of the parties are corrupted. They constructed a $$-fair $$-round $$-party protocol, tolerating up to $$ corrupted parties. Recently, in a breakthrough result, Haitner and Tsfadia [STOC 2014] constructed an $$-fair (almost optimal) three-party coin-tossing protocol. Their work brings 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 $$, where $$) were $$-fair. We construct an $$-fair $$-party coin-tossing protocol, tolerating up to $$ corrupted parties, whenever $$ is constant and $$.

Note: A few minor changes were made.