Three Voting Protocols: ThreeBallot, VAV, and Twin

Ronald L. Rivest rivest AT mit.edu
Computer Science and Artificial Intelligence Laboratory
Massachusetts Institute of Technology, Cambridge, MA 02139

Warren D. Smith warren.wds AT gmail.com
Center for Range Voting,
June 2007 – (addenda here)

Abstract

We present three new paper-based voting methods with interesting security properties. Our goal is to achieve the same security properties as recently proposed cryptographic voting protocols, but using only paper ballots and no cryptography. From a security viewpoint we get reasonably close, particularly for short ballots. However, our proposals should probably be considered as more "academic" than "practical."

In these proposals, not only can each voter verify that her vote is recorded as intended, but she gets a "receipt" she can take home that can be used later to verify that her vote is actually included in the final tally. But her receipt does not allow her to prove to anyone else how she voted. All ballots cast are scanned and published in plaintext on a "public bulletin board" (web site), so anyone may correctly compute the election result.

In ThreeBallot, each voter casts three paper ballots, with certain restrictions on how they may be filled out. These paper ballots are of course "voter-verifiable."

A voter receives a copy of one of her ballots as her "receipt", 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.

VAV is like ThreeBallot, except that the ballot-marking rules are different: one ballot may "cancel" another (VAV = Vote/Anti-Vote/Vote). VAV is better suited to – i.e. yields better security properties for – Plurality and preference (Borda, Condorcet, IRV) voting, while ThreeBallot is better suited for Approval and Range voting.

Finally, we introduce "Floating Receipts," wherein voters may take home a copy of another voter's ballot (but she doesn't know whose). Floating Receipts are well-tuned to the security requirements of ThreeBallot-like schemes, and we examine protocols for achieving them.

Our final voting system, Twin, is based almost entirely on Floating Receipts. Each voter casts a single ballot and takes home a single receipt. Twin is quite simple and close to being practical.

1. 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 proposals presented here are an attempt to satisfy these constraints without cryptography. We get pretty close.

