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

Collective Coin Flipping.

Michael Ben-Or, Nathan Linial

Published Jan 1, 1989• 199 citations
OpenAlex

Related papers

A Robust Noncryptographic Protocol for Collective Coin Flipping

Michael Saks

A new protocol for global coin flipping in the model of Ben-Or and Linial is presented. In this model, global coin flipping is considered to be an asynchronous perfect information game among n players, some of whom are dishonest. Each player possesses a fair coin and they wish to agree on the value of a single bit, which the honest players want to be random. A protocol is $\varepsilon $-robust for t dishonest players if no set of t dishonest players can bias the bit by more than $\varepsilon $. The protocol given here is $\varepsilon $-robust against $\theta (n/\log n)$ dishonest players for any fixed $\varepsilon $, improving on the $\theta (n^{.63 \cdots } )$ robust protocol given by Ben-Or and Linial.

SIAM Journal on Discrete Mathematics•May 1, 1989•57 citations

Going random

Federico Levi

Nature Physics•Oct 1, 2017•1 citation

Robust Coin Flipping

Gene S. Kopp, John D. Wiltshire-Gordon

arXiv:1009.4188•Lecture notes in computer science•Jan 1, 2012•0 citations

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

Ilan Komargodski, Ran Raz, Yael Tauman Kalai

Electronic colloquium on computational complexity•Jan 1, 2018•0 citations

Randomness

Deborah J. Bennett, Stephen G. Gasiorowicz

Physics Today•Jan 1, 1999•4 citations

Thought Experiments

Joshua Knobe

Scientific American•Oct 18, 2011•4 citations
A new protocol for global coin flipping in the model of Ben-Or and Linial is presented. In this model, global coin flipping is considered to be an asynchronous perfect information game among n players, some of whom are dishonest. Each player possesses a fair coin and they wish to agree on the value of a single bit, which the honest players want to be random. A protocol is $\varepsilon $-robust for t dishonest players if no set of t dishonest players can bias the bit by more than $\varepsilon $. The protocol given here is $\varepsilon $-robust against θ(n/log⁡n)\theta (n/\log n)θ(n/logn) dishonest players for any fixed $\varepsilon $, improving on the θ(n.63⋯)\theta (n^{.63 \cdots } )θ(n.63⋯) robust protocol given by Ben-Or and Linial.