Editing Practical Quantum Electronic Voting
Jump to navigation
Jump to search
The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 6: | Line 6: | ||
<!--Tags: related pages or category --> | <!--Tags: related pages or category --> | ||
== | ==Assumptions== | ||
<!-- It describes the setting in which the protocol will be successful. --> | <!-- It describes the setting in which the protocol will be successful. --> | ||
==Outline== | ==Outline== | ||
Line 48: | Line 44: | ||
''Resources'': Classical communication, random numbers, N-qubit GHZ source, quantum channels | ''Resources'': Classical communication, random numbers, N-qubit GHZ source, quantum channels | ||
* Phase 1 [getting unique secret indices] | * Phase 1 [getting unique secret indices] | ||
** Agents perform | ** Agents perform [[#Protocol 5 : UniqueIndex| UniqueIndex]] until each agent has a secret unique random index <math>\omega_k</math> | ||
* Phase 2 [casting votes] | * Phase 2 [casting votes] | ||
** For <math>l = 1</math> to <math>N</math> | ** For <math>l = 1</math> to <math>N</math> | ||
*** The voting agent is the agent <math>k</math> with <math>\omega_k = l</math> | *** The voting agent is the agent <math>k</math> with <math>\omega_k = l</math> | ||
*** Repeat until | *** Repeat until [[#Protocol 7 : Voting| Voting]] is announced | ||
**** The source distributes to each of the N agents one qubit of the GHZ source | **** 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> | **** 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 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 | **** 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 | **** 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'' | *** If for any <math>j \in [N], \delta_j = \frac{rejections_j}{trials_j} > \delta </math>, the protocol ''Aborts'' | ||
*** Perform | *** 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. | ** Given the votes '''E''', the tally '''T''' can be computed. | ||
*Phase 3 [Verification of results]: | *Phase 3 [Verification of results]: | ||
** All agents perform | ** 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 | ** 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=== | |||
===Protocol 2 | |||
''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> | ''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> | ||
Line 125: | Line 79: | ||
# 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> | # 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 | |||
''Input'': Security parameter S to be used in | ===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. | ''Output'': The voting agent anonymously announces a random bit according to D. | ||
Line 132: | Line 87: | ||
''Resources'': Classical communication and random numbers. | ''Resources'': Classical communication and random numbers. | ||
*Perform | *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 | ===Protocol 4 : RandomAgent=== | ||
''Input'': Security parameter S to be used in | ''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. | ''Output'': The voting agent anonymously chooses a random agent according to D. | ||
Line 142: | Line 97: | ||
''Resources'': Classical communication and random numbers. | ''Resources'': Classical communication and random numbers. | ||
* Repeat '' | * 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. | |||
===Protocol 7 : Voting=== | |||
==Properties== | |||
<!-- important information on the protocol: parameters (threshold values), security claim, success probability... --> | |||
==Further Information== | ==Further Information== | ||
<!-- theoretical and experimental papers including requirements, security proof (important), which protocol does it implement, benchmark values... --> | <!-- theoretical and experimental papers including requirements, security proof (important), which protocol does it implement, benchmark values... --> | ||
==References== |