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

International Conference on Information Technology: Coding and Computing (ITCC)

n-state quantum coin flipping protocol

A. Waseda, Masakazu Soshi, Atsuko Miyaji

Published Jan 1, 2005• 0 citations
Publisher

Abstract

We propose the n-state quantum coin flipping protocol by generalizing the three states protocol. Furthermore, we conduct security analysis on our protocol and show that in our protocol we can reduce the bias of one player arbitrarily, but at the cost of increase of the bias of the other.
DOI
10.1109/itcc.2005.208

Related papers

A Fair Loss-Tolerant Quantum Coin Flipping Protocol

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

Coin flipping is a cryptographic primitive in which two spatially separated players, who in principle do not trust each other, wish to agree on a random bit. Classical and quantum coin flipping protocols have been studied extensively for more than twenty‐five years. However, until recently, quantum coin flipping protocols were designed without taking into consideration the losses of quantum information that would be unavoidable in any realistic implementation. We introduced in 2008 a novel protocol and proved its security even when losses are taken into account: no cheating player could obtain a desired outcome with a probability greater than (6+2)/8≈93%. Here, we refine our earlier protocol by making it fair in the sense that the optimal cheating strategies allow either player to bias the outcome by the same amount. Specifically, either player can cheat to obtain a desired outcome with probability exactly 90%, but no more. An implementation is underway.

AIP conference proceedings•Jan 1, 2009•1 citation

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 in principle 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 participants 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 can completely bias the outcome to his choosing. If we allow for 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 cannot tolerate realistic losses on the quantum channel between the participants or in their quantum storage and measurement apparatus. In this paper, we introduce a novel quantum protocol and we prove its unconditional security even when such losses are taken into account.

International Conference on Quantum, Nano and Micro Technologies (ICQNM)•Feb 1, 2008•9 citations

Unconditionally secure quantum coin flipping

Guang Ping He

Quantum coin flipping (QCF) is an essential primitive for quantum cryptography. Unconditionally secure strong QCF with an arbitrarily small bias was widely believed to be impossible. But basing on a problem which cannot be solved without quantum algorithm, here we propose such a QCF protocol, and show how it manages to evade all existing no-go proofs on QCF.

arXiv:1602.01430•Results in Physics•Mar 30, 2023•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. (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.

Conference on Computational Complexity•Jun 21, 2004•55 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

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
Coin flipping is a cryptographic primitive in which two spatially separated players, who in principle do not trust each other, wish to agree on a random bit. Classical and quantum coin flipping protocols have been studied extensively for more than twenty‐five years. However, until recently, quantum coin flipping protocols were designed without taking into consideration the losses of quantum information that would be unavoidable in any realistic implementation. We introduced in 2008 a novel protocol and proved its security even when losses are taken into account: no cheating player could obtain a desired outcome with a probability greater than (6+2)/8≈93%. Here, we refine our earlier protocol by making it fair in the sense that the optimal cheating strategies allow either player to bias the outcome by the same amount. Specifically, either player can cheat to obtain a desired outcome with probability exactly 90%, but no more. An implementation is underway.
Coin flipping is a cryptographic primitive in which two spatially separated players, who in principle 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 participants 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 can completely bias the outcome to his choosing. If we allow for 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 cannot tolerate realistic losses on the quantum channel between the participants or in their quantum storage and measurement apparatus. In this paper, we introduce a novel quantum protocol and we prove its unconditional security even when such losses are taken into account.
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.
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.
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.