Paper 2015/202

Adaptively Secure Coin-Flipping, Revisited

Shafi Goldwasser, Yael Tauman Kalai, and Sunoo Park

Abstract

The full-information model was introduced by Ben-Or and Linial in 1985 to study collective coin-flipping: the problem of generating a common bounded-bias bit in a network of $n$ players with $t=t(n)$ faults. They showed that the majority protocol, in which each player sends a random bit and the output is the majority of the players' bits, can tolerate $t(n)=O (\sqrt n)$ even in the presence of \emph{adaptive} corruptions, and they conjectured that this is optimal for such adversaries. Lichtenstein, Linial, and Saks proved that the conjecture holds for protocols in which each player sends only a single bit. Their result has been the main progress on the conjecture during 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 allow for a larger fraction of corrupt players? We introduce a model of \emph{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 sabotage its delivery) or not. This is in contrast to the (classical) adaptive adversary who can corrupt parties only based on past messages, and cannot alter messages already sent. We prove that any one-round coin-flipping protocol, \emph{regardless of message length}, can be secure against at most $\widetilde{O}(\sqrt 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 coin-flipping 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 $\widetilde{O}(\sqrt n)$ adaptive corruptions. At the heart of our results there is a novel use of the Minimax Theorem and 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.