**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 $t\geq m/2$ corrupted parties, were only
$O(t/\sqrt{r})$-fair.
In a surprising result,
Moran, Naor, and Segev [TCC 2009] constructed an $r$-round two-party
$O(1/r)$-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 $2^{2^k}/r$-fair $r$-round $m$-party protocol,
tolerating up to $t=\frac{m+k}{2}$ corrupted parties.

Recently, in a breakthrough result, Haitner and Tsfadia [STOC 2014] constructed an $O(\log^3(r)/r)$-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 $t=2m/3$, where $m>3$) were $\theta(1/\sqrt{r})$-fair. We construct an $O(\log^3(r)/r)$-fair $m$-party coin-tossing protocol, tolerating up to $t$ corrupted parties, whenever $m$ is constant and $t<3m/4$.

**Category / Keywords: **foundations / Keywords: coin-tossing; coin-flipping; protocols; fairness; fair computation; dishonest majority

**Original Publication**** (with major differences): **IACR-TCC-2016

**Date: **received 21 Aug 2016, last revised 23 Aug 2016

**Contact author: **omrier at gmail com

**Available format(s): **PDF | BibTeX Citation

**Note: **A few minor changes were made.

**Version: **20160824:140924 (All versions of this report)

**Short URL: **ia.cr/2016/800

[ Cryptology ePrint archive ]