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

arXiv:1009.4741 · Lecture notes in computer science

Tight Bounds for Classical and Quantum Coin Flipping

Esther Hänggi, Jürg Wullschleger

Published Jan 1, 2011• 20 citations
arXivHTMLPDF
DOI
10.1007/978-3-642-19571-6_28

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

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

Multiparty quantum coin flipping

Andris Ambainis, Harry Buhrman, Yevgeniy Dodis +1 more

We investigate coin-flipping protocols for multiple parties in a quantum broadcast setting: (1) we propose and motivate a definition for quantum broadcast. Our model of quantum broadcast channel is new. (2) We discovered that quantum broadcast is essentially a combination of pairwise quantum channels and a classical broadcast channel. This is a somewhat surprising conclusion, but helps us in both our lower and upper bounds. (3) We provide tight upper and lower bounds on the optimal bias /spl epsiv/ of a coin which can be flipped by k parties of which exactly g parties are honest: for any 1 /spl les/ g /spl les/ k, /spl epsiv/ = 1/2 - /spl Theta/ (g/k). Thus, as long as a constant fraction of the players are honest, they can prevent the coin from being fixed with at least a constant probability. This result stands in sharp contrast with the classical setting, where no non-trivial coin-flipping is possible when g /spl les/ k/2.

arXiv:quant-ph/0304112•IEEE Conference on Computational Complexity (CCC)•Nov 12, 2004•65 citations

Large family of quantum weak coin-flipping protocols

Carlos Mochon

Each classical public-coin protocol for coin flipping is naturally associated with a quantum protocol for weak coin flipping. The quantum protocol is obtained by replacing classical randomness with quantum entanglement and by adding a cheat detection test in the last round that verifies the integrity of this entanglement. The set of such protocols defines a family which contains the protocol with bias 0.192 previously found by the author, as well as protocols with bias as low as $1∕6$ described herein. The family is analyzed by identifying a set of optimal protocols for every number of messages. In the end, tight lower bounds for the bias are obtained which prove that $1∕6$ is optimal for all protocols within the family.

arXiv:quant-ph/0502068•Physical Review A•Aug 29, 2005•52 citations

Practical aspects of quantum coin flipping

Anna Pappa, Paul Jouguet, Thomas Lawson +4 more

•Nov 1, 2012•0 citations

Tighter Bounds on Multi-Party Coin Flipping, via Augmented Weak Martingales and Di erentially Private Sampling.

Amos Beimel, Iftach Haitner, Nikolaos Makriyannis +1 more

Electronic colloquium on computational complexity•Jan 1, 2017•3 citations
We investigate coin-flipping protocols for multiple parties in a quantum broadcast setting: (1) we propose and motivate a definition for quantum broadcast. Our model of quantum broadcast channel is new. (2) We discovered that quantum broadcast is essentially a combination of pairwise quantum channels and a classical broadcast channel. This is a somewhat surprising conclusion, but helps us in both our lower and upper bounds. (3) We provide tight upper and lower bounds on the optimal bias /spl epsiv/ of a coin which can be flipped by k parties of which exactly g parties are honest: for any 1 /spl les/ g /spl les/ k, /spl epsiv/ = 1/2 - /spl Theta/ (g/k). Thus, as long as a constant fraction of the players are honest, they can prevent the coin from being fixed with at least a constant probability. This result stands in sharp contrast with the classical setting, where no non-trivial coin-flipping is possible when g /spl les/ k/2.
Each classical public-coin protocol for coin flipping is naturally associated with a quantum protocol for weak coin flipping. The quantum protocol is obtained by replacing classical randomness with quantum entanglement and by adding a cheat detection test in the last round that verifies the integrity of this entanglement. The set of such protocols defines a family which contains the protocol with bias 0.192 previously found by the author, as well as protocols with bias as low as 1∕61∕61∕6 described herein. The family is analyzed by identifying a set of optimal protocols for every number of messages. In the end, tight lower bounds for the bias are obtained which prove that 1∕61∕61∕6 is optimal for all protocols within the family.