Verifiable Quantum Anonymous Transmission

This [example protocol] implements the task of anonymous transmission in a multi-node quantum network. The protocol uses an untrusted $n$-partite GHZ state to enable two nodes, Sender and Receiver, to establish a link which they use to transmit a quantum message. In addition to adversarial nodes, the source of the GHZ state may be controlled by an adversary. To address this, the protocol includes verification of the GHZ state. It incorporates a reduced fidelity GHZ state used for anonymous transmission, resulting in a notion of anonymity for imperfect scenarios called $\epsilon$-anonymity.

Assumptions

Network: The network consists of $n$ nodes (honest or adversarial) with pairwise authenticated classical channels and a classical broadcast channel.
Source: Untrusted multipartite state source.
Adversarial model: Active adversary who can control the source.

Outline

This verified GHZ-based quantum anonymous transmission protocol is based on the work of \cite{Unnikrishnan}, which uses the following subroutines from \cite{Wehner}, \cite{Broadbent}, \cite{Pappa}, \cite{McCutcheon}:

Template:Smallcaps \cite{Broadbent}: privately computes the parity of an input string.
Template:Smallcaps \cite{Broadbent}: privately computes the logical OR of an input string, using a modified version of Template:Smallcaps.
Template:Smallcaps \cite{Broadbent}: allows one player to anonymously notify another player, using Template:Smallcaps.
Template:Smallcaps \cite{Unnikrishnan}: allows one player to anonymously choose a bit according to a probability distribution, using Template:Smallcaps.
Template:Smallcaps \cite{Pappa, McCutcheon}: allows one player (the Verifier) to run a test to check if the shared state is the GHZ state. The Verifier instructs each player to measure their qubit in a particular basis and checks the parity of the measurement outcomes.
Template:Smallcaps \cite{Wehner}: $n-2$ nodes (all except for $\mathcal{S}$ and $\mathcal{R}$) measure in the $X$ basis and broadcast their measurement outcome. $\mathcal{S}$ and $\mathcal{R}$ broadcast random dummy bits. The parity of measurement outcomes allows the establishment of an entangled link between $\mathcal{S}$ and $\mathcal{R}$ which is called anonymous entanglement.

The protocol for quantum anonymous transmission consists of the following steps:

\textit{Receiver notification}: The Sender $\mathcal{S}$ notifies the Receiver $R$ by running Template:Smallcaps.
\textit{State distribution}: A source, who may be untrusted, distributes a state claiming to be the GHZ state.
\textit{Verification or anonymous transmission}: $\mathcal{S}$ anonymously chooses whether to verify the state or use it for anonymous transmission, using Template:Smallcaps (\ket{0^n} + \ket{1^n})$: GHZ state.

$\ket{\Psi}$: state provided by the untrusted source for anonymous transmission (in the ideal case, this is the GHZ state).
$\mathcal{S}$: the Sender of the quantum message.
$\mathcal{R}$: the Receiver of the quantum message.
$q$: the security parameter.

Properties

%The pseudocode given below implements anonymous transmission of a quantum message, incorporating a verification stage. Further, the following analysis considers anonymous transmission with a reduced fidelity state rather than a perfect GHZ state.

Let $C_\epsilon$ be the event that the protocol does not abort and the state used for anonymous transmission is such that, no matter what operation the adversarial players do to their part, the fidelity of the state with the GHZ state is at most $\sqrt{1-\epsilon^2}$. Then, \begin{align*} P[C_\epsilon] \leq 2^{-q} \frac{4n}{1 - \sqrt{1-\epsilon^2}}. \end{align*} By doing many repetitions of the protocol, the honest players can ensure that this probability is negligible.

If the state used for anonymous transmission is of fidelity at least $\sqrt{1-\epsilon^2}$ with the GHZ state, \begin{align*} P_{\text{guess}} [\mathcal{S} | C, \mathcal{S} \notin \mathcal{A} ] \leq \frac{1}{n-t} + \epsilon, \\ P_{\text{guess}} [\mathcal{R} | C, \mathcal{S} \notin \mathcal{A} ] \leq \frac{1}{n-t} + \epsilon, \end{align*} where $\mathcal{A}$ is the subset of $t$ adversaries among $n$ nodes and $C$ is the register that contains all classical and quantum side information accessible to the adversaries.

Pseudocode

Template:Smallcaps

\noindent \textit{Input}: Security parameter $q$. \\ \textit{Goal}: $\mathcal{S}$ sends message qubit $\ket{\psi}$ to $\mathcal{R}$ with $\epsilon$-anonymity.

{\bf Receiver notification}: \\

Run Template:Smallcaps for $\mathcal{S}$ to notify $\mathcal{R}$ as the Receiver.

{\bf Distribution of state}: \\

A source (who may be untrusted) generates a state $\ket{\Psi}$ and distributes it to the players (in the ideal case, $\ket{\Psi}$ is the GHZ state).

