Welcome to the resource topic for 2022/791
Title:
log*-Round Game-Theoretically-Fair Leader Election
Authors: Ilan Komargodski, Shin’ichiro Matsuo, Elaine Shi, and Ke Wu
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.
ePrint: https://eprint.iacr.org/2022/791
Talk: https://www.youtube.com/watch?v=v_24fALa4Mw
Slides: https://iacr.org/submit/files/slides/2022/crypto/crypto2022/264/slides.pptx
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .