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

arXiv: https://arxiv.org/abs/2105.00743 · HTML: https://mlsanity.com/paper/2105.00743/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2021.

## Built on by (most cited first, 1 of 1)

- [Private PAC Learning May be Harder than Online Learning](https://mlsanity.com/paper/2402.11119/) (2024)

## Abstract (arXiv)

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.