Verifiable Quantum Anonymous Transmission: Difference between revisions

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

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

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

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

# {\bf <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.

\noindent ''{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>.

\noindent ''{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.  

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

\noindent ''{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>.