Warning: Rivest and I are going to be writing a joint paper on this, and the info in these CRV pages at present (20 Oct 2006) is known to contain some errors.

Ron Rivest's "3ballot" scheme for cryptographically-secure voting – without cryptography! – and the "BOFFO" plan

By Warren D. Smith 1 Oct 2006; revised to make it clearer 3&5 Oct

Warning: This page is now largely OBSOLETE since the actual Rivest-Smith paper came out. See press releases (which will link to the actual paper, among other things).

(Executive Summary)   (Recipes only)   (Cheapo plan)   (Return to main page)

Sometimes, in the course of human events, it becomes necessary to whack yourself upside the head for missing that easy idea which really turns perceptions of "what is possible" upside down. Many surfaces upside my head were awarded that treatment when MIT's Turing-laureate cryptographer Ron Rivest in late 2006 invented his brilliantly simple "3ballot" system for secure voting. Another nice name for it might be Rivest's "triple threat" system. (Then later, Rivest himself probably began smiting his own head mightily when he realized his 3-ballot plan actually did not work – in his words was only a "partial success" – for plurality voting elections – but I was able to fix that with the even-simpler "BOFFO plan," described below, to turn it into a total success!)

Before starting, let us briefly review. Initially, all desired to

1. Have voter's votes be "secret ballot" – so that nobody can know how anyone voted (not even if the voter wants to tell them) and hence nobody could bribe or coerce you to vote some way, and you could not sell your vote.
2. Have the election be secure and verifiable – so that we could all be confident that nobody voted more than once, no votes were inserted, deleted, or altered, only authorized voters voted, and the results were computed correctly from those votes.

Trouble is, these two desires seem incompatible. It is trivial to get secure elections if the ballots are not secret; just publicize every voter-vote pair to make it trivial to verify that everybody voted as they said they did (or didn't) and the ballots were tallied correctly. But then it'd also be trivial to coerce voters, rather undermining "democracy."

But (as usual in the voting area) your initial perception of an "obvious" fact (i.e. this incompatibility) is wrong. Various different schemes employing advanced cryptographic ideas have been independently invented by several people (including me) that make it possible – at least in somewhat-idealized mathematical worlds. These schemes involve voters submitting their votes in encrypted form so nobody knows what they are, and having the vote-talliers output "zero knowledge proofs" that their tallying is correct. That way, independent verifiers (e.g. international election-validity-assurance organizations, the LINUX community, the League of Women Voters, etc) can verify the proofs and become confident the talliers did not cheat, etc, but the proofs reveal nothing about who cast what votes (aside from the knowledge attainable by knowing the final election result). Note, in these schemes it is not necessary to place your trust in the government, or in the programmers the government employs, or anybody. They cannot cheat. It is mathematically impossible for them to cheat without being spotted (with proof they cheated) by the verifiers. All we need is that at least some of the verifiers programmed the verification right – and in principle any hacker in the world could code up their own verifier and check the proof themselves according to standard published procedures.

That was all very fine in principle, but these schemes were very complicated. I'm a math PhD and I invented some of those schemes, and I still regard them as very complicated and tricky math. It seemed impossible to gain the confidence of Joe Public in these schemes, unless Joe Public was willing to devote several months (?) of his life to studying the (beyond undergrad level) math and learning these schemes. Not likely.

So cryptographically-secure voting was largely regarded as a great idea in principle in an ivory tower – but in practice, fuhgeddaboutdit. Then suddenly, in 2006, bursting upon this squalid scene like a giant waterballoon filled with laughing gas, came Rivest's 3ballot scheme. It is low tech, understandable by children, and involves no fancy math or cryptography whatsoever. We reassure the brainiacs in the audience, however, that it also is possible to make various "medium-tech" hybrids of 3ballot with high tech cryptographic ideas – as well as various different extra low-tech gimmicks and gizmos can be inserted into the picture. Some of that will be discussed at the end.

Range and Approval voting: good.
Plurality: mediocre.
Borda and Condorcet: bad.
IRV: very bad.

Rivest's scheme turns out to be most natural and nicest and securest and simplest, if it is used with approval voting. It also is highly natural and simple if used with range voting.

One can attempt to employ Rivest's 3ballot scheme with plurality voting, but then it is less natural, less simple, and has greater vulnerability to an attack Rivest calls the "reconstruction attack," and is devastatingly vulnerable to the "specified pattern attack." However, a new variant, the "BOFFO plan," stated here for the first time, works for plurality voting and is essentially immune to those two attacks.

3ballot also can be made to work with Borda and Condorcet (rank-order ballot) voting, but the resulting scheme is vulnerable to the reconstruction and and specified-pattern attacks, i.e. is a clear failure in elections with 12 or more candidates.

Finally, 3ballot does not work at all if used with Instant Runoff (IRV),

So this is (yet more) evidence for the superiority of range and approval voting (in yet another way – ability to make them secure) over those other voting methods. It is actually a very interesting and pedagogically useful way to explain and organize the exposition, to do it one voting method (Approval, Range, Plurality, Borda) at a time comparing what works and what doesn't for each.

Ok, that is enough buildup. Now to describe the scheme itself...

Here's the 3ballot scheme! (For Range and Approval voting)

In 3ballot, voters vote in each election, not once, but exactly 3 times. Their individual votes have to satisfy certain constraints, though. We shall discuss range voting and approval voting, and focus attention on a single candidate named Gladstone. Recall that each voter's job in range voting is to produce a score for Gladstone from 0 to 99. (Or more simply, from 0 to 9. We'll do it for 0-99 for concreteness, but the reader should easily be able to change it to any other range A-B.) In approval voting the voter's job is even easier – merely to say whether he "approves" Gladstone (score 1) or "disapproves" (score 0).

