Skip to main content

A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols

Author(s): Kalai, Yael T; Komargodski, Ilan; Raz, Ran

To refer to this page use:
Abstract: 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(sqrt 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).
Publication Date: 2018
Citation: Kalai, Yael Tauman, Ilan Komargodski, and Ran Raz. "A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols." 32nd International Symposium on Distributed Computing 121 (2018): pp. 34:1-34:16. doi:10.4230/LIPIcs.DISC.2018.34
DOI: 10.4230/LIPIcs.DISC.2018.34
ISSN: 1868-8969
Pages: 34:1 - 34:16
Type of Material: Conference Article
Journal/Proceeding Title: 32nd International Symposium on Distributed Computing
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.