As in the cryptographic proposals, the proposals presented here use a "public bulletin board" (PBB) – a public web site where election officials post copies (but now in plaintext) of all of the cast ballots and a separate list of the names of the voters who voted. (Some states might post voter ID's rather than voter names.)

ThreeBallot, VAV, and Twin provide 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 on voting

Douglas W. Jones: Voting and Elections, Ronald L. Rivest: Voting resources page, CalTech/MIT Voting Technology Project, ACCURATE, Election Assistance Commission

Some important single-winner voting systems LevinNa95,Nurmi87

We now describe ThreeBallot in more detail. (An earlier version of ThreeBallot was posted Rivest06 in 2006; it contains some variations and discussion not included here for lack of space, but unfortunately also some flaws.)

Voting in ThreeBallot

Checking In at the Poll Site

The voter receives a paper "multi-ballot" to vote with. A multi-ballot consists of three paper ballots, printed on separate sheets. (They could be printed on a single sheet, with perforations for later separation, but this introduces some unnecessary security concerns, so we do not recommend this approach.)

We imagine that the poll-site has a bin of pre-printed blank ballots, and that the voter randomly selects three to form her multi-ballot.

The Multi-Ballot

ThreeBallot is perhaps most easily viewed as an extension of "mark-sense" ("optical scan" or "opscan") systems JonesOptical.

Each ballot in the multiballot is an identical complete ballot; think of it as a standard opscan ballot with the addition of a unique coded ballot ID on the bottom of each ballot. See Figure §. The upper voting region lists candidate names with matching op-scan bubbles that can be filled in (marked).

Each ballot ID is different from other ballot ID's on the multi-ballot or elsewhere. The ballot ID's on a multi-ballot are thus unrelated, random (but unique) ballot ID's.

The ballot ID might also be a long random string of symbols or some other unique identifier. For now, we assume that coded ballot ID's are pre-printed on the ballots, but we'll see there can be security advantages to having ballot ID's added later instead by the voter or by the "checker" (see §).

Filling Out The Multi-Ballot

For simplicity, we assume for now that we are using approval voting, the simplest form of voting, where the voter merely indicates for each candidate whether or not she approves of that candidate (see BramsFi83). For expository convenience, the voters will be female and everybody else male. This is like ordinary plurality voting except that voters may approve of more than one candidate in a race. Figure § gives an example of a filled-out multi-ballot.

We will call a filled-in bubble a mark (for a candidate).

The voter is given the following instructions for filling out the multi-ballot.

• You have three ballots; you will be casting all three. Proceed candidate by candidate through the multi-ballot. Each candidate has three "bubbles," one on each ballot.
• To vote for (approve) a candidate, fill in any two, but exactly two, of the bubbles for that candidate.
• To vote against (disapprove) a candidate fill in any one, but exactly one, of the bubbles for that candidate.
• Your ballot will not be accepted if any candidate has no bubbles filled or has three bubbles filled.
• You may vote for (approve) any number of candidates, including none of them or all of them.

Checking the Filled-Out Multi-Ballot

The voter takes her receipt, and goes home. (See § for a possible extension to "Floating Receipts", where the voter will take home a copy of some other voter's ballot instead of her own.)

Once home, a voter may check that her receipt matches a ballot posted on the PBB. We note that ballot ID's are coded to make them difficult to remember at the poll-site; but they can be coded with symbol strings that are still easy to type into a web site. (She could also give her receipt, or a copy of it, to someone else, to check for her, if she doesn't have a convenient way or is too busy to access the PBB herself. Adida06 discusses helper organizations. The helper organization should wait until election day is over and all ballots are posted before looking at the receipts received, so that it can not gain any possible statistical information on the voting trends during the day.)

If the PBB doesn't contain a matching ballot, she takes her receipt to an election official within two days and files a protest. The election official may examine the voter's receipt to determine its authenticity, and may authorize a rescan of the cast paper ballots.

Tallying and Announcing the Winners

The ballots can be tallied by anyone, since they are publicly posted in plaintext on the PBB. No decryption is needed.

The winners can be announced.

Each voter has marked once or twice for each candidate; the checker has enforced this.

So each candidate's tally will be "as usual," except that each total is inflated by the number n of voters. The election outcome is the same. For example, if candidates A, B, and C would ordinarily have received a, b, and c votes, respectively, then with ThreeBallot the final tallies will be n+a, n+b, and n+c; the true vote totals are obtained by subtracting n from the total number of marks for each candidate.

What about range voting?

For a Range rather than Approval voting election: same procedure works, except for these changes. Suppose the allowed scores are {0,1,2,…,R}, where, e.g. R=9 for single-digit range voting. Instead of marking (or not) a bubble to indicate approval or disapproval of that candidate the voter fills in a slot with a number in {0,1,2,…,R} (or by marking one of R+1 bubbles). The candidate constraints are that the sum S of the candidate's three scores satisfy R ≤ S ≤ 2R. The checker enforces this. To give Perot score P, 0 ≤ P ≤ R, she should make sure S = R+P. See Figure §.

This completes our description of the operation of the ThreeBallot voting system for Approval and Range voting.

Security Assumptions & Mechanisms

ThreeBallot has some unique concerns among voting systems, since the voter has as a receipt a copy of part of her vote, in plaintext, and all ballots cast are available in plaintext on the PBB.

Without some additional assumptions or mechanisms, the voter privacy of ThreeBallot can be attacked, as noted below. We now propose one assumption and one mechanism.

The Short Ballot Assumption (SBA) assumes that the ballot is short—there are many more voters in an election than ways to fill out an individual ballot—i.e., there are only a few races and only a few candidates in each race. That is, if the ballot has C candidates total, then (for approval voting) the number 2^C of voting patterns must be much smaller than the number of voters. Depending on the voting system used, the SBA may be more or less reasonable; for example a rank-order voting system with C candidates has C! possible voting patterns, which may easily exceed the number of voters. See Table §. It is reasonable to assume under the SBA that each possible ballot is likely to be cast by several voters. The security of all three of our secure voting protocols depends on the SBA.

An important related idea is debundling – separating different races, or even different candidates in the same race onto separate ballots, so that the SBA holds for each ballot.

With Approval and Range voting, the voter provides a rating for each candidate – "approve"/"disapprove," or a numerical score in, say, [0,9]. Her rating for Xerxes is independent of her rating for Yu. So in these voting systems it is unnecessary and indeed unnatural to force her to rate all the candidates in a race on the same ballot. With Range and Approval voting, ballots can be debundled all the way down to single candidates if desired, thus guaranteeing that the SBA holds.

However, for Plurality, all candidates must be on the same ballot, because votes for the different candidates are dependent —if you vote for Xerxes, you may not vote for Yu. A plurality race with many candidates may have to violate SBA. (Well, you can have a multi-page ballot with separate coded ID on each one, as long as they are checked simultaneously. Long candidate lists cause problems for many voting systems.)

There is a clear SBA/bundling trade-off. Debundling would have been essential to achieve SBA for approval or range voting for the 2006 Congo presidential election, which had C=33 candidates. But VAV (see §) could handle Plurality for this election with no debundling; VAV can also handle rank-order ballot elections when C! is well below the number of voters. In many cases no debundling may be needed.

"Floating Receipts" is a new security mechanism introduced in this paper (see §), wherein a voter may bring home a receipt that is a copy of some other voter's ballot, and/or extra copies of receipts could be "floating" around in unknown hands. That can provide additional helpful layers of anonymity or security.

Twin depends on floating receipts, while VAV and ThreeBallot do not, but one can add floating receipts as an extra security feature to either, so that these protocols become secure even against a wide class of collusive attacks (§). For simplicity we describe ThreeBallot and VAV without such collusion-protection, then will describe ways to add it in §.

ThreeBallot Security — Integrity

The two main voting system security requirements are integrity of election results and voter privacy. We begin with integrity.

The voter can check that

• a ballot matching her receipt is posted on the PBB in the list of cast ballots (using the coded ID as the lookup key),
• the total number of ballots on the PBB is three times the number of voters who voted (the list of voters who actually voted is also published on the PBB).

The first check has no analogue in most current voting systems. We'll see these checks allow detection of several kinds of fraud. Of course, one has to ensure that the new security mechanisms can't themselves be easily attacked.

Adding Ballots can be Detected

An adversary can't add ballots to the PBB without putting more voter names on the PBB, which makes the fraud detectable. (Grandma, did you really vote? Weren't you sick that day?) On this issue of ballot stuffing, ThreeBallot is little different from other voting systems; the best defense is public oversight of voter check-in process and the posting of lists of voters who voted.

