Editing Verifiable Quantum Anonymous Transmission

This [https://arxiv.org/abs/1811.04729 example protocol] implements the task of [[Anonymous Transmission]] in a multi-node quantum network. The protocol uses an untrusted <math>n</math>-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 <math>\epsilon</math>-anonymity.

==Assumptions==

* '''Network''': The network consists of <math>n</math> 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 [[Verifiable Quantum Anonymous Transmission#References|[1]]], which uses the following subroutines from [[Verifiable Quantum Anonymous Transmission#References|[2]]], [[Verifiable Quantum Anonymous Transmission#References|[3]]], [[Verifiable Quantum Anonymous Transmission#References|[4]]], [[Verifiable Quantum Anonymous Transmission#References|[5]]] :
* <span style="font-variant:small-caps">Parity</span> [[Verifiable Quantum Anonymous Transmission#References|[3]]]: privately computes the parity of an input string.
* <span style="font-variant:small-caps">LogicalOR</span> [[Verifiable Quantum Anonymous Transmission#References|[3]]]: privately computes the logical OR of an input string, using a modified version of <span style="font-variant:small-caps">Parity</span>.
* <span style="font-variant:small-caps">Notification</span> [[Verifiable Quantum Anonymous Transmission#References|[3]]]: allows one player to anonymously notify another player, using <span style="font-variant:small-caps">LogicalOR</span>.
* <span style="font-variant:small-caps">RandomBit</span> [[Verifiable Quantum Anonymous Transmission#References|[1]]]: allows one player to anonymously choose a bit according to a probability distribution, using <span style="font-variant:small-caps">LogicalOR</span>.
* <span style="font-variant:small-caps">Verification</span> [[Verifiable Quantum Anonymous Transmission#References|[4,5]]]: 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. 
* <span style="font-variant:small-caps">Anonymous Entanglement</span> [[Verifiable Quantum Anonymous Transmission#References|[2]]]: <math>n-2</math> nodes (all except for <math>\mathcal{S}</math> and <math>\mathcal{R}</math>) measure in the <math>X</math> basis and broadcast their measurement outcome. <math>\mathcal{S}</math> and <math>\mathcal{R}</math> broadcast random dummy bits. The parity of measurement outcomes allows the establishment of an entangled link between <math>\mathcal{S}</math> and <math>\mathcal{R}</math> which is called anonymous entanglement.

The protocol for quantum anonymous transmission consists of the following steps:
# ''Receiver notification'': The Sender <math>\mathcal{S}</math> notifies the Receiver <math>R</math> by running <span style="font-variant:small-caps">Notification</span>.
# ''State distribution'': A source, who may be untrusted, distributes a state claiming to be the GHZ state.
# ''Verification or anonymous transmission'': <math>\mathcal{S}</math> anonymously chooses whether to verify the state or use it for anonymous transmission, using <span style="font-variant:small-caps">RandomBit</span>. 

If verification is chosen, a player is chosen to run <span style="font-variant:small-caps">Verification</span>, using <math>\log_2 n</math> repetitions of  <span style="font-variant:small-caps">RandomBit</span>. 
If the test passes, the protocol goes back to the ''State distribution'' stage and runs again. If the test fails, the players abort. 

If anonymous transmission is chosen, the players run <span style="font-variant:small-caps">Anonymous Entanglement</span>, establishing an anonymous entanglement link between <math>\mathcal{S}</math> and <math>\mathcal{R}</math>.
<math>\mathcal{S}</math> then teleports the message state <math>|\psi\rangle</math> to <math>\mathcal{R}</math> using the established anonymous entanglement. The classical message <math>m</math> associated with teleportation is also sent anonymously.

==Notation==
* <math>n</math>: number of network nodes taking part in the anonymous transmission.
* <math>t</math>: number of adversarial network nodes taking part in the anonymous transmission.
* <math>|\psi\rangle</math>: quantum message which the Sender wants to send anonymously.
* <math>|GHZ\rangle = \frac{1}{\sqrt{2}} (|0^n\rangle + |1^n\rangle)</math>: GHZ state. 
* <math>|\Psi\rangle</math>: state provided by the untrusted source for anonymous transmission (in the ideal case, this is the GHZ state).
* <math>\mathcal{S}</math>: the Sender of the quantum message.
* <math>\mathcal{R}</math>: the Receiver of the quantum message.
* <math>q</math>: the security parameter.

==Requirements==

[[File:Verifiable Quantum Anonymous Transmission.png|center|Verifiable Quantum Anonymous Transmission]]

==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 <math>C_\epsilon</math> 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 <math>\sqrt{1-\epsilon^2}</math>. Then, 
<center>
<math>P[C_\epsilon] \leq 2^{-q} \frac{4n}{1 - \sqrt{1-\epsilon^2}}</math>
</center>
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 <math>\sqrt{1-\epsilon^2}</math> with the GHZ state, 
<center><math>
P_{\text{guess}} [\mathcal{S} | C, \mathcal{S} \notin \mathcal{A} ] \leq \frac{1}{n-t} + \epsilon
</math></center>
<center><math>
P_{\text{guess}} [\mathcal{R} | C, \mathcal{S} \notin \mathcal{A} ] \leq \frac{1}{n-t} + \epsilon
</math></center>
where <math>\mathcal{A}</math> is the subset of <math>t</math> adversaries among <math>n</math> nodes and <math>C</math> is the register that contains all classical and quantum side information accessible to the adversaries.

==Pseudocode==

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

''Input'': Security parameter <math>q</math>.

''Goal'': <math>\mathcal{S}</math> sends message qubit <math>|\psi\rangle</math> to <math>\mathcal{R}</math> with <math>\epsilon</math>-anonymity. 


# ''' Receiver notification ''': Run <span style="font-variant:small-caps">Notification</span> for <math>\mathcal{S}</math> to notify <math>\mathcal{R}</math> as the Receiver.
# ''' Distribution of state ''': A source (who may be untrusted) generates a state <math>|\Psi\rangle</math> and distributes it to the players (in the ideal case, <math>|\Psi\rangle</math> is the GHZ state).
# ''' <math>\mathcal{S}</math> anonymously chooses verification or anonymous transmission ''': 
## Run <span style="font-variant:small-caps">RandomBit</span>, with the input of <math>\mathcal{S}</math> chosen as follows: she flips <math>q</math> fair classical coins, and if all coins are heads, she inputs 0, else she inputs 1. Let the outcome be <math>x</math>.
## If <math>x=1</math>,
### Run <span style="font-variant:small-caps">RandomBit</span> <math>\log_2 n</math> times, with the input of <math>\mathcal{S}</math> chosen according to the uniform random distribution. Let the outcome be <math>v</math>.
### Run <span style="font-variant:small-caps">Verification</span> with player <math>v</math> as the Verifier. If she accepts the outcome of the test, return to step 2, otherwise abort. Else if <math>x=0</math>, run <span style="font-variant:small-caps">Anonymous Transmission</span>.

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


====<span style="font-variant:small-caps">Subroutines</span>====

*<span style="font-variant:small-caps">Parity</span>

''Input'': <math>\{ x_i \}_{i=1}^n</math>.

''Goal'': Each player gets <math>y_i = \bigoplus_{i=1}^n x_i</math>.

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

*<span style="font-variant:small-caps">LogicalOR</span>

''Input'': <math>\{ x_i \}_{i=1}^n</math>, security parameter <math>q</math>.

''Goal'': Each player gets <math>y_i = \bigvee_{i=1}^n x_i</math>.

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

*<span style="font-variant:small-caps">Notification</span>

''Input'': Security parameter <math>q</math>, <math>\mathcal{S}</math>'s choice of <math>\mathcal{R}</math> is player <math>r</math>.

''Goal'': <math>\mathcal{S}</math> notifies <math>\mathcal{R}</math>.

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

*<span style="font-variant:small-caps">RandomBit</span>

''Input'': All: parameter <math>q</math>. <math>\mathcal{S}</math>: distribution <math>D</math>.

''Goal'': <math>\mathcal{S}</math> chooses a bit according to <math>D</math>.

# The players pick bits <math>\{ x_i \}_{i=1}^n</math> as follows: <math>\mathcal{S}</math> picks bit <math>x_i</math> to be 0 or 1 according to <math>D</math>; all other players pick <math>x_i = 0</math>.
# Run <span style="font-variant:small-caps">LogicalOR</span> with input <math>\{ x_i \}_{i=1}^n</math> and security parameter <math>q</math> and output its outcome.

*<span style="font-variant:small-caps">Verification</span>

''Input'': <math>n</math> players share state <math>|\Psi\rangle</math>.

''Goal'': GHZ verification of <math>|\Psi\rangle</math> for <math>n-t</math> honest players.

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

*<span style="font-variant:small-caps">Anonymous Transmission</span>

''Input'': <math>n</math> players share a GHZ state.

''Goal'': Anonymous transmission of quantum message <math>|\psi\rangle</math> from <math>\mathcal{S}</math> to <math>\mathcal{R}</math>.

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

==Further Information==
* For simplicity, the same security parameter <math>q</math> has been used throughout, however, this is not required.
* Although <span style="font-variant:small-caps">Parity</span> requires a simultaneous broadcast channel, only modified versions of <span style="font-variant:small-caps">Parity</span> 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 [[Verifiable Quantum Anonymous Transmission#References|[3]]] or quantum [[Verifiable Quantum Anonymous Transmission#References|[2]]] collision detection protocol to deal with multiple Senders. 
* To send classical teleportation bits <math>m_0, m_1</math>, the players can run <span style="font-variant:small-caps">Fixed Role Anonymous Message Transmission</span> from [[Verifiable Quantum Anonymous Transmission#References|[3]]], or the anonymous transmission protocol for classical bits with quantum resources from [[Verifiable Quantum Anonymous Transmission#References|[2]]].
* <span style="font-variant:small-caps">Verification</span> was experimentally demonstrated for 3- and 4-party GHZ states in [[Verifiable Quantum Anonymous Transmission#References|[5]]].
* The Broadbent-Tapp protocol [[Verifiable Quantum Anonymous Transmission#References|[3]]] implements classical anonymous transmission. It requires pairwise authenticated classical channels and a classical broadcast channel. 
* The Christandl-Wehner protocol [[Verifiable Quantum Anonymous Transmission#References|[2]]] implements both classical and quantum anonymous transmission. However, this protocol assumes the nodes share a perfect, trusted GHZ state.
* The Brassard et. al. protocol [[Verifiable Quantum Anonymous Transmission#References|[6]]] implements verified quantum anonymous transmission. While their protocol includes a verification stage, it requires each player to perform a size-<math>n</math> quantum circuit and to have access to quantum communication with all other agents.
* The Lipinska et. al. protocol [[Verifiable Quantum Anonymous Transmission#References|[7]]] 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. 

==References==
# [https://arxiv.org/abs/1811.04729 Unnikrishnan et al (2018)]
# [https://link.springer.com/chapter/10.1007/11593447_12 Christandl and Wehner (2005)]
# [https://arxiv.org/abs/0706.2010 Broadbent and Tapp (2007)]
# [https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.108.260502 Pappa et al (2012)]
# [https://www.nature.com/articles/ncomms13251 McCutcheon et al (2016)]
# [https://arxiv.org/abs/0706.2356 Brassard et al (2007)] 
# [https://arxiv.org/abs/1806.10973 Lipinska et al (2018)]

<div style='text-align: right;'>''contributed by Anupama Unnikrishnan''</div>