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. The work by Chung et al. (TCC’18) was the first to explore the feasibility of game-theoretically fair n-party coin toss in the presence of a 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.
We give a complete characterization of the regime in which CSP-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. In this talk, we will show how to construct CSP-fair multi-party coin-toss and how to generalize it to any utility functions.
Bio:
Ke Wu is an assistant professor in the Theory of Computation Lab of the EECS Department at the University of Michigan. She obtained her PhD at Carnegie Mellon University, fortunately advised by Prof. Elaine Shi. Prior to this, she was a master’s student and research assistant advised by Prof. Xin Li at Johns Hopkins University. She previously got her bachelor’s degree in Information and Computing Science from the School of Mathematical Sciences at Fudan University.