New Voting Protocol

Interesting voting protocol from Ron Rivest:

Abstract:

We present a new paper-based voting method with attractive security properties. Not only can each voter verify that her vote is recorded as she intended, but she gets a “receipt” that she can take home that can be used later to verify that her vote is actually included in the final tally. Her receipt, however, does not allow her to prove to anyone else how she voted.

The new voting system is in some ways similar to recent cryptographic voting system proposals, but it achieves very nearly the same objectives without using any cryptography at all. Its principles are simple and easy to understand.

In this “ThreeBallot” voting system, each voter casts three paper ballots (with certain restrictions on how they may be filled out, so the tallying works). These paper ballots are of course “voter-verifiable.” All ballots cast are scanned and published on a web site, so anyone may correctly compute the election result.

A voter receives a copy of one of her ballots as her “receipt,” which she may take home. Only the voter knows which ballot she copied for her receipt. The voter is unable to use her receipt to prove how she voted or to sell her vote, as the receipt doesn’t reveal how she voted.

A voter can check that the web site contains a ballot matching her receipt. Deletion or modification of ballots is thus detectable; so the integrity of the election is verifiable.

The method can be implemented in a quite practical manner, although further refinements to improve usability would be nice.

Very clever.

Tags: , ,

Posted on October 2, 2006 at 1:27 PM • 49 Comments

Comments

bob • October 2, 2006 2:19 PM

Excellent idea. Too complicated for average americans, though. I mean after all they can’t poke out a pre-perforated hole from a piece of cardboard with a sharp-edged stylus while the cardboard is held steady in a die designed for that purpose; so this one if by land – two if by sea stuff will completely exceed their grasp.

Anonymous • October 2, 2006 2:20 PM

So… you just have to discard duplicates which favor the opposing candidate. Makes fraud more difficult, but not impossible.

Unless I’m missing something.

Koray • October 2, 2006 2:38 PM

Very simple idea. If the process for the average voter is deemed too complicated, perhaps the randomization of the columns could be done by the checker to translate a simple ballot into a multi-ballot?

Fred P • October 2, 2006 2:40 PM

Interesting; my question is why the authors didn’t decide to defeat vote-buying in the following manner:
1) The voter enters in their voting preferences on a single ballot in the typical way.
2) A device takes the entered votes, and gives the voter (or poll person) three ballots which have the identical intent, in a random (valid) format; the original ballot is destroyed.
3) The voter verifies that those three ballots combined reflect the original intent of the voter.

Max • October 2, 2006 2:44 PM

@Anonymous: Each voter takes a copy of 1 of the 3 ballots they submit home with them and can later check to see that the copy of their receipt is posted to a bulletin board and matches their copy. The names of the voters are also published, so if the number of ballots is not 3 times the number of voters, you know you have a problem. A voter also knows there is a problem if their ballot doesn’t show up on the bulletin board.

Richard Braakman • October 2, 2006 2:48 PM

I like the alternative of OneBallot with mandatory receipt swapping. Simpler user interface, and all the security constraints around the triple ballot (keep them together for checking, keep them completely separate after checking) just disappear.

The “basket” approach might not be strong enough, though. Consider a vote-buying approach where payment is made for all receipts that show a vote for a certain candidate. Voters who want to be paid off would pick those receipts from the basket, so each individual voter can expect all such receipts will be gone from the basket. Thus, the voter will have to vote for that candidate in order to be sure of having a receipt that will pay off.

Swiss Connection • October 2, 2006 2:53 PM

Have not done the math on this, but I believe it suffices that about 5% of the population check their votes to detect 99% of all manipulations.

Joe • October 2, 2006 3:20 PM

If a person cannot understand a simple task like voting, then they shouldn’t be choosing the leaders of the country.

dave glasser • October 2, 2006 3:21 PM

One thing I didn’t understand: the checker puts a “red stripe” on the bottom, but what’s to stop somebody from adding a mark to the third after checking it? (Will the “red stripe” encode what’s written on it too?)

Chris • October 2, 2006 3:28 PM

Unfortunately paper voting seems to have an oldfashioned style for the people who decide about ist.

asqui • October 2, 2006 5:02 PM

@PAE: Ballot Box Stuffing is covered in Section 4.1 of the paper:

