Rivest & Smith invent revolutionary secure voting protocols

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.

The two usual bad ways to respond to that.
"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?

1987-2007: The cryptographers find out how

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).

2007: Breakthrough: Secure, Private, Verifiable, Simple, Low-tech voting

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:

  1. The candidate regarded as worst by a huge majority of voters can easily win the election;
  2. Voting for your favorite candidate can be a huge strategic mistake;
  3. Plurality voters express the least amount of information they possibly could in their vote, defeating the purpose of voting as an information-gathering process;
  4. Over time plurality voting countries evolve into two-party domination so that voters have minimum choice, defeating the whole goal of democracy.

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.

R&S's three protocols – ThreeBallot, VAV, and Twin – what they are and how they work

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):

  1. Each voter casts three ballots: a vote, an antivote, and a second vote. For example, to vote for Bush, a voter could vote for both Bush and Gore, while also antivoting for Gore. (The antivote must be the same as one of her votes, and cancels it. Ballot triples disobeying this property are immediately rejected.)
  2. The voter than takes home, as her receipt, a copy of one of the these three ballots. It is crucial that the voter chooses which one to copy and take home, and that her choice is secret – a government machine gives her the chosen signed certified receipt but does not remember it.
  3. Finally, the government posts all the ballots – 3N in all, if there are N voters – on a Public Bulletin Board on the internet, along with a list of the voters' names and addresses (but not saying which voters cast which votes).

What is so good about this?

  1. Any voter can check that the vote recorded on her official receipt number 576388321 is on that bulletin board (by looking up 576388321). If it is absent or disagrees, she has official certified proof that there was election fraud.
  2. Anybody can total the votes (since all are posted publicly) to verify the right winner won.
  3. If anybody corruptly deletes or alters a lot of ballots, then (since nobody knows which third of the ballots are copied) they will with overwhelming probability delete/alter a lot of ballots that have receipts. So the fraud will be immediately visible.
  4. If anybody corruptly adds a lot of ballots, then there will be more than 3N. So the fraud will be immediately visible.
  5. If anybody corruptly adds a lot of fake voters too, then some fraction of the published voter name-address pairs will be fake. (If trying for a 1% fraud, then 1% will be fake.) This is easily checked by, e.g, reporters who will find one fake voter per 100 random people they check. Note that detecting this kind of nationwide fraud is thus within the reach of a single checker.
  6. If anybody tries to buy (or coerce) your vote for (say) Gore, then you can show them your Gore-receipt and ask for your money, while still actually voting for Bush (or for anybody else). The receipt has absolutely no relation to how you really voted. (Anybody willing to pay for that "proof" is very easily parted from their money...)

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).

Machines

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.

Conclusion

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.

For more details

Please read the paper-pdf. (Also contains nice pictures. Also html version and addendum.) Follow-up stories. Kenya. Late-breaking attacks on RS schemes.

About the inventors

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, http://RangeVoting.org.

Contact Info

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


Return to main page