Modifying or Deleting Ballots can be Detected

An adversary can't delete or modify any posted ballots, without risking a voter protesting that her receipt matches no ballot on the PBB. (The PBB has no ballot with the same ID, or shows one with different marks.)

Of course, an adversary might risk modifying just a few ballots, hoping to avoid detection since only 1/3 of the ballots are protected. It's key that nobody knows which 1/3, which assures that any large-scale fraud would get detected with even a low level of vigilance by voters or their proxies. (The actual chance of detecting such fraud can be computed with the usual sort of "auditing math" AslamPoRi07.)

E.g.: to detect a fixed level of fraud (e.g. 6%) with significant probability (e.g. 95%), only a fixed number of voters (in this case 50) need to check, no matter how large the electorate.

The receipt may need some additional authentication (cf. §5.3 of Adida06) to prevent voters from maliciously claiming that their (fabricated) receipt doesn't match any ballot on the PBB. This authentication could be a seal or sticker on the receipt, or (better) an unforgeable digital signature for {the vote on the receipt, the election-name ("2008 Presidential"), and the ballot ID}.

It is OK for the voter to let an official sign her receipt as an officially approved receipt, since voter privacy isn't threatened. However the digital-signing machine must not remember the ballot ID. This worrisome requirement can be avoided by not revealing the ID to the signer and not including it as part of the signed bit-string. In that case the digital signature would protect only the vote while the ballot ID would be protected by old-fashioned paper-and-ink anti\-forgery technology.

Attacking the Checker

The checker needs to be tested carefully. A maliciously modified checker could, e.g. allow some voters, by violating the row-constraints, to effectively have three votes!

Note that such illegal voting patterns can't be detected later, since the row-constraint can't be re-tested once the multi-ballot is split up. (Of course, in some cases you may be able to tell that such an attack has been mounted: e.g., if a candidate ends up with more than 2n marks.)

Thus, we see that there is some dependency of the correctness of the election outcome on the correctness of the checker (assuming that some voters would exploit an opportunity afforded by a defective checker).

On the other hand, the candidate conditions are exceptionally simple to check, and a simple hard-wired row-constraint checker may be sufficiently trustable that one can have confidence in its correct operation on election day.