4.1 Adding Ballots can be Detected
An adversary can’t increase the number
of ballots on the bulletin board without
simultaneously putting more voter names
on the bulletin board, which should be
detected by someone, somehow (Grandma,
did you really vote? Weren’t you sick that day?)

Or, people who purposely abstain can ‘verify’ their non-vote by ensuring that their name does not appear on the buletin board.

TimH • October 2, 2006 5:09 PM

Joe: Unfortunately, it seems much of the government agrees with you, and prefers to decide amongst themselves who the next ‘elected leader’ is.

Ben Hutchings • October 2, 2006 5:13 PM

This is a rather clever implementation of “first past the post”, but doesn’t appear to be compatible with more representative voting systems such as STV or Condorcet.

Filias Cupio • October 2, 2006 6:13 PM

It is a very elegant system. I don’t think it will ever be used directly as proposed as it would be too confusing for voters. However, most of the confusion can be made optional.

The voter votes at an electronic terminal. Before print-out, they get a yes/no option ‘do you want to customize the appearance of your receipt?’ The vast majority say ‘no’, and the machine prints out a ballot randomly filled in according to the rules and the voter’s intent, which they can check manually before handing it in to get split into three, and they get a random one of the three ballots as their receipt.

If they choose “yes” to the final question, they get to specify the yes/nos of their receipt, the ballot printed will have one column as specified, and this is the one they’ll get as their receipt. The other columns will be random, within the contraints. (This randomness makes the “pattern voting” vote buying attack much harder.)

I haven’t fully thought through the mechanism for the receipt. One possibility is you use an impact printer to print the ballots, with two-layer carbonless copy covering just one of the three columns, at random. (There are obstacles problems to achieving this.) Or it copies all three, and the device which cuts the ballots into three returns only one of the three possible receipts.

One final idea – make the receipt be a lottery ticket. This will encourage voting, and encourage people to pay attention to their receipts.

Along those lines, the voting ballot prior to division into three could have a fourth column stating in plaintext what the vote is. The voter can check this is what they intended, and there can be a big cash prize for any not-yet-divided voting paper in which the fourth column does not agree with the other three. This bribes voters to look out for the results of compromised voting machines.

Skate • October 2, 2006 7:18 PM

This receipt seems silly. What good is a receipt that you can’t use to audit? Great, so you detect that your vote was altered, only you can’t prove it. I’m not sure that is worth having to fill out three ballots.

packrat • October 2, 2006 7:22 PM

Am I misunderstanding the “Three-Pattern” attack from section 4.4 of the paper? It appears to say that an attacker attempting to buy someone’s vote specifies all three column patterns to the voter, and then pays the voter if those three columns exist anywhere in the set of all ballots cast. Isn’t it extremely likely that, for a large election, any three arbitrary patterns will occur by chance?

CD • October 2, 2006 11:18 PM

@packrat
I was confused by that, as well. The attack they have in mind could proceed as follows:

Group bought voters such that each group is paid to vote in a specific pattern. Require the ith group member to retain the i%3 stub. If n complete “sets” are not present on the bulletin board, then nobody in the group gets paid. With more of the “patterned” ballots accounted for- and with the added social pressure- escaping detection seems less likely (coupled with the next point).

Further, recall that some combinations of votes are highly unlikely and may be good “watermarks” for ballot buyers. If both marijuana legalization and school prayer are on a ballot- with a set of candidates who support/oppose them- then uncommon configurations of votes may be part of the pattern and may further dilute the collection of accidentally-patterned matches. If the state has a “voter initiative” system, one could even inject a collection of “ridiculous” ballot measures to use for this purpose. Requiring members to abstain on only the most controvercial issues would be a good check, too; it’s infrequent that one bothers to develop an opinion on the county water inspector, clerk, and sheriff but fail register any reaction to physician-assisted suicide.

For sufficiently large groups and sufficiently bloated ballots, it’s not impossible that detection could be plausible enough for people to sell their vote and follow through with it.

Gaius Obvious • October 2, 2006 11:24 PM

