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

Conference on Computational Complexity

Multiparty quantum coin flipping

Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig

Published Jun 21, 2004• 55 citations
Publisher

Abstract

We investigate coin-flipping protocols for multiple parties in a quantum broadcast setting: (1) We propose and motivate a definition for quantum broadcast. (2) We prove that in this model, there are protocols for k parties with guaranteed bias 1/2 - Omega(1/k^1.78) for (k-1) computationally-unbounded cheating parties. Classically, no bias < 1/2 can be achieved if a majority of the players is bad. (3) We extend our protocol to a setting where at most (1-epsilon) k of the players are bad, for epsilon > 0. We show that in this case we can achieve a constant bias delta < 1/2 - Omega(epsilon^1.78), independent of k. (4) We show that our results are essentially optimal: for k parties with one good party, any quantum protocol can achieve bias at best 1/2 - O(1/k), while for (1-epsilon)k cheating parties achieving constant bias delta < 1/2 - O(epsilon) is impossible, too.

DOI
10.1109/ccc.2004.19

Related papers

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

Cheat-Penalised Quantum Weak Coin-Flipping

Atul Singh Arora, Carl A. Miller, Mauro E. S. Morales +1 more

Coin-flipping is a fundamental task in two-party cryptography where two remote mistrustful parties wish to generate a shared uniformly random bit. While quantum protocols promising near-perfect security exist for weak coin-flipping -- when the parties want opposing outcomes -- it has been shown that they must be inefficient in terms of their round complexity, and it is an open question of how space efficient they can be. In this work, we consider a variant called cheat-penalised weak coin-flipping in which if a party gets caught cheating, they lose $Λ$ points (compared to $0$ in the standard definition). We find that already for a small cheating penalty, the landscape of coin-flipping changes dramatically. For example, with $Λ=0.01$, we exhibit a protocol where neither Alice nor Bob can bias the result in their favour beyond $1/2 + 10^{-8}$, which uses $24$ qubits and $10^{16}$ rounds of communication (provably $10^{7}$ times better than any weak coin-flipping protocol with matching security). For the same space requirements, we demonstrate how one can choose between lowering how much a malicious party can bias the result (down to $1/2 + 10^{-10}$) and reducing the rounds of communication (down to $25,180$), depending on what is preferred. To find these protocols, we make two technical contributions. First, we extend the point game-protocol correspondence introduced by Kitaev and Mochon, to incorporate: (i) approximate point games, (ii) the cheat-penalised setting, and (iii) round and space complexity. Second, we give the first (to the best of our knowledge) numerical algorithm for constructing (approximate) point games that correspond to high security and low complexity. Our results open up the possibility of having secure and practical quantum protocols for multiparty computation.

arXiv:2510.03218•Oct 3, 2025•0 citations

Fair loss-tolerant quantum coin flipping

Guido Berlín, Gilles Brassard, Félix Bussières +1 more

Coin flipping is a cryptographic primitive in which two spatially separated players, who do not trust each other, wish to establish a common random bit. If we limit ourselves to classical communication, this task requires either assumptions on the computational power of the players or it requires them to send messages to each other with sufficient simultaneity to force their complete independence. Without such assumptions, all classical protocols are so that one dishonest player has complete control over the outcome. If we use quantum communication, on the other hand, protocols have been introduced that limit the maximal bias that dishonest players can produce. However, those protocols would be very difficult to implement in practice because they are susceptible to realistic losses on the quantum channel between the players or in their quantum memory and measurement apparatus. In this paper, we introduce a quantum protocol and we prove that it is completely impervious to loss. The protocol is fair in the sense that either player has the same probability of success in cheating attempts at biasing the outcome of the coin flip. We also give explicit and optimal cheating strategies for both players.

arXiv:0904.3945•Physical Review A•Dec 10, 2009•41 citations

An almost-optimally fair three-party coin-flipping protocol

Iftach Haitner, Eliad Tsfadia