{\bf $\mathcal{S}$ anonymously chooses verification or anonymous transmission}:
1. Run Template:Smallcaps, with the input of $\mathcal{S}$ chosen as follows: she flips $q$ fair classical coins, and if all coins are heads, she inputs 0, else she inputs 1. Let the outcome be $x$.
2. If $x=1$,
  1. Run Template:Smallcaps $\log_2 n$ times, with the input of $\mathcal{S}$ chosen according to the uniform random distribution. Let the outcome be $v$.
  2. Run Template:Smallcaps with player $v$ as the Verifier. If she accepts the outcome of the test, return to step 2, otherwise abort.

Else if $x=0$, run Template:Smallcaps.

If at any point in the protocol, $\mathcal{S}$ realises someone does not follow the protocol, she stops behaving like the Sender and behaves as any player.

Subroutines

Template:Smallcaps

\noindent \textit{Input}: $\{ x_i \}_{i=1}^n$. \\ \textit{Goal}: Each player gets $y_i = \bigoplus_{i=1}^n x_i$.

Every player $i$ chooses random bits $\{r_i^j \}_{j=1}^n$ such that $\bigoplus_{j=1}^n r_i^j = x_i$.
Every player $i$ sends their $j$th bit $r_i^j$ to player $j$ ($j$ can equal $i$).
Every player $j$ computes $z_j=\bigoplus_{i=1}^n r_i^j$ and reports the value in the simultaneous broadcast channel.
The value $z=\bigoplus_{j=1}^n z_j$ is computed, which equals $y_i$.

Template:Smallcaps

\noindent \textit{Input}: $\{ x_i \}_{i=1}^n$, security parameter $q$. \\ \textit{Goal}: Each player gets $y_i = \bigvee_{i=1}^n x_i$.

The players agree on $n$ orderings, with each ordering having a different last participant.
For each ordering:
1. Each player $i$ picks the value of $p_i$ as follows: if $x_i=0$, then $p_i=0$; if $x_i=1$, then $p_i=1$ with probability $\frac{1}{2}$ and $p_i=0$ with probability $\frac{1}{2}$.
2. Run Template:Smallcaps with input $\{p_i\}_{i=1}^n$, with a regular broadcast channel rather than simultaneous broadcast, and with the players broadcasting according to the current ordering. If the result is $1$, then $y_i = 1$.
3. Repeat steps 2(a) - 2(b) $q$ times in total. If the result of Template:Smallcaps is never $1$, then $y_i = 0$.

Template:Smallcaps

\noindent \textit{Input}: Security parameter $q$, $\mathcal{S}$'s choice of $\mathcal{R}$ is player $r$. \\ \textit{Goal}: $\mathcal{S}$ notifies $\mathcal{R}$. \\ For each player $i$:

For each player $i$:
1. Each player $j \neq i$ picks $p_j$ as follows: if $i = r$ and player $j$ is $S$, then $p_j = 1$ with probability $\frac{1}{2}$ and $p_j = 0$ with probability $\frac{1}{2}$. Otherwise, $p_j = 0$. Let $p_i = 0$.
2. Run Template:Smallcaps with input $\{p_i\}_{i=1}^n$, with the following differences: player $i$ does not broadcast her value, and they use a regular broadcast channel rather than simultaneous broadcast. If the result is $1$, then $y_i = 1$.
3. Repeat steps 1(a) - (b) $q$ times. If the result of Template:Smallcaps is never 1, then $y_i = 0$.
If player $i$ obtained $y_i = 1$, then she is $\mathcal{R}$.

Template:Smallcaps

\noindent \textit{Input:} All: parameter $q$. $\mathcal{S}$: distribution $D$. \\ \textit{Goal:} $\mathcal{S}$ chooses a bit according to $D$.

The players pick bits $\{ x_i \}_{i=1}^n$ as follows: $\mathcal{S}$ picks bit $x_i$ to be 0 or 1 according to $D$; all other players pick $x_i = 0$.
Run Template:Smallcaps with input $\{ x_i \}_{i=1}^n$ and security parameter $q$ and output its outcome.

Template:Smallcaps

\noindent \textit{Input}: $n$ players share state $\ket{\Psi}$. \\ \textit{Goal}: GHZ verification of $\ket{\Psi}$ for $n-t$ honest players.

The Verifier generates random angles $\theta_j \in [0,\pi)$ for all players including themselves ($j\in[n]$), such that $\sum_j \theta_j$ is a multiple of $\pi$. The angles are then sent out to all the players in the network.
Player $j$ measures in the basis $\{\ket{+_{\theta_j}},\ket{-_{\theta_j}}\}=\{\frac{1}{\sqrt{2}}(\ket{0}+e^{i\theta_j}\ket{1}),\frac{1}{\sqrt{2}}(\ket{0}-e^{i\theta_j}\ket{1})\}$, and sends the outcome $Y_j=\{0,1\}$ to the Verifier.
The state passes the verification test if

$ \bigoplus_j Y_j=\frac{1}{\pi}\sum_j\theta_j\pmod 2. $

