Paper 2026/2916
Cleve's Bound Is Tight: Optimally Fair Coin Flipping for Every Fixed Number of Parties
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
-
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}
}