Paper 2021/748

A Complete Characterization of Game-Theoretically Fair, Multi-Party Coin Toss

Ke Wu, Gilad Asharov, and Elaine Shi


Cleve’s celebrated lower bound (STOC’86) showed that a de facto strong fairness notion is impossible in 2-party coin toss, i.e., the corrupt party always has a strategy of biasing the honest party’s outcome by a noticeable amount. Nonetheless, Blum’s famous coin-tossing protocol(CRYPTO’81) achieves a strictly weaker “game-theoretic” notion of fairness — specifically, it is a 2-party coin toss protocol in which neither party can bias the outcome towards its own preference; and thus the honest protocol forms a Nash equilibrium in which neither party would want to deviate. Surprisingly, an n-party analog of Blum’s famous coin toss protocol was not studied till recently. The elegant work by Chung et al. was the first to explore the feasibility of game-theoretically fair n-party coin toss in the presence of corrupt majority. We may assume that each party has a publicly stated preference for either the bit 0 or 1, and if the outcome agrees with the party’s preference, it obtains utility 1; else it obtains nothing.A natural game-theoretic formulation is to require that the honest protocol form a coalition-resistant Nash equilibrium, i.e., no coalition should have incentive to deviate from the honest behavior. Chung et al. phrased this game-theoretic notion as “cooperative-strategy-proofness”or “CSP-fairness” for short. Unfortunately, Chung et al. showed that under (n-1)-sized coalitions, it is impossible to design such a CSP-fair coin toss protocol, unless all parties except one prefer the same bit.In this paper, we show that the impossibility of Chung et al. is in fact not as broad as it may seem. When coalitions are majority but not n-1 in size, we can indeed get feasibility results in some meaningful parameter regimes. We give a complete characterization of the regime in whichCSP-fair coin toss is possible, by providing a matching upper- and lower-bound. Our complete characterization theorem also shows that the mathematical structure of game-theoretic fairness is starkly different from the de facto strong fairness notion in the multi-party computation literature.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2022
game theorycoin tossmulti-party computationfairness
Contact author(s)
kew2 @ andrew cmu edu
2022-03-05: last of 4 revisions
2021-06-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ke Wu and Gilad Asharov and Elaine Shi},
      title = {A Complete Characterization of Game-Theoretically Fair, Multi-Party Coin Toss},
      howpublished = {Cryptology ePrint Archive, Paper 2021/748},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.