Quantum Strong Coin Flipping

Quantum Coin Tossing allows two remote participants to share a uniformly distributed random bit. The parties do not trust each other and can only use classical and quantum channels to communicate. The protocol allows them to perform what coin tossing for nearby parties performs without the involvement of any trusted third party.

Outline

We consider two parties who wish to perform a coin tossing experiment remotely. Two single qubit quantum states are initially decided which have equal probability distribution in the computational basis and label them 0 and 1. The Coin Tossing protocol consists of 5 steps:

1. Both the parties prepare an equal number of random bits.
2. Now, both parties prepare another equal number of random bits for each random bit prepared in step 1. For each random bit thus prepared, each party sends the other party a pair of qubits in the two states defined earlier, the sequence of which is decided by the random bit.
3. Both the parties now announce the xor of each random bit prepared in the second step with the corresponding random bit from the first step. Based on the value of the xor operation performed by the other party, each party returns one of the two qubits it received in the second step. For every random bit prepared in the first step, each party is now left with qubits in the state labeled by the other party's random bit.
4. Both the parties now announce their random bits which they prepared in the first step. They also measure the qubits they did not return based on the values of the random bits announced by the other party. If any of the measurement fails, the protocol aborts.
5. For every random bit prepared in the first step, each party now also measures the qubits they were returned back. If any of the measurement fails, the protocol aborts.

The final bit of each of the party is the xor of xor of the random bits they prepared in the first step and xor of the bits they measured in the fourth step. This final bit is the random bit which has come up in the 'coin toss'. Thus ends the protocol.

Notation

1. $\psi (i)\ \forall \ i\in \{0,1\}$: Predetermined single qubit states
2. $\theta$: Angle between $\psi (0)$ and $\psi (1)$
3. $a_{j}$: A random bit prepared by the first party in step 1
4. $b_{j}$: A random bit prepared by the second party in step 1
5. $\{a_{1},...,a_{m}\}$: Set of random bits prepared by first party in step 1
6. $\{b_{1},...,b_{m}\}$: Set of random bits prepared by second party in step 1
7. $c_{ij}$: A random bit prepared by the first party in step 2
8. $d_{ij}$: A random bit prepared by the second party in step 2
9. $\{c_{11},...,c_{nm}\}$: Set of random bits prepared by first party in step 2
10. $\{d_{11},...,d_{nm}\}$: Set of random bits prepared by second party in step 2
11. $\Phi (i)$: Set of $n$ qubits, each in $\psi (i)$ state
12. $(E_{i},E_{i}^{\perp })$: POVMs defined by $E_{i}=|\Phi (i)\rangle \langle \Phi (i)|$ and $E_{i}^{\perp }=1-E_{i}$.

Hardware Requirements

• Authenticated Quantum channel capable of sending a pair of qubits
• Authenticated Classical channel to send multiple bits
• Quantum memory for both parties to store qubits
• Measurement Devices for each party
• Random bit generator for each party

Properties

• The protocol is successfully completed when both parties are honest.
• If any of the parties is dishonest at any step, the protocol simply aborts.
• The attack on the protocol can generate a bias which is greater than $O(1/{m^{3}})$ and less than $1/m$.

Pseudocode

Two single qubit quantum states $\psi (0)=c|0\rangle +s|1\rangle$ and $\psi (1)=c|0\rangle -s|1\rangle$, where $c,s\in \mathbb {R}$ are defined such that the angle between them is $\theta$. $\theta$ is proposed to be $\pi /9$. Thus, $\Phi (0)=\otimes _{k=1}^{n}\psi (0)$ and $\Phi (1)=\otimes _{k=1}^{n}\psi (1)$.

1. For $j=1,2,...,m$:
   1. First party picks at random a bit $a_{j}$.
   2. Second party picks at random a bit $b_{j}$.
2. For $i=1,2,...n,$:
   1. For $j=1,2,...,m$:
      1. The first party picks a random bit $c_{ij}$ and sends a pair of qubits in the state $\psi (c_{ij})\otimes \psi ({\bar {c}}_{ij})$ to the second party.
      2. The second party picks a random bit $d_{ij}$ and sends a pair of qubits in the state $\psi (d_{ij})\otimes \psi ({\bar {d}}_{ij})$ to the first party.
3. For $i=1,2,...n,$:
   1. For $j=1,2,...,m$:
      1. The first party announces $e_{ij}=a_{j}\oplus c_{ij}$.
      2. The second party returns the second particle if $e_{ij}=0$ and first particle otherwise.
      3. The second party announces $f_{ij}=b_{j}\oplus d_{ij}$.
      4. The first party returns the second particle if $f_{ij}=0$ and first particle otherwise.
         At this stage, for every $j$, the $n$ qubits sent by the first party and not returned by the second party are in the state $\Phi (a_{j})$ and the $n$ qubits sent by the second party and not returned by the first party are in the state $\Phi (b_{j})$.
         Also, for every j, the n qubits returned by the first party are in the state $\Phi ({\bar {b}}_{j})$ and the n qubits returned by the second party are in the state $\Phi ({\bar {a}}_{j})$.
4. For $j=1,2,...,m$:
   1. First party announces $a_{j}$.
   2. Second party announces $b_{j}$.
   3. Second party executes POVM $(E_{a_{j}},E_{a_{j}}^{\perp })$ on $\Phi (a_{j})$ and notes the outcome ${\tilde {a}}$.
   4. First party executes POVM $(E_{b_{j}},E_{b_{j}}^{\perp })$ on $\Phi (b_{j})$ and notes the outcome ${\tilde {b}}$.
      If either ${\tilde {a}}=\perp$ or ${\tilde {b}}=\perp$, the protocol aborts.
5. For $j=1,2,...,m$:
   1. First party measures the returned state $\Phi ({\bar {a}}_{j})$ with POVM $(E_{{\bar {a}}_{j}},E_{{\bar {a}}_{j}}^{\perp })$.
   2. Second party measures the returned state $\Phi ({\bar {b}}_{j})$ with POVM $(E_{{\bar {b}}_{j}},E_{{\bar {b}}_{j}}^{\perp })$.

If either of the outcomes is $\perp$, the protocol aborts.

The final bit of the first party is $A\oplus {\tilde {B}}$ where $A=\oplus _{j}a_{j}$ and ${\tilde {B}}=\oplus _{j}{\tilde {b}}_{j}$. The second party’s final bit is ${\tilde {A}}\oplus B$ where ${\tilde {A}}=\oplus _{j}{\tilde {a}}_{j}$ and $B=\oplus _{j}b_{j}$.

Further Information

*contributed by Natansh Mathur