International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: log∗-Round Game-Theoretically-Fair Leader Election

Ilan Komargodski , Hebrew University and NTT Research
Shin’ichiro Matsuo , NTT Research and Georgetown University
Elaine Shi , Carnegie Mellon University
Ke Wu , Carnegie Mellon University
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2022
Abstract: It is well-known that in the presence of majority coalitions, strongly fair coin toss is impossible. A line of recent works have shown that by relaxing the fairness notion to game theoretic, we can overcome this classical lower bound. In particular, Chung et al. (CRYPTO'21) showed how to achieve approximately (game-theoretically) fair leader election in the presence of majority coalitions, with round complexity as small as O(log log n) rounds. In this paper, we revisit the round complexity of game-theoretically fair leader election. We construct O(log* n) rounds leader election protocols that achieve (1-o(1))-approximate fairness in the presence of (1-o(1)) n-sized coalitions. Our protocols achieve the same round-fairness trade offs as Chung et al.'s and have the advantage of being conceptually simpler. Finally, we also obtain game-theoretically fair protocols for committee election which might be of independent interest.
Video from CRYPTO 2022
  title={log∗-Round Game-Theoretically-Fair Leader Election},
  author={Ilan Komargodski and Shin’ichiro Matsuo and Elaine Shi and Ke Wu},