A lower bound for adaptively-secure collective coin-flipping protocols

Yael Tauman Kalai, Ilan Komargodski, Ran Raz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


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).

Original languageEnglish (US)
Title of host publication32nd International Symposium on Distributed Computing, DISC 2018
EditorsUlrich Schmid, Josef Widder
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770927
StatePublished - Oct 1 2018
Event32nd International Symposium on Distributed Computing, DISC 2018 - New Orleans, United States
Duration: Oct 15 2018Oct 19 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Other32nd International Symposium on Distributed Computing, DISC 2018
Country/TerritoryUnited States
CityNew Orleans

All Science Journal Classification (ASJC) codes

  • Software


  • Adaptive corruptions
  • Byzantine faults
  • Coin flipping
  • Lower bound

Cite this