Editing Verifiable Quantum Anonymous Transmission (section)

==Protocol Description==

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