I often explain quantum coin flipping to people using a simple scenario: two people who do not trust each other, maybe on opposite sides of the planet, want to flip a fair coin over a phone line and both agree on the result. Neither wants the other to be able to force the outcome. Quantum Coin Flipping (QCF) uses quantum states to try to guarantee fairness in this remote coin toss, without needing a trusted third party. I find this topic naturally connected to quantum bit commitment, since most coin-flipping protocols are literally built on top of a commitment step, and I present it right after QBC for that reason.
History and Background
I trace quantum coin flipping back to Manuel Blum’s original classical protocol from 1981, which relied on computational assumptions. The quantum version was first proposed alongside early quantum cryptography work by Bennett and Brassard in 1984, in the same paper that introduced BB84 key distribution. For a while, researchers hoped quantum coin flipping might achieve perfect (zero-bias) fairness, similar to the initial optimism around bit commitment. That hope was tempered by Aharonov, Ta-Shma, Vazirani, and Yao, who in 2000 proved a fundamental lower bound: no quantum coin flipping protocol can achieve a cheating probability below approximately 0.739 (the Kitaev bound, later tightened by Kitaev himself using semidefinite programming arguments). Chailloux and Kerenidis in 2009 constructed protocols that essentially meet this bound, closing the gap between the theoretical limit and practical constructions.
Problem Statement
I want two mutually distrustful parties, Alice and Bob, to jointly generate a single random bit $c \in {0,1}$ such that: if both are honest, $c$ is uniformly random; and even if one party actively cheats, they cannot force $c$ to be their preferred outcome with certainty. Classical coin flipping without computational assumptions is provably impossible over a simple communication channel, since one side always sends information last and could bias the result. I want to see whether quantum mechanics can reduce (even if it cannot eliminate) this bias.
Core Concepts
- Weak coin flipping — the parties have known opposing preferred outcomes, and cheating means forcing that specific preferred result.
- Strong coin flipping — neither party has a publicly known preference, and cheating means forcing any specific outcome.
- Cheating probability — the maximum probability, over all possible cheating strategies, that a dishonest party can force their desired result.
- Kitaev bound — the proven lower limit of $\frac{1}{\sqrt2} \approx 0.7071$ for a cheating party’s success probability advantage over honest play in one variant of strong coin flipping (some analyses use different but related bounds around 0.75).
- Commitment sub-protocol — quantum coin flipping protocols typically use a quantum-bit-commitment-like step before revealing values.
How It Works
I outline a standard quantum strong coin-flipping protocol, based on the commit-and-reveal structure:
- Alice picks a random bit $a \in {0,1}$ and prepares a quantum state that commits to $a$, sending it to Bob (similar in spirit to a QBC commit phase).
- Bob, without knowing $a$, picks his own random bit $b \in {0,1}$ and sends it to Alice in the clear.
- Alice reveals $a$ along with whatever information Bob needs to verify her commitment (opening her quantum state).
- Bob verifies that Alice’s revealed value matches what she originally sent (using measurement outcomes analogous to the QBC reveal phase).
- If verification succeeds, both parties compute the final coin as $c = a \oplus b$.
- If verification fails, Bob (or Alice) declares “abort,” meaning at least one party detected cheating, and the protocol halts without producing a trusted result.
Working Principle
I understand the logic here as trying to make sure that neither party controls the final XOR outcome alone. Bob commits to $b$ only after Alice has already committed to $a$ — this stops Bob from choosing $b$ based on $a$. Meanwhile, Alice cannot change her value of $a$ after seeing $b$, because her earlier commitment (if done correctly using strong quantum hiding/binding techniques) constrains her. If both commitments were perfectly binding, the XOR $c = a \oplus b$ would be perfectly fair — but because unconditional quantum bit commitment is impossible (as shown by Mayers, Lo, and Chau), the coin-flipping protocol inherits some residual bias, which is exactly what the Kitaev-type lower bounds quantify.
Mathematical Foundation
I define Alice’s or Bob’s cheating probability as the maximum probability, using an optimal cheating strategy, that they can force the coin toward their preferred value:
$$ P_A^* = \max_{\text{Alice’s strategy}} P(c = 0) $$
$$ P_B^* = \max_{\text{Bob’s strategy}} P(c = 1) $$
The Kitaev-type bound for a broad class of quantum strong coin-flipping protocols states:
$$ P_A^* \cdot P_B^* \geq \frac{1}{2} $$
which implies at least one party can cheat with probability:
$$ \max(P_A^, P_B^) \geq \frac{1}{\sqrt2} \approx 0.7071 $$
For the honest case, where both parties follow the protocol faithfully, I expect:
$$ P(c=0) = P(c=1) = \frac{1}{2} $$
since $c = a \oplus b$ is the XOR of two independently uniform random bits.
Diagrams
sequenceDiagram
participant A as Alice
participant B as Bob
A->>A: Choose random bit a
A->>B: Send commitment to a (quantum state)
B->>B: Choose random bit b
B->>A: Send b in the clear
A->>B: Reveal a and opening information
B->>B: Verify commitment consistency
Note over A,B: If valid, compute c = a XOR bPseudocode
Protocol QuantumCoinFlip():
Alice:
a = random(0,1)
commitment = QuantumCommit(a) // uses QBC-style state
send commitment to Bob
Bob:
receive commitment
b = random(0,1)
send b to Alice
Alice:
send (a, openingInfo) to Bob // reveal phase
Bob:
valid = VerifyCommitment(commitment, a, openingInfo)
if valid:
c = a XOR b
output c
else:
output ABORT
Step-by-Step Example
Suppose I let Alice pick $a=1$ and commit to it using a quantum state sent to Bob. Bob, unable to learn $a$ from the commitment, picks $b=0$ and sends it back. Alice reveals $a=1$ along with the opening information for her commitment. Bob checks the revealed value against his earlier recorded quantum measurements from the commit phase; if consistent, he accepts and both parties compute $c = 1 \oplus 0 = 1$. If Alice had instead tried to cheat by committing to a state that could later be opened as either $0$ or $1$ using entangled ancilla qubits (per the MLC-style attack), she could try to bias the outcome after seeing $b=0$ — wanting $c=1$, she reveals $a=1$; wanting $c=0$, she would need to reveal $a=0$, requiring the commitment to convincingly “become” $0$ after the fact. The Kitaev bound tells me she can succeed at this kind of bias with probability up to roughly 0.707 in the worst realistic protocol design, not certainty, and well-designed protocols push her cheating probability as close to this bound as possible rather than higher.
Time Complexity
I count the protocol as three main rounds of communication — commit, reveal-b, reveal-a-and-verify — each involving $O(n)$ quantum or classical operations if the underlying commitment uses $n$ qubits. This gives:
$$ T(n) = O(n) $$
Space Complexity
Both parties need to store their chosen bits, the commitment data (up to $n$ qubits worth of classical description or quantum state), and verification data, giving:
$$ S(n) = O(n) $$
Correctness Analysis
I consider the protocol correct in the honest case because $c = a \oplus b$ is guaranteed to be uniformly distributed whenever at least one of $a$ or $b$ is chosen uniformly at random and independently of the other — which holds here since Bob picks $b$ without knowing $a$, and Alice cannot alter $a$ after seeing $b$ if her commitment is binding. The subtlety, formalized by Aharonov, Ta-Shma, Vazirani, Yao, and later Kitaev, is that quantum commitments cannot be perfectly binding, so a fully “correct,” bias-free protocol is provably unattainable; correctness here really means the protocol achieves fairness up to the proven optimal bound, not perfect fairness.
Advantages
- Provides remote, trustless fairness guarantees stronger than naive classical protocols without computational assumptions.
- Well-understood theoretical bounds (Kitaev, Chailloux-Kerenidis) mean the security level is provably quantified, not just conjectured.
- Serves as a foundational primitive for more advanced quantum multiparty protocols and quantum-secure gambling/lottery systems.
- Near-optimal protocols exist that match the theoretical lower bound closely.
Disadvantages
- Cannot achieve perfectly unbiased coin flips — some cheating advantage is unavoidable, unlike some classical solutions using trusted third parties.
- Requires practical quantum hardware for real implementation, inheriting all the noise and cost issues of QBC and QOT.
- Complex to analyze rigorously; cheating-probability proofs often require semidefinite programming and advanced quantum information theory.
- Susceptible to the same entanglement-based attacks that break unconditional quantum bit commitment.
Applications
- Remote fair-random-number generation for distributed systems and blockchains exploring quantum-secure randomness beacons.
- Secure multiparty games and online gambling systems seeking provable fairness.
- Cryptographic protocol design as a building block for leader election and consensus mechanisms.
- Academic research into optimal cheating bounds and semidefinite programming techniques in quantum information theory.
Implementation in C
I implement a classical simulation modeling the commit-reveal-verify structure and the final XOR computation, again standing in for the underlying quantum commitment.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int random_bit() { return rand() % 2; }
/* Simulated commitment: in a real system this is a quantum state;
here I use a simple hash-like scramble to emulate hiding + binding. */
int simulate_commit(int bit, int nonce) {
return (bit ^ (nonce * 2654435761u)) & 0xFFFF;
}
int simulate_verify(int commitment, int bit, int nonce) {
return simulate_commit(bit, nonce) == commitment;
}
int main() {
srand((unsigned)time(NULL));
/* Alice's side */
int a = random_bit();
int nonce = rand();
int commitment = simulate_commit(a, nonce);
printf("Alice commits to a (hidden). Commitment value: %d\n", commitment);
/* Bob's side */
int b = random_bit();
printf("Bob sends b = %d\n", b);
/* Alice reveals */
printf("Alice reveals a = %d with nonce = %d\n", a, nonce);
/* Bob verifies */
int valid = simulate_verify(commitment, a, nonce);
if (valid) {
int c = a ^ b;
printf("Commitment verified. Final coin c = a XOR b = %d\n", c);
} else {
printf("Commitment invalid. Protocol ABORTED.\n");
}
return 0;
}
Sample Input and Output
A typical run might output:
Alice commits to a (hidden). Commitment value: 41823
Bob sends b = 1
Alice reveals a = 0 with nonce = 837291
Commitment verified. Final coin c = a XOR b = 1
Optimization Techniques
- Using near-optimal protocols such as the Chailloux–Kerenidis construction pushes cheating probability as close as possible to the proven Kitaev-type lower bound.
- Repeating the protocol multiple times and taking a majority or additional XOR can slightly reduce practical bias from imperfect implementations, though it does not beat the fundamental theoretical bound.
- Combining weak coin flipping (where cheating incentives are asymmetric and known) can sometimes achieve better bounds than strong coin flipping for specific applications.
- Careful choice of the commitment sub-protocol (e.g., relativistic or noisy-storage based) can improve practical, though not unconditional, security.
Common Mistakes
- Expecting perfectly unbiased results — the Kitaev-type bound guarantees this is impossible for standalone quantum protocols.
- Conflating weak and strong coin flipping, which have different threat models and different optimal cheating bounds.
- Implementing the commitment step insecurely, which can push the real-world cheating probability well above the theoretical bound.
- Failing to handle the “abort” case properly, letting a party who detects cheating be forced to still produce an unverified result.
Further Reading
- Aharonov, D., Ta-Shma, A., Vazirani, U., Yao, A., “Quantum Bit Escrow,” STOC 2000. https://dl.acm.org/doi/10.1145/335305.335404
- Kitaev, A., unpublished lower bound proof, referenced widely; formal treatment in Ambainis, A. et al., “Quantum Coin Flipping,” 2004 survey. https://arxiv.org/abs/quant-ph/0304076
- Chailloux, A., Kerenidis, I., “Optimal Quantum Strong Coin Flipping,” FOCS 2009. https://arxiv.org/abs/0904.1511
- Blum, M., “Coin Flipping by Telephone,” CRYPTO 1981. https://www.cs.cmu.edu/~mblum/research/pdf/coin/
- Bennett, C. H., Brassard, G., “Quantum Cryptography: Public Key Distribution and Coin Tossing,” 1984. https://arxiv.org/abs/2003.06557
