Direct Recording Electronic with integrity

Short description: E2E verifiable e-voting system

Direct Recording Electronic with Integrity (DRE-i) is an End-to-End (E2E) verifiable e-voting system, first designed by Feng Hao and Matthew Kreeger in 2010 and formally published in 2014 with additional authors Brian Randell, Dylan Clarke, Siamak Shahandashti, and Peter Hyun-Jeen Lee.

DRE-i is the first E2E verifiable e-voting system without involving any tallying authorities. The authors call such a tallying-authority-free E2E voting system "self-enforcing e-voting". The removal of tallying authorities is realized in DRE-i by pre-computing encrypted ballots in a structured way such that after the election, multiplying the ciphertexts will cancel out all the random factors, hence allowing any public observer to verify the tallying integrity. An improved version called DRE-i with enhanced privacy (DRE-ip), which adopts a real-time computation strategy instead of a pre-computation strategy, was successfully trialed in a polling station in Gateshead during the 2019 UK local elections.

Protocol

Let [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] be two large primes, where [math]\displaystyle{ q\,|\, p-1 }[/math]. Let [math]\displaystyle{ g }[/math] be a generator for the subgroup of [math]\displaystyle{ Z_p^* }[/math] of the prime order [math]\displaystyle{ q }[/math]. The parameters [math]\displaystyle{ (p, q, g) }[/math] are publicly agreed before the election. All modulo operations are performed with respect to the modulus [math]\displaystyle{ p }[/math]. The protocol can also be implemented using an elliptic curve, while the specification remains the same.

In the following example, the protocol is explained in the context of a single-candidate Yes/No election held at supervised polling stations using touch-screen DRE machines. 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 encoded values for candidates. The protocol can also be implemented for Internet voting as done for verifiable classroom voting.

The DRE-i protocol consists of three phases: setup, voting and tallying.

Setup

A DRE-i implementation may include a server and distributed DRE clients that connect to the server through a secure channel. Before the election, the server pre-computes a table as shown below.

Election Setup

Ballot No [math]\displaystyle{ i }[/math]	Random public key [math]\displaystyle{ g^{x_i} }[/math]	Restructured public key [math]\displaystyle{ g^{y_i} }[/math]	Cryptogram of yes-vote	Cryptogram of no-vote
[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ g^{x_1} }[/math]	[math]\displaystyle{ g^{y_1} }[/math]	[math]\displaystyle{ g^{x_1 y_1} }[/math], 1-out-of-2 ZKP	[math]\displaystyle{ g^{x_1 y_1} g }[/math], 1-out-of-2 ZKP
[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ g^{x_2} }[/math]	[math]\displaystyle{ g^{y_2} }[/math]	[math]\displaystyle{ g^{x_2 y_2} }[/math], 1-out-of-2 ZKP	[math]\displaystyle{ g^{x_2 y_2} g }[/math], 1-out-of-2 ZKP
...	...	...	...	...
[math]\displaystyle{ n }[/math]	[math]\displaystyle{ g^{x_n} }[/math]	[math]\displaystyle{ g^{y_n} }[/math]	[math]\displaystyle{ g^{x_n y_n} }[/math], 1-out-of-2 ZKP	[math]\displaystyle{ g^{x_n y_n} g }[/math], 1-out-of-2 ZKP

The table contains [math]\displaystyle{ n }[/math] rows with each row corresponding to a ballot. The number [math]\displaystyle{ n }[/math] is larger than the maximum number of the eligible voters to accommodate voter auditing. For each of the [math]\displaystyle{ n }[/math] ballots, the server chooses a random secret key [math]\displaystyle{ x_{i}\in_{R}[1,q-1] }[/math] and computes the corresponding public key [math]\displaystyle{ g^{x_{i}} }[/math]. When this has been done for all ballots, the server computes a restructured public key for every ballot as follows:

[math]\displaystyle{ g^{y_{i}}=\prod_{j\lt i}g^{x_{j}}/\prod_{j\gt i}g^{x_{j}} }[/math]

The Yes/No value in each ballot is encrypted in the form of [math]\displaystyle{ C_{i}=g^{x_{i}y_{i}}\cdot g^{v_{i}} }[/math] where [math]\displaystyle{ v_{i} }[/math] = 0 for "No" and 1 for "Yes". In addition, the machine computes a 1-out-of-2 Zero-knowledge proof (ZKP) for each Yes/No value. This is to ensure that the encrypted vote is well-formed. In other words, the value of the vote [math]\displaystyle{ v_{i} }[/math] can only be either 0 or 1. When the pre-computation is finished, the server publishes all the random public keys and restructured public keys (first three columns of the setup table) while keeping the Yes and No cryptograms secret (last two columns).

Voting

After authentication at a polling station, a voter obtains a random password or a smart card and logs onto a DRE client in a private voting booth. Casting a vote involves two basic steps.

