ThreeBallot is a new voting method from Ron Rivest that is supposed to make elections more secure without compromising voter privacy. It got favorable reviews at first – Michael Shamos even endorsed it at a congressional hearing – but further analysis shows that it has some serious problems. The story of ThreeBallot and its difficulties is a good illustration of why voting security is hard, and also (I hope) an interesting story in its own right.
One reason secure voting is hard is that it must meet seemingly contradictory goals. On the one hand, votes must be counted as cast, meaning the vote totals reported at the end are the correct summation of the ballots actually cast by the voters. The obvious way to guarantee this is to build a careful audit trail connecting each voter to a ballot and each ballot to the final tally. But this is at odds with the secret ballot requirement, which says that there can be no way to connect a particular voter to a particular ballot. Importantly, this last requirement must hold even if the voter wants to reveal his ballot, because letting a voter prove how he voted opens the door to coercion and vote-buying.
If we were willing to abandon the secret ballot, we could help secure elections by giving each voter a receipt to take home, with a unique serial number and the list of votes cast, and publishing all of the ballots (with serial numbers) on the web after the election. A voter could then check his receipt against the online ballot-list, and complain if they didn’t match. But of course the receipt violates the secret-ballot requirement.
Rivest tries to work around this by having the voter fill out three ballots. To vote for a candidate, the voter marks that candidate on exactly two of the three ballots. To vote against a candidate, the voter marks that candidate on exactly one ballot. All three ballots are put in the ballot box, but the voter gets to take home a copy of one of them (he chooses which one). At the end of election day, all ballots are published, and the voter can compare the ballot-copy he kept against the published list. If anybody modifies a ballot after it is cast, there is a one-third chance that the voter will have a copy of that ballot and will therefore be able to detect the modification. (Or so the theory goes.)
Consider a two-candidate race between George Washington and Benedict Arnold. Alice wants to cast her vote for Washington, so she marks Washington on two ballots and Arnold on one. The key property is that Alice can choose to take home a copy of a Washington ballot or a copy of an Arnold ballot – so the mark on the ballot she takes doesn’t reveal her vote. Arnold’s crooked minions can offer to pay her, or threaten to harm her, if she doesn’t produce an Arnold ballot afterward, and she can satisfy them while still casting her vote for Washington.
ThreeBallot is a clever idea and a genuine contribution to the debate about voting methods. But we shouldn’t rush out and adopt it. Other researchers, including Charlie Strauss and Andrew Appel, have some pretty devastating criticisms of it. They’ll be the topic of my next post.
Helger,
Looking at the paper you referenced, I don’t see how ThreeBallot qualifies as an RRT. It doesn’t match any of the RRT methods mentioned in the paper; it doesn’t rely on cryptography; and it doesn’t rely on randomness. (Voters are free to fill out their ballot-triples in any way they like, as long as they meet the basic constraint.)
Maybe there’s another type of RRT I don’t know about that matches ThreeBallot, but at this point ThreeBallot doesn’t look like an RRT to me.
I’ve also been thinking about RRTs. You’d only require about 5% of the population to retain their receipts to validate even a close election. But the bigger problem exists with distributing receipts to millions of people- those intent on throwing the election can simply produce faked or marred receipts- gumming up the courts for months or years. In the end, physical security is necessary, at which point paper ballots look better and better.
For paper ballots, perhaps if two copies are made simultaneously by poking holes in the ballot. One copy in the official box, and one in a box held by a third party. Makes ballot faking much harder…
Actually letting the people be custodians and counters of their own votes seems to me to be an even superior solution to a paper based system.
For all except opaque votes, any voter can retrieve any vote from any web terminal, and if it’s theirs they can check it’s contents. Moreover, an audit can be made of random votes and the respective voters be invited to demonstrate the votes are owned.
An audit can also be done on opaque votes, but at significant computation cost requiring collaboration by all voters’ PCs to break the encryption on a sample. And this only sanctioned if opaque votes could potentially change the outcome.
All these web-verifiable voting protocols seem like a big waste of time to me, as do a lot of the “paper audit trails” mechanisms that are out there too. The beauty of a paper ballot (say, an optical-scan ballot) is that it can be authenticated as an individual entity (this piece of paper is a valid ballot because it has these marks), it can be counted independently, repeatedly, and in several ways (hand-count, optical scan, whatever) and perhaps most important in this context, the representation of the vote (an ink mark) is identical to the vote itself (hanging chads prove the importance of that point).
None of these solutions seems to put these three elements together. I can authenticate a ballot, sort of, by getting a printed paper receipt of my vote, or visiting a web site to verify my ballot, or verify the three-vote version of my ballot/anti-ballot. But does this mean that this electronically-produced representation of my ballot is in fact the ballot that was counted? There are transformations and representations (software-driven, presumably) between that vote and its presentation to me for authentication, between that vote and its counting. What are the recounting mechanisms for these ballots if fraud is suspected?
Paper ballots are imperfect, too, and more thought could be given to how to use technology to assist the valid-ballot-creation process, but I’m willing to say that ideal electronic voting is inferior to ideal paper voting.
And I forgot to add:
Is this totally worthless? Why?
Now here’s my plan:
1. Voter enters booth. Votes. Gets receipt with ID number and copy of ballot (IDs must be big, and random).
2. If not trying to scam vote buyer, voter leaves with ID’d ballot.
3. Otherwise, voter can vote again. Gets another receipt with another ID.
4. But the step 3 vote generates an anti-vote ballot–a vote for all the opponents of the second ballot. This requires several ballots when there are more than two candidates per office. However, these anti-votes generate no printed receipts, and no ID numbers.
5. Step 3. may be repeated as often as the voter cares to, in case he has sold his vote several times.
After the election, all the IDs and their ballots are published.
There are more ballots than voters because of the step 3 ballots.
And there are a large number of unrecorded votes–the phantoms from step 4.
But winning margins are preserved. In fact, the true number of votes for a candidate= (total of receipted votes for him) – (total of non-receipted votes).
The result is:
The voter can check his vote against the ID’d vote list.
The vote purchaser can check his phony receipt against the ID’d vote list.
The anti-votes do not appear on the list–they have no receipts.
The advantage over the threefold ballot is: for non-scammers, voting is no more complex than it is now.
People can sell their votes, but then given the buyer has no way of knowing whether they truly are getting a real vote or an invalid vote, the buyer is likely to be wasting their money on all except the most honest of voters (who are probably unlikely to sell their votes).
The voter with a silent PIN has to rely on their memory. They can write it down if they want, along with any number of false PINs (assuming they leave clues to themselves as to how to distinguish).
A voter can determine if a specific PIN has been used already (which would only happen if they’ve used it, or they’ve given their credentials to another). So, after receiving their pin (displayed on an LED readout say), the voter can be reasonably certain that the pin at least functions in enabling them to store/retrieve a particular vote.
Once voting is over and counting has begun, no more votes can be made. Given their credentials, people can still find all votes with their ID on them, and check that they would be counted correctly. PIN made votes can be counted, and valid can be distinguished from invalid, but they cannot be tied back to the voter.
PIN votes are made by proxies that are only active prior to the counting phase.
Every voter can find out at any time if they used any PIN to submit a vote. The number of pseudo identities created for proxy votes must therefore match the number of voters using a PIN.
Matching PIN votes back to voters could be made possible if desired, but computationally hard.
You might be interested in the low-tech but ingenious mechanisms the ancient Athenians used for this purpose:
http://www.alamut.com/subj/artiface/deadMedia/agoraMuseum.html
ThreeBallot is just a reinvention (?) of the well-known randomized response technique. It’s use in voting has been proposed before, see, e.g., http://www.adastral.ucl.ac.uk/~helger/papers/ajl04/. I have been myself tinkering around with the idea of using RRT in voting, and I talked about that with the people from electorate committee of Estonia, but they did not think it to be feasible. (Especially in close races, say Bush-Gore 2000…)
Of course, Rivest is visible and it is good that he is popularizing the idea.
Crosbie,
What about voters that want to sell their votes? Would they not surrender their pins?
and how does the voter know they are using a valid pin if they cannot demonstrate which is true?
Only voters subject to coercion need to memorise their 4 digit PIN. The other 9,999 permutations are available as chaff.
The PIN is supplied at the same time as the body of the voter is associated with the voting identity.
Unless you involve another trusted party the only way a person can avoid being coerced to provide the truth is if:
1) there is an inexhaustible supply of potentially true PINs,
2) even the person themselves is unable to demonstrate which PIN is true,
3) the truth is recorded only in the mind of the voter
4) if finite, each PIN must have a time cost, e.g. 24hours between 4 digit PIN based votes.
I suspect that a PIN could be used to retrieve one of 10,000 potential keys from a variety of official dispensaries. Only one of these would provide the correct digital signature for an override vote.
“Everyone is given a silent PIN which they only need to use if they fear coercion. The correct PIN (in addition to their other credentials) enables the entry of an override vote. The incorrect PIN creates an invalid vote. Only the voter’s memory enables them to determine the difference – otherwise all their votes appear the same.”
Logistically, this is not likely to work. People have to remember a pair of numbers they only use once every 2 or 4 years. And they must remember which one is the real one.
Even those of us who use passwords every day will forget crucial ones that are only used several times a year. So you need a support structure that will let tens of millions of people reset/relearn their PINs, and this must be secure against fraud.
Plus, the lack of finality is a problem. The public will not like the possibility that, even after they vote, an identity thief can recast their vote.
The only thing the receipt shows (when compared to the posted list) is that the marks on the retained copy match the marks recorded. The other two are also posted but cannot be verified. The receipt cannot be used to prove who the voter voted for. In the case of Washington against Arnold, any given ballot could have any possible combination of marks (none, W, A, or both); a given receipt proves nothing. This does assume that voters are not able to know the ID numbers of the two ballots they don’t copy; Rivest does address this as an issue.
Now, it is possible that the technology used to count the ballots could remember which ID numbers were not retained and then alter those at some point to steal votes. Getting the implementation details right would be important.
As Ed stated, this system is not ready for prime time; however, the paper should be required reading for students of voting technology. Ultimately I think that marking three ballots may be too complex for too many voters.
Thanks for the mention Ed, looking forward to tommorrow post. I’ll add a quick, but important clarification to your description of the 3-ballot system. All the ballots have unique, separate, ID numbers and so the ID number of the ballot the voter choses to take a receipt for will bear that same ID number too. That way she can tell which of the many aggregated votes for george washington is hers. It also provides one route to selling your ballot as well, as I’m sure you’ll discuss tommorrow.
So my critique of his system should not be consider implied praise for others receipt based systesm. All the other forms of receipt-based tracking systems I am aware of have their own potential for vote manipulation issues. The prime advantages of Rivest’s method are that it can be done on paper by the voters hand, and has no chain of custody of encryption keys to secure permenantly. The downside is that it has some pretty significant, perhaps show stopping, flaws.
What about this one: http://www.vreceipt.com/article.pdf ? It got some press when it was written, but I haven’t heard anything about it since. Was it found to be insecure?
Imagine a gigantic ballot box accessible by any Internet terminal, and one that has no central point of control.
Anyone can put any number of valid and invalid votes into it at any cybercafe.
Anyone can use the voting app at any time and ask if any of their votes have been recorded.
Everyone is given a silent PIN which they only need to use if they fear coercion. The correct PIN (in addition to their other credentials) enables the entry of an override vote. The incorrect PIN creates an invalid vote. Only the voter’s memory enables them to determine the difference – otherwise all their votes appear the same.
Once a certain key is revealed, all votes become countable by anyone (though not traceable except by their owners).