What about plurality voting? (& why 3ballot is broken for plurality)

We are going to explain why the 3ballot scheme above, is broken for plurality voting, as preparation for explaining our new "BOFFO plan" (which works).

One trouble with plurality voting is that if you vote Gladstone, you are not allowed to vote for any of his rivals (that would be "overvoting," which is illegal in plurality voting, but allowed with approval voting).

So suppose we do plurality-voting-3ballot in a race between Gladstone and 45 rival candidates. You vote YES for Gladstone and NO for each of the 45 others. You then get your 46 votes (actually 138 votes due to the tripling) checked for validity by the government checking machine – which now has to be a more-complicated machine because it checks 138 ballots at once, with more complicated validity-rule, as opposed to just checking 3 ballots with a simple validity rule. That means the check machine has to be more complicated. That complexity means it probably has to include a computer, and then it is more risky it might cheat by remembering stuff, at which point the security guarantees of the whole scheme would be blown out of the water since an evil government would trivially be able to alter ballots undetectedly.

But let us assume the check machines can be trusted and continue on. If all the 46-subvotes are posted as one lump on the bulletin board (3 such lumps posted in total) then it becomes possible for anybody examining the bulletin board to try to reconstruct the 3ballot triples. That is, suppose your vote is

where for simplicity some of 46 columns of the table have been replaced by "...". Gladstone (sum=2; he got your vote) is the first column and the rivals are in subsequent columns (sum=1 each; did not get your vote).

The point is, an evil vote-buyer/coercer could observe that the possible two-ballot pairs that complete the triple with the one ballot the voter has an official certified copy of, are very few and very rare. If you just choose two ballots at random from the bulletin board they will [with very high probability, somewhere around 1-(4/9)⁴⁵] not satisfy the legality condition that the sum of the three ballots is 1 in all 45 non-Gladstone entries. In fact, it is quite likely that only one ballot-pair from the entire country-wide bulletin board, could possibly work. And even if several work, then the vote-buyer might well be able to reconstruct all ballot triples countrywide at once (kind of like putting together a jigsaw puzzle – even though some puzzle pieces fit together in several ways, only one of them works when the whole puzzle is assembled).

