Write, autoreview, editor, reviewer
3,125
edits
Verifiable Quantum Anonymous Transmission: Difference between revisions
→Pseudocode
| Line 59: | Line 59: | ||
====<span style="font-variant:small-caps"><math>\epsilon</math>-anonymous transmission of a quantum message</span>==== | ====<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>. | ## 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>, | ## 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">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. | ### 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>. | ||
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. | 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. | ||
| Line 83: | Line 79: | ||
====<span style="font-variant:small-caps">Parity</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> 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>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>). | ||
| Line 91: | Line 90: | ||
====<span style="font-variant:small-caps">LogicalOR</span>==== | ====<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. | # The players agree on <math>n</math> orderings, with each ordering having a different last participant. | ||
# For each ordering: | # For each ordering: | ||
| Line 100: | Line 102: | ||
====<span style="font-variant:small-caps">Notification</span>==== | ====<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>: | ||
# For each player <math>i</math>: | # For each player <math>i</math>: | ||
| Line 110: | Line 115: | ||
====<span style="font-variant:small-caps">RandomBit</span>==== | ====<span style="font-variant:small-caps">RandomBit</span>==== | ||
'' | ''Input'': All: parameter <math>q</math>. <math>\mathcal{S}</math>: distribution <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. | ''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>==== | ====<span style="font-variant:small-caps">Verification</span>==== | ||
'' | ''Input'': <math>n</math> players share state <math>|\Psi\rangle</math>. | ||
# 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>\{ | ''Goal'': GHZ verification of <math>|\Psi\rangle</math> for <math>n-t</math> honest players. | ||
# The state passes the verification test if | |||
<math> | # 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. | ||
\bigoplus_j Y_j=\frac{1}{\pi}\sum_j\theta_j\pmod 2. | # 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. | ||
<math> | # 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>==== | ====<span style="font-variant:small-caps">Anonymous Transmission</span>==== | ||
'' | ''Input'': <math>n</math> players share a GHZ state. | ||
# <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>: | ''Goal'': Anonymous transmission of quantum message <math>|\psi\rangle</math> from <math>\mathcal{S}</math> to <math>\mathcal{R}</math>. | ||
## Applies a Hadamard transform to her qubit | |||
## Measures this qubit in the computational basis with outcome <math>m_j<math> | # <math>\mathcal{S}</math> and <math>\mathcal{R}</math> do not do anything to their part of the state. | ||
## Broadcasts <math>m_j<math>. | # Every player <math>j \in [n] \backslash \{ \mathcal{S}, \mathcal{R} \}</math>: | ||
# <math>\mathcal{S}<math> picks a random bit <math>b \in_R \{ 0, 1 \}<math> and broadcasts <math>b<math>. | ## Applies a Hadamard transform to her qubit | ||
# <math>\mathcal{S}<math> applies a phase flip <math>Z<math> to her qubit if <math>b=1<math>. | ## Measures this qubit in the computational basis with outcome <math>m_j</math> | ||
# <math>\mathcal{R}<math> picks a random bit <math>b' \in_R \{ 0, 1 \}<math> and broadcasts <math>b'<math>. | ## Broadcasts <math>m_j</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} \ | # <math>\mathcal{S}</math> picks a random bit <math>b \in_R \{ 0, 1 \}</math> and broadcasts <math>b</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>\ | # <math>\mathcal{S}</math> applies a phase flip <math>Z</math> to her qubit if <math>b=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> picks a random bit <math>b' \in_R \{ 0, 1 \}</math> and broadcasts <math>b'</math>. | ||
# <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>\ | # <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== | ==Further Information== | ||