• In step one, the voter selects a choice, "Yes" or "No", for the candidate shown on the touch screen. Upon the selection, the DRE machine prints the following data on the paper receipt: the ballot serial number [math]\displaystyle{ i }[/math], and the cryptogram of the selected choice, along with a digital signature for proving the data authenticity.

• In step two, the voter has the option to either confirm or cancel the previous selection. If the confirm option is chosen, the machine prints a “finish” on the paper receipt with a digital signature to indicate that a valid ballot has been cast. On the other hand, if the cancel option is selected, the machine prints the canceled candidate choice in plain text and the other cryptogram, along with a digital signature. In this case, a dummy vote has been cast. The voter should check if the canceled candidate choice printed on the receipt matches their selection; if not, a dispute should be raised to the election staff at the polling station. This "confirm/cancel" option enables a voter to verify that the vote is "cast as intended". The voter can cast as many dummy votes as they wish (subject to a reasonable limit), but is allowed to cast only one valid vote.

All receipts are published on a public bulletin board (i.e., a mirrored public website), together with digital signatures to prove the data authenticity. After voting, the voter leaves the voting booth with a receipt (or more than one receipt if the voter chooses to cancel ballots). The voter checks if the same content of the receipt is published on the bulletin board. This ensures their vote is "recorded as cast".

Tallying

When the election is finished, the server announces the tally of the "Yes" votes. In addition, it publishes the "Yes" and "No" cryptograms for all the unused ballots on the bulletin board, as if they were canceled by voters. An example of the bulletin board after the election is shown below.

An example of bulletin board after the election

Ballot No [math]\displaystyle{ i }[/math]	Random public key [math]\displaystyle{ g^{x_i} }[/math]	Restructured public key [math]\displaystyle{ g^{y_i} }[/math]	Published Votes [math]\displaystyle{ V_i }[/math]	ZKPs
[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ g^{x_1} }[/math]	[math]\displaystyle{ g^{y_1} }[/math]	Valid: [math]\displaystyle{ g^{x_1 y_1} }[/math]	a 1-out-of-2 ZKP
[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ g^{x_2} }[/math]	[math]\displaystyle{ g^{y_2} }[/math]	valid: [math]\displaystyle{ g^{x_2 y_2} }[/math]	a 1-out-of-2 ZKP
[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ g^{x_3} }[/math]	[math]\displaystyle{ g^{y_3} }[/math]	Cancelled: [math]\displaystyle{ g^{x_3 y_3} }[/math], [math]\displaystyle{ g^{x_3 y_3}\cdot g }[/math]	two 1-out-of-2 ZKPs
...	...	...	...	...
[math]\displaystyle{ n }[/math]	[math]\displaystyle{ g^{x_n} }[/math]	[math]\displaystyle{ g^{y_n} }[/math]	Unused: [math]\displaystyle{ g^{x_n y_n} }[/math], [math]\displaystyle{ g^{x_n y_n}\cdot g }[/math]	two 1-out-of-2 ZKPs

To verify the tally announced by the server, one simply multiplies all the published votes [math]\displaystyle{ V_i }[/math]. For canceled (dummy) and unused votes, only the no-votes are included in the multiplication.

[math]\displaystyle{ \prod_{i}V_{i}=\prod_i g^{x_{i}y_{i}}g^{v_{i}}=\prod_{i}g^{v_{i}}=g^{\sum_{i}v_{i}} }[/math]

In the above computation, all random factors are cancelled out on the exponent because [math]\displaystyle{ \sum_i {x_i y_i} = 0 }[/math] based on a cancellation technique used in Anonymous veto network. This leaves only [math]\displaystyle{ \sum_i v_i }[/math] on the exponent. To verify the tally [math]\displaystyle{ t }[/math] announced by the server, one just needs to check if the following equation holds. This ensures all votes are "tallied as recorded", which together with the earlier assurance on "cast as intended" and "recorded as cast" ensures the entire voting process is end-to-end verifiable.

[math]\displaystyle{ \prod_i V_i \; \overset{?}{=} \; g^t }[/math]

Implementation and practical applications

A prototype of a verifiable classroom voting system, based on the DRE-i protocol, has been implemented for pedagogical purposes and used for classroom voting and student prize competitions.

Limitation

The DRE-i protocol works by pre-computing the encrypted ballots. However, the pre-computed ballots need to be stored securely. If the pre-computed ballots are revealed, the secrecy of the votes will be compromised (however, the tallying integrity remains intact as guaranteed by the end-to-end verifiability). This limitation is addressed by using a different real-time computation strategy which leads to an improved protocol called DRE-i with enhanced privacy (DRE-ip). Both the DRE-i and DRE-ip protocols are end-to-end verifiable without tallying authorities, in contrast to other E2E verifiable e-voting schemes that involve tallying authorities for performing decryption and tallying operations.

See also

• DRE voting machine