DRE-i with enhanced privacy

Direct Recording Electronic with Integrity and Enforced Privacy (DRE-ip) is an End-to-End (E2E) verifiable e-voting system without involving any tallying authorities, proposed by Siamak Shahandashti and Feng Hao in 2016. ^[1] It improves a previous DRE-i system by using a real-time computation strategy and providing enhanced privacy. A touch-screen based prototype of the system was trialed in the Gateshead Civic Centre polling station on 2 May 2019 during the 2019 United Kingdom local elections with positive voter feedback. ^[2] A proposal that includes DRE-ip as a solution for large-scale elections was ranked 3rd place in the 2016 Economist Cybersecurity Challenge jointly organized by The Economist and Kaspersky Lab. ^[3]

Protocol

The DRE-ip protocol is applicable to both onsite polling station voting and remote Internet voting implementations. In the specification below, it is described for polling station voting. The protocol consists of three stages: setup, voting and tallying.

Setup

Let ${\displaystyle p}$ and ${\displaystyle q}$ be two large primes, where ${\textstyle q\,|\,p-1}$. ${\displaystyle G_{q}}$ is a subgroup of ${\displaystyle Z_{p}^{*}}$ of prime order ${\displaystyle q}$. Let ${\displaystyle g_{1}}$ and ${\displaystyle g_{2}}$ be two random generators of ${\displaystyle G_{q}}$, whose discrete logarithm relationship is unknown. This can be realized by choosing a non-identity element in ${\displaystyle G_{q}}$ as ${\displaystyle g_{1}}$ and computing ${\displaystyle g_{2}}$ based on applying a one-way hash function with the inclusion of election specific information such as the date, election title and questions as the input. ^[4] All modulo operations are performed with respect to the modulus ${\displaystyle p}$. Alternatively, the protocol can be implemented using an elliptic curve, while the protocol specification remains unchanged.

Voting

For simplicity, the voting process is described for a single-candidate (Yes/No) election held in a polling station using a touch-screen DRE machine. There are standard ways to extend a single candidate election to support multiple candidates, e.g., providing a Yes/No selection for each of the candidates or using different encoded values for different candidates as described by Baudron et al. ^[5]

After being authenticated at a polling station, a voter obtains an authentication credential, which can be a random passcode or a smartcard. The authentication credential allows the voter to log onto a DRE machine in a private voting booth and cast a vote, but the machine does not know the voter's real identity.

A voter casts a vote on a DRE machine in two steps. First, he is presented with "Yes" and "No" options for the displayed candidate on the screen. Once the voter makes a choice on the touch screen, the DRE prints the first part of the receipt, containing ${\displaystyle i,R_{i}=g_{2}^{r_{i}},Z_{i}=g_{1}^{r_{i}}g_{1}^{v_{i}}}$ where ${\displaystyle i}$ is a unique ballot index number, ${\displaystyle r_{i}}$ is a number chosen uniformly at random from ${\displaystyle [1,q-1]}$, and ${\displaystyle v_{i}}$ is either 1 or 0 (corresponding to "Yes" and "No" respectively). The cipher text also comes with a zero knowledge proof to prove that ${\displaystyle R_{i}}$ and ${\displaystyle Z_{i}}$ are well-formed. This zero knowledge proof can be realized by using a technique due to Ronald Cramer, Ivan Damgård and Berry Schoenmakers (also called the CDS technique). ^[6] The interactive CDS technique can be made non-interactive by applying Fiat-Shamir heuristics. ^[7]

In the second step, the voter has the option to either confirm or cancel the selection. In case of "confirm", the DRE updates the aggregated values ${\displaystyle t}$ and ${\displaystyle s}$ in memory as below, deletes individual values ${\displaystyle r_{i}}$ and ${\displaystyle v_{i}}$, and marks the ballot as "confirmed" on the receipt.

${\displaystyle t=\sum v_{i},s=\sum r_{i}}$.

In case of “cancel”, the DRE reveals ${\displaystyle r_{i}}$ and ${\displaystyle v_{i}}$ on the receipt, marks the ballot as "cancelled" and prompts the voter to choose again. The voter can check if the printed ${\displaystyle v_{i}}$ matches his previous selection and raise a dispute if it does not. The voter can cancel as many ballots as he wishes but can only cast one confirmed ballot. The canceling option allows the voter to verify if the data printed on the receipt during the first step corresponds to the correct encryption of the voter's choice, hence ensuring the vote is "cast as intended". This follows the same approach of voter-initiated auditing as proposed by Joshua Benaloh. ^[8] However, in DRE-ip, voter-initiated auditing is realized without requiring the voter to understand cryptography (the voter merely needs to check whether the printed plaintext ${\displaystyle v_{i}}$ is correct).