Template:Smallcaps

\noindent \textit{Input}: $n$ players share a GHZ state. \\ \textit{Goal}: Anonymous transmission of quantum message $\ket{\psi}$ from $\mathcal{S}$ to $\mathcal{R}$.

$\mathcal{S}$ and $\mathcal{R}$ do not do anything to their part of the state.
Every player $j \in [n] \backslash \{ \mathcal{S}, \mathcal{R} \}$:
1. Applies a Hadamard transform to her qubit, \
2. Measures this qubit in the computational basis with outcome $m_j$,
3. Broadcasts $m_j$.
$\mathcal{S}$ picks a random bit $b \in_R \{ 0, 1 \}$ and broadcasts $b$.
$\mathcal{S}$ applies a phase flip $Z$ to her qubit if $b=1$.
$\mathcal{R}$ picks a random bit $b' \in_R \{ 0, 1 \}$ and broadcasts $b'$.
$\mathcal{R}$ applies a phase flip $Z$ to her qubit, if $b \oplus \underset{j \in [n] \backslash \{ \mathcal{S}, \mathcal{R} \}}{\bigoplus} m_j = 1$.
$\mathcal{S}$ and $\mathcal{R}$ share $\epsilon$-anonymous entanglement. $\mathcal{S}$ then uses the quantum teleportation circuit with input $\ket{\psi}$, and obtains measurement outcomes $m_0, m_1$.
The players run a protocol to anonymously send bits $m_0, m_1$ from $\mathcal{S}$ to $\mathcal{R}$ (see Further Information for details).
$\mathcal{R}$ applies the transformation described by $m_0, m_1$ on her part of the entangled state and obtains $\ket{\psi}$.

Further Information

For simplicity, the same security parameter $q$ has been used throughout, however this is not required.
Although Template:Smallcaps requires a simultaneous broadcast channel, only modified versions of Template:Smallcaps that remove this requirement are used in the anonymous transmission protocol.
The protocol assumes there is only one Sender for simplicity. However, if this is not the case, the players can run a classical \cite{Broadbent} or quantum \cite{Wehner} collision detection protocol to deal with multiple Senders.
To send classical teleportation bits $m_0, m_1$, the players can run Template:Smallcaps from \cite{Broadbent}, or the anonymous transmission protocol for classical bits with quantum resources from \cite{Wehner}.
Template:Smallcaps was experimentally demonstrated for 3- and 4-party GHZ states in \cite{McCutcheon}.
The Broadbent-Tapp protocol \cite{Broadbent} implements classical anonymous transmission. It requires pairwise authenticated classical channels, and a classical broadcast channel.
The Christandl-Wehner protocol \cite{Wehner} implements both classical and quantum anonymous transmission. However, this protocol assumes the nodes share a perfect, trusted GHZ state.
The Brassard et. al. protocol \cite{Brassard} implements verified quantum anonymous transmission. While their protocol includes a verification stage, it requires each player to perform a size-$n$ quantum circuit and to have access to quantum communication with all other agents.
The Lipinska et. al. protocol \cite{Lipinska} implements quantum anonymous transmission with a trusted W state instead of a GHZ state. While this is beneficial in terms of robustness to noise, the protocol proceeds to create anonymous entanglement only probabilistically, whereas GHZ-based anonymous entanglement proceeds deterministically.

\begin{thebibliography}{9} \bibitem{Unnikrishnan} A. Unnikrishnan, I. J. MacFarlane, R. Yi, E. Diamanti, D. Markham, and I. Kerenidis. \textit{Anonymity for practical quantum networks.} To be published in Physical Review Letters. arXiv:1811.04729 (2018). \bibitem{Wehner} M. Christandl and S. Wehner. \textit{Quantum anonymous transmissions.} Proceedings of ASIACRYPT (2005). \bibitem{Broadbent} A. Broadbent and A. Tapp. \textit{Information-theoretic security without an honest majority.} Proceedings of ASIACRYPT (2007). \bibitem{Pappa} A. Pappa, A. Chailloux, S. Wehner, E. Diamanti, and I. Kerenidis. \textit{Multipartite entanglement verification resistant against dishonest parties.} Physical Review Letters, 108 (2012). \bibitem{McCutcheon} W. McCutcheon, A. Pappa, B. A. Bell, A. McMillan, A. Chailloux, T. Lawson, M. Mafu, D. Markham, E. Diamanti, I. Kerenidis, J. G. Rarity, and M. S. Tame. \textit{Experimental verification of multipartite entanglement in quantum networks.} Nature Communications (2016). \bibitem{Brassard} G. Brassard, A. Broadbent, J. Fitzsimons, S. Gambs, and A. Tapp. \textit{Anonymous quantum communication.} Proceedings of ASIACRYPT (2007). \bibitem{Lipinska} V. Lipinska, G. Murta, and S. Wehner. \textit{Anonymous transmission in a noisy quantum network using the W state.} Physical Review A, 98 (2018).

\end{thebibliography}