Direct Recording Electronic with integrity

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 ^[1] and formally published in 2014 with additional authors Brian Randell, Dylan Clarke, Siamak Shahandashti, and Peter Hyun-Jeen Lee. ^[2]

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". ^[2] 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. ^[3]

Protocol

Let ${\displaystyle p}$ and ${\displaystyle q}$ be two large primes, where ${\textstyle q\,|\,p-1}$. Let ${\displaystyle g}$ be a generator for the subgroup of ${\displaystyle Z_{p}^{*}}$ of the prime order ${\displaystyle q}$. The parameters ${\displaystyle (p,q,g)}$ are publicly agreed before the election. All modulo operations are performed with respect to the modulus ${\displaystyle p}$. 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. ^[4]

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 ${\displaystyle i}$	Random public key ${\displaystyle g^{x_{i}}}$	Restructured public key ${\displaystyle g^{y_{i}}}$	Cryptogram of yes-vote	Cryptogram of no-vote
${\displaystyle 1}$	${\displaystyle g^{x_{1}}}$	${\displaystyle g^{y_{1}}}$	${\displaystyle g^{x_{1}y_{1}}}$, 1-out-of-2 ZKP	${\displaystyle g^{x_{1}y_{1}}g}$, 1-out-of-2 ZKP
${\displaystyle 2}$	${\displaystyle g^{x_{2}}}$	${\displaystyle g^{y_{2}}}$	${\displaystyle g^{x_{2}y_{2}}}$, 1-out-of-2 ZKP	${\displaystyle g^{x_{2}y_{2}}g}$, 1-out-of-2 ZKP
...	...	...	...	...
${\displaystyle n}$	${\displaystyle g^{x_{n}}}$	${\displaystyle g^{y_{n}}}$	${\displaystyle g^{x_{n}y_{n}}}$, 1-out-of-2 ZKP	${\displaystyle g^{x_{n}y_{n}}g}$, 1-out-of-2 ZKP

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

${\displaystyle g^{y_{i}}=\prod _{j<i}g^{x_{j}}/\prod _{j>i}g^{x_{j}}}$

The Yes/No value in each ballot is encrypted in the form of ${\displaystyle C_{i}=g^{x_{i}y_{i}}\cdot g^{v_{i}}}$ where ${\displaystyle v_{i}}$ = 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 ${\displaystyle v_{i}}$ 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 ${\displaystyle i}$, 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 ${\displaystyle i}$	Random public key ${\displaystyle g^{x_{i}}}$	Restructured public key ${\displaystyle g^{y_{i}}}$	Published Votes ${\displaystyle V_{i}}$	ZKPs
${\displaystyle 1}$	${\displaystyle g^{x_{1}}}$	${\displaystyle g^{y_{1}}}$	Valid: ${\displaystyle g^{x_{1}y_{1}}}$	a 1-out-of-2 ZKP
${\displaystyle 2}$	${\displaystyle g^{x_{2}}}$	${\displaystyle g^{y_{2}}}$	valid: ${\displaystyle g^{x_{2}y_{2}}}$	a 1-out-of-2 ZKP
${\displaystyle 3}$	${\displaystyle g^{x_{3}}}$	${\displaystyle g^{y_{3}}}$	Cancelled: ${\displaystyle g^{x_{3}y_{3}}}$, ${\displaystyle g^{x_{3}y_{3}}\cdot g}$	two 1-out-of-2 ZKPs
...	...	...	...	...
${\displaystyle n}$	${\displaystyle g^{x_{n}}}$	${\displaystyle g^{y_{n}}}$	Unused: ${\displaystyle g^{x_{n}y_{n}}}$, ${\displaystyle g^{x_{n}y_{n}}\cdot g}$	two 1-out-of-2 ZKPs

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

${\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}}}$

In the above computation, all random factors are cancelled out on the exponent because ${\textstyle \sum _{i}{x_{i}y_{i}}=0}$ based on a cancellation technique used in Anonymous veto network. This leaves only ${\textstyle \sum _{i}v_{i}}$ on the exponent. To verify the tally ${\displaystyle t}$ 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.

${\displaystyle \prod _{i}V_{i}\;{\overset {?}{=}}\;g^{t}}$

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. ^[4]

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

References

1. Hao, Feng; Kreeger, Matthew Nicolas (2010). "Every Vote Counts: Ensuring Integrity in Large-Scale DRE-based Electronic Voting" (PDF).
2. Feng Hao, Matthew N. Kreeger, Brian Randell, Dylan Clarke, Siamak F. Shahandashti, and Peter Hyun-Jeen Lee. "Every Vote Counts: Ensuring Integrity in Large-Scale Electronic Voting". USENIX Journal of Election Technology and Systems (JETS) Volume 2, Number 3, July 2014
3. "E-voting by touch-screen trialled in local elections". BBC News. 2 May 2019.
4. Hao, Feng; Clarke, Dylan; Randell, Brian; Shahandashti, Siamak F. (January 2018). "Verifiable Classroom Voting in Practice" (PDF). IEEE Security & Privacy. 16 (1): 72–81. doi:10.1109/MSP.2018.1331032.