Rivest's 3ballot scheme for verifiable secret ballot elections (summary)

A revolutionary new protocol called "3ballot" was introduced in September 2006 by MIT's Turing-award-winning cryptographer Ron Rivest. It accomplishes the seemingly incompatible goals of

1. Each voter's vote is secret, preventing vote-selling and coercion.
2. Each voter can verify that his vote was not discarded, and was correctly used and not altered, in the computation of the election result. (And if not, the voter is in a position to prove the vote counters cheated.)
3. Everybody can verify the election result was computed correctly.
4. Everybody can verify that extra fake "voters" were not added, and the full list of voters is publically known.
5. The whole protocol can be done without computers or cryptography – only low-tech devices like paper and pens are needed – and is so simple it can be understood by children. (It is, however, also possible to put in computers and cryptography; several flavors are possible.)

Interestingly, 3ballot turns out to work most naturally, securely, and simply, for approval voting and range voting. It still works – but less naturally, securely, and simply for plurality voting (the kind of voting currently most common throughout the USA and world) – and it essentially does not work at all for voting methods based on rank-order ballots such as instant runoff voting.

Actually, Rivest's original plan was intended for plurality voting, but it turned out not to work because it permitted vote-buying. I pointed out to Rivest, though, that (a) it did work for approval and for range voting, and (b) a certain modification of his idea, called BOFFO, works for plurality voting. I presume later versions will appear of the Rivest paper which will incorporate these improvements and fixes. They are, at any rate, described in these here CRV pages.
–Warren D. Smith 4 Oct 2006.

Later note (November 2006): Rivest & I have agreed to produce a joint paper. These here web pages at CRV will be obsoleted by that paper (you are warned). The paper is now described in press releases and is available as pdf and html and there is also an addendum.

The details

Just the recipes, without too many details

Sleator's "cheapo" semi-secure plan

US Presidents and fraud

Lectures at CMU (2nd lecture discusses this secure voting stuff)

Return to main page