Practical Quantum Electronic Voting

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

Outline

• 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

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} : Number of agents
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V = \{v_k\}_{k \in [N]} } : The votes
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} : Security parameter
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon} : Distance from the perfect GHZ state
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta} : Threshold for verification
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \eta} : Probability of failure of verification
• B: Bulletin board - Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} x Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} 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 $N$ rounds. Each element is computed as the parity of a row from B
• T: Final tally

Protocol Description

Protocol 1 : Quantum e-voting

Inputs: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V = \{v_k\}_{k \in [N]} } - Set of votes; Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} - Security parameter; $\epsilon$ - Distance from the perfect GHZ state; $\delta$ - Threshold for verification; Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \eta} 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 UniqueIndex until each agent has a secret unique random index Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega_k}
• Phase 2 [casting votes]
  • For $l=1$ to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N}
    • The voting agent is the agent Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega_k = l}
    • Repeat until Voting is announced
      • The source distributes to each of the N agents one qubit of the GHZ source
      • All agents Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j \in [N] } set rejections$_{j}=$ trialsFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle _j = 0}
      • The voting agent tosses logFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle _2[\frac{16N\epsilon^2}{(\epsilon^2-4\delta)^2}} ln$({\frac {1}{\eta }})]$
      • The agents perform LogicalOR, where output 1 indicates Verification and output 0 indicates 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 Verification is chosen, the agents perform RandomAgent and the voting agent anonymously picks an agent Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j \in [N]} to be the verifier. Agent Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} updates trialsFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle _j+ = 1} and if Verification outputs reject: rejections$_{j}+=1$
    • If for any $j\in [N],\delta _{j}={\frac {rejections_{j}}{trials_{j}}}>\delta$, the protocol Aborts
    • Perform 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 LogicalOR with security parameter $S$, 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 LogicalOR outputs 1, Abort the protocol. Else output the candidate with the most votes according to the tally T.

Protocol 2 : LogicalOR

Inputs: $N$ agents, $N$ boolean variables $x_{i}$, security parameter Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S = (1 - 2^{-\Gamma})^\Sigma \in (0,1)}

Output: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y = \vee_i^N x_i }

Resources: Classical communication and random numbers

1. Decide Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} random orderings, such that each voter is the last once. For each ordering repeat \Sigma times the following.
2. Each voter Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} gives an input Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_k}
3. If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_k = 0 } , set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_k = 0} , otherwise toss $\Gamma$ coins and set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_k} to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} if the result is ‘all heads’ and to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} otherwise
4. Then each voter generates uniformly at random an Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} -bit string Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_k = r_k^1r_k^2...r_k^N} , such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \bigoplus_{i=1}^N r_k^i = p_k}
5. Voter Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} sends Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_k^i} to voter Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} , keeping $r_{k}^{k}$
6. Each voter sums the received bits and broadcasts the parity Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_i = \bigoplus_{k=1}^N r_k^i } according to the ordering.
7. Compute the parity of the original bits Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y = \bigoplus_i z_i}
8. From this everyone can also compute the parity of all other inputs except their own Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_k = \bigoplus_{i = 1}^N (z_i \otimes r_k^i)}
9. Repeat Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma} times from step 4: each time repeat with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_k} as new inputs
10. If at least once in the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma} repetitions for the various orderings Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y = 1} , this is the output of the protocol, otherwise it is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y = 0}

Protocol 3 : RandomBit

Input: Security parameter S to be used in 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 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 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 RandomBit log2 N times.

Protocol 5 : UniqueIndex

Input: Security parameter Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} to be used in LogicalOR,Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} random boolean variables Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i} .

Output: Each agent Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} has a secret unique index Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega_k} .

Resources: Classical communication and random numbers.

1. Beginning of round R = 1
2. Agents perform LogicalOR with inputs Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_k = 0} if they already have an index and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_k = 1} if they do not.
3. If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y = 0} , repeat from step 2
4. If an agent Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} has a bit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_k = 1} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega_k = 0} they know they are the only one and has been assigned the secret index corresponding to the round Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega_k = R} , otherwise there is a collision.
5. \[notification\] Everybody performs a LogicalOR with input 0, unless they received the index in this round, in which case they input 1.
6. If the output of LogicalOR is 0, no index was assigned and we repeat from step 2.
7. If the output of LogicalOR is 1, the index was assigned and we repeat from step 2 with R+ = 1.
8. Repeat from step 2 until all indices have been assigned.

Protocol 6 : Verification

Input: A quantum state distributed and shared by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} parties, security parameter Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} for RandomAgent.

Output: If the state is a GHZ state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rightarrow } YES.

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

1. Everyone executes RandomAgent to choose uniformly at random one of the voters to be the verifier.
2. The verifier generates random angles Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \theta_j \in [0, \pi)} for all agents including themselves, such that the sum is a multiple of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi} . The angles are then sent out to all the agents.