Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling
This addresses a foundational problem in cryptography for designing secure distributed protocols, representing an incremental advance in theoretical bounds.
The paper tackles the problem of improving lower bounds on bias in multi-party coin-flipping protocols, showing that for any constant ε>0, an r^ε-party r-round protocol can be efficiently biased by Ω̃(1/√r), which is the first improvement over Cleve's bound and close to the known upper bound.
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/\sqrt{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 $\widetildeΩ(1/\sqrt{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.