Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling
share
In his seminal work, Cleve [STOC '86] has proved that any r-round coin-flipping protocol can be efficiently biased by Θ(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 Ω(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.
READ FULL TEXT