paper

Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling

arXiv:2105.00743

Abstract

In his seminal work, Cleve [STOC '86] has proved that any -round coin-flipping protocol can be efficiently biased by . This lower bound was met for the two-party case by Moran, Naor, and Segev [Journal of Cryptology '16], and the three-party case (up to a factor) by Haitner and Tsfadi [SICOMP '17], and was approached for -party protocols when by Buchbinder, Haitner, Levi, and Tsfadia [SODA '17]. For , however, the best bias for -party coin-flipping protocols remains achieved by the majority protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript '85]. Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant , an -party -round coin-flipping protocol can be efficiently biased by . As far as we know, this is the first improvement of Cleve's bound, and is only (multiplicative) far from the aforementioned upper bound of Awerbuch et al.

arXiv commentA preliminary version appeared in FOCS 18