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.

Notations

1. $\psi (i)\ \forall \ i\in \{0,1\}$: Predetermined single qubit states
2. $\theta$: Angle between $\psi (0)$ and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \psi(1)}
3. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_j} : A random bit prepared by the first party in step 1
4. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_j} : A random bit prepared by the second party in step 1
5. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{a_1,...,a_m\}} : Set of random bits prepared by first party in step 1
6. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{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. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{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. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi(i)} : Set of $n$ qubits, each in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \psi(i)} state
12. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/m} .

Pseudo Code

Two single qubit quantum states Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \psi(0) = c|0\rangle + s|1\rangle} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi(0)=\otimes^n_{k=1}\psi(0)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi(1)=\otimes^n_{k=1}\psi(1)} .

1. For $j=1,2,...,m$:
   1. First party picks at random a bit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_j} .
   2. Second party picks at random a bit $b_{j}$.
2. For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_{ij}} and sends a pair of qubits in the state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \psi(d_{ij})\otimes\psi(\bar{d}_{ij})} to the first party.
3. For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i = 1,2,...n,} :
   1. For $j=1,2,...,m$:
      1. The first party announces Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_{ij} = a_j \oplus c_{ij}} .
      2. The second party returns the second particle if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_{ij}=0} and first particle otherwise.
      3. The second party announces Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} , the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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}$.