The ThreeBallot Voting System
Ronald L. Rivest
Computer Science and Artificial Intelligence Laboratory
Massachusetts Institute of Technology
Cambridge,
MA 02139
October 1, 2006?

Abstract

We present a new paper-based voting method with interesting security properties. The attempt here is to see if one can achieve the same security properties of recently proposed cryptographic voting protocols, but without using any cryptography, using only paper ballots. We partially succeed. (Initially, I thought the proposal accomplished this goal, but several readers discovered a vote-buying attack (see Section 4.4) that appears to be rather di?cult to fix without making the resulting system much less usable in practice. Currently, this paper should thus be viewed more as an academic proposal than a practical proposal. Perhaps some variation on these ideas in this paper might still turn out to be of practical use. The &lquot;OneBallot with Exchanged Receipts&rquot; system sketched at the end of Section 5.3.1, looks particularly promising at the moment. . . ) The principles of ThreeBallot are simple and easy to understand. In this proposal, not only can each voter verify that her vote is recorded as she intended, but she gets a &lquot;receipt&rquot; that she can take home that can be used later to verify that her vote is actually included in the final tally. Her receipt, however, does not allow her to prove to anyone else how she voted. In this &lquot;ThreeBallot&rquot; voting system, each voter casts three paper ballots, with certain restrictions on how they may be filled out, so the tallying works. These paper ballots are of course &lquot;voter-verifiable.&rquot; All ballots cast are scanned and published on a web site, so anyone may correctly compute the election result. A voter receives a copy of one of her ballots as her &lquot;receipt&rquot;, which she may take home. Only the voter knows which ballot she copied for her receipt. The voter is unable to use her receipt to prove how she voted or to sell her vote, as the receipt doesn’t reveal how she voted. A voter can check that the web site contains a ballot matching her receipt. Deletion or modification of ballots is thus detectable; so the integrity of the election is verifiable.

? The latest version of this paper can always be found at http://theory.csail.mit.edu/~rivest/ Rivest-TheThreeBallotVotingSystem.pdf

Introduction

Designing secure voting systems is tough, since the constraints are apparently contradictory. In particular, the requirement for voter privacy (no one should know how Alice voted, even if Alice wants them to know) seems to contradict verifiability (how can Alice verify that her vote was counted as she intended?). The proposal presented here is an attempt to satisfy these constraints without the use of cryptograpy. We get pretty close… Like most cryptographic proposals, ThreeBallot uses a public &lquot;bulletin board&rquot;–a public web site where election officials post copies of all of the cast ballots (there will be 3n of them if there are n voters) and a list of the names of the voters who voted. (Some states might use voter ID’s rather than voter names.) One key principle of ThreeBallot is to &lquot;vote by rows&rquot; and &lquot;cast by columns&rquot;. The ThreeBallot ballot can viewed as an array, where the voter places marks in rows corresponding to candidates, but then separates the columns and casts them separately, keeping a copy of one. ThreeBallot provides a nice level of end-to-end verifiability—the voter gets assurance that her vote was cast as intended and counted as cast, and that election officials haven’t tampered with the collection of ballots counted.

Background

We assume that the reader is somewhat familiar with voting systems. For more background, the following readings are recommended:

• Roy Saltman’s new book, The History and Politics 1 of Voting Technology [19] is an outstanding scholarly history of the evolution of voting technology.
• Andrew Gumbel’s book Steal This Vote [9] is an excellent, entertaining, and very readable review of election fraud in America.
• The Brennan Center for Justice has published an excellent report [1] on voting system security, with detailed discussions of specific threats and assessments of the risks they represent.
• Randell and Ryan’s recent excellent article, &lquot;Voting Technologies and Trust,&rquot; [15], which, like this paper, explores paper-based voting system architectures similar to those of cryptographic voting systems.
• Ben Adida’s recent PhD thesis [3] (particularly Chapter 1) reviews voting system requirements and cryptographic voting systems, before giving improved cryptographic voting systems.
• There are numerous web sites with information and links about voting and voting technology, such those of Doug Jones [10], myself [16], the CalTechMIT Voting Technology Project [14], ACCURATE [2], or the Election Assistance Commission [7], to name just a few. (Try googling &lquot;voting technology&rquot;.)

Each ballot has two parts: the upper &lquot;voting region,&rquot; and then the &lquot;ballot ID region&rquot; on the lower part. The voting region of a ballot contains the candidate names, each with an op-scan bubble that can be filled in by the voter. Each ballot has a distinct ballot ID, di?erent from the ID’s of other ballots on its multi-ballot and from all other ballot ID’s. The ballot ID’s on the three ballots of a multi-ballot are unrelated in any way to each other, they are merely randomly assigned unique ballot ID’s, with no cryptographic or other significance. The ballot ID might be a long (e.g. 7-digit) number which is essentially random, or some other unique identifier, possibly in barcoded form. For now, we’ll assume that the ballot ID’s are pre-printed on the ballots, but we’ll see that there are security advantages to having them added later instead by the voter or by the &lquot;checker&rquot; (see Section 3.4).

Filling Out The Multi-Ballot

• The voter is given the following instructions for filling out the multi-ballot. See Figure 2 for an example of a filled-out multi-ballot.
• You have here three optical scan ballots arranged as three columns; you will be casting all three ballots.
• Proceed row by row through the multi-ballot. Each row corresponds to one candidate. There are three &lquot;bubbles&rquot; in a row, one on each ballot.
• To vote FOR a candidate, you must fill in exactly two of the bubbles on that candidate’s row. You may choose arbitrarily which two bubbles in that row to fill in. (It doesn’t matter, as all three ballots will be cast.)
• To vote AGAINST a candidate (i.e., to not vote FOR the candidate, or to cast a &lquot;null&rquot; vote for that candidate), you must fill in exactly one of the bubbles on that candidate’s row. You may choose arbitrarily which bubble in that row to fill in. (It doesn’t matter, as all three ballots will be cast.)
• You must fill in at least one bubble in each row; your multi-ballot will not be accepted if a row is left entirely blank.
• You may not fill in all three bubbles in a row; your multi-ballot will not be accepted if a row has all three bubbles filled in.
• You may vote FOR at most one candidate per race, unless indicated otherwise (In some races, you are allowed to vote FOR several candidates, up to a specified maximum number.) It is OK to vote AGAINST all candidates. 2

Details

We now describe the ThreeBallot voting system in more detail.

[…]

Read the rest of this paper at Scribd.

This entry was posted on Tuesday, March 4th, 2008 at 10:05 am and is filed under Beautiful, Geekn, NIR, Someone Clever Said, Wishware, Yes yes yes!.