Hidden complexities in tamper-proof voting

Ron Rivest has recently circulated an interesting scheme for a paper-based voting scheme that attempts to achieve the same security properties of cryptographic voting protocols, using only paper ballots.

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 “receipt” 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 “ThreeBallot” 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 “voter-verifiable.” 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 “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.

Although the scheme seemed a bit more complicated than I think the average voter will tolerate, I was pleased to see how far it seemed possible to go in this direction with paper ballots.

Alas, it's not that simple. Ed Felten has posted clear explanations of some fairly serious flaws (first, second, third). He also provides links to more detailed critiques by Charlie Strauss and Andrew Appel.

Moral: Even security experts need to have their protocols vetted by a number of other experts--it's very easy not to see potential weaknesses in your own scheme and not to realize what assumptions you have made implicitly.