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

ACM SIGACT News

Coin flipping by telephone a protocol for solving impossible problems

Manuel Blum

Published Jan 1, 1983• 532 citations
Publisher

Abstract

Alice and Bob want to flip a coin by telephone. (They have just divorced, live in different cities, want to decide who gets the car.) Bob would not like to tell Alice HEADS and hear Alice (at the other end of the line) say "Here goes . . . I'm flipping the coin. . . . You lost!"Coin-flipping in the SPECIAL way done here has a serious purpose. Indeed, it should prove an INDISPENSABLE TOOL of the protocol designer. Whenever a protocol requires one of two adversaries, say Alice, to pick a sequence of bits at random, and whenever it serves Alice's interests best NOT to pick her sequence of bits at random, then coin-flipping (Bob flipping coins to Alice) as defined here achieves the desired goal:1. It GUARANTEES to Bob that Alice will pick her sequence of bits at random. Her bit is 1 if Bob flips heads to her, O otherwise.2. It GUARANTEES to Alice that Bob will not know WHAT sequence of bits he flipped to her.Coin-flipping has already proved useful in solving a number of problems once thought impossible: mental poker, certified mail, and exchange of secrets. It will certainly prove a useful tool in solving other problems as well.

DOI
10.1145/1008908.1008911

Related papers

Transmutation scheme of coin flipping protocol and utilization

Xie Yumin, Ming Yang, Shi Feng +1 more

Coin flipping by telephone protocol(CFP) is utilized in a system to exchange a binary sequence at random between two person apart far from each other. However, CFP cannot be used in a system with many users like in a group environment system. A transmutation of CFP named T-CFP is proposed in this paper. The precondition of T-CFP is the system's user trusts the system center and center's cheating is meaningless at the same time. The significant difference between CFP and T-CFP is that CFP supports only two users while T-CFP can support many users to exchange special information. The security and efficiency of T-CFP are discussed with a detailed example on T-CFP utilization is demonstrated in this paper.

Wuhan University Journal of Natural Sciences•Nov 1, 2006•0 citations

Improving device-independent weak coin flipping protocols

Atul Singh Arora, Jamie Sikora, Thomas van Himbeeck

Weak coin flipping is the cryptographic task where Alice and Bob remotely flip a coin but want opposite outcomes. This work studies this task in the device-independent regime where Alice and Bob neither trust each other, nor their quantum devices. The best protocol was devised over a decade ago by Silman, Chailloux, Aharon, Kerenidis, Pironio, and Massar with bias $\varepsilon \approx 0.33664$, where the bias is a commonly adopted security measure for coin flipping protocols. This work presents two techniques to lower the bias of such protocols, namely self-testing and abort-phobic compositions. We apply these techniques to the SCAKPM '11 protocol above and, assuming a continuity conjecture, lower the bias to $\varepsilon \approx 0.29104$. We believe that these techniques could be useful in the design of device-independent protocols for a variety of other tasks. Independently of weak coin flipping, en route to our results, we show how one can test $n-1$ out of $n$ devices, and estimate the performance of the remaining device, for later use in the protocol. The proof uses linear programming and, due to its generality, may find applications elsewhere.

arXiv:2404.17079•Apr 25, 2024•3 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

Unconditionally Secure Quantum Coin Tossing. (arXiv:quant-ph/9904078v2 UPDATED)

Dominic Mayers, Louis Salvail, Yoshie Chiba-Kohno

In coin tossing two remote participants want to share a uniformly distributed random bit. At the least in the quantum version, each participant test whether or not the other has attempted to create a bias on this bit. It is requested that, for b = 0,1, the probability that Alice gets bit b and pass the test is smaller than 1/2 whatever she does, and similarly for Bob. If the bound 1/2 holds perfectly against any of the two participants, the task realised is called an exact coin tossing. If the bound is actually $1/2 + \xi$ where the bias $\xi$ vanishes when a security parameter m defined by the protocol increases, the task realised is a (non exact) coin tossing. It is found here that exact coin tossing is impossible. At the same time, an unconditionally secure quantum protocol that realises a (non exact) coin tossing is proposed. The protocol executes m biased quantum coin tossing procedures at the same time. It executes the first round in each of these m procedures sequentially, then the second rounds are executed, and so on until the end of the n procedures. Each procedure requires 4n particles where $n \in O(\lg m)$. The final bit x is the parity of the m random bits. The information about each of these m bits is announced a little bit at a time which implies that the principle used against bit commitment does not apply. The bias on x is smaller than $1/m$. The result is discussed in the light of the impossibility result for exact coin tossing.

•Feb 27, 2018•0 citations

Unconditionally Secure Quantum Coin Tossing

Dominic Mayers, Louis Salvail, Yoshie Chiba-Kohno