In other words, the buyer/coercer reconstructs the vote-triples, enabling him to determine from a voter's receipt, not just that individual vote, but in fact the whole vote-triple it was part of. In either case, the vote buyer/coercer would happily pay the voter for his vote – or happily punish him for not voting the "right" way.

With approval voting, even if all scores for all candidates were bundled (which there would be absolutely no reason to do, because candidate-scoring decisions in approval voting are independent) then, still, random ballot triples would satisfy the (much less severe since overvoting is now fine) constraints with probability about (3/4)⁴⁵, which, although small, still is large enough that there would (in a country like the USA with 10⁸ voters) be expected to be billions of ballot-pairs that would work. So the vote-buyer would have no good reason to pay almost any voter, and vote-buying and vote-coercion would be effectively shut down with approval voting (with these numbers of candidates and voters).

Now of course, you could un-bundle all the votes to defeat the reconstruction attack. For example, instead of posting all 46 in one lump, post 46 one-candidate sublumps. That totally shuts down the reconstruction attack. But then, we all have to trust that nobody overvoted – this cannot be verified by examining the bulletin board. Then by clever intentional distribution by the evil government of checking machines that have different efficiencies at spotting overvoting, a plurality election could be manipulated. (And indeed, precisely this sort of manipulation was used in the Florida 2000 Bush-Gore-Nader election.)

But, what is even worse is an absolutely devastating attack on 3ballot-for-plurality-voting called the selected-pattern attack (but that attack cannot be used on approval and range voting elections).

The selected pattern attack

The attacker (vote buyer or coercer) says to the voter (in a 33-candidate race like the Congo September 2006 presidential race)

I want you to vote A=1, B=1, C=0, D=1, E=0, ..., Z=1 as your first vote, and A=0, B=0, C=1, ... as your second, and and A=1, B=0, C=0, ... as your third (completely specifies all patterns), and copy vote #1 for me to see.

Then there are 2³³ possible kinds of votes (which far exceeds the population of the Congo), so the coercer can uniquify easily. Then the coercer, if he does not see all three demanded patterns posted on Rivest's "bulletin board," exacts horrific punishment on the voter, such as making him listen to a Bush press conference.

This illustrates the tremendous devastation the "3-pattern attack" (also called the "selected pattern attack") can wreak. But in range and approval voting, all candidate scoring decisions are independent and can be on separate "ballots" so there is no pattern, so for those voting systems (and apparently those alone), the selected pattern attack is simply not a problem. With Condorcet, Borda, and Plurality voting, etc, the individual candidate-scores depend and hence cannot be separated without making ballot-validity-checking impossible. That means the ballot-validity checker would have to check all 33 – i.e. with the tripling all 99 – of your candidate-scores to make sure their combination is legal. That means either

