Verifiable Quantum Anonymous Transmission: Difference between revisions

* <span style="font-variant:small-caps">Anonymous Entanglement</span> \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.

# \textit{Receiver notification}: The Sender $\mathcal{S}$ notifies the Receiver $R$ by running <span style="font-variant:small-caps">Notification</span>.

# \textit{Verification or anonymous transmission}: $\mathcal{S}$ anonymously chooses whether to verify the state or use it for anonymous transmission, using <span style="font-variant:small-caps">RandomBit}.  

If verification is chosen, a player is chosen to run <span style="font-variant:small-caps">Verification</span>, using $\log_2 n$ repetitions of  <span style="font-variant:small-caps">RandomBit</span>.  

If anonymous transmission is chosen, the players run <span style="font-variant:small-caps">Anonymous Entanglement</span>, establishing an anonymous entanglement link between $\mathcal{S}$ and $\mathcal{R}$.

$\mathcal{S}$ then teleports the message state $\ket{\psi}$ to $\mathcal{R}$ using the established anonymous entanglement. The classical message $m$ associated with teleportation is also sent anonymously.

* $n$: number of network nodes taking part in the anonymous transmission.

* $t$: number of adversarial network nodes taking part in the anonymous transmission.

* $\ket{\psi}$: quantum message which the Sender wants to send anonymously.

* $\ket{GHZ}  = \frac{1}{\sqrt{2</span> (\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.

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,  

If the state used for anonymous transmission is of fidelity at least $\sqrt{1-\epsilon^2}$ with the GHZ state,  

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.  

====<span style="font-variant:small-caps">$\epsilon$-anonymous transmission of a quantum message</span>====

\noindent \textit{Input}: Security parameter $q$. \\  

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

Run <span style="font-variant:small-caps">Notification</span> for $\mathcal{S}$ to notify $\mathcal{R}$ as the Receiver.

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}:  

## Run <span style="font-variant:small-caps">RandomBit</span>, 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$.

## If $x=1$,

### Run <span style="font-variant:small-caps">RandomBit</span> $\log_2 n$ times, with the input of $\mathcal{S}$ chosen according to the uniform random distribution. Let the outcome be $v$.

### Run <span style="font-variant:small-caps">Verification</span> 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 <span style="font-variant:small-caps">Anonymous Transmission</span>.

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.

\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$.

\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.  

## 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}$.  

## Run <span style="font-variant:small-caps">Parity</span> 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$.  

## Repeat steps 2(a) - 2(b) $q$ times in total. If the result of <span style="font-variant:small-caps">Parity</span> is never $1$, then $y_i = 0$.

\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$:

## 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$.

## Run <span style="font-variant:small-caps">Parity</span> 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$.

## Repeat steps 1(a) - (b) $q$ times. If the result of <span style="font-variant:small-caps">Parity</span> is never 1, then $y_i = 0$.  

# If player $i$ obtained $y_i = 1$, then she is $\mathcal{R}$.

\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 <span style="font-variant:small-caps">LogicalOR</span> with input $\{ x_i \}_{i=1}^n$ and security parameter $q$ and output its outcome.

\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</span>,\ket{-_{\theta_j</span>\}=\{\frac{1}{\sqrt{2</span>(\ket{0}+e^{i\theta_j}\ket{1}),\frac{1}{\sqrt{2</span>(\ket{0}-e^{i\theta_j}\ket{1})\}$, and sends the outcome $Y_j=\{0,1\}$ to the Verifier.  

\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} \}$:  

## Measures this qubit in the computational basis with outcome $m_j$,  

## 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} \</span>{\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}$.

* For simplicity, the same security parameter $q$ has been used throughout, however this is not required.

* To send classical teleportation bits $m_0, m_1$, the players can run <span style="font-variant:small-caps">Fixed Role Anonymous Message Transmission</span> from \cite{Broadbent}, or the anonymous transmission protocol for classical bits with quantum resources from \cite{Wehner}.

* 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.