Detailed Press Release – the Center for Range Voting – 19 July 2007 (see also shorter plaintext press release with more contact info)
Vote-buying and election fraud have happened for over 100 years.
| "Australian" secret ballot (introduced ≈1880) | Post each vote next to voter's name on huge public list |
|---|---|
| Prevents vote-buying and coercion | Makes election integrity & correctness (or lack) clear. |
| But makes it very hard to prove (or disprove) vote-alteration fraud | But makes vote-buying and coercion easy |
The question: can we both prevent fraud and prevent vote-buying & coercion – having cake and eating it too?
The net answer from a community of about 20 cryptography and computational-complexity experts from several countries over the last 20 years is yes. But only with complicated cryptography algorithms, and with each voter needing a personal trusted "digital assistant" in order to be able to cast a vote. So: dubious political & technical realism.
One of the best such schemes is the "homomorphic encryption" approach advocated by Berry Schoenmakers at TU Eindhoven (Netherlands).
Rivest & Smith found a way to have it all. Their new voting protocols are almost obvious in retrospect; they could have been discovered 100 years ago and are incredibly simple – explainable to children. They don't need computers and don't need cryptography.
Even better, the Rivest-Smith security protocols
can handle a wide variety of vote-totaling systems.
The US public is most familiar with Plurality voting
where your vote is "name one candidate then shut up." (Most-named candidate wins.)
Unfortunately this is a poor system:
But political scientists have known for over 200 years that better vote-totaling systems exist. One of the simplest is Approval voting where your vote is "mark all the candidates you 'approve'." (Most-approved wins.) This actually is simpler than plurality voting because there is no special rule against "overvoting." (Little-known fact: the USA's first four presidential elections employed a variant of approval voting. The Soviets also tried it.) Probably the best simple voting system – cf. the Olympics – is Range Voting where your vote is "provide a score for every candidate on a fixed scale (e.g. 0-to-9)." (Highest average score wins.) In this system, voting 9 for your honest favorite is never a strategic mistake, so voters provide more-honest information, and they also provide far more information.
More information + more honest information = better election winners = better world.
Rivest & Smith's paper introduces three different antifraud voting protocols: "ThreeBallot", "VAV," and "Twin." (At EVT 07 conference, Sheraton in Boston, evening of 6 August 2007.)
VAV (vote-antivote-vote):
What is so good about this?
ThreeBallot is related to VAV and designed to be even simpler if voters are using range or approval voting. To "approve" Clinton a voter approves him twice and disapproves him once; to "disapprove" Bush you disapprove twice and approve once. This also permits "write-in" candidates.
Too complicated? We can just give voters who find this too complicated the option of voting in the old-fashioned "OneBallot" style. (Total number of ballots cast is 3A+B where A is number of ThreeBallot voters and B is number of old-style voters.) Upon mixing in the OneBallots with the ThreeBallot ballots in the same box, the OneBallots – almost magically – become protected against fraud because fraudsters do not know which are the protected ThreeBallots and which are the fraudable OneBallots, so they can't afford to alter either. This "mix-in compatibility" property allows "easy upgrade" from insecure to secure voting.
Twin is the simplest of Rivest & Smith's schemes. With Twin, voters do not need to make three ballots to vote once – they only need to make one and drop it in a ballot box as usual. Each voter after the initial 10 gets as a take-home receipt, a copy of a randomly chosen ballot in the box that was cast by a previous voter. Then all ballots are posted on a public bulletin board as usual.
(An elegant "circular" twist suggested by Stefan Popoveniuc is that the first 10 voters must be election workers, and at the end of the day, after the last voter, they each get a take-home receipt too, again a copy of a random ballot in the box. That way everybody gets exactly one receipt.)
The security properties of Twin are the same as VAV, except that voters now check somebody else's receipt (which is also the reason that the receipt has absolutely no relation to your vote and hence is not useful for a vote-buyer or coercer).
In all three schemes, certain simple machines are needed at polling places that check that the voter is submitting a valid (rule-obeying) vote, that make receipt-copies, and/or that randomly sample from a box of ballots. The tasks these machines perform are, however, simple and performable without computers, purely mechanically. (Mechanical no-computer adders, copiers, and random lottery-sampling machines all have been widely manufactured and used in the past.) It is important that these machines be simple and transparent in their operation, so everybody can plainly see they are doing what they are supposed to; and we also want it to be plain they do not contain a computer or sophisticated electronics, because then the machines could "cheat." For example they could "remember" which of the three VAV ballots the voters chose to copy and which not; a fraudster armed with that information could then safely alter the uncopied ballots. (For the same reason, it is important that no spy devices such as cameras are allowed in the voting booth.)
It is interesting that Rivest & Smith's work actually indicates that computers are bad for security. However, it is OK to use computers in all stages of the process after the voters have had their ballots validity-checked and they've gotten their take-home receipts, because any hacking or cheating by the computers would then be detectable.
These are very simple schemes which solve a problem open for over 100 years. Subject to certain assumptions about what the checking machines do, etc, they can be proven to make fraud detectable, allow each voter to verify her vote was counted correctly (unlike now where that is purely a matter of trust), keep votes private, and make vote-buying and coercion impossible.
Please read the paper-pdf. (Also contains nice pictures. Also html version and addendum.) Follow-up stories. Kenya. Late-breaking attacks on RS schemes.
Ronald L. Rivest is most famous for being the "R" in the RSA cryptosystem. This was the first practicible "public key" cryptosystem in which you can publish the method of writing secret messages to you, and even an eavesdropper who knows the entire encrypted message, and has full knowledge of the encryption procedure, still cannot feasibly decrypt the message (but you can). This 1977 invention revolutionized cryptography and later became an essential ingredient in all cryptographic secure-voting schemes. In 2002, Rivest was awarded the Turing Award, the highest award in computer science, for RSA. He is a professor at MIT.
Warren D. Smith got his PhD in Applied Math from Princeton in 1988 and worked in a variety of research jobs including at AT&T Bell Labs and NEC Research Institute (both now defunct). Smith is the developer of cryptographic voting protocols that hold the current records for security properties, and he's also performed the most computer simulation comparisons of vote-totaling methods. In 2005 he, with Colorado Electrical Engineer Jan Kok, founded the Center for Range Voting, .
Dr. Warren D. Smith 631-675-6128 warren.wds AT gmail.com (prefer email)
EVT 07 stands for "Electronic Voting Technology 2007." Answers to NY Times reader questions