Why not just have a electronic device that accepts the voters votes in however manner you desire, but then simply outputs a traditional human- and machine-readable paper ballot. The voter would then look at the ballot to see if it as marked as he/she intended and if it is correct puts it into an optical reader, if incorrect he/she notifies the election official and it is put into a shredder and the person then votes again to get a correctly marked ballot. Here we already use an optical ballot but it is marked with a Sharpie leading to possible mismarks (such as circling the bubble instead of filling it in). Making the computer print the ballot out removes that. Having it human readable (by the voter) removes the possibility of a hanging chad where the voter is not sure if the vote was recorded properly or not before it is placed in the optical reader.

The goal should be to have the machine mark the human-readable ballot and then you have both the initial electronic tabluation for quick results on election night and the paper ballots with indisputable markings that the voter approved for later hand audits and official tabulation.

Why is this difficult?

Stefan Wagner • October 2, 2006 11:51 PM

My analog voting machine is an array of pipes, not connected between each other (easy to proof).
Every party has it’s pipe.
Instead of voting, you put a ball into your prefered pipe, which rolls down.
On the end of voting, the panel from the rear of the machine is removed, and the number of balls can be read on a measure, printed on the transparent pipe.
An electric scale would be an alternative.

A noisy ramp would protect from multiple votes by one person.
Or an more complicated mechanic barrier, which only allows one ball to put into the pipes, which is opened and closed per citizen by an official.

But I don’t see much improvement to traditional elections on paper. Votecounting is speeded up but – can’t we wait a few hours for the final result?

Jed Davis • October 3, 2006 12:47 AM

It’s true that it won’t do Condorcet, but I don’t see anything that would prevent its being used for approval voting; just remove the “only one candidate per race??? restriction.

Ping-Che Chen • October 3, 2006 12:56 AM

@Skate: You can prove your vote was altered using your receipt. It’s just that you can’t use the receipt to prove that you voted for a specific candidate.

Stephen Waits • October 3, 2006 2:34 AM

If used for Approval voting, you also lose some ability to prove your vote. It becomes he said/she said.

Yes, the US needs approval voting. It beats IRV, it’s easier than Condorcet, and it’s considerably better than the idiot system we have now. Call your local government about this today.

–Steve

wm • October 3, 2006 5:33 AM

@Gaius Obvious

What you’ve described is indeed a huge improvement on pure-electronic voting (where no voter-verified paper record is used for the count), and a significant improvement in the user interface for a paper-based voting system.

However, it provides no means to detect corrupt election officials burning your vote, deliberately mis-reading your vote, or inventing extra votes of their own choice. The method proposed here prevents this from being done on any significant scale without it being detectable by the disenfranchised voters themselves.

So while the method you describe would be a major step forward (and should be implemented as a bare minimum), the proposed method prevents even more types of election fraud or error.

roy • October 3, 2006 5:48 AM

The way to educate people is to teach their children to use this at school, then the children can patiently explain it to the grownups.

This won’t stop election fraud, but it may make fraud detection, and prosecution, tractable.

There will still be lots of phony ballots due to votes cast by dead people, people who have moved, and people who didn’t vote.

Ron • October 3, 2006 10:08 AM

This method doesn’t work. It requires a vote for each office. It’s perfectly legal and valid to decline to vote for every possible office. E.g.: You may vote for your choice of president, but leave blank and be indifferent about the candidates for dogcatcher.

Mike Sherwood • October 3, 2006 10:21 AM

I don’t get why people selling their votes is such a big concern. It seems to me that if it’s such a big problem, allow people to get a receipt showing who they voted for so the buyer knows that they got what they paid for. It’s capitalism at it’s finest. A voting entrepreneur should be able to get any number of receipts to provide to his various customers, each with the set of candidates the customer wants to see. It seems silly to me to try to come up with a system that can fight all kinds of corruption by creating more complex processes. Sabotage is a legitimate military tactic for dealing with an enemy. Why not do the same thing with people who want to buy votes?

Zwack • October 3, 2006 10:35 AM

Looking through the paper it would work if people understood it.

Personally I think that it would become three separate machines. With a single slight improvement over the methods in the paper.

First machine is a straightforward voting machine. Person A selects the candidates that they want and a human readable ballot is printed out with three strips as mentioned. The marks are randomly distributed so all the voter needs to do is verify that the things they were voting for got one extra mark in that row.

