Paper 2026/2916

Cleve's Bound Is Tight: Optimally Fair Coin Flipping for Every Fixed Number of Parties

Yuwen Zhou, University of British Columbia Okanagan
Abstract

Proof-of-stake chains, committee selection and lotteries draw public randomness from protocols whose participants may collude. Cleve [STOC 1986] showed that without an honest majority, aborting alone lets a coalition bias the outcome of any $r$-round $n$-party coin flip by $\Omega(1/r)$. Moran, Naor and Segev [TCC 2009] matched this bound for two parties, and later work came within a $\sqrt{\log r}$ factor of it for three. For four or more parties, the best known bias is about $r^{-1/2-1/(2^{n-1}-2)}$, which approaches the $r^{-1/2}$ of the simple majority protocol as $n$ grows. The obstacle is recovery: after an abort, the remaining parties must carry on without giving the coalition a fresh chance to bias the outcome. In the best earlier protocol they reconstruct a noisy copy of the current expected outcome, and with more than three parties this costs a power of $r$ at each level. We show that Cleve's bound is tight for every fixed number of parties. Assuming constant-round oblivious transfer and constant-round passively secure computation, we give an $n$-party $r$-round protocol over a broadcast channel whose bias against $n-1$ corrupted parties is $O(n^3 2^n / r)$. The protocol draws the outcome at the start and keeps it secret, and the coins it reveals form a random walk conditioned on that outcome. After an abort, the remaining parties reconstruct nothing: they start a new run whose outcome probability is a public table evaluated on bits they hold in secret-shared form. Our main technical result is that the entries of every such table stay within a factor of two of each other, however many aborts came before, so each level of recovery costs only a constant factor. The protocol therefore improves on majority for up to about $\frac{1}{2}\log_2 r$ parties, and a variant for any number of parties has an exponential factor set only by how many more parties are corrupted than honest.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
fair coin flippingmultiparty computationfairnessCleve's bounddishonest majority
Contact author(s)
zhouyw07 @ student ubc ca
History
2026-11-21: approved
2026-11-16: received
See all versions
Short URL
https://ia.cr/2026/2916
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2916,
      author = {Yuwen Zhou},
      title = {Cleve's Bound Is Tight: Optimally Fair Coin Flipping for Every Fixed Number of Parties},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2916},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2916}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.