The recipe for Rivest's "3ballot" and Smith's "boffo" schemes for secure voting

By Warren D. Smith 3 Oct 2006

Here we just describe the bare bones procedures. To understand the ideas behind it and to understand exactly what is "secure" about it, check the detailed exposition. For the recipe for Sleator's "cheapo" semi-secure plan (which is simpler but less secure than these) click this: cheapo plan.

Secure Approval Voting via 3-ballot:

  1. Voter decides (for some given candidate "Gladstone") whether she approves Gladstone or not.
  2. Voter submits 3 ballots about Gladstone, 2 of which agree with her decision and one of which disagrees. (e.g. If approve, then do two approves and one disapprove.) Simultaneously she signs a form saying "I, Jill Voter, address 57 Bogus Road, Baloney Town certify that I just voted about Gladstone." (And shows ID to the polling officials...)
  3. Trivially simple machine (a) checks that these 3 ballots obey the 2+1 rule, (b) drops them into a bin in random order, and (c) spits out a government-certified official ballot copy ("receipt") of one of the three ballots, for the voter to take home and keep in a safe place. It is important that (i) this machine be so simple that it cannot possibly be remembering the ballot-triple and (ii) it is the voter who chooses which of the three to copy.
  4. Government posts all ballots in all bins onto a world-readable bulletin board. For example, if you voted for Gladstone, then up there on that bulletin board, somewhere, will be your 3 ballots saying "I approve Gladstone," "I approve Gladstone" , and "I disapprove Gladstone" respectively. Also posted (on another list) will be the names & addresses of all the voters who voted about Gladstone.
  5. Anybody can now total the votes to find out who is the most-approved candidate (election winner).
  6. The voter can check that her vote was used in unaltered form by simply going to the bulletin board and looking up ballot number 16674568703 (Or whatever her ballot number is; it says the number on her official copy) and comparing it with her official copy. [If differs, raise hell.]
  7. Voter can also check that her name is on the list (lookup "Jill Voter").
  8. Reporters can check that the names posted on the list really are of real people who live at their addresses and who agree that they voted about Gladstone. [If not, raise hell.]

Secure Range Voting via 3-ballot:

  1. Voter decides (for some given candidate "Gladstone") what score S, on an 0-9 scale, to award Gladstone.
  2. Voter submits 3 ballots about Gladstone, with scores A,B,C where A+B+C=S+9 and 0≤A≤9 and 0≤B≤9 and 0≤C≤9. Simultaneously she signs a form saying "I, Jill Voter, address 57 Bogus Road, Baloney Town certify that I just gave Gladstone a score." (And shows ID to the polling officials...)
  3. Trivially simple machine (a) checks that these 3 ballots obey the 9≤A+B+C≤18 and 0≤A,B,C≤9 rules. (b) drops them into a glass-walled bin in random order, and (c) spits out a government-certified official ballot copy ("receipt") of one of the three ballots, for the voter to take home and keep in a safe place. It is important that (i) this machine be so simple that it cannot possibly be remembering the ballot-triple – preferably not computerized – and (ii) it is the voter who chooses which of the three to copy.
    Worried that this might be too complicated for voters (especially Florida voters) or for a noncomputerized checking machine? Check this out.
  4. Government posts all ballots in all bins onto a world-readable bulletin board. For example, if you voted for Gladstone, then up there on that bulletin board, somewhere, will be your 3 ballots saying "Gladstone=7," "Gladstone=3" , and "Gladstone=5" (or whatever) respectively. Also posted (on another list) will be the names & addresses of all the voters who voted about Gladstone.
  5. Anybody can now total the votes to find out who is the candidate with the highest average score (election winner).
  6. The voter can check that her vote was used in unaltered form by simply going to the bulletin board and looking up ballot number 16674568703 (Or whatever her ballot number is; it says the number on her official copy) and comparing it with her official copy. [If differs, raise hell.]
  7. Voter can also check that her name is on the list (lookup "Jill Voter").
  8. Reporters can check that the names posted on the list really are of real people who live at their addresses and who agree that they voted about Gladstone. [If not, raise hell.]

Secure Plurality Voting via BOFFO (and incorporating defenses against collusive attacks):

We shall assume it is an N-candidate election for some N≥2.

  1. Voter decides for which of the N candidates she wishes to vote. Suppose the candidate she chooses is Bozo.
  2. Voter also chooses two other candidates, call them for concreteness Osbert and Foo. These could be anybody. It is also allowed for Osbert and Bozo to be the same (or Osbert and Foo to be the same, or all three the same, or all three different).
  3. Voter submits these 5 ballots:
    FOR Bozo
    FOR Osbert
    FOR Foo
    AGAINST Foo
    AGAINST Osbert
    Simultaneously she signs a form saying "I, Jill Voter, address 57 Bogus Road, Baloney Town certify that I just voted." (And shows ID to the polling officials...)
  4. Trivially simple machine (a) checks that these 5 ballots obey the BOFFO format rules above (i.e. there are exactly 3 FOR and 2 AGAINST votes (in some order, not necessarily the order shown) and the AGAINST votes each are paired with a FOR vote that it cancels out), (b) drops them into a bin in random order, and (c) spits out a government-certified official ballot copy ("receipt") of (A) one or (B) two or (C) two-copies-of-the-same-one of the five ballots, for the voter to take home and keep in a safe place. It is important that (i) this machine be so simple that it cannot possibly be remembering the ballot-quintuple and (ii) it is the voter who chooses which one (or two) of the five to copy, although we can allow it to be an obviously-random device (rather than the voter) which decides among possibilities A, B, or C. A random device can at this point also decide to make the voter be a "lucky" voter who also gets a take-home official copy of some previously-cast ballot randomly selected from the bin.
  5. Government posts all ballots in all bins onto a world-readable bulletin board. For example, with this vote, up there on that bulletin board, somewhere, will be your 5 ballots saying "FOR Bozo", "FOR Osbert", "AGAINST Osbert" etc. Also posted (on another list) will be the names & addresses of all the voters who voted in this race.
  6. Anybody can now total the votes to find out who is the candidate with the largest number of votes (election winner) where each FOR vote counts as +1 and each AGAINST vote as -1.
  7. The voter can check that her vote was used in unaltered form by simply going to the bulletin board and looking up ballot number 16674568703 (Or whatever her ballot number is; it says the number on her official copy) and comparing it and with her official copy. [If differs, raise hell.]
  8. Voter can also check that her name is on the list (lookup "Jill Voter").
  9. Reporters can check that the names posted on the list really are of real people who live at their addresses and who agree that they voted in that race. [If not, raise hell.]

Why the talliers cannot alter your vote and cheat

Yes, an evil government could alter the two (or four) votes/scores Jill Voter cast that she does not have a certified copy of, but the government does not know which those two (or four) were – so if it tries, it is liable to mess with the one that she does have a copy of, enabling her to prove the cheating happened. If any substantial number of votes are altered, detection of the cheating becomes essentially certain.

Why you can't sell your vote or be coerced

Because your vote is secret. So the vote-buyer or coercer cannot be sure you really voted the way he wanted. Even if you intentionally show the vote-buyer your receipt (even all of them if you have more than one), the vote-buyer still has absolutely no idea how you really voted in total because he cannot see the other parts of your vote (for which you have no receipt) – all possibilities are still open. Even if you swear a sacred oath that you voted for Bozo in those other parts, you have no way to prove it to the vote buyer. (You might swear another oath to another buyer tomorrow, that you voted for Clodnik!)


Link to Rivest's original paper/notes (pdf)

Return to main page