One may compare this situation with other forms of VVPR (voter-verified paper records), such as DRE-VVPAT or ordinary opscan. ThreeBallot is like them in that the voter can directly verify her own paper ballot, to ensure that her intent has been captured correctly on paper. As with other VVPR methods we must worry about "casting multiple votes," and "ballot box stuffing." But ThreeBallot has an additional risk: that a corrupt checker would allow some voters to cast a "heavier" vote than others. But ThreeBallot allows voters to detect modification of the collection of cast ballots, whereas other VVPR schemes don't even attempt this. On balance ThreeBallot addresses better the more serious threats.

To compare this situation with that for cryptographic voting schemes: A bad checker in ThreeBallot might allow a voter to cast an invalid multi-ballot; cryptographic schemes either make such invalid voting impossible or require the voter to post with her vote a proof that her (encrypted) ballot is valid.

John Kelsey noted that a maliciously modified checker, since it knows which ballot is being copied as a receipt, might be able to encode this information on the ballots themselves (say by using a bit of steganography); a correspondingly corrupted scanner would then know which ballots it could scan incorrectly. This sort of mischievous behavior also needs to be prevented, by design of the checker, or by other controls.

The adversary may be able to buy voters' receipts as they leave, and then be able to manipulate the contents of the PBB. (This is a "collusive attack," § since the vote-buyer and the PBB staff must collude for it to work.)

Knowing that the voter has given up her ability to contest PBB corruption, the adversary alters the PBB copy of her corresponding ballot.

Voters should thus be cautioned not to casually discard or give away (the only copy of) their receipts. If she uses a "helper organization" (e.g. the ACLU) as a proxy to check PBB integrity, the voter might give the helper organization a copy of her receipt, rather than the original. (The receipt might be signed at the poll site with a bar-coded digital signature, so a copy is as "authentic" as the original here.)

There should also be strong safeguards on PBB modification for a "layered defense." Current voting systems rely for their security entirely on such safeguards, so ThreeBallot can't help but be an improvement.

This attack works for many cryptographic schemes in the literature; the only prior countermeasures we know of are by §5.4 of RyanPe05, who suggest both voter education and having election officials keeping additional copies of the receipts at the polling site, and §5.2 of KarlofSaWa05, who suggest voter education.

Chain Voting

In the chain voting JonesChain attack on paper-based voting systems, a buyer hands a voter a pre-marked ballot. She casts it as "her" vote, then gives the blank ballot she should have used to the vote-buyer (receiving payment and allowing the cycle to begin anew). The usual remedy ensures that a voter casts the ballot she was given. Ballots have tear-off stubs. When the voter first picks up a blank ballot, a random number (e.g. from dice) is written on the stub and recorded under that voter's name on a list; when she casts her ballot the stub number is checked, and the stub torn off and visibly destroyed. Poll procedures ensure voters cannot leave then re-enter the polls with ballots.

Voter Privacy in ThreeBallot

We now turn to the second main security requirement: maintaining voter privacy.

The first of Professor Michael Shamos's "Commandments" Shamos93 on voting is:

Thou shalt keep each voter's choices an inviolable secret.

A voter should not be able to violate her own privacy, even if she wishes: she should be unable to convince anyone else that she voted in a particular way. Otherwise she could sell her vote. (This is why we strongly favor pollsite voting, with its enforced voter isolation during voting, over remote voting schemes such vote-by-mail, vote-by-phone, or vote-by-Internet.)

What could the voter show an adversary to persuade the adversary of how she voted? Three sorts of evidence are available:

