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 can tolerate $t=O(\sqrt n)$ adaptive corruptions, and conjectured that this is optimal in the adaptive setting. Lichtenstein, Linial, and Saks proved that the conjecture holds for protocols in which each player sends a single bit. Their result has been the main progress on the conjecture in the last 30 years. In this work we revisit this question and ask: what about protocols involving longer messages? Can increased communication allow for a larger fraction of faulty players? We introduce a model of strong adaptive corruptions, where in each round, the adversary sees all messages sent by honest parties and, based on the message content, decides whether to corrupt a party (and intercept his message) or not. We prove that any one-round coin-flipping protocol, regardless of message length, is secure against at most $\tilde{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. Returning to the standard adaptive model, we can now prove that any symmetric one-round protocol with arbitrarily long messages can tolerate at most $\tilde{O}(\sqrt n)$ adaptive corruptions. At the heart of our results lies a novel use of the Minimax Theorem and a new technique for converting any one-round secure protocol into a protocol with messages of $polylog(n)$ bits. This technique may be of independent interest.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 can tolerate $t=O(\sqrt n)$ adaptive corruptions, and conjectured that this is optimal in the adaptive setting. Lichtenstein, Linial, and Saks proved that the conjecture holds for protocols in which each player sends a single bit. Their result has been the main progress on the conjecture in the last 30 years. In this work we revisit this question and ask: what about protocols involving longer messages? Can increased communication allow for a larger fraction of faulty players? We introduce a model of strong adaptive corruptions, where in each round, the adversary sees all messages sent by honest parties and, based on the message content, decides whether to corrupt a party (and intercept his message) or not. We prove that any one-round coin-flipping protocol, regardless of message length, is secure against at most $\tilde{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. Returning to the standard adaptive model, we can now prove that any symmetric one-round protocol with arbitrarily long messages can tolerate at most $\tilde{O}(\sqrt n)$ adaptive corruptions. At the heart of our results lies a novel use of the Minimax Theorem and a new technique for converting any one-round secure protocol into a protocol with messages of $polylog(n)$ bits. This technique may be of independent interest.

arXiv:1503.01588Mar 5, 20150 citations

Impossibility of Black-Box Reduction from Non-Adaptively to Adaptively Secure Coin-Flipping

Yevgeniy Dodis

Collective Coin-Flipping is a classical problem where n computationally unbounded processors are trying to generate a random bit in a setting where only a single broadcast channel is available for communication. The protocol is said to be b(n)-resilient if any adversary that can corrupt up to b(n) players, still cannot bias the coin to some desired outcome almost certainly. The problem is extensively studied for the case of non-adaptive adversaries who have to decide which players to corrupt before the protocol starts. In particular, it is well-known that the optimum resilience threshold is n=2 in this case. However, none of these protocols is resilient against an adaptive adversary who can corrupt just a single player in the course of the execution. In fact, Ben-Or and Linial [BL90] conjectured that the adaptive adversary is much more powerful than the non-adaptive adversary. More specically, that the optimal resilience threshold for adaptive adversaries is only O( p n) (which is achieved by a simple "majority " protocol). We give strong evidence towards this conjecture by showing that no black-box transformation from any statically secure coin-flipping protocol can yield an adaptively secure protocol toleratingCollective Coin-Flipping is a classical problem where n computationally unbounded processors are trying to generate a random bit in a setting where only a single broadcast channel is available for communication. The protocol is said to be b(n)-resilient if any adversary that can corrupt up to b(n) players, still cannot bias the coin to some desired outcome almost certainly. The problem is extensively studied for the case of non-adaptive adversaries who have to decide which players to corrupt before the protocol starts. In particular, it is well-known that the optimum resilience threshold is n=2 in this case. However, none of these protocols is resilient against an adaptive adversary who can corrupt just a single player in the course of the execution. In fact, Ben-Or and Linial [BL90] conjectured that the adaptive adversary is much more powerful than the non-adaptive adversary. More specically, that the optimal resilience threshold for adaptive adversaries is only O( p n) (which is achieved by a simple "majority " protocol). We give strong evidence towards this conjecture by showing that no black-box transformation from any statically secure coin-flipping protocol can yield an adaptively secure protocol tolerating

Electronic colloquium on computational complexityJan 1, 20009 citations

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 can tolerate

t=O(\sqrt n)

adaptive corruptions, and conjectured that this is optimal in the adaptive setting. Lichtenstein, Linial, and Saks proved that the conjecture holds for protocols in which each player sends a single bit. Their result has been the main progress on the conjecture in the last 30 years. In this work we revisit this question and ask: what about protocols involving longer messages? Can increased communication allow for a larger fraction of faulty players? We introduce a model of strong adaptive corruptions, where in each round, the adversary sees all messages sent by honest parties and, based on the message content, decides whether to corrupt a party (and intercept his message) or not. We prove that any one-round coin-flipping protocol, regardless of message length, is secure against at most

\tilde{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. Returning to the standard adaptive model, we can now prove that any symmetric one-round protocol with arbitrarily long messages can tolerate at most

\tilde{O}(\sqrt n)

adaptive corruptions. At the heart of our results lies a novel use of the Minimax Theorem and a new technique for converting any one-round secure protocol into a protocol with messages of

polylog(n)

bits. This technique may be of independent interest.