File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-030-84245-1_1
- WOS: WOS:000696697800001
Supplementary
-
Citations:
- Web of Science: 0
- Appears in Collections:
Conference Paper: Game-Theoretic Fairness Meets Multi-party Protocols: The Case of Leader Election
Title | Game-Theoretic Fairness Meets Multi-party Protocols: The Case of Leader Election |
---|---|
Authors | |
Issue Date | 2021 |
Publisher | Springer. |
Citation | CRYPTO: 41st Annual International Cryptology Conference 2021 (Onliine). In 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021: Proceedings. Part II, Multi-Party Computation; Lattice Cryptography; and Lattice Cryptanalysis, p. 3-32 How to Cite? |
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 a majority coalition 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Θ(r))
-fairness in r rounds for Θ(loglogn)≤r≤Θ(logn), 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(loglogn)
rounds. We also prove a lower bound showing that logarithmically many rounds are 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 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. |
Description | Lecture Notes in Computer Science ; volume 12826 LNCS sublibrary, SL 4, Security and cryptology |
Persistent Identifier | http://hdl.handle.net/10722/320325 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chung, KM | - |
dc.contributor.author | Chan, HTH | - |
dc.contributor.author | Wen, T | - |
dc.contributor.author | Shi, E | - |
dc.date.accessioned | 2022-10-21T07:51:12Z | - |
dc.date.available | 2022-10-21T07:51:12Z | - |
dc.date.issued | 2021 | - |
dc.identifier.citation | CRYPTO: 41st Annual International Cryptology Conference 2021 (Onliine). In 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021: Proceedings. Part II, Multi-Party Computation; Lattice Cryptography; and Lattice Cryptanalysis, p. 3-32 | - |
dc.identifier.uri | http://hdl.handle.net/10722/320325 | - |
dc.description | Lecture Notes in Computer Science ; volume 12826 | - |
dc.description | LNCS sublibrary, SL 4, Security and cryptology | - |
dc.description.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 a majority coalition 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Θ(r)) -fairness in r rounds for Θ(loglogn)≤r≤Θ(logn), 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(loglogn) rounds. We also prove a lower bound showing that logarithmically many rounds are 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 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. | - |
dc.language | eng | - |
dc.publisher | Springer. | - |
dc.relation.ispartof | 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021: Proceedings. Part II, Multi-Party Computation; Lattice Cryptography; and Lattice Cryptanalysis | - |
dc.rights | This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/[insert DOI] | - |
dc.title | Game-Theoretic Fairness Meets Multi-party Protocols: The Case of Leader Election | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Chan, HTH: hubert@cs.hku.hk | - |
dc.identifier.authority | Chan, HTH=rp01312 | - |
dc.identifier.doi | 10.1007/978-3-030-84245-1_1 | - |
dc.identifier.hkuros | 339701 | - |
dc.identifier.spage | 3 | - |
dc.identifier.epage | 32 | - |
dc.identifier.isi | WOS:000696697800001 | - |
dc.publisher.place | Cham, Germany | - |
dc.identifier.eisbn | 9783030842451 | - |