• physical evidence she brings away from the the voting session (such as her voting receipt),
• other evidence the voter may bring away from the voting session (such as ballot ID's she may have memorized or photographed), and
• the cast ballots on the PBB.

Can Receipt violate Voter Privacy?

Can the voter violate her own privacy using her receipt?

Nothing prevents a voter from voting entirely honestly on her first ballot. If she then copies that first ballot for her receipt, it indicates exactly how her votes will be tallied.

But this receipt is at best a "reminder" of how she voted, not a proof that will convince anyone else as to how she voted. She is unable to intentionally violate her own privacy by showing someone else her receipt. (We have already argued, in §, that a voter's receipt, by itself, bears no information about how a voter voted. So it cannot violate voter privacy.)

Can the Receipt be linked with its other two ballots?

No one should be able to reliably and convincingly link together the three ballots on the PBB that constitute an original cast multi-ballot. Otherwise, the voter's privacy is at risk.

If the multi-ballot were to be printed on a single sheet of paper (e.g., with perforations), then there would be a risk that the printer could remember which triples of ballot ID's were valid. (Some cryptographic voting schemes, such as Prêt à Voter RyanPe05 also have have security vulnerabilities at the ballot printers.) However, with our recommended procedure of having the voter randomly select three ballots from a bin to constitute her multiballot, this isn't a problem.

We have five approaches for this:
1. Printing ballot ID's in a coded way, using punctuation and other symbols. Advantages: (a) simple. (b) hard for the voter to remember. Unfortunately it's easy for a voter to copy manually. 2. Barcode. Somewhat harder to copy, but also harder to read later when looking the ballot up on the PBB.
3. ID's could be under "scratch-off." That's more secure, but precludes cheap and common printing equipment.
4. Ballot ID's could be printed using "visual cryptography" NaorSh94; with this approach ballot IDs by themselves are just "random dots" which convey no information whatever. The voter is given the plastic overlay that allows her to read the ballot ID only after she receives her receipt. Almost impossible to copy or remember without a (incriminating) camera or overlay.
5. (The "Shamos checker".) Michael Shamos suggested the following nifty approach, which prevents the voter from ever seeing the ballot IDs of the two ballots not copied:

• All multi-ballots are initially identical and contain no ballot ID's.
• When the checker determines that a multi-ballot is OK, it prints three randomly generated ballot ID's on the three ballots, but retains the ballots for now.
• The voter selects which ballot she wants copied for her receipt.
• The checker spits out both the selected ballot and a copy of it (her receipt), and puts the other two ballots into a holding bin.
• She checks that the receipt and the selected ballot match. If so, she puts the selected ballot into the ballot box and presses the "Done" button on the checker, which empties the holding bin (containing her other two ballots) into the ballot box, in such a way that she never sees their ballot ID's. If not, she pushes the "I got a bad receipt" button on the checker (which now empties the holding bin with her other two ballots into a spoiled ballot bucket), complains to a pollworker by showing her ballot and unequal receipt, and votes again.

Risk of Copying

It is better not to let the voter use a generic copying machine to make her receipt, lest she make a copy of all three ballots.

The procedures we've suggested are designed to ensure that the voter only gets a copy of one of her three ballots, and can't copy her other ballots or their ID's.

Reconstruction Attack

In a "reconstruction" attack the adversary examines all possible triples of ballots from the PBB, and determines which of them form legal ThreeBallot ballots.

The information gained may, in some cases, be sufficient to determine how an individual voter voted, when taken together with either the ballot ID available on the voter's receipt, or if that voter made an agreement beforehand (like the three-pattern attack).

Under the Short Ballot Assumption, there will be many ways to piece ballots together, and the adversary gains insufficient information to combine triples of ballots to infer the voter's vote.

Strauss Strauss06B provides some empirical evidence on the effectiveness of reconstruction attacks for various sized ballots, as do Jones et al. JonesJuBe06,BeloteJoJu06. Also see Cichon et al. CichonKuWe07 for some careful analysis of how short a ballot needs to be to provide voter privacy in ThreeBallot.

Early publication "threat"

Some critics have worried that PBB posts or "leaks" could reveal information about our vote totals (say, halfway through the election) "early"; while with full-cryptographic voting protocols, supposedly that couldn't happen. The simplest approach is not to publish the PBB until polls close, as in §.

But one of us (WDS) feels this really is not a security issue at all; it is a voting method issue. After all, exit polls will defeat any security measures (and restricting exit poll publication would be unconstitutional, cause more problems than it would solve, and would not prevent "secret" exit polls whose results were revealed only to the right people in private). WDS feels the real problem is mainly that the Plurality voting method (§) is highly vulnerable to insincere "strategic voting," whereas, e.g, in Approval and Range voting strategic decisions based on early returns have less importance.

ThreeBallot Usability

For Voters

The ThreeBallot voting process is more complex than current conventional voting systems, so the impact on usability must be considered. An interesting preliminary field study JonesJuBe06 indicates that ThreeBallot has significant usability issues.

Of course, the main method for making sure that the voting system works well for voters is voter education. Although ThreeBallot is new, it is nonetheless quite workable, and a little voter education may make its operation clear for many or most voters.

However, if a voter makes a mistake, the process of recasting a ballot is not so simple. (Well, it's like opscan: you need to start over with a clean ballot.)

Voters who have difficulty with filling out a ThreeBallot multiballot could be given simplified instructions (e.g. always fill in the bubbles for a candidate from left to right).

Probably the best approach is to merely let voters who have undue difficulty with ThreeBallot use conventional ("OneBallot") methods, since you can "mix" OneBallot and ThreeBallot ballots together (§).

Still, any increase in the voting complexity will cause additional voter confusion and problems, so there is certainly a potential price to be paid, in terms of usability, for the security benefits of ThreeBallot.

For Election Officials & Workers

ThreeBallot causes extra work for pollworkers, since the number of paper ballots cast that need to be handled is now three times as large as with conventional ("OneBallot") voting. Furthermore ThreeBallot may encourage inefficient use of the ballot page as compared to traditional opscan layouts, requiring even more ballot pages.

The benefit that compensates for this extra work and extra usability problems for voters, is, of course, a higher degree of confidence in the integrity of the voting process and election results.

Variations and Improvements

We have presented and discussed the main architectural components of a ThreeBallot voting scheme: vote-by-candidates (rows) but cast-by-columns, take a column copy home as a receipt, and post all ballots on a PBB. We now review further variations and extensions.

ThreeBallot Range and Approval voting trivially permit "write-in" votes if voter-ratings of write-in candidates are handled debundled on separate ballots. (If they were bundled on the same ballot as the regular candidates, voters could attempt to identify their ballots by writing-in unique "candidate" names. Cf. KiayiasYu04.) Range voting with high-precision scores also has to be forbidden for the same reason (insist on single-digit range voting).

Albeit in principle it could be handled by a further level of debundling – down below single candidates into single digits of large numbers.

Our schemes for plurality and rank-order voting systems unfortunately cannot handle write-in candidates.

Although we prefer to handle plurality voting with VAV (§), ThreeBallot can do it too; we add "race constraints" to the "row-constraints" already discussed; each race constraint permits the voter to approve at most one candidate per race. This makes the checker more complicated (it now must know which candidates are in the same race), but otherwise not much changes. (We note that an individual ballot might be part of a legal threeballot, yet now look like an illegal overvote; that is OK.)

ThreeBallot does not work at all for ranked preference voting systems such as Borda, IRV, %(instant runoff voting), or Condorcet. Our VAV protocol (§) does.

ThreeBallot – Summary

Cryptographic techniques can also provide all of the security properties of ThreeBallot, and more. See Chaum Chaum04, Chaum et al. ChaumRySc04, Ryan et al. RyanSc06,RyanPe05, Karloff et al. KarlofSaWa05, Smith Smith05, SmithV1, SmithV2, and Adida Adida06 for presentations and discussions of cryptographic voting methods.

However, ThreeBallot achieves almost as good security properties, without cryptography.

We note for the record that we have nothing against cryptographic voting methods—they are very appealing, although a bit complex.

That's why this paper's goal is to see to what extent the security properties of cryptographic schemes can be achieved in a "low-tech" manner, without cryptography.

What happens after our protocols prove there was fraud? Election systems need a more graceful way to recover from errors than merely declaring failure; we somehow need to insert accountability and corrective feedback. Our protocols, while imperfect in that respect, seem as good, and in some ways superior, to present-day paper balloting. The potential for "superiority" is since in our schemes with preprinted ballot IDs, we can set up a chain of custody for all ballots within ballot-number intervals. E.g, there will be records saying "Joe Schnoz obtained custody of ballots #785400-823100 at 6pm on 30 September." Now suppose some cast ballots vanished or were altered, or fake voters voted (on stolen blank ballots). Then we know exactly who was supposed to have custody of the ballots with those numbers and when, so we can try to assign blame and stop the corruption.

Recovery from some errors (e.g. too many ballots on the PBB) can be problematic. Rescanning the cast paper ballots may suffice to fix many problems. ThreeBallot is really just a paper ballot scheme, with the usual issues and remedies, except that voters cast three ballots constructed in a novel manner, and have a new protocol for checking that at least one of their ballots is counted in the final ballot box.

ThreeBallot also has pedagogic value as a "stepping stone" when explaining cryptographic voting protocols, as it strives to achieve similar properties with simpler methods.

Note that the voter is getting not only verification that her vote is "cast as intended" (as with most VVPAT or paper-trail systems), but also getting evidence that her vote is actually affecting the final tally as it should.

So, the ThreeBallot voting system seems to give a nice level of end-to-end verifiability with "plausible" (but not great) user interface, without cryptography.

In VAV each ballot is pre-marked as either a "Vote" (positive, marked "V"), or an "Anti-Vote" (negative, marked "A"). The voter casts one two Votes and one Anti-Vote, and we demand that one of the Votes exactly cancels the Anti-Vote (it is identical except for the A/V indicators). See Figure §.

She takes home as her receipt a copy of any one of her three ballots, just as in ThreeBallot.

VAV can support any kind of voting system.

It is important that each ballot be pre-labeled as "V" or "A" and that the talliers explicitly eliminate each A-antivote and a matching V-vote before tallying. (One could imagine a VAV-like scheme without explicit VAV labeling, and while that would work for Condorcet and Borda

This was noted by Michael A. Rouse; you reverse order for the anti-vote.

The only concern is that each Vote shouldn't contain too much information – that would allow the voter to cast a ballot highly likely to be unique, thus allowing her to sell her vote to a buyer who can verify its presence on the PBB. Thus, we are again assuming a version of the Short Ballot Assumption (SBA). The reason that VAV is superior to ThreeBallot for plurality voting, is that with VAV in a C-candidate race, the number of possible ballot-patterns is C – small, easily permitting satisfaction of the SBA – whereas with ThreeBallot it would have been 2^C – large, often forcing violation of the SBA.

VAV and OneBallot voting can also be mixed as in § (the OneBallots are all "V").

"Floating Receipts" is a simple and powerful security-enhancing idea. How can it help? ThreeBallot and VAV, as we have described them, can unfortunately be vulnerable to collusive attacks (e.g. modifying the PBB after obtaining some receipts) as described in §.

The method proposed here ("floating receipts") addresses these concerns by having voters take home copies of receipts other than their own. Essentially, there is a big bin of receipts, and voters first make a copy (to take home) of one receipt already in the bin (leaving the original in the bin), then %randomly toss their own original receipt into the bin. This method has the following properties:

Anonymity: No one knows which voter cast the ballot corresponding to a given receipt copy with any useful probability.

Exchange: No voter takes home a copy of her own receipt.

Coverage: A constant fraction of the original receipts are copied, with high probability (and there is no way for anybody to know what that subset is).

Collusion-Resistance: An adversary has no efficient method for confidently obtaining all the copies of a given receipt.

The Exchange property fights any attacks wherein an adversary pays for receipts of a given form. Collusion-Resistance fights attacks where the adversary collects all copies of a given receipt, so as to evade PBB manipulation detection. Coverage ensures that any significant PBB manipulation has a good probability of being detected. And Anonymity is useful for use in voting schemes (like "Twin" below) that would otherwise not have anonymity.

Voters traditionally have been anonymous "going into" the voting process (submitting ballots). Floating receipts now provide a new layer of anonymization "coming out" (taking home receipt copies).

Note that to check the integrity of the PBB, the voter only needs to bring home a copy of some cast ballot. We admit she would have more motivation to check her own ballot, but assume that many voters will check anyway.

Making "floating receipts"

The method here, though developed independently, can be also usefully be viewed as an extension of the earlier "Farnel" protocol (see A.J. Devegili Devegili01,AraujoCuWiTa06) to handle ballot receipts rather than ballots themselves; in the Farnel protocol no take-home receipts were envisioned.

Let T be a constant (e.g. T=20), significantly less than the number of voters, such that 1/T is a "small" probability. There is an initially empty "bin" (receipt reservoir). %no longer fixed size 2T.

Each voter begins our "floating receipt" protocol having cast her ballots, and having the receipt. So far everything is as in ThreeBallot or VAV but we now consider adding an additional Floating Receipts layer of defense.

[Phase I] The first T voters put their original receipts in the bin, and receive nothing to take home.

[Phase II] After that every voter: (a) gets a copy to take home of a receipt chosen randomly from the bin (the original is returned to the bin), and then (b) deposits her own original receipt into the bin. The take-home receipt copies are certified as authentic as the voter leaves, with a notary-like stamp or a digital signature (as long as the signing device doesn't record what it sees). When the voter leaves she might also be required to sign the registration book to certify that she has voted.

After the polls close, the final contents of the bin may be discarded or published in some manner

We could also add an optional Phase III in which the first T voters return to the polls at the end of the day and collect "delayed" receipts as in IIa – or we might only demand phase III for voting machines on which < 2T voters voted (i.e. precisely those seen ex post facto to have violated our assumption that T was small compared to the number of voters).

The voter may use her receipt copy to check the PBB integrity and, if necessary, file a protest.

Clearly, no voter gets a copy of her own receipt to take home; she only gets copies of receipts from randomly chosen previous voters. That is, our "floating receipt" protocol satisfies both the Anonymity and Exchange properties. The protocol also satisfies the Coverage property, since, e.g, each of the first half of the deposited receipts has probability at least 1- &prod_n+1≤n≤2n(1-1/m) = 1/2 of being selected at least once for copying. And it satisfies Collusion-Resistance since it is not clear from a receipt copy when the corresponding original receipt was deposited, and any voter since the original deposit might also have a copy of that receipt.

We note that even if all voters conspire to sell their votes, there is no way to prove how any one of them voted, even if they all reveal the receipt copies they brought home.

Floating receipts are quite powerful; in the next section we examine a voting system based almost entirely on the use of floating receipts.

Each voter simply marks a ballot and puts it in a bin, receiving a copy of a random previously-cast ballot from that bin as her take-home receipt. (Ballots have ID numbers hidden under scratch-off. A checking machine can check that the marking is valid and the scratch-off remains unscratched, and only if so is the ballot placed in the bin; the scratch-off is automatically removed as it enters. The bin can be transparent enough so that everybody can see this all is happening, although not transparent enough to permit voters to read their ballot's ID number. Only voters later than the Tth receive take-home receipts, although an optional "phase III" can be added as in §.)

Juho Laatu and D.D.K.Sleator also emailed us some related proposals.

Watchdog groups, or anybody with a computer, could provide publicly-usable digital-signature verifiers everywhere.

Twin is simple; the voter need not do any arithmetic, nor worry about strange consistency conditions for multiple ballots. You can't sell your vote because your receipt is a copy of somebody else's ballot. Talliers can't manipulate the PBB without risking detection, since there is a certified copy of most ballots somewhere and they don't know which ones and who has the copies. Talliers can't add or delete ballots (cf. §). "Dumpster-diving" or other methods to collect discarded receipts, followed by cheating to alter the corresponding PBB ballots, are unsafe for cheaters because the collusion-resistance property of floating receipts.

One worry with Twin is that since voters cannot verify their own ballots, a small political party may feel that only a tiny fraction of its ballots are verified by loyal party members. But a major party may well be motivated to prevent fraud against a minor party in cases where it alters an election, and voter education should stress that voters should check whatever receipt they were given, as part of their civic duty.

6. Conclusion

Our new voting system, ThreeBallot, allows voters to verify that their votes are cast as intended, and to check that their vote is included in the final tally. All cast ballots are published, tampering with votes can be detected, and vote-privacy seems unbreachable, given SBA.

This is the first time such end-to-end verifiability has been obtained without the use of cryptographic techniques. Indeed the use of powerful computerized DRE machines with our protocols is actually bad because those computers might be, e.g, remembering things, such as ballot-triples, which would destroy our security. We require simple and manifestly un-powerful machines.

However, after the ballots have been cast and checked and the voters have gotten their receipts, from then onward everything could be computerized, and it would not matter if those computers perhaps were penetrated, in the sense that anything they did wrong or fraudulently would be detectable.

All three systems can be "mixed" with ordinary OneBallot voting as in §; this exerts a protective effect on the ordinary ballots and provides an "easy upgrade path."

7. Acknowledgments

We thank Ben Adida, Andrew Appel, Jessy Baker, Alan Bawden, David Chaum, Ronald Crane, Chris Crutchfield, Kathy Dopp, John Kelsey, Jan Kok, Juho Laatu, Silvio Micali, Peter Neumann, Ben Riva, Alex Rivest, Michael A. Rouse, Julie Shamos, Michael Shamos, Emily Shen, Clay Shentrup, Daniel D.K. Sleator, Charlie Strauss, Jeroen van de Graaf, and Dan Wallach for feedback and comments. (But errors are ours.)

8. References