In a multiparty fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. Cleve [STOC 1986] has shown that in the case of dishonest majority (i.e., at least half of the parties can be corrupted), in any m-round coin-flipping protocol, the corrupted parties can bias the honest parties' common output bit by Ω(1/m). For more than two decades, the best known coin-flipping protocols against dishonest majority had bias [EQUATION], where ℓ is the number of corrupted parties. This was changed by a recent breakthrough result of Moran et al. [TCC 2009], who constructed an m-round, two-party coin-flipping protocol with optimal bias Θ(1/m). In a subsequent work, Beimel et al. [Crypto 2010] extended this result to the multiparty case in which less than 2/3 of the parties can be corrupted. Still for the case of 2/3 (or more) corrupted parties, the best known protocol had bias [EQUATION]. In particular, this was the state of affairs for the natural three-party case.

ACM Symposium on Theory of Computing (STOC)•May 31, 2014•22 citations

Experimental loss-tolerant quantum coin flipping

Guido Berlín, Gilles Brassard, Félix Bussières +3 more

Coin flipping is a cryptographic primitive in which two distrustful parties wish to generate a random bit to choose between two alternatives. This task is impossible to realize when it relies solely on the asynchronous exchange of classical bits: one dishonest player has complete control over the final outcome. It is only when coin flipping is supplemented with quantum communication that this problem can be alleviated, although partial bias remains. Unfortunately, practical systems are subject to loss of quantum data, which allows a cheater to force a bias that is complete or arbitrarily close to complete in all previous protocols and implementations. Here we report on the first experimental demonstration of a quantum coin-flipping protocol for which loss cannot be exploited to cheat better. By eliminating the problem of loss, which is unavoidable in any realistic setting, quantum coin flipping takes a significant step towards real-world applications of quantum communication. When two spatially separated parties flip a coin, it is impossible to choose between two alternatives in an unbiased manner. This study presents a quantum coin-flipping protocol that overcomes this problem and ensures a dishonest party cannot bias the outcome completely.

arXiv:0904.3946•Nature Communications•Nov 29, 2011•60 citations

Optimal Quantum Strong Coin Flipping

André Chailloux, Iordanis Kerenidis

Coin flipping is a fundamental cryptographic primitive that enables two distrustful and far apart parties to create a uniformly random bit. Quantum information allows for protocols in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum protocol by Ambain is achieved a cheating probability of at most 3/4. On the other hand, Kitaev showed that no quantum protocol can have cheating probability less than 1/sqrt{2}. Closing this gap has been one of the important open questions in quantum cryptography. In this paper, we resolve this question by presenting a quantum strong coin flipping protocol with cheating probability arbitrarily close to 1/sqrt{2}.More precisely, we show how to use any weak coin flipping protocol with cheating probability 1/2+epsilon in order to achieve a strong coin flipping protocol with cheating probability 1/sqrt{2}+O(epsilon). The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by Mochon.