In coin tossing two remote participants want to share a uniformly distributed random bit. At the least in the quantum version, each participant test whether or not the other has attempted to create a bias on this bit. It is requested that, for b = 0,1, the probability that Alice gets bit b and pass the test is smaller than 1/2 whatever she does, and similarly for Bob. If the bound 1/2 holds perfectly against any of the two participants, the task realised is called an exact coin tossing. If the bound is actually $1/2 + ξ$ where the bias $ξ$ vanishes when a security parameter m defined by the protocol increases, the task realised is a (non exact) coin tossing. It is found here that exact coin tossing is impossible. At the same time, an unconditionally secure quantum protocol that realises a (non exact) coin tossing is proposed. The protocol executes m biased quantum coin tossing procedures at the same time. It executes the first round in each of these m procedures sequentially, then the second rounds are executed, and so on until the end of the n procedures. Each procedure requires 4n particles where $n \in O(\lg m)$. The final bit x is the parity of the m random bits. The information about each of these m bits is announced a little bit at a time which implies that the principle used against bit commitment does not apply. The bias on x is smaller than $1/m$. The result is discussed in the light of the impossibility result for exact coin tossing.

arXiv:quant-ph/9904078•Apr 22, 1999•28 citations

From non-abelian anyons to quantum computation to coin-flipping by telephone

Carlos Mochon

Following their divorce, Alice and Bob would like to split some of their possessions by flipping a coin. Unwilling to meet in person, and without a trusted third party, they must figure out a scheme to flip the coin over a telephone that guarantees that neither party can cheat. The preceding scenario is the traditional definition of two-party coin-flipping. In a classical setting, without limits on the available computational power, one player can always guarantee a coin-flipping victory by cheating. However, by employing quantum communication it is possible to guarantee, with only information-theoretic assumptions, that neither party can win by cheating, with a probability greater than two thirds. Along with the description of such a protocol, this thesis derives a tight lower bound on the bias for a large family of quantum weak coin-flipping protocols, proving such a protocol optimal within the family. The protocol described herein is an improvement and generalization of one examined by Spekkens and Rudolph. The key steps of the analysis involve Kitaev's description of quantum coin-flipping as a semidefinite program whose dual problem provides a certificate that upper bounds the amount of cheating for each party. In order for such quantum protocols to be viable, though, a number of practical obstacles involving the communication and processing of quantum information must be resolved. In the second half of this thesis, a scheme for processing quantum information is presented, which uses non-abelian anyons that are the magnetic and electric excitations of a discrete-group quantum gauge theory. In particular, the connections between group structure and computational power are examined, generalizing previous work by Kitaev, Ogburn and Preskill. Anyon based computation has the advantage of being topological, which exponentially suppresses the rate of decoherence and the errors associated with the elementary quantum gates. Though no physical systems with such excitations are currently known to exist, it remains an exciting open possibility that such particles could be either engineered or discovered in exotic two-dimensional systems.