The second machine is the Checker/Ballot box. The ballot is put into the machine which checks that each row has at least one mark on it. It can also check race constraints if desired. It then cuts the ballot into three strips and displays them behind a window for the voter to check again.

The voter checks that this still looks right and selects one of the three strips with a button. The strips then have ID numbers printed on them in red ink and are deposited into the ballot box. The checker then prints out a slip showing the ballot ID number for the selected strip, and the marks on that strip. This should be printed in a different format from the ballot itself so that it cannot be confused.

If the voter decides that they’ve made a mistake or that the ballot isn’t what they meant then all three strips are dumped into a “waste ballot box” without any IDs printed on them. The voter then gets to go back and vote again.

This stops the voter from being able to get the ID numbers of the ballots they didn’t choose in any way. So they can’t reconstruct their vote.

Total votes cast is still (A +B) x N where A is the number of Candidates, B is the number of selections each person can make (Normally 1 in first past the post) and N is the number of voters. This can be verified quickly by anyone and any number that doesn’t make sense should invalidate that election.

The third machine of course is the final optical scan machine that just counts the contents of the ballot box, and reads the ID numbers.

Z.

Zwack • October 3, 2006 10:42 AM

Ron:

If you read the paper you would realise that you don’t HAVE to vote FOR a particular candidate.

If you put ONE mark in every row then you vote for nobody.

If you put TWO marks in ONE row then you vote for that candidate.

Not having to vote for every candidate makes my math above wrong.

Total number of “votes” cast would be between A x C and (A + B) x C where A is the number of candidates, B is the number of candidates you are allowed to select) and C is the number of voters.

Thus given three candidates, one selection and fifty voters every candidate should get a minimum of fifty “votes” and the total number of votes would be between 150 and 200. To get the actual vote tallies you would subtract C from everyone’s final counts…
Given final tallies of 55, 60 and 75 the candidates recieved 5, 10 and 25 votes each. Ten people abstained from voting.

Z.

Ben • October 3, 2006 11:03 AM

I really don’t like giving you a receipt that you take away from the polling place. It makes it too easy to coerce people. “Show me your receipt…”

Ben

Julian Morrison • October 3, 2006 2:07 PM

Surely it would be simpler by far just to give a reciept, and declare vote buying to be legal?

Matthew Skala • October 3, 2006 4:13 PM

Stephen, what you don’t understand is that the voting machine is not a truck. It’s a series of pipes, and just Friday my staff tried to send me a voting machine which I didn’t get until today because if you stuff too many ballots into the pipes, it doesn’t go anywhere.

Chris De Young • October 3, 2006 6:49 PM

I really don’t like giving you a receipt that
you take away from the polling place. It
makes it too easy to coerce people.
“Show me your receipt…”

But the receipt doesn’t tell you anything interesting – you can’t determine from it how the person voted.

wm • October 4, 2006 4:25 AM

@Mike Sherwood: “I don’t get why people selling their votes is such a big concern.”
@Julian Morrison: “Surely it would be simpler by far just to give a reciept, and declare vote buying to be legal?”

Vote buying doesn’t just include “give me your vote and I’ll let you have 50 dollars”. It also includes “give me your vote and I’ll let you stay alive”.

At this point, it’s not really a democracy…

averros • October 4, 2006 4:46 AM

@wm: “At this point, it’s not really a democracy…”

Yep. Democracy is generally understood to be limited to “give us your money and we’ll let you stay out of prison”.

Unless you happen to live in an oil-rich desert, in which case democracy means you’ve got good chances to become collateral damage.

Who cares about stinking votes anyway, when you only get to choose which scoundrel seems to be the least odious?

Ben • October 4, 2006 9:29 AM

The names of the people I voted for don’t have to be on the receipt. If I have the receipt, I can see that the ballot is in the system. That means that there must be a way to find the ballot from the receipt number. If the system can’t do that the check doesn’t work. If you can determine which ballot belongs to which receipt you can find out how someone voted.

Ben

blah • October 4, 2006 11:08 AM

@packrat/CD – I was also confused.

The group buying attack that CD discusses would be prevented using the electronic ballot printer Ron discusses. The process does seem somewhat complicated for the voter, maybe the user should mark the candidate they want to vote for and the printer does the rest (yes this does create a machine that learns your vote – but at least you don’t need a degree to operate it)

