License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.34
URN: urn:nbn:de:0030-drops-98230
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9823/
Go to the corresponding LIPIcs Volume Portal

Tauman Kalai, Yael ; Komargodski, Ilan ; Raz, Ran

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

pdf-format:
LIPIcs-DISC-2018-34.pdf (0.5 MB)

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

BibTeX - Entry

@InProceedings{taumankalai_et_al:LIPIcs:2018:9823,
  author =	{Yael Tauman Kalai and Ilan Komargodski and Ran Raz},
  title =	{{A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols}},
  booktitle =	{32nd International Symposium on Distributed Computing  (DISC 2018)},
  pages =	{34:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Ulrich Schmid and Josef Widder},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9823},
  URN =		{urn:nbn:de:0030-drops-98230},
  doi =		{10.4230/LIPIcs.DISC.2018.34},
  annote =	{Keywords: Coin flipping, adaptive corruptions, byzantine faults, lower bound}
}

Keywords: Coin flipping, adaptive corruptions, byzantine faults, lower bound
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI