Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Electronic colloquium on computational complexity

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

Ilan Komargodski, Ran Raz, Yael Tauman Kalai

Published Jan 1, 2018• 0 citations
OpenAlex

Related papers

A new protocol and lower bounds for quantum coin flipping

Andris Ambainis

arXiv:quant-ph/0204022•Journal of Computer and System Sciences•Oct 17, 2003•81 citations

Adaptively Secure Coin-Flipping, Revisited

Shafi Goldwasser, Yael Tauman Kalai, Sunoo Park

Lecture notes in computer science•Jan 1, 2015•18 citations

Adaptively Secure Coin-Flipping, Revisited

Shafi Goldwasser, Yael Tauman Kalai, Sunoo Park

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.01588•Mar 5, 2015•0 citations

A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip

Iftach Haitner, Yonatan Karidi-Heller

In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems ’83], the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS ’85], the parties communicate over a broadcast channel, and a computationally unbounded adversary can choose which parties to corrupt along the protocol execution. Ben-Or and Linial proved that the n -party majority protocol is resilient to \(O(\sqrt {n})\) corruptions, and conjectured this is a tight upper bound for any n -party protocol (of any round complexity). Their conjecture was proved to be correct, up to polylogarithmic factors, for single-turn (each party sends a single message) single-bit (a message is one bit) protocols Lichtenstein et al. [Combinatorica ’89], symmetric protocols Goldwasser et al. [ICALP ’15], and recently for (arbitrary message length) single-turn protocols Tauman Kalai et al. [DISC ’18]. Yet, the question of many-turn protocols was left entirely open. In this work, we close the above gap, proving that no n -party protocol (of any round complexity) is resilient to \(\Omega (\sqrt {n} \cdot \log ^3 n)\) adaptive corruptions. Namely, majority is the optimal coin-flipping protocol against adaptive adversaries (up to polylogarithmic factors).

arXiv:2005.01565•Journal of the ACM•Nov 1, 2020•15 citations

Quantum-Secure Coin-Flipping and Applications

Ivan Damgård, Carolin Lunemann

Lecture notes in computer science•Jan 1, 2009•25 citations

On Adaptively Secure Protocols

Muthuramakrishnan Venkitasubramaniam

Lecture notes in computer science•Jan 1, 2014•13 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 nnn players with t=t(n)t=t(n)t=t(n) faults. They showed that the majority protocol can tolerate t=O(n)t=O(\sqrt n)t=O(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 O~(n)\tilde{O}(\sqrt n)O~(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 ttt adaptive corruptions, there is a symmetric one-round coin-flipping protocol secure against ttt 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 O~(n)\tilde{O}(\sqrt n)O~(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)polylog(n)polylog(n) bits. This technique may be of independent interest.
In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems ’83], the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS ’85], the parties communicate over a broadcast channel, and a computationally unbounded adversary can choose which parties to corrupt along the protocol execution. Ben-Or and Linial proved that the n -party majority protocol is resilient to O(n)O(\sqrt {n})O(n​) corruptions, and conjectured this is a tight upper bound for any n -party protocol (of any round complexity). Their conjecture was proved to be correct, up to polylogarithmic factors, for single-turn (each party sends a single message) single-bit (a message is one bit) protocols Lichtenstein et al. [Combinatorica ’89], symmetric protocols Goldwasser et al. [ICALP ’15], and recently for (arbitrary message length) single-turn protocols Tauman Kalai et al. [DISC ’18]. Yet, the question of many-turn protocols was left entirely open. In this work, we close the above gap, proving that no n -party protocol (of any round complexity) is resilient to Ω(n⋅log⁡3n)\Omega (\sqrt {n} \cdot \log ^3 n)Ω(n​⋅log3n) adaptive corruptions. Namely, majority is the optimal coin-flipping protocol against adaptive adversaries (up to polylogarithmic factors).