Paper 2022/791

log*-Round Game-Theoretically-Fair Leader Election

Ilan Komargodski, Hebrew University of Jerusalem, NTT Research
Shin’ichiro Matsuo, NTT Research, Georgetown University
Elaine Shi, Carnegie Mellon University
Ke Wu, Carnegie Mellon University
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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in CRYPTO 2022
Keywords
game theory leader election multi-party computation fairness
Contact author(s)
ilank @ cs huji ac il
shinichiro matsuo @ ntt-research com
runting @ gmail com
kew2 @ andrew cmu edu
History
2022-06-23: revised
2022-06-20: received
See all versions
Short URL
https://ia.cr/2022/791
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/791,
      author = {Ilan Komargodski and Shin’ichiro Matsuo and Elaine Shi and Ke Wu},
      title = {log*-Round Game-Theoretically-Fair Leader Election},
      howpublished = {Cryptology ePrint Archive, Paper 2022/791},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/791}},
      url = {https://eprint.iacr.org/2022/791}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.