Fair Coin Flipping: Tighter Analysis and the Many-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, i.e. at least half of the parties can be corrupted. Cleve (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 dishonest majority was the protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript 85], who presented a t-party, m-round protocol of bias t/\sqrt{m}. This was  changed by the breakthrough result of Moran, Naor and Segev (TCC 2009), who constructed an m-round, 2-party coin-flipping protocol with optimal bias of 1/m. Recently, Haitner and Tsafadia (STOC 14) constructed an m-round, three-party coin-flipping protocol with bias O(log^3(m) / m). Still for the case of more  than three parties, the best known protocol remains the \Theta(t / \sqrt{m})-bias protocol of Awerbuch et al.

We make a step towards eliminating the above gap, presenting a t-party, m-round coin-flipping protocol, with bias O(\frac{t * 2^t * \sqrt{\log m}}{m^{1/2+1/(2^{t-1}-2)}}). This improves upon the \Theta(t / \sqrt{m})-bias protocol of Awerbuch et al. for any t < 1/2 * log(log(m)), and in particular for t \in O(1), this yields an 1/m^{1/2 + \Theta(1)}-bias protocol. For the three-party case, this yields an O(\sqrt{log m}/m)-bias protocol, improving over the the O(log^3m / m)-bias protocol of Haitner and Tsafadia. Our protocol generalizes that of Haitner and Tsafadia, by presenting an appropriate "defense protocols" for the remaining parties to interact in, in the case that some parties abort or caught cheating (Haitner and Tsafadia 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 optimal value of the linear program by constructing a feasible solution to its dual.

This is a joint work with Niv Buchbinder, Iftach Haitner, and Eliad Tsfadia.