Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling
| Autor: | Beimel, Amos, Haitner, Iftach, Makriyannis, Nikolaos, Omri, Eran |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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/\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 $\epsilon >0$, an $r^{\epsilon}$-party $r$-round coin-flipping protocol can be efficiently biased by $\widetilde{\Omega}(1/\sqrt{r})$. As far as we know, this is the first improvement of Cleve's bound, and is only $n=r^{\epsilon}$ (multiplicative) far from the aforementioned upper bound of Awerbuch et al. Comment: A preliminary version appeared in FOCS 18 |
| Databáze: | arXiv |
| Externí odkaz: |
|