Usable Security

Ron Rivest suggests a paper-based voting system called ThreeBallot, which is unusual in that it lets voters verify the integrity of the election from end to end, but doesn’t require computers to do fancy cryptographic operations.  Designers of voting schemes have long desired to enable each voter to ascertain with confidence that their ballot was cast and counted properly in the final result, without enabling voters to sell their votes.  It is possible to achieve these two goals together, but previous proposals for doing so have required some fairly sophisticated cryptography (for example, many of the proposed solutions are based on mixnets).  Such schemes are typically criticized for requiring all voters to perform a tricky voting procedure, for having a complex verification procedure for those who wish to check their votes, or both.

However, the ThreeBallot voting procedure is quite simple to understand and can be carried out completely on paper.  Each voter takes three identical blank ballots, marks them all, and casts them all.  These ballots would be just like today’s optical scan ballots (for example, with a bubble to fill in next to each option).  To do the equivalent of filling a bubble on an ordinary ballot, the voter fills exactly two of the three corresponding bubbles on the three ballots.  To do the equivalent of leaving a bubble empty on an ordinary ballot, the voter fills exactly one of the three corresponding bubbles on the three ballots.  Filling all three bubbles or leaving all three empty is illegal.

When all the ballots are counted, the effect is as if the voter had cast two votes for the chosen candidate and one vote for all the other candidates in each contest — so the totals produce the same winner.  (To produce an actual count of votes, you would just subtract the number of voters from each candidate’s count.)

What is gained by marking three ballots instead of one?  Each voter now has the option to take home a copy of any one of their three ballots.  Each ballot has a unique ID number printed on it, and all the collected ballots are posted online.  The voter can go online, look up the ballot they took home, and verify that it was correctly counted.  But, since it’s only one of the voter’s three ballots, it doesn’t reveal how they voted, and can’t be sold as proof of how they voted.  (True, the voter only gets to verify one of the three ballots, but that’s enough: since the voter gets to choose which one, it would be very unlikely for the tampering of any significant number of ballots to escape detection.) Also, anyone can count up all the posted ballots to check the election result.

This is a big leap forward for end-to-end-verifiable voting schemes.  It’s vastly simpler than end-to-end-verifiable schemes that have been proposed before.  But is it simple enough to work in practice?  Here are some of my thoughts on this, following a discussion about this voting scheme in a reading group meeting today.

Let’s first look at the scheme as presented.  There is a pile of identical blank ballots at the polling place.  The voter takes three, marks them in private, then brings them back to be checked.  A checking machine scans the marked ballots to make sure that they are legal (i.e.  exactly one or two of the bubbles in each triplet are filled, and the maximum number of allowed selections in each contest has not been exceeded).  The checking machine prints a random ID number on each ballot.  The voter selects one of the three ballots; the machine produces a copy of the selected ballot for the voter, then drops all three original ballots into the ballot box.

How hard would it be to get voters to properly mark three ballots (or a perforated ballot with three separable columns)?  The instructions are simple — mark one or two in each row — but it may not be so easy to convince voters why they should do this.  I’m not convinced that we’d be able to get voters to put a mark next to a candidate they want to vote against.  That’s an action that seems likely to produce some cognitive dissonance.  I don’t know for sure; maybe voters would still do it, but it’s not immediately obvious to me.  Pollworkers would probably be busy answering lots of questions.

The bigger problem, it seems to me, would be convincing voters to mark one out of three for every unselected option on the ballot.  A San Francisco voter who just wants to cast a vote for Governor and ignore the other contests would have to fill in over 100 bubbles instead of just one.  (This fall, there will be over 20 offices and 24 propositions on the ballot in San Francisco.) I’d like to be less cynical about the behaviour of typical voters, but I’m inclined to think it will be even harder to get voters to do something really inconvenient than to do something they don’t fully understand.  The inconvenience might be the real killer obstacle here.

Would the ThreeBallot scheme truly prevent voters from selling their votes?  Not necessarily.  If the voter can identify all three of the ballots they marked in the public record of ballots, that would probably be enough to sell their vote.  Since the voter only gets to see the ID number on the ballot they choose to take home, but not on the other two ballots, that makes it harder to identify the other ballots — but it might not be impossible.  A vote-buyer might demand that the voter mark all three of the ballots in a specific way, and then the pattern of marks might be distinguishable, depending on how the rest of the voters behave.  If most voters vote uniformly (for example, always marking either the first ballot or the first two ballots), then a specific pattern of three ballots would stand out from the crowd.  The coercion prevention of ThreeBallot depends on the voters to randomize how they distribute their marks among the three ballots.

Let’s consider now a possible alternative.  If it’s too tedious for voters to mark three ballots in this way, how about a machine that marks the ballot for them?  Then voters could have the same familiar touchscreen interface that many of them like and find convenient, but still produce ballots that work with this scheme.  Imagine a machine that prints three ballots and then prints an extra copy of one of them (perhaps on a different colour of paper) at the voter’s choice.  The voter has the option to verify the three ballots before dropping them in the ballot box, and takes home the extra copy.

Suppose we compare this scheme to regular touchscreen voting.  The printed ballots are similar to the paper trail produced by today’s machines.  Some fraction of voters would check the printed ballots, just as some fraction of voters would check the paper audit trail (though checking the three ballots takes a little more work than checking a single ballot summary).  The voter also gets to check the take-home ballot against the online records, which is an extra advantage provided by machine-assisted ThreeBallot.

However, now we have a new problem: the ballot-marking machine becomes responsible for randomly distributing the marks among the three ballots.  If the distribution is not random, then the voter becomes vulnerable to coercion.  It’s difficult to generate true randomness in a machine, and randomness can’t be verified by an observer.

I conclude that there remain some significant obstacles to practical deployment for ThreeBallot.  I’m not certain that it’s an unworkable scheme — it’s certainly much better than any other end-to-end-verifiable voting scheme I’ve seen — but I’m also not sure its advantages would outweigh its disadvantages in practice.  I welcome your thoughts on ways that the remaining obstacles could be addressed.

This entry was posted on Friday, September 29, 2006 at 11:29 under Ideas, Opinions, Voting. You can leave a comment here or trackback from your own site. Use the comment feed to follow comments on this entry.