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:
Voter decides (for some given candidate "Gladstone") whether she approves
Gladstone or not.
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...)
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.
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.
Anybody can now total the votes to find out who is the most-approved candidate (election winner).
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.]
Voter can also check that her name is on the list (lookup "Jill Voter").
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:
Voter decides (for some given candidate "Gladstone") what score S, on an 0-9 scale, to
award Gladstone.
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...)
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.
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.
Anybody can now total the votes to find out who is the candidate with the
highest average score (election winner).
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.]
Voter can also check that her name is on the list (lookup "Jill Voter").
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.
Voter decides for which of the N candidates she wishes to vote.
Suppose the candidate she chooses is Bozo.
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).
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...)
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.
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.
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.
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.]
Voter can also check that her name is on the list (lookup "Jill Voter").
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!)