Quantum Weak Coin Flipping

Quantum Weak Coin Flipping (QWCF) is a cryptographic primitive that allows two remote and distrustful parties, Alice and Bob, to generate a random bit, such that each party has a known and opposite preferred outcome. In other words, the outcome of the flip will designate a winner and a loser. The parties can only communicate through classical and quantum channels, and they do not trust each other or any third party.

Tags: Two Party Protocols, Quantum Enhanced Classical Functionality, Specific Task

Assumptions

The parties:

1. have access to a quantum channel that can transmit single qubits and a classical channel that can transmit bits.
2. can prepare and measure single qubits in any basis they choose.
3. can perform local quantum operations on their qubits, such as applying unitary transformations or performing entanglement swapping.
4. can abort the protocol at any time if they detect cheating or errors.

Outline

The QWCF protocol by Spekkens and Rudolph consists of the following steps:

1. Alice and Bob agree on two orthogonal single-qubit states, ψ(0) and ψ(1), that have equal probability distribution in the computational basis. They also agree on an angle θ between ψ(0) and ψ(1), which determines the bias of the protocol.
2. Alice and Bob each choose a secret bit, a and b, respectively, that represents their preferred outcome. They also choose a random bit, x and y, respectively, that will be used to encode their qubits.
3. Alice and Bob each send two qubits to the other party, one in the state ψ(x) and the other in the state ψ(x⊕a). They also send a classical bit, z and w, respectively, that is the XOR of their secret bit and their random bit, i.e., z=x⊕a and w=y⊕b.
4. Alice and Bob each return one of the qubits they received from the other party, depending on the value of the classical bit they received. If the classical bit is 0, they return the first qubit; if the classical bit is 1, they return the second qubit.
5. Alice and Bob each measure the qubit they kept from the other party in the basis spanned by ψ(0) and ψ(1). They also measure the qubit they returned to the other party in the same basis. If any of the measurements fails, they abort the protocol.
6. Alice and Bob each announce their secret bit, a and b, respectively. They also announce the result of their measurements, m and n, respectively. The outcome of the coin flip is the XOR of their secret bits and their measurements, i.e., c=a⊕m=b⊕n.

Notation

1. ψ(i) for i∈{0,1}: The predetermined single-qubit states that have equal probability distribution in the computational basis.
2. θ: The angle between ψ(0) and ψ(1), which determines the bias of the protocol.
3. a and b: The secret bits chosen by Alice and Bob, respectively, that represent their preferred outcome.
4. x and y: The random bits chosen by Alice and Bob, respectively, that are used to encode their qubits.
5. z and w: The classical bits sent by Alice and Bob, respectively, that are the XOR of their secret bit and their random bit, i.e., z=x⊕a and w=y⊕b.
6. m and n: The results of the measurements performed by Alice and Bob, respectively, on the qubits they kept from the other party.
7. c: The outcome of the coin flip, which is the XOR of the secret bits and the measurements, i.e., c=a⊕m=b⊕n.

Properties

• The protocol is fair if θ=π/4, i.e., the states ψ(0) and ψ(1) are the same as the computational basis states ∣0⟩ and ∣1⟩.
• The protocol is secure with bias ϵ=sin(θ/2), i.e., the maximum probability of a dishonest party winning the coin flip if the other party is honest is 1/2+sin(θ/2).
• The protocol is balanced for any value of θ, i.e., the bias of the protocol is the same for both parties.

Protocol Description

The QWCF protocol by Spekkens and Rudolph consists of the following steps:

1. Alice and Bob agree on two orthogonal single-qubit states, ψ(0) and ψ(1), that have equal probability distribution in the computational basis, and an angle θ between them, which determines the bias of the protocol. For simplicity, we assume that they choose ψ(0)=cos(θ/2)∣0⟩+sin(θ/2)∣1⟩ and ψ(1)=sin(θ/2)∣0⟩−cos(θ/2)∣1⟩, where θ∈[0,π/2].
2. Alice and Bob each choose a secret bit, a,b∈{0,1}, that represents their preferred outcome, and a random bit, x,y∈{0,1}, that is used to encode their qubits. They keep their bits secret from the other party.
3. Alice and Bob each send two qubits to the other party, one in the state ψ(x) and the other in the state ψ(x⊕a), and a classical bit, z=x⊕a and w=y⊕b, respectively.
4. Alice and Bob each return one of the qubits they received from the other party, depending on the value of the classical bit they received. If the classical bit is 0, they return the first qubit; if the classical bit is 1, they return the second qubit.
5. Alice and Bob each measure the qubit they kept from the other party in the basis {ψ(0),ψ(1)}, and the qubit they returned to the other party in the same basis. If any of the measurements fails, they abort the protocol. They obtain the results m,n∈{0,1} for the qubits they kept, and m′,n′∈{0,1} for the qubits they returned, respectively.
6. Alice and Bob each announce their secret bit, a and b, and their measurement result, m and n, respectively. The outcome of the coin flip is c=a⊕m=b⊕n.

Further Information

1. The QWCF protocol by Spekkens and Rudolph is optimal, i.e., it achieves the minimum possible bias for any QWCF protocol, which is ϵ=sin(θ/2).
2. This protocol is cheat-sensitive, i.e., if a dishonest party tries to cheat by deviating from the protocol, the honest party can detect it with some probability and abort the protocol.
3. This protocol is based on entanglement swapping, i.e., the parties exchange qubits that are entangled with their own qubits, and then perform a Bell measurement on their qubits to obtain a shared random bit.
4. The mentioned protocol is similar to the Quantum Strong Coin Flipping (QSCF) protocol by Ambainis, but with a different choice of states and measurements. The QSCF protocol by Ambainis uses the states ∣+⟩=(∣0⟩+∣1⟩)/2 and ∣−⟩=(∣0⟩−∣1⟩)/2, and the measurements {∣0⟩,∣1⟩} and {∣+⟩,∣−⟩}. The QSCF protocol by Ambainis achieves a bias of ϵ=1/2, which is optimal for QSCF, but not for QWCF.
5. This protocol can be generalized to a Quantum Weak Dice Rolling (QWDR) protocol, where the parties want to generate a random integer between 1 and N, such that each party has a known and opposite preferred outcome. The QWDR protocol can be implemented by using N orthogonal states and N measurements, and choosing the outcome as the index of the state that matches the measurement.

• Quantum Protocol for Cheat-Sensitive Weak Coin Flipping, R.W. Spekkens, T. Rudolph, Physical Review Letters 89, 2002
• A New Protocol and Lower Bounds for Quantum Coin Flipping, A. Ambainis, Journal of Computer and System Sciences, 2004
• Quantum weak coin flipping with arbitrarily small bias, C. Mochon, 2007

*contributed by Mohammadreza Vali