Editing Practical Quantum Electronic Voting

<!-- This is a comment. You can erase them or write below -->


<!-- Intro: brief description of the protocol -->
This [https://arxiv.org/abs/2107.14719 example protocol] achieves the functionality of [[Quantum Electronic Voting]]. In this protocol, an untrusted multipartite entanglement source can be used to carry out an election without any election authorities.

<!--Tags: related pages or category -->

==Assumptions==
<!-- It describes the setting in which the protocol will be successful. -->

==Outline==
<!-- A non-mathematical detailed outline which provides a rough idea of the concerned protocol -->
* In the first phase of the protocol, each agent is assigned a secret unique random index
* Next, we perform multiple rounds of voting, one for each agent. In each round, the following steps are carried out:
** The agent with the same index as the round number is designated the voter for that round
** The source distributes one qubit of a GHZ state to each agent. The voting agent randomly chooses to either '''verify''' the GHZ state or '''vote''' with a certain probability. This step, including state distribution, is repeated until the voter chooses to vote. Once voting is chosen, the voter anonymously transmits their vote to all agents.
* Finally, all the votes are tallied. All agents have the votes for each round and can thus verify the final tally.

==Notation==
<!--  Connects the non-mathematical outline with further sections. -->
* <math>N</math>: Number of agents
* <math>V = \{v_k\}_{k \in [N]} </math>: The votes
* <math>S</math>: Security parameter
* <math>\epsilon</math>: Distance from the perfect GHZ state
* <math>\delta</math>: Threshold for verification
* <math>\eta</math>: Probability of failure of verification
* '''B''': Bulletin board - <math>N</math> x <math>N</math> binary matrix. Each row corresponds to one round of voting, and each column contains the output of a single voter across all rounds
* '''E''': Vote vector - The list of votes across <math>N</math> rounds. Each element is computed as the parity of a row from '''B'''
* '''T''': Final tally

<!-- ==Knowledge Graph== -->
<!-- Add this part if the protocol is already in the graph -->
<!-- {{graph}} -->


==Protocol Description==
<!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. -->
===Protocol 1 : Quantum e-voting===
''Inputs'': <math>V = \{v_k\}_{k \in [N]} </math> - Set of votes; <math>S</math> - Security parameter; <math>\epsilon</math> - Distance from the perfect GHZ state; <math>\delta</math> - Threshold for verification; <math>\eta</math> Probability of failure of verification

''Output'': The candidate with majority votes or ''Abort''
 
''Resources'': Classical communication, random numbers, N-qubit GHZ source, quantum channels
* Phase 1 [getting unique secret indices]
** Agents perform [[#Protocol 5 : UniqueIndex| UniqueIndex]] until each agent has a secret unique random index  <math>\omega_k</math>
* Phase 2 [casting votes]
** For <math>l = 1</math> to <math>N</math>
*** The voting agent is the agent <math>k</math> with <math>\omega_k = l</math>
*** Repeat until [[#Protocol 7 : Voting| Voting]] is announced
**** The source distributes to each of the N agents one qubit of the GHZ source
**** All agents <math> j \in [N] </math> set rejections<math>_j = </math> trials<math>_j = 0</math>
**** The voting agent tosses log<math>_2[\frac{16N\epsilon^2}{(\epsilon^2-4\delta)^2}</math>ln<math>(\frac{1}{\eta})]</math> <!--NEEDS FORMATTING CHANGES-->
**** The agents perform [[#Protocol 2 : LogicalOR| LogicalOR]], where output 1 indicates [[#Protocol 6 : Verification| Verification]] and output 0 indicates [[#Protocol 7 : Voting| Voting]]. Everyone except the voting agent inputs 0; if the coin toss is 'all heads' the voting agent also inputs 0, otherwise the voting agent inputs 1
**** If [[#Protocol 6 : Verification| Verification]] is chosen, the agents perform [[#Protocol 4 : RandomAgent| RandomAgent]] and the voting agent anonymously picks an agent <math>j \in [N]</math> to be the verifier. Agent <math>j</math> updates trials<math>_j+ = 1</math> and if [[#Protocol 6 : Verification| Verification]] outputs reject: rejections<math>_j+ = 1</math>
*** If for any <math>j \in [N], \delta_j = \frac{rejections_j}{trials_j} > \delta </math>, the protocol ''Aborts''
*** Perform [[#Protocol 7 : Voting| Voting]]. The outcome is one row of the Bulletin Board '''B'''. The parity of the row gives one entry in the vote vector '''E'''.
** Given the votes '''E''', the tally '''T''' can be computed.
*Phase 3 [Verification of results]:
** All agents perform [[#Protocol 2 : LogicalOR| LogicalOR]] with security parameter <math>S</math>, and input 1 if their vote is not the same as the entry in '''E''' for the round in which they voted, and 0 otherwise.
** If [[#Protocol 2 : LogicalOR| LogicalOR]] outputs 1, ''Abort'' the protocol. Else output the candidate with the most votes according to the tally '''T'''.

===Protocol 2 : LogicalOR===
''Inputs'': <math>N</math> agents, <math>N</math> boolean variables <math>x_i</math>, security parameter <math>S = (1 - 2^{-\Gamma})^\Sigma \in (0,1)</math>

''Output'': <math>y = \vee_i^N x_i </math>

''Resources'': Classical communication and random numbers

# Decide <math>N</math> random orderings, such that each voter is the last once. For each ordering repeat \Sigma times the following.
# Each voter <math>k</math> gives an input <math>x_k</math>
# If <math>x_k = 0 </math>, set <math>p_k = 0</math>, otherwise toss <math>\Gamma</math> coins and set <math>p_k</math> to <math>1</math> if the result is ‘all heads’ and to <math>0</math> otherwise
# Then each voter generates uniformly at random an <math>N</math>-bit string <math>r_k = r_k^1r_k^2...r_k^N</math>, such that <math>\bigoplus_{i=1}^N r_k^i = p_k</math> 
# Voter <math>k</math> sends <math>r_k^i</math> to voter <math>i</math> for all <math>i</math>, keeping <math>r_k^k</math>
# Each voter sums the received bits and broadcasts the parity <math>z_i = \bigoplus_{k=1}^N r_k^i </math> according to the ordering.
# Compute the parity of the original bits <math>y = \bigoplus_i z_i</math>
# From this everyone can also compute the parity of all other inputs except their own <math>w_k = \bigoplus_{i = 1}^N (z_i \otimes r_k^i)</math>
# Repeat <math>\Sigma</math> times from step 4: each time repeat with <math>p_k</math> as new inputs
# If at least once in the <math>\Sigma</math> repetitions for the various orderings <math>y = 1</math>, this is the output of the protocol, otherwise it is <math>y = 0</math>


===Protocol 3 : RandomBit===
''Input'': Security parameter S to be used in [[#Protocol 2 : LogicalOR| LogicalOR]], ''voting agent'': probability distribution D.

''Output'': The voting agent anonymously announces a random bit according to D.

''Resources'': Classical communication and random numbers.

*Perform [[#Protocol 2 : LogicalOR| LogicalOR]] with security parameter S where the voting agent inputs a random bit according to D and the other agents input 0.

===Protocol 4 : RandomAgent===

''Input'': Security parameter S to be used in [[#Protocol 3 : RandomBit| RandomBit]], voting agent: probability distribution D.

''Output'': The voting agent anonymously chooses a random agent according to D.

''Resources'': Classical communication and random numbers.

* Repeat [[#Protocol 3 : RandomBit| RandomBit]] log2 N times.

===Protocol 5 : UniqueIndex===

''Input'': Security parameter <math>S</math> to be used in LogicalOR,<math>N</math> random boolean variables <math>x_i</math>.

''Output'': Each agent <math>k</math> has a secret unique index <math>\omega_k</math>.

''Resources'': Classical communication and random numbers.

# Beginning of round R = 1
# Agents perform [[#Protocol 2 : LogicalOR| LogicalOR]] with inputs <math>x_k = 0</math> if they already have an index and <math>x_k = 1</math> if they do not.
# If <math>y = 0</math>, repeat from step 2
# If an agent <math>k</math> has a bit <math>x_k = 1</math> and <math>\omega_k = 0</math> they know they are the only one and has been assigned the secret index corresponding to the round <math>\omega_k = R</math>, otherwise there is a collision.
# \[notification\]  Everybody performs a [[#Protocol 2 : LogicalOR| LogicalOR]] with input 0, unless they received the index in this round, in which case they input 1.
# If the output of [[#Protocol 2 : LogicalOR| LogicalOR]] is 0, no index was assigned and we repeat from step 2.
# If the output of [[#Protocol 2 : LogicalOR| LogicalOR]] is 1, the index was assigned and we repeat from step 2 with R+ = 1.
# Repeat from step 2 until all indices have been assigned.

===Protocol 6 : Verification===
''Input'': A quantum state distributed and shared by <math>N</math> parties, security parameter <math>S</math> for [[#Protocol 4 : RandomAgent| RandomAgent]].

''Output'': If the state is a GHZ state <math> \rightarrow </math> YES.

''Resources'': Classical communication, random numbers, quantum state source, quantum channels.

# Everyone executes [[#Protocol 4 : RandomAgent| RandomAgent]] to choose uniformly at random one of the voters to be the verifier.
# The verifier generates random angles <math>\theta_j \in [0, \pi)</math> for all agents including themselves, such that the sum is a multiple of <math>\pi</math>. The angles are then sent out to all the agents.
# Agent <math>j</math> measures in the basis <math>[|+_\theta\rangle,|-_\theta\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 publicly announces the result <math>Y_j = \{0,1\}</math>
# The state passes the verification test when the following condition is satisfied: if the sum of the randomly chosen angles is an even multiple of <math>\pi</math>, there must be an even number of 1 outcomes for <math<Y_j</math> , and if the sum is an odd multiple of <math>\pi</math>, there must be an odd number of 1 outcomes for <math>Y_j : \bigoplus_j Y_j = \frac{1}{\pi}\sum_i\theta_i</math>

===Protocol 7 : Voting===
''Input'': Voting agent preference <math>v_k</math>.

''Output'': All agents get one row of the bulletin board.

''Resources'': Classical communication, GHZ source, quantum channels.

# Each agent measures the state they received in the Hadamard basis and records the outcome.
# The outcomes of the measurement of each voter <math>k</math> is <math>d_k</math>. Then we know that <math>\sum_kd_k = 0</math> mod <math> 2</math>
# The voting agent performs an XOR between the outcome <math>d_k</math> and their vote <math>v_k</math>: <math>d_k \leftarrow d_k \oplus v_k </math>. However, this alone will still appear as a random string.
# Every agent publicly broadcasts <math>d_k</math> which gives one line <math>b_k</math> of the bulletin board '''B''' <math> = \{b_k\}</math>
==Properties==
<!-- important information on the protocol: parameters (threshold values), security claim, success probability... -->


==Further Information==
<!-- theoretical and experimental papers including requirements, security proof (important), which protocol does it implement, benchmark values... -->

==References==