After voting is finished, the voter leaves the voting booth with one receipt for the confirmed ballot and zero or more receipts for the canceled ballots. The same data printed on the receipts are also published on a mirrored public election website (also known as a public bulletin board) with a digital signature to prove the data authenticity. To ensure the vote is "recorded as cast", the voter just needs to check if the same receipt has been published on the election website.

Tallying

Once the election has finished, the DRE publishes the final values ${\displaystyle t}$ and ${\displaystyle s}$ on the election website, in addition to all the receipts. Anyone will be able to verify the tallying integrity by checking the published audit data, in particular, whether the following two equations hold. This ensures that all votes are "tallied as recorded", which together with the earlier assurance on "cast as intended" and "recorded as cast" guarantees that the entire voting process is "end-to-end verifiable".

An "end-to-end verifiable" voting system is also said to be "software independent", a phrase coined by Ron Rivest. ^[9] The DRE-ip system differs from other E2E verifiable voting systems in that it does not require tallying authorities, hence the election management is much simpler.

${\displaystyle \prod R_{i}=g_{2}^{s}}$ and ${\displaystyle \prod Z_{i}=g_{1}^{s}g_{1}^{t}}$.

Real-world trial

Counts of voter preferences in the Gateshead e-voting Trial

A touch-screen based prototype of DRE-ip had been implemented and trialed in a polling station in Gateshead on 2 May 2019 during the 2019 United Kingdom local elections. ^{[2] [10]} During the trial, voters first voted as normal using paper ballots. Upon exiting the polling station, they were invited to participate in a voluntary trial of using a DRE-ip e-voting system for a dummy election. On average, it took each voter only 33 seconds to cast a vote on the DRE-ip system. ^[4]

As part of the trial, voters were asked to compare their voting experiences of using paper ballots and the DRE-ip e-voting system, and indicate which system they would prefer. Among the participating voters, 11 chose "strongly prefer paper", 9 chose "prefer paper", 16 chose "neutral", 23 chose "prefer e-voting", and 32 chose "strongly prefer e-voting". ^[4]

References

1. Shahandashti, Siamak F.; Hao, Feng (2016). "DRE-ip: A Verifiable E-Voting Scheme Without Tallying Authorities" (PDF). Computer Security – ESORICS 2016. Lecture Notes in Computer Science. Vol. 9879. pp. 223–240. doi:10.1007/978-3-319-45741-3_12. ISBN   978-3-319-45740-6.
2. Wakefield, Jane (2 May 2019). "E-voting trialled in local elections". BBC News.
3. Esposito, Jeffrey (8 December 2016). "Can Blockchain Technology Secure Digital Voting Systems?".
4. Hao, Feng; Wang, Shen; Bag, Samiran; Procter, Rob; Shahandashti, Siamak F; Mehrnezhad, Maryam; Toreini, Ehsan; Metere, Roberto; Liu, Lana (2020). "End-to-End Verifiable E-Voting Trial for Polling Station Voting" (PDF). IEEE Security & Privacy. 18 (6): 6–13. doi:10.1109/MSEC.2020.3002728. S2CID   219616040.
5. Baudron, Olivier; Fouque, Pierre-Alain; Pointcheval, David; Stern, Jacques; Poupard, Guillaume (1 August 2001). "Practical multi-candidate election system". Proceedings of the twentieth annual ACM symposium on Principles of distributed computing (PDF). Association for Computing Machinery. pp. 274–283. doi:10.1145/383962.384044. ISBN   1581133839. S2CID   1702409.
6. Cramer, Ronald; Damgård, Ivan; Schoenmakers, Berry (1994). "Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols". Advances in Cryptology — CRYPTO '94. Lecture Notes in Computer Science. Vol. 839. Springer. pp. 174–187. doi:10.1007/3-540-48658-5_19. ISBN   978-3-540-58333-2. S2CID   1556546.
7. Fiat, Amos; Shamir, Adi (1987). "How to Prove Yourself: Practical Solutions to Identification and Signature Problems". Advances in Cryptology — CRYPTO' 86. Lecture Notes in Computer Science. Vol. 263. Springer. pp. 186–194. doi: 10.1007/3-540-47721-7_12 . ISBN   978-3-540-18047-0.
8. Benaloh, Josh (6 August 2007). "Ballot casting assurance via voter-initiated poll station auditing". Proceedings of the USENIX Workshop on Accurate Electronic Voting Technology. USENIX Association: 14.
9. Rivest, Ronald L (28 October 2008). "On the notion of 'software independence' in voting systems". Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences. 366 (1881): 3759–3767. Bibcode:2008RSPTA.366.3759R. doi: 10.1098/rsta.2008.0149 . PMID   18684694.
10. "Gateshead to host prototype e-voting trial - Gateshead Council". www.gateshead.gov.uk.