Paper 2024/1961

On the (Im)possibility of Game-Theoretically Fair Leader Election Protocols

Ohad Klein, Hebrew University of Jerusalem
Ilan Komargodski, Hebrew University of Jerusalem, NTT Research
Chenzhi Zhu, University of Washington
Abstract

We consider the problem of electing a leader among $n$ parties with the guarantee that each (honest) party has a reasonable probability of being elected, even in the presence of a coalition that controls a subset of parties, trying to bias the output. This notion is called ``game-theoretic fairness'' because such protocols ensure that following the honest behavior is an equilibrium and also the best response for every party and coalition. In the two-party case, Blum's commit-and-reveal protocol (where if one party aborts, then the other is declared the leader) satisfies this notion and it is also known that one-way functions are necessary. Recent works study this problem in the multi-party setting. They show that composing Blum's 2-party protocol for $\log n$ rounds in a tournament-tree-style manner results with {perfect game-theoretic fairness}: each honest party has probability $\ge 1/n$ of being elected as leader, no matter how large the coalition is. Logarithmic round complexity is also shown to be necessary if we require perfect fairness against a coalition of size $n-1$. Relaxing the above two requirements, i.e., settling for approximate game-theoretic fairness and guaranteeing fairness against only constant fraction size coalitions, it is known that there are $O(\log ^* n)$ round protocols. This leaves many open problems, in particular, whether one can go below logarithmic round complexity by relaxing only one of the strong requirements from above. We manage to resolve this problem for commit-and-reveal style protocols, showing that - $\Omega(\log n/\log\log n)$ rounds are necessary if we settle for approximate fairness against very large (more than constant fraction) coalitions; - $\Omega(\log n)$ rounds are necessary if we settle for perfect fairness against $n^\epsilon$ size coalitions (for any constant $\epsilon>0$). These show that both relaxations made in prior works are necessary to go below logarithmic round complexity. Lastly, we provide several additional upper and lower bounds for the case of single-round commit-and-reveal style protocols.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in TCC 2024
Keywords
Leader election
Contact author(s)
ohadkel @ gmail com
ilank @ cs huji ac il
zhucz20 @ cs washington edu
History
2024-12-06: approved
2024-12-04: received
See all versions
Short URL
https://ia.cr/2024/1961
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1961,
      author = {Ohad Klein and Ilan Komargodski and Chenzhi Zhu},
      title = {On the (Im)possibility of Game-Theoretically Fair Leader Election Protocols},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1961},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1961}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.