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

In his seminal work, Cleve [STOC '86] has proved that any r-round coin-flipping protocol can be efficiently biased by Theta(1/r). 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 polylog factor) by Haitner and Tsfadi [SICOMP '17], and was approached for n-party protocols when n< loglog r by Buchbinder, Haitner, Levi, and Tsfadia [SODA '17]. For n> loglog r, however, the best bias for n-party coin-flipping protocols remains O(n/√r) 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 ε >0, an rε-party r-round coin-flipping protocol can be efficiently biased by widetildeOmega(1/√r). As far as we know, this is the first improvement of Cleve's bound, and is only n=rε (multiplicative) far from the aforementioned upper bound of Awerbuch et al.