Adaptively secure coin-flipping, revisited

Shafi Goldwasser, Yael Tauman Kalai, Sunoo Park

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


The question of how much bias a coalition of faulty players can introduce into distributed sampling protocols in the full information model was first studied by Ben-Or and Linial in 1985. They focused on the problem of collective coin-flipping, in which a set of n players wish to use their private randomness to generate a common random bit b in the presence of t(n) faulty players, such that the probability that b = 0 (and 1) are at least ε for some constant ε > 0. They showed that the majority function can tolerate t = Θ(√n) corruptions even in the presence of adaptive adversaries and conjectured that this is optimal in the adaptive setting. Shortly thereafter, Lichtenstein, Linial, and Saks proved that the conjecture holds for protocols where each player sends a single bit. Their result has been the main progress on the conjecture for the last 30 years. In this work we revisit this question, and ask: what about protocols where players can send longer messages? Can increased communication enable tolerance of a larger fraction of corrupt players? We introduce a model of strong adaptive corruptions, in which an adversary sees all messages sent by honest parties in any given round, and based on the message content, decides whether to corrupt a party (and alter its message) or not. This is in contrast to the (classical) adaptive adversary, who corrupts parties based on prior communication history, and cannot alter messages already sent. Such strongly adaptive corruptions seem to be a realistic concern in settings where malicious parties can alter (or sabotage the delivery) of honest messages depending on their content, yet existing adversarial models do not take this into account. We prove that any one-round coin-flipping protocol, regardless of message length, can be secure against at most Õ(√n) strong adaptive corruptions. Thus, increased message length does not help in this setting. We then shed light on the connection between adaptive and strongly adaptive adversaries, by proving that for any symmetric one-round coinflipping protocol secure against t adaptive corruptions, there is a symmetric one-round coin-flipping protocol secure against t strongly adaptive corruptions. Going back to the standard adaptive model, we can now prove that any symmetric one-round protocol with arbitrarily long messages can tolerate at most Õ(√n) adaptive corruptions. At the heart of our results there is a new technique for converting any one-round secure protocol with arbitrarily long messages into a secure one where each player sends only polylog(n) bits. This technique may be of independent interest.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings
EditorsNaoki Kobayashi, Bettina Speckmann, Kazuo Iwama, Magnus M. Halldorsson
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783662476659
StatePublished - 2015
Event42nd International Colloquium on Automata, Languages and Programming, ICALP 2015 - Kyoto, Japan
Duration: Jul 6 2015Jul 10 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference42nd International Colloquium on Automata, Languages and Programming, ICALP 2015

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Adaptively secure coin-flipping, revisited'. Together they form a unique fingerprint.

Cite this