Game Theoretic Notions of Fairness in Multi-Party Coin Toss

Kai-Min Chung, Yue Guo, Wei-Kai Lin, Rafael Pass, and Elaine Shi

Abstract

Coin toss has been extensively studied in the cryptography literature, and the well-accepted notion of fairness (henceforth called strong fairness) requires that a corrupt coalition cannot cause non-negligible bias. It is well-understood that two-party coin toss is impossible if one of the parties can prematurely abort; further, this impossibility generalizes to multiple parties with a corrupt majority (even if the adversary is computationally bounded and fail-stop only). Interestingly, the original proposal of (two-party) coin toss protocols by Blum in fact considered a weaker notion of fairness: imagine that the (randomized) transcript of the coin toss protocol defines a winner among the two parties. Now Blum's notion requires that a corrupt party cannot bias the outcome in its favor (but self-sacrificing bias is allowed). Blum showed that this weak notion is indeed attainable for two parties assuming the existence of one-way functions. In this paper, we ask a very natural question which, surprisingly, has been overlooked by the cryptography literature: can we achieve Blum's weak fairness notion in multi-party coin toss? What is particularly interesting is whether this relaxation allows us to circumvent the corrupt majority impossibility that pertains to strong fairness. Even more surprisingly, in answering this question, we realize that it is not even understood how to define weak fairness for multi-party coin toss. We propose several natural notions drawing inspirations from game theory, all of which equate to Blum's notion for the special case of two parties. We show, however, that for multiple parties, these notions vary in strength and lead to different feasibility and infeasibility results.

Available format(s)
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in TCC 2018
Keywords
coin tosscoin flip
Contact author(s)
wklin @ cs cornell edu
yg393 @ cornell edu
runting @ gmail com
rafael @ cs cornell edu
kmchung @ iis sinica edu tw
History
2020-12-09: revised
See all versions
Short URL
https://ia.cr/2018/1076

CC BY

BibTeX

@misc{cryptoeprint:2018/1076,
author = {Kai-Min Chung and Yue Guo and Wei-Kai Lin and Rafael Pass and Elaine Shi},
title = {Game Theoretic Notions of Fairness in Multi-Party Coin Toss},
howpublished = {Cryptology ePrint Archive, Paper 2018/1076},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/1076}},
url = {https://eprint.iacr.org/2018/1076}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.