CD • October 4, 2006 2:43 PM

@blah

Permitting the machine to mark the appropriate boxes is probably necessary for any practical use, I agree. I can’t think of a modification to the “group buying” attack that would defeat it, either… even patterned “junk initiatives” are insufficient.

I don’t think anybody mentioned the obvious possibility of taking a picture of one’s ballot with a cell-phone. Even if election officals witnessed it and required the voter to delete the picture, it could still be recovered (though re-casting is more likely). Posting the ballots online actually makes faking the picture (and deceiving the attacker) more difficult…

GA • October 5, 2006 2:12 PM

The issue that concerns me is that it seem s that once it has been determined that tampering has taken place (ballots have been removed, added, or changed) then the only recourse is a completely new election. The malicious party may not have a way to get their candidate into office, but they could stall the process indefinitely with repeated attacks.

aws • October 6, 2006 4:52 AM

@CD,

You can protect against the taking a picture attack to some extent (and for that matter live video feed) – the vote buyer essentially sees everything the voter sees. By allowing a voter to vote twice, with the more recent vote being the one that is counted. Of course the vote buyer may force the voter to vote at the last minute.

@RvnPhnx,

Write in vote is wide open to fraud!

nobody • October 6, 2006 9:19 PM

GA: That’s always a risk. Think of a DRE voting system. Suppose there are some strange results, and an investigation shows that unauthorized software changes had been made to at least some DREs. What do you do with the electronic results? There’s probably no good answer here–rerunning the election is a lousy but better-than-nothing approach.

Nobody • October 6, 2006 9:42 PM

Ben:

You get a 1/3 copy of your ballot. Think about a vote for either Alice or Bob. You get three ballots like:

ballot 1 2 3
Alice: X
Bob: X X

Now, you can copy any one of those three ballots, complete with serial number. For any of those three ballots (each ballot is in a column), it’s possible that you got that ballot as one of your three, yet voted for either Alice or Bob. The ballot can’t directly be used to prove how you voted, because given a copy of one ballot, you could have voted either way.

Now, the trick here is that all three ballots will appear on the bulletin board. The election officials don’t know which ballot you copied to make a receipt, so they can’t replace or throw out or alter any of your three ballots without running the risk that you will have a receipt for a ballot that’s not on the bulletin board. That receipt is digitally signed or stamped or something, so that it can be used as evidence that the election was rigged. So while corrupt election officials might get away with tossing out or replacing a few ballots, they can’t do very many without getting caught.

Because all the ballots are posted on a bulletin board, anyone can count them up and know the result of the election.

You have to use other measures to make sure that extra ballots weren’t inserted, or that some people weren’t allowed to vote multiple times. But that’s true of every voting system–if you imagine the strongest possible voting system, it would still be susceptible to attacks where the same person was allowed to stand at a voting machine and vote repeatedly, all day long. The good news is, that is stuff that can be observed in public.

This is a fun voting protocol to play with, because it’s so much simpler than most cryptographic voting protocols. That has a cost–look at the patterned vote attack to see what the cost looks like. (Work out the probabilities for, say, an election with ten races on it, and you’ll see that making patterned ballots that are likely to stand out isn’t too hard.) The greater complexity of a scheme like Punchscan is partly to prevent this kind of attack.

The paper isn’t too complicated. It’s much simpler than most cryptographic voting system papers. If you want to understand these protocols, read the paper and play with the system a bit–it’s a great introduction, and the voting protocol is simple enough to hold in your head.

JimA • October 9, 2006 5:33 AM

Just an aside – what is so wrong about vote buying?
After all rich people/corporations can more or less buy an election with campain contributions (if it did not work they would not poor so much money into it!).
Whats wrong with letting the little guy benefit from the fix?

Etienne Fortin • October 10, 2006 3:21 PM

Why go to such extent to make an electronic voting machine? Oh I know. It’s way too difficult to have a paper voting system with human counting the votes…

But seriously, why do we have to invent such complicated electronics methods when we have one that works (at least in France, Germany, Canada, UK and others) : Standardised paper voting ballots with human counting the votes at the end.

What’s the added value of electronic voting machine? Why do we need them? Because it counts faster? We have elections each 4 years for god’s sake! We can wait a little bit to know the results with such a voting interval.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.