Paper 2020/1591

Game-Theoretic Fairness Meets Multi-Party Protocols: The Case of Leader Election

Kai-Min Chung, T-H. Hubert Chan, Ting Wen, and Elaine Shi

Abstract

Suppose that $n$ players want to elect a random leader and they communicate by posting messages to a common broadcast channel. This problem is called leader election, and it is fundamental to the distributed systems and cryptography literature. Recently, it has attracted renewed interests due to its promised applications in decentralized environments. In a game theoretically fair leader election protocol, roughly speaking, we want that even majority coalitions cannot increase its own chance of getting elected, nor hurt the chance of any honest individual. The folklore tournament-tree protocol, which completes in logarithmically many rounds, can easily be shown to satisfy game theoretic security. To the best of our knowledge, no sub-logarithmic round protocol was known in the setting that we consider. We show that by adopting an appropriate notion of approximate game-theoretic fairness, and under standard cryptographic assumption, we can achieve $(1-1/2^{\Theta(r)})$-fairness in $r$ rounds for $\Theta(\log \log n) \leq r \leq \Theta(\log n)$, where $n$ denotes the number of players. In particular, this means that we can approximately match the fairness of the tournament tree protocol using as few as $O(\log \log n)$ rounds. We also prove a lower bound showing that logarithmically many rounds is necessary if we restrict ourselves to ``perfect'' game-theoretic fairness and protocols that are ``very similar in structure'' to the tournament-tree protocol. Although leader election is a well-studied problem in other contexts in distributed computing, our work is the first exploration of the round complexity of {\it game-theoretically fair} leader election in the presence of a possibly majority coalition. As a by-product of our exploration, we suggest a new, approximate game-theoretic fairness notion, called ``approximate sequential fairness'', which provides a more desirable solution concept than some previously studied approximate fairness notions.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
game theoryleader electionmulti-party computationextractorround complexity
Contact author(s)
runting @ gmail com
History
2021-06-22: revised
2020-12-24: received
See all versions
Short URL
https://ia.cr/2020/1591
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1591,
      author = {Kai-Min Chung and T-H.  Hubert Chan and Ting Wen and Elaine Shi},
      title = {Game-Theoretic Fairness Meets Multi-Party Protocols: The Case of Leader Election},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1591},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1591}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.