•Jan 1, 2005•0 citations
Alice and Bob want to flip a coin by telephone. (They have just divorced, live in different cities, want to decide who gets the car.) Bob would not like to tell Alice HEADS and hear Alice (at the other end of the line) say "Here goes . . . I'm flipping the coin. . . . You lost!"Coin-flipping in the SPECIAL way done here has a serious purpose. Indeed, it should prove an INDISPENSABLE TOOL of the protocol designer. Whenever a protocol requires one of two adversaries, say Alice, to pick a sequence of bits at random, and whenever it serves Alice's interests best NOT to pick her sequence of bits at random, then coin-flipping (Bob flipping coins to Alice) as defined here achieves the desired goal:1. It GUARANTEES to Bob that Alice will pick her sequence of bits at random. Her bit is 1 if Bob flips heads to her, O otherwise.2. It GUARANTEES to Alice that Bob will not know WHAT sequence of bits he flipped to her.Coin-flipping has already proved useful in solving a number of problems once thought impossible: mental poker, certified mail, and exchange of secrets. It will certainly prove a useful tool in solving other problems as well.
Coin flipping by telephone protocol(CFP) is utilized in a system to exchange a binary sequence at random between two person apart far from each other. However, CFP cannot be used in a system with many users like in a group environment system. A transmutation of CFP named T-CFP is proposed in this paper. The precondition of T-CFP is the system's user trusts the system center and center's cheating is meaningless at the same time. The significant difference between CFP and T-CFP is that CFP supports only two users while T-CFP can support many users to exchange special information. The security and efficiency of T-CFP are discussed with a detailed example on T-CFP utilization is demonstrated in this paper.
Weak coin flipping is the cryptographic task where Alice and Bob remotely flip a coin but want opposite outcomes. This work studies this task in the device-independent regime where Alice and Bob neither trust each other, nor their quantum devices. The best protocol was devised over a decade ago by Silman, Chailloux, Aharon, Kerenidis, Pironio, and Massar with bias ε≈0.33664\varepsilon \approx 0.33664ε≈0.33664, where the bias is a commonly adopted security measure for coin flipping protocols. This work presents two techniques to lower the bias of such protocols, namely self-testing and abort-phobic compositions. We apply these techniques to the SCAKPM '11 protocol above and, assuming a continuity conjecture, lower the bias to ε≈0.29104\varepsilon \approx 0.29104ε≈0.29104. We believe that these techniques could be useful in the design of device-independent protocols for a variety of other tasks. Independently of weak coin flipping, en route to our results, we show how one can test n−1n-1n−1 out of nnn devices, and estimate the performance of the remaining device, for later use in the protocol. The proof uses linear programming and, due to its generality, may find applications elsewhere.
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.
In coin tossing two remote participants want to share a uniformly distributed random bit. At the least in the quantum version, each participant test whether or not the other has attempted to create a bias on this bit. It is requested that, for b = 0,1, the probability that Alice gets bit b and pass the test is smaller than 1/2 whatever she does, and similarly for Bob. If the bound 1/2 holds perfectly against any of the two participants, the task realised is called an exact coin tossing. If the bound is actually 1/2+ξ1/2 + \xi1/2+ξ where the bias ξ\xiξ vanishes when a security parameter m defined by the protocol increases, the task realised is a (non exact) coin tossing. It is found here that exact coin tossing is impossible. At the same time, an unconditionally secure quantum protocol that realises a (non exact) coin tossing is proposed. The protocol executes m biased quantum coin tossing procedures at the same time. It executes the first round in each of these m procedures sequentially, then the second rounds are executed, and so on until the end of the n procedures. Each procedure requires 4n particles where n∈O(lg⁡m)n \in O(\lg m)n∈O(lgm). The final bit x is the parity of the m random bits. The information about each of these m bits is announced a little bit at a time which implies that the principle used against bit commitment does not apply. The bias on x is smaller than 1/m1/m1/m. The result is discussed in the light of the impossibility result for exact coin tossing.
In coin tossing two remote participants want to share a uniformly distributed random bit. At the least in the quantum version, each participant test whether or not the other has attempted to create a bias on this bit. It is requested that, for b = 0,1, the probability that Alice gets bit b and pass the test is smaller than 1/2 whatever she does, and similarly for Bob. If the bound 1/2 holds perfectly against any of the two participants, the task realised is called an exact coin tossing. If the bound is actually 1/2+ξ1/2 + ξ1/2+ξ where the bias ξξξ vanishes when a security parameter m defined by the protocol increases, the task realised is a (non exact) coin tossing. It is found here that exact coin tossing is impossible. At the same time, an unconditionally secure quantum protocol that realises a (non exact) coin tossing is proposed. The protocol executes m biased quantum coin tossing procedures at the same time. It executes the first round in each of these m procedures sequentially, then the second rounds are executed, and so on until the end of the n procedures. Each procedure requires 4n particles where n∈O(lg⁡m)n \in O(\lg m)n∈O(lgm). The final bit x is the parity of the m random bits. The information about each of these m bits is announced a little bit at a time which implies that the principle used against bit commitment does not apply. The bias on x is smaller than 1/m1/m1/m. The result is discussed in the light of the impossibility result for exact coin tossing.
Following their divorce, Alice and Bob would like to split some of their possessions by flipping a coin. Unwilling to meet in person, and without a trusted third party, they must figure out a scheme to flip the coin over a telephone that guarantees that neither party can cheat. The preceding scenario is the traditional definition of two-party coin-flipping. In a classical setting, without limits on the available computational power, one player can always guarantee a coin-flipping victory by cheating. However, by employing quantum communication it is possible to guarantee, with only information-theoretic assumptions, that neither party can win by cheating, with a probability greater than two thirds. Along with the description of such a protocol, this thesis derives a tight lower bound on the bias for a large family of quantum weak coin-flipping protocols, proving such a protocol optimal within the family. The protocol described herein is an improvement and generalization of one examined by Spekkens and Rudolph. The key steps of the analysis involve Kitaev's description of quantum coin-flipping as a semidefinite program whose dual problem provides a certificate that upper bounds the amount of cheating for each party. In order for such quantum protocols to be viable, though, a number of practical obstacles involving the communication and processing of quantum information must be resolved. In the second half of this thesis, a scheme for processing quantum information is presented, which uses non-abelian anyons that are the magnetic and electric excitations of a discrete-group quantum gauge theory. In particular, the connections between group structure and computational power are examined, generalizing previous work by Kitaev, Ogburn and Preskill. Anyon based computation has the advantage of being topological, which exponentially suppresses the rate of decoherence and the errors associated with the elementary quantum gates. Though no physical systems with such excitations are currently known to exist, it remains an exciting open possibility that such particles could be either engineered or discovered in exotic two-dimensional systems.