Quantum coin flipping is a cryptographic protocol that allows two distrustful parties, Alice and Bob, to agree on the outcome of a random bit (representing the flip of a coin) over a distance. The idea, first introduced by Manuel Blum in 1981, addresses the setup where one party, say Alice, flips a coin and asks the other, Bob, to guess the outcome over the phone. In the classical setting, because Bob cannot see the actual flip, Alice could easily cheat. Quantum coin flipping discovers how the principles of quantum mechanics can be used to create a fair coin toss even when the parties do not trust each other.
Classical vs. Quantum Coin Flipping
In a classical coin toss, the outcome is either heads or tails. Even if the coin is covered after being tossed, it is definitively in one of those two states. A classical coin flip can be replicated on a classical computer by using a ‘coin-flipping gate’ outputs a random binary value.
Quantum coin flipping introduces the concept of a “quantum coin“ which, can exist in a superposition of states between heads and tails. This is similar to a qubit in a superposition of |0⟩ and |1⟩. Only upon measurement does the quantum coin “collapse” to a definite state (heads or tails). If the result of the measurement is not observed, the quantum state collapses into a classical coin. The Hadamard gate (H) applied to a qubit in the |0⟩ state can be seen as applying a quantum coin toss, resulting in the state |+⟩ = {|0⟩+ |1⟩}/√2, which upon measurement in the {|0⟩, |1⟩} basis yields 0 or 1 with equal probability.
The Impossibility of Quantum Coin Tossing
Early suggestions for quantum coin flipping existed, restricting from the work of Bennett and Brassard. However, it was later proven by Lo and Chau in 1998 that ideal secure quantum coin tossing is impossible. This impossibility result extends not only to the security of existing schemes to all possible quantum coin-flipping protocols. These schemes are not strong against EPR attacks, where parties might use entangled particles to gain an unfair advantage. This impossibility result is closely related to quantum bit commitment.
Types of Quantum Coin Tossing
Given the impossibility of quantum coin tossing, research has focused on non-ideal situations, categorizing quantum coin tossing into three types:
- Ideal coin tossing: In this ideal situation, neither party can bias the outcome with any probability of success. As mentioned, this is probably impossible in the quantum realm.
- Weak coin tossing with bias ε: In this type, Alice cannot bias the outcome in her favor by more than a probability ε, and similarly, Bob cannot bias the outcome in his favor by more than ε. A protocol is balanced if, when both parties are honest, the probability of Alice winning equals the probability of Bob winning, both being 1/2.
- Strong coin tossing with bias ε: Here, neither Alice nor Bob can bias the outcome in any direction by more than a probability ε. Mathematically
- If Alice and Bob are honest, then P(Alice wins) = P(Bob wins) = 1/2 ;
- If Alice cheats and Bob is honest, then max(P(Alice wins), wins),P(Bob wins)) ≤ 1/2 + ε;
- If Bob cheats and Alice is honest, then max(P(Alice wins), P(Bob wins)) ≤ 1/2 + ε;
Possibility of Weak and Strong Quantum Coin Tossing
Despite the impossibility of ideal quantum coin tossing, weak and strong quantum coin tossing are possible. Weak quantum coin tossing can be performed with a small bias ε. However, achieving a small bias in weak quantum coin tossing is not very efficient, requiring at least an exponential number of communication rounds in terms of (Ω(1√ε)).Strong quantum coin tossing also has limitations. While it is possible, there is a bias associated with it, approximately √2/2 – ½. Nevertheless, the bias can be made arbitrarily close to this value.
Quantum Coin-Flipping Protocols
One of the quantum bit commitment protocols was actually a quantum coin-flipping protocol. Quantum bit commitment protocols (QBCP) involve a commitment phase where Alice commits to a bit and an opening phase where she reveals it. The coin-flipping protocol involves Alice sending a sequence of photons with randomly chosen bits and polarizations (rectilinear or diagonal) to Bob. Bob then randomly chooses a measurement basis (rectilinear or diagonal) for each photon and records the results. After all transmissions, Bob guesses the polarization Alice used and announces his guess. Alice then reveals her chosen polarization and the original bit sequence to verify her claim. Bob can check if his measurements in the claimed basis agree with the received bits.
The security of protocols against cheating by either Alice or Bob has been a subject of study. If Bob cannot learn Alice’s commitment (in the bit commitment context, which is closely related to coin flipping) with high probability, then Alice can potentially change her commitment during the opening phase if she has a quantum computer.
Relation to Quantum Bit Commitment
The relationship between quantum coin flipping and quantum bit commitment is early bit commitment protocols were derived from coin-flipping schemes. Both primitives deal with situations where two doubting parties need to perform a task (agree on a random bit or commit to a secret bit) securely over a distance. The impossibility results for ideal versions of both primitives stem from similar original principles related to the limits compulsory by quantum mechanics on information gain and disturbance.
Finally, quantum coin flipping is an area of quantum cryptography that discovers the possibility of achieving equality in a coin toss between doubting parties using quantum mechanical principles. The initial hope for perfectly secure (ideal) quantum coin tossing has been in trouble by impossibility proofs; the field has progressed to study non-ideal situations such as weak and strong quantum coin tossing, which are certainly possible but come with essential limitations on the achievable bias and efficiency. The study of quantum coin flipping is tangled with other quantum cryptographic primitives, particularly quantum bit commitment, and contributes to our understanding of the potential and limitations of quantum information processing for secure communication and agreement.