Quantum voting based on conjugate coding

This example protocol implements the task of E-voting. The participants in this family of protocols are one or more election authorities, the tallier, and the voters. The election authorities are only trusted for the purpose of eligibility and the voters do not share any entangled states with neither EA nor T in order to cast their ballots.

Assumptions

• The election authorities need to be trusted only for the purpose of eligibility; privacy should be guaranteed by the protocol against malicious parties.
• Existence of anonymous channel and authenticated channel.

Outline

In the beginning, the election authority chooses a vector for encoding ballots which will be kept secret from the tallier until the end of the ballot casting phase. Then the EA prepares w=polynomial(n) fragments that constitute a blank ballot and sends them to voters by an authenticated channel. After reception of the blank ballot, each voter re randomizes it and then applies a unitary to the blank ballot fragment and encodes the candidate of choice in the (n + 1)th-qubit of the last blank ballot fragments.

Finally, she sends the ballot to the tallier over an anonymous channel. Once the ballot casting phase ends, the election authority announces the vector to the tallier so the tallier can decode each cast ballot by measuring it in the correct basis and announces the election result.

Notations

• $V_{i}:i^{th}$ voter
• c: number of possible candidates
• N: number of voters
• $v_{i}:$ vote of $i^{th}$ voter
• T: tallier
• n: security parameter
• EA: election authority

Properties

• Verifiability: An adversary can change the vote of an eligible voter when the corresponding ballot is cast over the anonymous channel.
• Privacy: EA can introduce a “serial number” in a blank ballot to identify a voter and therefore violate privacy.

The security of the protocol relies on a quantum problem, named one-more-unforgeability, and the assumption that it is computationally hard for a quantum adversary.

Requirements

• a quantum anonymous channel between voters and tallier
• an authenticated channel between voters and the election authority.
• Measurement Device for the tallier.

Protocol Description

• Setup phase:

1. EA picks a vector ${\bar {b}}=(b_{1},...,b_{n+1})\in \{0,1\}^{n+1}$ that will be kept secret from T until the end of the ballot casting phase.
2. For each $V_{k}$, EA prepares w = poly(n) blank ballot fragments each of the form $|\phi _{{\bar {a}}_{j},{\bar {b}}}\rangle =|\psi _{a_{j}^{1},b_{1}}\rangle \otimes ...\otimes |\psi _{a_{j}^{n+1},b_{n+1}}\rangle ,j\in \{1,...,w\}$ where ${\bar {a}}_{j}=(a_{j}^{1},...,a_{j}^{n+1}){\text{ such that }}(a_{j}^{1},...,a_{j}^{n})\in \{0,1\}^{n},a_{j}^{n+1}=a_{j}^{1}\oplus ...\oplus a_{j}^{n}$ and $|\psi _{0,0}\rangle =|0\rangle ,|\psi _{1,0}\rangle =|1\rangle ,|\psi _{0,1}\rangle ={\dfrac {1}{\sqrt {2}}}(|0\rangle +|1\rangle ),|\psi _{1,1}\rangle ={\dfrac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )$
3. EA sends one blank ballot to each $V_{k}$ over an authenticated channel.

• Casting phase:

1. Each $V_{k}$ picks for each blank ballot fragment a vector $d_{j}=(d_{j}^{1},...,d_{j}^{n+1})$ such that: $(d_{j}^{1},...,d_{j}^{n})\in \{0,1\}^{n},d_{j}^{n+1}=d_{j}^{1}\oplus ...\oplus d_{j}^{n}$

   $\forall j\in \{1,...,w\},V_{k}$applies the unitary $U_{j}^{{\bar {d}}_{j}}=Y^{d_{j}^{1}}\otimes ...\otimes Y^{d_{j}^{n+1}}$ to the blank ballot fragment $|\phi _{{\bar {a}}_{j},{\bar {b}}}\rangle$ where

   $$Y^{1}={\begin{bmatrix}0&-1\\1&0\end{bmatrix}},Y^{0}=I$$
   $V_{k}$ encodes the candidate of choice in the (n + 1)th-qubit of the last blank ballot fragments.

2. $V_{k}$ sends the ballot to T over an anonymous channel.

• Tally phase:

1. EA announces ${\bar {b}}$ to T.
2. T decodes each ballot fragment by measuring it in the basis described by vector ${\bar {b}}$ and XORs the resulting bits and does this to each ballot fragment ending up with a string, which is the actual vote cast.
3. T announces the election result.

Further Information

*contributed by Sara Sarfaraz