arXiv:0904.1511•Annual Symposium on Foundations of Computer Science•Oct 1, 2009•81 citations
We investigate coin-flipping protocols for multiple parties in a quantum broadcast setting: (1) We propose and motivate a definition for quantum broadcast. (2) We prove that in this model, there are protocols for k parties with guaranteed bias 1/2 - Omega(1/k^1.78) for (k-1) computationally-unbounded cheating parties. Classically, no bias < 1/2 can be achieved if a majority of the players is bad. (3) We extend our protocol to a setting where at most (1-epsilon) k of the players are bad, for epsilon > 0. We show that in this case we can achieve a constant bias delta < 1/2 - Omega(epsilon^1.78), independent of k. (4) We show that our results are essentially optimal: for k parties with one good party, any quantum protocol can achieve bias at best 1/2 - O(1/k), while for (1-epsilon)k cheating parties achieving constant bias delta < 1/2 - O(epsilon) is impossible, too.
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.
Coin-flipping is a fundamental task in two-party cryptography where two remote mistrustful parties wish to generate a shared uniformly random bit. While quantum protocols promising near-perfect security exist for weak coin-flipping -- when the parties want opposing outcomes -- it has been shown that they must be inefficient in terms of their round complexity, and it is an open question of how space efficient they can be. In this work, we consider a variant called cheat-penalised weak coin-flipping in which if a party gets caught cheating, they lose ΛΛΛ points (compared to 000 in the standard definition). We find that already for a small cheating penalty, the landscape of coin-flipping changes dramatically. For example, with Λ=0.01Λ=0.01Λ=0.01, we exhibit a protocol where neither Alice nor Bob can bias the result in their favour beyond 1/2+10−81/2 + 10^{-8}1/2+10−8, which uses 242424 qubits and 101610^{16}1016 rounds of communication (provably 10710^{7}107 times better than any weak coin-flipping protocol with matching security). For the same space requirements, we demonstrate how one can choose between lowering how much a malicious party can bias the result (down to 1/2+10−101/2 + 10^{-10}1/2+10−10) and reducing the rounds of communication (down to 25,18025,18025,180), depending on what is preferred. To find these protocols, we make two technical contributions. First, we extend the point game-protocol correspondence introduced by Kitaev and Mochon, to incorporate: (i) approximate point games, (ii) the cheat-penalised setting, and (iii) round and space complexity. Second, we give the first (to the best of our knowledge) numerical algorithm for constructing (approximate) point games that correspond to high security and low complexity. Our results open up the possibility of having secure and practical quantum protocols for multiparty computation.
Coin flipping is a cryptographic primitive in which two spatially separated players, who do not trust each other, wish to establish a common random bit. If we limit ourselves to classical communication, this task requires either assumptions on the computational power of the players or it requires them to send messages to each other with sufficient simultaneity to force their complete independence. Without such assumptions, all classical protocols are so that one dishonest player has complete control over the outcome. If we use quantum communication, on the other hand, protocols have been introduced that limit the maximal bias that dishonest players can produce. However, those protocols would be very difficult to implement in practice because they are susceptible to realistic losses on the quantum channel between the players or in their quantum memory and measurement apparatus. In this paper, we introduce a quantum protocol and we prove that it is completely impervious to loss. The protocol is fair in the sense that either player has the same probability of success in cheating attempts at biasing the outcome of the coin flip. We also give explicit and optimal cheating strategies for both players.
In a multiparty fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. Cleve [STOC 1986] has shown that in the case of dishonest majority (i.e., at least half of the parties can be corrupted), in any m-round coin-flipping protocol, the corrupted parties can bias the honest parties' common output bit by Ω(1/m). For more than two decades, the best known coin-flipping protocols against dishonest majority had bias [EQUATION], where ℓ is the number of corrupted parties. This was changed by a recent breakthrough result of Moran et al. [TCC 2009], who constructed an m-round, two-party coin-flipping protocol with optimal bias Θ(1/m). In a subsequent work, Beimel et al. [Crypto 2010] extended this result to the multiparty case in which less than 2/3 of the parties can be corrupted. Still for the case of 2/3 (or more) corrupted parties, the best known protocol had bias [EQUATION]. In particular, this was the state of affairs for the natural three-party case.
Coin flipping is a cryptographic primitive in which two distrustful parties wish to generate a random bit to choose between two alternatives. This task is impossible to realize when it relies solely on the asynchronous exchange of classical bits: one dishonest player has complete control over the final outcome. It is only when coin flipping is supplemented with quantum communication that this problem can be alleviated, although partial bias remains. Unfortunately, practical systems are subject to loss of quantum data, which allows a cheater to force a bias that is complete or arbitrarily close to complete in all previous protocols and implementations. Here we report on the first experimental demonstration of a quantum coin-flipping protocol for which loss cannot be exploited to cheat better. By eliminating the problem of loss, which is unavoidable in any realistic setting, quantum coin flipping takes a significant step towards real-world applications of quantum communication. When two spatially separated parties flip a coin, it is impossible to choose between two alternatives in an unbiased manner. This study presents a quantum coin-flipping protocol that overcomes this problem and ensures a dishonest party cannot bias the outcome completely.
Coin flipping is a fundamental cryptographic primitive that enables two distrustful and far apart parties to create a uniformly random bit. Quantum information allows for protocols in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum protocol by Ambain is achieved a cheating probability of at most 3/4. On the other hand, Kitaev showed that no quantum protocol can have cheating probability less than 1/sqrt{2}. Closing this gap has been one of the important open questions in quantum cryptography. In this paper, we resolve this question by presenting a quantum strong coin flipping protocol with cheating probability arbitrarily close to 1/sqrt{2}.More precisely, we show how to use any weak coin flipping protocol with cheating probability 1/2+epsilon in order to achieve a strong coin flipping protocol with cheating probability 1/sqrt{2}+O(epsilon). The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by Mochon.