Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Electronic colloquium on computational complexity

Tighter Bounds on Multi-Party Coin Flipping, via Augmented Weak Martingales and Di erentially Private Sampling.

Amos Beimel, Iftach Haitner, Nikolaos Makriyannis, Eran Omri

Published Jan 1, 2017• 3 citations
OpenAlex

Related papers

A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols.

Ilan Komargodski, Ran Raz, Yael Tauman Kalai

Electronic colloquium on computational complexity•Jan 1, 2018•0 citations

Tight Bounds for Classical and Quantum Coin Flipping

Esther Hänggi, Jürg Wullschleger

arXiv:1009.4741•Lecture notes in computer science•Jan 1, 2011•20 citations

A new protocol and lower bounds for quantum coin flipping

Andris Ambainis

arXiv:quant-ph/0204022•Journal of Computer and System Sciences•Oct 17, 2003•81 citations

Weak coin flipping with small bias

Iordanis Kerenidis, Ashwin Nayak

Information Processing Letters•Dec 5, 2003•45 citations

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

Amos Beimel, Iftach Haitner, Nikolaos Makriyannis +1 more

In his seminal work, Cleve [STOC '86] proved that the bias of any coin-flipping protocol is inversely proportional to the number of rounds. This lower bound was met for the two-party case by Moran et al. [Journal of Cryptology '16], and the three-party case (up to a polylogarithmic factor) by Haitner and Tsfadia [SICOMP '17], and was approached for multi-party protocols by Haitner et al. [SODA '17] when the number of rounds is at least doubly exponential in the number of parties. For the complement case, however, the best bias for multi-party coin-flipping protocols is proportional to the number of parties and inversely proportional to the square root of the number of rounds. The latter bias is achieved by the majority protocol of Awerbuch et al. [Manuscript '85]. Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, if the number of rounds is bounded by some polynomial in the number of parties, then the bias is lower-bounded by a quantity that is inversely proportional to the square root of the number of rounds (up to a polylogarithmic factor). As far as we know, this is the first improvement of Cleve's bound, and is far from the aforementioned upper bound of Awerbuch et al. only by a factor of the number of parties. We prove the above bound using two new results that we believe are of independent interest. The first result is that a sequence of ("augmented") weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes over the result of Cleve and Impagliazzo [Manuscript '93], who showed that the above holds for strong martingales, and allows in some setting to exploit this gap by efficient algorithms. We prove the above using a novel argument that does not follow the more complicated approach of Cleve and Impagliazzo. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence.

Annual Symposium on Foundations of Computer Science•Oct 1, 2018•17 citations

Tighter Bounds on MultiParty Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling

Amos Beimel, Iftach Haitner, Nikolaos Makriyannis +1 more

In his seminal work, Cleve [ Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986, pp. 364--369] 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 [ J. Cryptology, 29 (2016), pp. 491--513] and the three-party case (up to a ${polylog}$ factor) by Haitner and Tsfadia [ SIAM J. Comput., 46 (2017), pp. 479--542] and was approached for $n$-party protocols when $n< {loglog} r$ by Buchbinder et al. [ Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 2580--2600]. 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 et al. [ How to implement Bracha's ${O}(\log n)$ Byzantine Agreement Algorithm, manuscript, 1985]. Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant $\varepsilon >0$, an $r^{\varepsilon}$-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^{\varepsilon}$ (multiplicative) far from the aforementioned upper bound of Awerbuch et al. We prove the above bound using two new results that we believe are of independent interest. The first result is that a sequence of (``augmented'') weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes over the result of Cleve and Impagliazzo [ Martingales, Collective Coin Flipping and Discrete Control Processes (Extended Abstract), http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1797, 1993], who showed that the above holds for strong martingales, and allows in some setting to exploit this gap by efficient algorithms. We prove the above using a novel argument that does not follow the more complicated approach of R. Cleve and R. Impagliazzo. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence.

arXiv:2105.00743•SIAM Journal on Computing•Jul 21, 2022•5 citations
In his seminal work, Cleve [STOC '86] proved that the bias of any coin-flipping protocol is inversely proportional to the number of rounds. This lower bound was met for the two-party case by Moran et al. [Journal of Cryptology '16], and the three-party case (up to a polylogarithmic factor) by Haitner and Tsfadia [SICOMP '17], and was approached for multi-party protocols by Haitner et al. [SODA '17] when the number of rounds is at least doubly exponential in the number of parties. For the complement case, however, the best bias for multi-party coin-flipping protocols is proportional to the number of parties and inversely proportional to the square root of the number of rounds. The latter bias is achieved by the majority protocol of Awerbuch et al. [Manuscript '85]. Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, if the number of rounds is bounded by some polynomial in the number of parties, then the bias is lower-bounded by a quantity that is inversely proportional to the square root of the number of rounds (up to a polylogarithmic factor). As far as we know, this is the first improvement of Cleve's bound, and is far from the aforementioned upper bound of Awerbuch et al. only by a factor of the number of parties. We prove the above bound using two new results that we believe are of independent interest. The first result is that a sequence of ("augmented") weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes over the result of Cleve and Impagliazzo [Manuscript '93], who showed that the above holds for strong martingales, and allows in some setting to exploit this gap by efficient algorithms. We prove the above using a novel argument that does not follow the more complicated approach of Cleve and Impagliazzo. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence.
In his seminal work, Cleve [ Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986, pp. 364--369] has proved that any rrr-round coin-flipping protocol can be efficiently biased by Θ(1/r)\Theta(1/r)Θ(1/r). This lower bound was met for the two-party case by Moran, Naor, and Segev [ J. Cryptology, 29 (2016), pp. 491--513] and the three-party case (up to a polylog{polylog}polylog factor) by Haitner and Tsfadia [ SIAM J. Comput., 46 (2017), pp. 479--542] and was approached for nnn-party protocols when n<loglogrn< {loglog} rn<loglogr by Buchbinder et al. [ Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 2580--2600]. For n>loglogrn > {loglog} rn>loglogr, however, the best bias for nnn-party coin-flipping protocols remains O(n/r)O(n/\sqrt{r})O(n/r​) achieved by the majority protocol of Awerbuch et al. [ How to implement Bracha's O(log⁡n){O}(\log n)O(logn) Byzantine Agreement Algorithm, manuscript, 1985]. Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant ε>0\varepsilon >0ε>0, an rεr^{\varepsilon}rε-party rrr-round coin-flipping protocol can be efficiently biased by Ω~(1/r)\widetilde{\Omega}(1/\sqrt{r})Ω(1/r​). As far as we know, this is the first improvement of Cleve's bound and is only n=rεn=r^{\varepsilon}n=rε (multiplicative) far from the aforementioned upper bound of Awerbuch et al. We prove the above bound using two new results that we believe are of independent interest. The first result is that a sequence of (``augmented'') weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes over the result of Cleve and Impagliazzo [ Martingales, Collective Coin Flipping and Discrete Control Processes (Extended Abstract), http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1797, 1993], who showed that the above holds for strong martingales, and allows in some setting to exploit this gap by efficient algorithms. We prove the above using a novel argument that does not follow the more complicated approach of R. Cleve and R. Impagliazzo. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence.