TY - GEN
T1 - A lower bound for adaptively-secure collective coin-flipping protocols
AU - Kalai, Yael Tauman
AU - Komargodski, Ilan
AU - Raz, Ran
N1 - Publisher Copyright:
© Yael T. Kalai, Ilan Komargodski, and Ran Raz.
PY - 2018/10/1
Y1 - 2018/10/1
N2 - In 1985, Ben-Or and Linial (Advances in Computing Research’89) introduced the collective coin-flipping problem, where n parties communicate via a single broadcast channel and wish to generate a common random bit in the presence of adaptive Byzantine corruptions. In this model, the adversary can decide to corrupt a party in the course of the protocol as a function of the messages seen so far. They showed that the majority protocol, in which each player sends a random bit and the output is the majority value, tolerates O(n) adaptive corruptions. They conjectured that this is optimal for such adversaries. We prove that the majority protocol is optimal (up to a poly-logarithmic factor) among all protocols in which each party sends a single, possibly long, message. Previously, such a lower bound was known for protocols in which parties are allowed to send only a single bit (Lichtenstein, Linial, and Saks, Combinatorica’89), or for symmetric protocols (Goldwasser, Kalai, and Park, ICALP’15).
AB - In 1985, Ben-Or and Linial (Advances in Computing Research’89) introduced the collective coin-flipping problem, where n parties communicate via a single broadcast channel and wish to generate a common random bit in the presence of adaptive Byzantine corruptions. In this model, the adversary can decide to corrupt a party in the course of the protocol as a function of the messages seen so far. They showed that the majority protocol, in which each player sends a random bit and the output is the majority value, tolerates O(n) adaptive corruptions. They conjectured that this is optimal for such adversaries. We prove that the majority protocol is optimal (up to a poly-logarithmic factor) among all protocols in which each party sends a single, possibly long, message. Previously, such a lower bound was known for protocols in which parties are allowed to send only a single bit (Lichtenstein, Linial, and Saks, Combinatorica’89), or for symmetric protocols (Goldwasser, Kalai, and Park, ICALP’15).
KW - Adaptive corruptions
KW - Byzantine faults
KW - Coin flipping
KW - Lower bound
UR - http://www.scopus.com/inward/record.url?scp=85059642275&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85059642275&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.DISC.2018.34
DO - 10.4230/LIPIcs.DISC.2018.34
M3 - Conference contribution
AN - SCOPUS:85059642275
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 32nd International Symposium on Distributed Computing, DISC 2018
A2 - Schmid, Ulrich
A2 - Widder, Josef
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 32nd International Symposium on Distributed Computing, DISC 2018
Y2 - 15 October 2018 through 19 October 2018
ER -