1. you need a complicated validity checker (destroying Rivest's goal of not needing computers) and/or
2. you need to bundle all candidate scores into a 33-score (actually 99- or 132-score) ballot (enabling the selected pattern attack).

Avoid pointless bundling

Incidentally, Rivest at one point had the idea that ballots for many different races should be bundled onto a single sheet of paper. That idea is completely stupid – your vote in a 12-candidate 100-voter local school board election (in which the selected-pattern and reconstruction attacks would be maximally easy!) could then be used to attack your bundled vote on the US presidency – and such bundling is stupid not only for security reasons but also for reasons of countrywide standardization of ballot formats and simplicity. The sole "reason" for such multirace bundling is to have a pointless holdover from pre-3ballot election traditions.

Just say no to pointless bundling.

But bundling all the candidates in a single plurality (or Borda) election onto one sheet of paper, is, in contrast, not at all pointless. Some would even say it is "necessary" because otherwise it is impossible to tell (without examining many separate sheets of paper) whether your Borda or plurality vote is even a legal vote.

The BOFFO plan to handle plurality voting

An (even more blitheringly simple) fix against those attacks!

We shall now show how to handle plurality voting in a new way that is immune to the reconstruction and specified-pattern vote-buying attacks, and which actually is even simpler than the 3-ballot plan. I call it the "BOFFO plan."

The essential insight you need is that those attacks were enabled by the presence of extra, useless, redundant information in the voters' vote-triples (i.e. all those vast number of near-arbitrary 1s and 0s in the 3xN matrix). Specifically, in an N-candidate election, there are W(N)=N·3^N+1 possible legal 3ballots a voter could cast, which for N large is an exponentially enormous number. So to prevent those attacks – and indeed to prevent any attack whatever that is based on hiding information in votes – we need to get rid of that redundant information and reduce the exponentially enormous configuration-count to a small – low-degree polynomial in N – count. More precisely, let the number of configurations be called W(N) with N candidates, and let the number of voters be V. Then smaller W(N) is better because the voting mehtod will then be immune to vote buying (except for negligibly small percentage of the votes) if V>>W(N). More precisely, the maximum fraction F of the votes which it is possibly possible to buy, is bounded by F≤W(N)/V.

We may assume there are N≥3 candidates, since a plurality vote election with 1 candidate is silly, and a 2-candidate plurality election is mathematically the same thing as a 1-candidate approval election (and we already know how to do approval elections).

I call the repaired scheme "2 for and 3 against" or the "BOFFO plan." It is simple.

The BOFFO rule: Suppose you (Joe Voter) want to vote for B. We require you to do so by contributing exactly 5 votes (3 "for" votes and 2 "against" votes) as follows:

FOR B

FOR O

FOR F

AGAINST F

AGAINST O

and B=F (or B≠F) is allowed, i.e. it is allowed for the three mentioned candidates B,F, and O to be the same, or different, or whatever you want, but the two Bs must be the same and the two Fs must be the same. Call a vote 5-tuple of this type "of BOFFO format." Note that it includes 3 FOR votes and 2 AGAINST votes, with your AGAINST votes required to cancel your FOR votes so that the net effect is of a single FOR vote. Also note in the BOFFO plan, there is no matrix filled with 0s and 1s. (Anywhere. Ever. Not even merely mentally and virtually in anybody's head. No matrix.)

That, is, you vote for B (your "real" vote) but also vote both for-and-against O and both for-and-against F where O and F are two other candidates which do not matter because your votes about them cancel themselves out. O and F are there purely to allow disguise.

So in an N-candidate race, there are exactly N²(N+1)/2 valid BOFFO-style un-ordered vote-5-tuples you (a voter) are allowed to output. If we count different time-orderings of the 5 subvotes as different, then there are exactly 10N(6N²-9N+4), assuming I counted right. (If I did not, I'm not off by much and the error does not matter.) If we just count the number of distinct possible types of subvotes inside BOFFO-5-votes, then exactly 2N types are possible. All these counts are indeed bounded by low-degree polynomials (in fact degree=1 and 2 and 3) in N. (Note here that approval and range voting are superior to plurality in the sense that for them, the corresponding counts are bounded by constants independent of N.) We are going to assume from now on that the number V of voters far exceeds these numbers, e.g. V>>60N³ (actually, all we shall really need in practice is V>>20N or so) and the voters are diverse enough that we can assume that every possible vote-type will happen many times.

You submit your BOFFO-type 5-vote-tuple and a simple checking machine confirms your 5 votes were indeed of BOFFO format and produces an official goverment-certified copy (including copying the ballot number) of one of the five – you pick which – for you to take home with you. Variant: instead of taking one copy home, BOFFO also seems to work if we agree each voter is allowed to pick two of her 5 ballots to copy and take home (and those two may also be allowed to be two copies of the same one ballot). We'll come back later to why such a variant might be a good idea.

Why BOFFO works

1. Why cannot you sell your vote? Because if some buyer examines just one of your votes, that buyer has no idea which candidate (B here) is the one you really voted for. If he sees a FOR vote, it could have been for O or F, not A. Buyer has no idea. if he sees an AGAINST vote, then that still tells him nothing about who B was. (Say he sees "AGAINST F." Well, you could have voted for B (since F=B is allowed). You could have voted for A where A is anybody else (since F≠B is also allowed). Buyer has no idea. So you cannot sell your vote.

2. Similarly you cannot be coerced to vote for somebody:

Coercer: "I demand you vote for Clinton. And bring me a receipt saying 'FOR CLINTON' on it."
You: Yes, boss!
Coercer: Very good. But wait, how do I know you did not also vote AGAINST Clinton (cancelling out your FOR vote) and thus in total really voted for Bush?
You: You don't.
Coercer: (stymied).

Coercer: "I demand you vote AGAINST Bush. And bring me a receipt saying 'AGAINST BUSH' on it."
You: Yes, boss!
Coercer: Very good. But wait, how do I know you did not also vote FOR Bush twice (and also both FOR and AGAINST Nader) and thus in total really voted for Bush?
You: You don't.
Coercer: (foiled again).

3. The talliers cannot cheat without a high chance of being detected: Specifically, if they alter K votes, the chance of escaping detection declines exponentially with K. Altering a few hundred votes will in practice lead to essentially certain detection.

1. Because if they alter or delete even a single vote, then there is a 1-in-5 chance it'll be a vote somebody has an official copy of. That person could check the bulletin board, see his official copy of vote #164662348 does not correspond to the posted vote #164662348, and go to the League of Women Voters and their lawyers to raise hell. OK, 1-in-5 may not sound like much, but to change a typical important election the government is going to have to alter at least 1000 votes, and for sure some of those alterations are going to be spotted, with proof of the cheating.
2. And if they add fake votes, then the number B of votes posted on the bulletin board would no longer be exactly equal to 5V where V is the number of people who voted (the list of those names and addresses also would be posted there on a separate list). So the cheat again would be detected.
3. And if they add fake voters, then if they want to move the election by 1% they need to add 1% fake voters. Then reporters checking only a few hundred voter names and addresses would be able to spot some fake voters and prove the cheating.

4. No attack like the specified pattern or reconstruction attack (based on hiding information in, or using redundant information inside votes) works: in the sense that the necessary information just isn't there. That is, you cannot try to identify which vote 5-tuples are which by matching up subvotes, becasue essentially anything can match with essentially anything else. You cannot verify a voter voted with your specified 5-vote pattern, because each of the subvotes occurs zillions of times on the bulletin board whether or not your voter obeyed your command.

So it now should be clear exactly why (and exactly in what sense) cheating and vote-buying both are impossible.

Collusive attacks (and defenses)

We should say, however, that the BOFFO plan (and the 3-ballot plan for approval and range voting) both are vulnerable to certain collusive attacks. That is, a vote buyer acting alone cannot buy your vote (even if you, the voter, cooperate and try to sell it to him). And a government-tallier acting alone cannot alter a vote, delete a vote, or insert a fake vote without detection. But if the voter, the vote-buyer, and the government all collude (3-way collusion) then vote buying becomes possible in numerous ways.

So in this sense, these plans rather resemble "threshhold schemes" in cryptography. Those schemes are secure only if a number below threshhold of the players cheat – with too many colluding cheaters, they fail.

We now examine several collusive attacks in detail (and propose some defenses).

1. The voter simply agrees not to complain if anybody alters his vote, and then the government alters it, and the vote-buyer pays the voter and government to do so. (Probably not too serious a threat in practice since the colluders all have to trust one-another. An agent provacateur voter could bring the whole house of cards crashing down.)
2. The vote-buyer pays the voter to give him his receipt. From now on, any alteration of that voter's vote will be undetectable by anybody besides that vote-buyer. Now vote-buyer bribes government employee to alter the vote whose receipt he now owns. (For an even nastier-sounding variant, see collusive attack #4.)
3. The "dumpster diving" attack: The voter foolishly chucks his receipt in the garbage. Somebody dumpster-dives to get it, sells the receipts he collects to a vote-buyer, who now bribes government employees to alter the bulletin-board-posted votes whose receipts he now owns – and those alterations are undetectable except by the vote-buyer.

   Cures for dumpster-diving:

   1. Such receipt dumping can be discouraged by a rule that voters have to bring their old receipts to the next election in order to be qualified to vote in that next one – or pay a significant fine if they cannot...
   2. The "split receipt" idea may largely cure the dumpster diver problem.
   3. See below for the "extra copies" fix.

4. The "bible meeting attack":
   1. Republican voters all vote for Bush, which they do as usual (I discuss in 3ballot for simplicity, but this attack will also work against the "BOFFO" scheme which repairs 3-ballot against the redundant-info attacks; and it also works against receipt-swapping schemes...) by voting for, for, and against Bush.
   2. They copy their "against Bush" ballot.
   3. They turn in all their receipts to the friendly local Republican party boss at their born-again-Christian bible meeting, who'd told them all ahead of time he'd like to have their receipts for "safe keeping," and he'd like their "against Bush" receipts. (Oh, and he'd like their "for Clinton" receipts too, by the way.)
   4. Republican party corrupt bigwigs like DeLay arrange with the government election office (the officials in which, they of course all appointed in the first place rather like Ken Tomlinson to CPB because they were party hacks) to alter all those against-Bush votes to "for Bush" and to alter all those "for Clinton" votes to "against" and burns its receipt collection.
   5. As a result, each Republican voter-participant gets 3 votes instead of 1. The vote shifts by several percent in Bush's favor and he wins.
   [I've put in names from recent US history into this fantasy, but feel free to change the scenario to your favorite (or unfavorite) party and country.] This is technically a 3-way collusion, but not really. That is, generally large collusions are supposed to be unlikely and risky, but this collusion is especially nasty because it sounds likely and not very risky. It is not risky because only a few top Republicans actually know the secret. The rest (all the voters at all the meetings) are innocent or at least have "plausible deniability." In fact for all they know, the Republican party is doing precisely what it should do – helping them with possible vote-protests they might not otherwise be able to undertake, and acting as a watchdog to help preserve democracy.
   How can we protect against this attack?! Juho Laatu suggested the "extra ballot copy" fix. That is (as improved by me) the following alteration in the voting procedure:

   The random-extra-copy fix: As voting proceeds, the votes (3ballots or BOFFO 5ballots) drop in random order into a large glass-enclosed bin. Each voter, as she votes, rolls two dice (or some other obviously-random device is used). If the dice come up double-sixes, then that voter is a "lucky" voter who gets to reach into the bin, pull out a random ballot, and have an official copy made of that ballot for her to take home.

   The point of this is that this way, nobody can be sure that they have the only official copy (or copies) of ballots. So if evil Republicans (or whoever) try to alter a vote, even a vote they have burned the official copy of, there might still be an extra official copy floating around somewhere that'll prove their cheating.
   The random-extra copy fix is still slightly flawed because the last voter of the day knows his vote is uncopied, so the Evil Republicans could arrange for their conspirators to vote last, etc. But that would necessitate a large number of knowing colluders and hence would be riskier and unlikelier, and also the number of votes affectable would be smaller, so in practice this fix seems pretty adequate. (Note that this fix also protects against the "dumpster diving attack" and indeed every collusive attack we've mentioned so far.) There is another related fix, however, which does not even have that slight flaw (and it also can be used in combination with the randon-extra-copy fix):

   The two-or-one plan: The voter, after submitting her BOFFO 5ballot, gets either one of those 5 ballots (chosen by her) to copy and take home, or two, or two-copies-of-one. (Which? Perhaps this choice should be made randomly.)

   The point: this way, even the last voter of the day, still might be carrying around an extra ballot copy. Anybody collecting receipts for later evil destruction can never be entirely sure some voter was not double-crossing him...

What about Borda and Condorcet and IRV (rank-order ballot) voting?

Since it is non-additive, IRV (instant runoff voting) appears to be totally incapable of being made secure by any method like this. For Condorcet and Borda, there is a natural way to try to do it, invented by Mike Rouse – but it does not work, in the sense that it is vulnerable to vote-buyers who use the selected-pattern attack.

A few other tricks (an aside for the reader familiar with high tech cryptographic methods)

If you want to include some high tech cryptography, then the "signatures" by the voters could be unforgeable "digital signatures." The "government-certified official copy of the ballot" could instead be got by the voter requesting from the government an unforgeable "blind digital signature" on one of his three ballots. With blind signatures, the signer has no way to know what he is signing. (But the government can still be sure it is not signing some bogus non-ballot, because it can ask the voter for a "zero knowledge proof" that the thing being signed is A or B or C, using a "logical OR of zero knowledge proofs.")

What about "write-in" ballots?

Write-in ballots are trivially handled in approval and range voting. For plurality voting, the BOFFO scheme cannot handle write-in votes (which we must forbid) because they bring back from the grave that much-feared monster: mucho-information, thus permitting once again, the selected-pattern vote-buying (or coercing) method. E.g. if write-ins were allowed in BOFFO, then

Coercer: You miserable dog, I know you were probably planning on voting for Clinton, in which case I'd have to kill you.
Voter: Who, me?
Coercer: I insist you vote FOR Namsquattyfish, FOR & AGAINST Murgatroidodoggo, and FOR & AGAINST GoofyThePoofy.
Voter: (weak laugh) But there are no candidates with anywhere near those-weird names.
Coercer: That's why you're going to use write-in votes, worm. And I'll be checking the bulletin board afterwards to be sure somebody really did vote for & against all those weird names, so unless you figure another voter somewhere is going to be doing that, you better obey. And you better spell 'em exactly right, too.
Voter: But... then I won't have any votes left to vote for Clinton.
Coercer: (smiles toothily, in the evil manner common to his kind).

Denial of service attack / what happens after the fraud?

What if we hold an election, and protocol proves there was fraud? Then what? For altered or deleted votes, we'd know who cast the votes and could try to track down who cheated to punish them. (Even then, it would probably be impossible to "undo" the fraud.) But for added invented votes, we'd know there was fraud, but it would not necessarily be easy to track down the evildoer who added them, because they did not come from any particular voter (which was the point).

Indeed artificially adding such votes would be a way to try to "deny service" by forcing the election to "be fraudulent."

What can we do about this? Well... the only thing I can suggest is to try to keep track of the chain of custody of official ballots by numerical-range. If anybody introduces fake (non-official) ballots, they would fail (unless they could forge them, which would be comparable in difficulty to counterfeiting money). On the other hand: if anybody introduces fake votes written on official ballots, then because we know the chain of custody of those ballots, we could attempt to track down the evildoer.

A few important lessons

1. "DRE" voting machines (direct recording electronic computers) are a bad idea since they might remember things (like which of the ballots was copied) and thus would totally undermine the no-cheating guarantees.

But PBOS (paper ballot optical scan) machines are just fine (if done right and verification of 3ballot or BOFFO-5ballot validity occurs beforehand in a computer-free paper-based manner). And once the ballots are filled out, verified, copied, and turned in, everything is OK from then on. Wireless interfaces, internet, you name it. It doesn't matter. No many how many computers the government uses from then on, no matter how many flaky, bug-ridden, and penetrated systems there are, no cheating can occur from then on without detection!

2. Approval voting is simpler than range voting is simpler than plurality voting for making secure with the schemes here; Borda and Condorcet cannot be made secure, and IRV cannot be handled at all by these methods.

3. See this for why certain "enhancements" of these schemes by putting in "randomness," are actually a very bad idea.

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

Return to main page