Friday, January 04, 2008

Fraud-proof Voting: A Simple Proposal

I've been thinking, off and on, about whether it would be possible to design a voting system that would not be vulnerable to fraud. I think I have a simple answer.

Each voter, before he comes to the polls, obtains a 20 digit random number--by rolling dice, a computer program, or whatever. Once he gets into the voting booth he enters the number into the machine along with his votes; the machine prints out a document certifying that that is his number and records his votes, his number, but not his identity. It might be useful for him to be provided with a sheet of paper with his name on it, which he inserts into the voting machine and gets back with his number stamped on it.

Once all the votes are in, they are posted--all of them--to the web, labeled by number. Any voter can then check his number to see if his votes are correctly recorded. Anyone can download the votes--to a suitably large hard drive--and add up the totals for himself.

The only serious opportunity I can see for cheating with this system is to record all votes cast accurately but also record an additional hundred thousand votes with made-up numbers that correspond to no voter. To prevent that, poll watchers provided by anyone interested keep count of the total number of voters.

One possible problem with this system is that it makes vote buying easy, since the voter can prove how he voted to the buyer. But that's already true of absentee ballots, which are widely used, so is not a problem vis a vis current alternatives.

Have I missed anything?

27 comments:

Myslivec in San Diego said...

I believe that there is even simpler system. A voter enters the booth, press the screen with the name of his candidate (so far, electronic voting). A paper ballot is printed on a small piece of paper. Voter takes this paper, verifies that he voted for the right candidate and then drops the ballot into the box.
Or even simpler, the paper ballot is shown and automatically dropped in the box.
After the election, randomly chosen machines and boxes have their numbers verified.

Paper ballots may be preserved for a couple of days, if necessary. Moreover, since paper ballots are printed, using a scanner for verification should be trivial.

Such system is easier for user (no need to have the code and retype it), but lacks the beauty to be able to verify my own vote.

On the other hand, it has the advantage of electronic system (immediate results, some simplicity for users) and limits the costs of purely paper ballot (counting all votes, using that much paper).

Anonymous said...

I wouldn't call it fraud-proof, but that would be a fraud-resistant improvement.

That doesn't account for people voting in multiple jurisdictions, nor does it account for box-stuffing (like you indicate.) It doesn't do anything for identity-based fraud, either. (Voting someone else's ballot for them, or worse yet, creating fictional identities and voting those.)

Matt Brubeck said...

There are various cryptographic systems that offer the same fraud-protection while still attempting to prevent vote-buying (a voter can verify her own vote, but she can't prove it to anyone else).

Ron Rivest (one of the inventors of the RSA encryption algorithm) came up with ThreeBallot, which attempts to do the same without using any confusing math.

One problem with your system is what happens when a voter claims his vote wasn't counted. The voter might be truthful, or might be lying. How do you decide? Do you invalidate the election or not?

Matt Brubeck said...

The problem with verifying fraud claims would be helped by your suggestion of a receipt, but the receipt presents additional risks to anonymity. Rivest's paper suggests that some anonymity could be restored by allowing voters to (optionally) anonymously exchange receipts with each other after voting.

Forgery of receipts presents another avenue for attackers to falsely claim fraud.

The machine in your system would need to be trusted not to record potentially-indentifying information (which includes, for example, the time or order in which votes were cast).

Anonymous said...

You've re-invented an old protocol -- it has been in the literature for many years. There are some variants of increased sophistication as well that can prevent specific attacks.

If you're interested, I can suggest some references on the voting protocols literature -- you should find the stuff reasonably accessible even though you're a non-specialist.

Anonymous said...

http://www.vocomp.org/index.php
http://punchscan.org/
http://www.pretavoter.com/

Daniel A. Nagy said...

As far as I know, this is very similar to the last independence referendum in Quebec.
There used to be randomly numbered ballots that could be teared along a perforated line, with the random number printed on both parts. In order to obtain a ballot (which was handed over in a sealed envelope), you proved your identity. The vote was then dropped into a ballot box.
Upon counting, they published voter names in alphabetic order and the votes lexicographically ordered by their large random serial numbers second AND the vote itself first in phonebook-like books. Both lists were numbered from 1.

Thus, anyone could have verified their own vote and the total tally.

jimbino said...

It seems necessary that no random number be duplicated. Then what happens if a faked random number with associated vote were identical to the number associated with a legitimate vote? And would there be an advantage to generating random numbers consecutively from a limited sequential set of seed numbers assigned to each polling place, so as to have a tally of the number of votes that had been cast?

Anonymous said...

I like your system, it is very simple.

The problem with cryptographic solutions is they are very hard for policy makers and general public to understand and trust.

I would add only two things:

A list of all voters (this list count will match the count of the random number/vote list). That will help the ability to audit against the introduction of fake voters).

The receipt can have anti-forgery features such as a hologram, and a digital signature.

Anonymous said...

David asks: "Have I missed anything?"

The fact that it doesn't matter?

Beastin said...

The objections I've heard voiced to this sort of scheme all concern either vote buying or intimidation.

Of course, you might avoid such problems by letting people print fake receipts. :)

I agree that fraud investigations ought to be substantially easier. You would simply randomly select people to call and ask whether the votes associated with their random number were accurate.

I also kind of like the idea of avoiding identity fraud by taking down people's names. Forget ID cards, just have them sign the register.

Anonymous said...

If the random number in David's scheme is generated by the voter, there's a chance of collisions; the Web list would presumably then say "three voters had the following number, and they voted thus." Such collisions provide an opportunity for skewing the total, but creating too many collisions would be statistically detectable, so you'd have to simultaneously downplay some real collisions for your opponent, and if there aren't many real collisions, the tweak won't have much effect on the outcome.

Actually, the biggest problem I see with this system is, as matt_brubeck writes,

One problem with your system is what happens when a voter claims his vote wasn't counted. The voter might be truthful, or might be lying. How do you decide? Do you invalidate the election or not?


The predictable result is that people whose candidate loses will claim that their votes weren't counted, and I don't see any way to statistically distinguish this from the situation in which the election really was stolen. Unless, that is, voters have counterfeit-resistant receipts, which as others have pointed out raises vote-selling issues.

I'm still inclined towards the more mainstream approach: "produce a voter-verified paper record and keep it around for recounting." Individual voters can't check later that their votes went into the total correctly, but they can check before they leave the polling place that their ballots are correct, and the routine recounting of a random sample of ballots should detect totals that significantly differ from the paper ballots. And this approach requires less work and record-keeping of the voters.

See http://www.verifiedvoting.org , among others. I think Rubin and Rivest have both spoken out in favor of this approach.

Joel Davis said...

probably a better system would be to use PGP encryption key and/or some sort of key based off biometric information to encrypt the "ballot" storing an unencrypted version along with it. This way if the results are called into question then the voting data just gets shipped to a reliable third party who first recounts the unencrypted votes and if that's kosher they "re-poll" everyone by asking them to provide them with the information needed to decrypt the other ballot. The voting machines would could then just dispense their own vote ID numbers if they wanted to check the online version. This encryption an idea that has been said before, but the use of third-parties is essentially you're ever going to have unbiased elections. Beyond that, the only way I can say you can decrease voter fraud is to decrease the mandate of the elected officials to lower the incentive, which may not be a bad thing by itself.

Joel Davis said...
This comment has been removed by the author.
Joel Davis said...

forgot to mention the US military uses CAC cards which fit into standardized readers and in order for the equipment itself to be able to get the encryption keys off of it, the user has to supply the PIN for the card. The card itself usually has the user's real identity (name, base, address, etc) on the card, but a third-party could easily use the same technology and just make the biographic data non-identifying outside of going back through them.

Anonymous said...

The problem with any mathematical/computerized/cryptographic system (and I say this as a mathematician and computer scientist who's studied some cryptography) is getting Joe Public to trust it. If it takes a degree in math to understand the proof that the system is secure, the other 99.9% of the population won't believe it; indeed, they may suspect that it's rigged by intellectual math-geeks to favor their weird egghead candidates.

Joel Davis said...

I think the public will trust it, the majority of low-end IT tech trust it and I doubt they understand the math involved. If you just explain the concept of public key (or whatever) I think most people are willing to have faith unless someone comes along to disturb it. If people are informed of how the system works and that so many successful businesses use the same technology (whatever tech. is decided on) to secure their own data, I believe the general public would accept it. You couple the fact that the powerful actually depend on it with the fact that the CAC's come from third parties.

Although, if I can ask, why did he make the provision that their identities be made anonymous, it seems to me that the ability to determine the originator's ability to vote and that this isn't a double vote would seem to be needed.

Beastin said...

If the number of votes matches the number of voters on the register, then sufficient fraud detection ought to be possible simply by asking everyone to go check to make sure that the proper vote was recorded for their random number. A voter for the winning party in a contested district could even help to defend the result by claiming their random number.

Sure, some people may still lie and say that they were cheated, but people can always say that. There's really no way with an anonymous voting system that you can prove otherwise. David's original proposal is simple and effective. Personally I think it's a good idea.

Matt Brubeck said...

"Sure, some people may still lie and say that they were cheated, but people can always say that. There's really no way with an anonymous voting system that you can prove otherwise."

So why put any effort into a fraud-detection mechanism if you can't do anything about fraud (or even verify it) when it happens?

Beastin said...

Matt,
Just because you can't prove that a single individual is lying doesn't mean that you can't assert with high probability that the outcome of an election was valid.

If everyone decides to lie then you're sunk, but this would make the result of any election look suspect.

Leonard said...

If the voter chooses the number, then there is an almost dead certainty of collisions. Many voters won't bother with rolling dice or whatever. Instead they'll choose 12345678901234567890, or 77777777777777777777, or one of a relatively small set of other numbers that are easy for humans to self-generate.

I'm not sure that such collisions are necessarily a bug, however. In essence, they allow the reintroduction of the current blind system, but optionally at the discretion of the individual voter. Voters who are extra paranoid might feel more comfortable voting on 00000000000000000000, especially if that became a known convention. So the ability to create collisions intentionally might be seen as a feature.

Raphfrk said...

The 3 ballot system linked in a previous post covers most of the issues here.

It prevents vote buying, while also providing a receipt.

They also came up with an improved version called VAV (vote, anti-vote, vote).

The only requirement is that you have a simple machine that will ensure compliance with the protocol. Basically, the anti-vote must perfectally match its corresponding vote and also, it must be capable of generating a copy of any of the 3 ballots.

Each voter places 3 ballots in a ballot box

- a vote/anti-vote pair
These must be indentical and the vote must not have any marking to indicate that it was part of a pair.

- their actual vote

Each ballot has a random number printed on it by the machine that the voter cannot see.

After they have filled out their ballots, they pick one of the 3 and receive a copy of it. They are shown the number for that ballot and can confirm that the receipt matches.

They take the receipt with them and the 3 ballots end up in the ballot box.

After the election, all the votes are published along with a list of everyone who votes. The number of ballots must be three times the number of voters.

If a voter wants to vote for A, but is paid to vote for B, there is no way they can prove who they actually voted for.

They could vote:

Vote: B
Anti: B (must match vote 1)
Vote: A

They could then copy their first vote and show the buyer a receipt showing a vote for B.

If someone modifies any of the 3 of their votes, there is a 1/3 chance of it being detected and there is no way the fraudster would know if it was a protected vote.

If fraud does happen, it would also be possible to tell which way the fraud happened by which votes were modified.

Anonymous said...

Sure, some people may still lie and say that they were cheated, but people can always say that. There's really no way with an anonymous voting system that you can prove otherwise.

In a voter-verified paper system, it is the voter's responsibility to check the accuracy of the ballot before leaving the polling place; after that, (s)he has no right to complain. The other question is "do the totals match the actual ballots?", which can be checked by manually recounting a random sample of machines or polling places.

Anonymous said...

I have a simpler solution. Do away with secret balloting. The arguments for it are specious. If you are going to vote for my enslavement, then I have the right to fire you from my employ and talk my daughter out of marrying you. Evil philosophys do best in darkness. Every vote should be listed beside the name of the scoundral who cast it. The result would be better votes.

Maurizio said...

Prof. Friedman,

Though you have provided some insights (such as pointing out the true attitude of the Church towards witchcraft, or noting that Weinberg's statement is poorly phrased), it seems to me you are still focusing on marginal issues, and refusing to acknowledge some key points from Harris and Dawkins. At one time you even went close to taking the opposite stand: you seemed to support the position that Dawkins calls "the God of the gaps" in his book. That is where you say:

"Part [of my skepticism with regards to the efforts of my fellow atheists] comes from weaknesses I can perceive in the foundations for my own view of the world."

But the fact that your understanding of the world may be incomplete, or that your mind may be in principle incapable of understanding the universe, does not provide a reason to put a God in those gaps, or to believe that any religious claim is true. If you don't acknowledge that, it seems to me you are inviting misunderstanding.

Even in this new post, you don't seem to acknowledge the distinction between the possibility that something is true, and having good reasons to believe that it's true. The fact that a particular religion _could_ be true (the same could be said of the Invisible Pink Unicorn) hardly implies that anyone on this planet has a good reason to believe it's true, or that he is being reasonable believing it. Instead of concluding that they themselves should not be convinced, you seem to conclude that they are being reasonable, because our brain works by pattern-matching. (I may have missed your point, in which case I apologize.)

Anyway, please allow me to drop the issue of the truth of religion, because I have a more urgent question to ask you, to which your contribution could be decisive, as it will be clear by the end of this comment. But first I need to ask for your opinion concerning the dangers of religious faith, and the responsibility of religious faith in many events. Would you be so kind as to tell us if you agree or disagree with each of the following quotes?

__

1. Harris:

"Consider the second commandment; thou shalt not erect any graven images. You remember the Muslims who rioted by the hundreds of thousands over cartoons... All that pious mayhem, the burning of embassies, the killing of nuns... What got them so riled up? Well, this is it, the second commandment.

Do you agree or disagree?
__

2. Harris:

“If the Koran were exactly the same, and there were just one line added to it, and the line said, ‘If you see a red-haired woman on your lawn at sunset, kill her,’ I can tell you what kind of world we’d live in. We’d live in a world where red-haired women would be killed often. We’d live in a world where people like yourself would say, ‘That’s not the true Islam.’ Twenty women in Baghdad would have their heads cut off and someone would come forward and say, ‘This has nothing to do with Islam. Some of them were strawberry blond. Some of them were strangled.”

Do you agree or disagree?
__

3. Harris:


"Consider, for instance, the human papillomavirus (HPV). HPV is now the most common sexually transmitted disease in the United States. The virus infects over half the American population and causes nearly five thousand women to die each year from cervical cancer; the Centers for Disease Control (CDC) estimates that more than two hundred thousand die worldwide. We now have a vaccine for HPV that appears to be both safe and effective. The vaccine produced 100 percent immunity in the six thousand women who received it as part of a clinical trial. And yet, Christian conservatives in our government have resisted a vaccination program on the grounds that HPV is a valuable impediment to premarital sex. These pious men and women want to preserve cervical cancer as an incentive toward abstinence, even if it sacrifices the lives of thousands of women each year."

Do you agree that what those people believe (about God and sex) has something to do with their position?
__

4. Dawkins:

"In July 2005, London was the victim of a concerted suicide bomb attack: three bombs in the subway and one in a bus. Not as bad as the 2001 attack on the World Trade Center, .... The murderers were British citizens, cricket-loving, well-mannered, just the sort of young men whose company one might have enjoyed. Why did these cricket-loving young men do it? Unlike their Palestinian counterparts, or their kamikaze counterparts in Japan, or their Tamil Tiger counterparts in Sri Lanka, these human bombs had no expectation that their bereaved families would be lionized, looked after or supported on martyrs' pensions. On the contrary, their relatives in some cases had to go into hiding. One of the men wantonly widowed his pregnant wife and orphaned his toddler. The action of these four young men has been nothing short of a disaster not just for themselves and their victims, but for their families and for the whole Muslim community in Britain, which now faces a backlash. Only religious faith is a strong enough force to motivate such utter madness in otherwise sane and decent people. "

Do you agree at least in part with the last sentence?
__

5. Dawkins:

"Once again, Sam Harris put the point with percipient bluntness, taking the example of the Al-Qaida leader Osama bin Laden (who had nothing to do with the London bombings, by the way). Why would anyone want to destroy the World Trade Center and everybody in it? ..."

Harris: "The answer to this question is obvious - if only because it has been patiently articulated ad nauseam by bin Laden himself. The answer is that men like bin Laden actually believe what they say they believe. They believe in the literal truth of the Koran. Why did nineteen well-educated middle-class men trade their lives in this world for the privilege of killing thousands of our neighbors? Because they believed that they would go straight to paradise for doing so. It is rare to find the behavior of humans so fully and satisfactorily explained. Why have we been so reluctant to accept this explanation?"

...

"Our Western politicians avoid mentioning the R word (religion), and instead characterize their battle as a war against 'terror', as though terror were a kind of spirit or force, with a will and a mind
of its own. Or they characterize terrorists as motivated by pure 'evil'. But they are not motivated by evil. However misguided we may think them, they are motivated, like the Christian murderers of
abortion doctors, by what they perceive to be righteousness, faithfully pursuing what their religion tells them. They are not psychotic; they are religious idealists who, by their own lights, are rational. They
perceive their acts to be good, not because of some warped personal idiosyncrasy, and not because they have been possessed by Satan, but because they have been brought up, from the cradle, to have
total and unquestioning faith. Sam Harris quotes a failed Palestinian suicide bomber who said that what drove him to kill Israelis was 'the love of martyrdom .. . I didn't want revenge for anything. I just wanted to be a martyr.' "

Do you tend to agree with Harris' explanation above?
__


6. Harris:

It is, therefore, not an exaggeration to say that if the city of New York were suddenly replaced by a ball of fire, some significant percentage of the American population would see a silver-lining in the subsequent mushroom cloud, as it would suggest to them that the best thing that is ever going to happen was about to happen: the return of Christ. It should be blindingly obvious that beliefs of this sort will do little to help us create a durable future for ourselves - socially, economically, environmentally, or geopolitically. Imagine the consequences if any significant component of the U.S. government actually believed that
the world was about to end and that its ending would be glorious. The fact that nearly half of the American population apparently believes this, purely on the basis of religious dogma, should be considered a moral and intellectual emergency.

Do you agree with the last sentence?
__


I need to know if you subscribe to the above positions, and to what extent, because the next thing I am going to ask you is whether you think that anarcho-capitalism could be the best way to protect the world from religious fundamentalism. The point is that people like Harris and Dawkins can't seem to figure out a way to oppose the threat of fundamentalism, especially the one offered by Islam. The only thing they can come up with, when asked what we can do, are unconvincing replies like "Fight bad ideas in your conversations, wherever you encounter them; do not withdraw your objections for fear of being impolite"; or "It is time to cease the automatic respect for religious beliefs, which causes them to propagate indefinitely", and also "Try to finance dissent in the muslim world; for example help finance protection to Ayaan Hirsi Ali". As you can see, they probably even realize the importance of economics in the issue, but can't figure out a way to exploit economics in such a way as to make fundamentalist laws inconvenient; in such a way to provide the most disincentive to fundamentalists from intruding other people's freedom. Do you see where I am going? I suggest that, if you can convince the "new atheists" that anarcho-capitalism is the best way to protect ourselves, you have the potential to convince the vast majority of atheists to embrace anarcho-capitalism.

Thank you very much for your attention,

Maurizio

Anonymous said...

Try the 'Robinson Method' - fraud proof, no computers or technology needed whatsoever, the result is known INSTANTLY the moment the final vote has been cast. The 'ballot' boxes are never taken out of the site of whoever wants to be present throughout the voting period (which could be thousands of people if necessary), and the results can be shown on video, over the internet, as they are revealed.
http://paul-robinson.us/index.php?blog=5&title=the_robinson_method_a_really_simple_way_&more=1&c=1&tb=1&pb=1

Scheme said...

Great post! After hearing about all the voting fraud that's going on right now, specifically in the Republican Caucus, South Carolina, Nevada, Iowa with Ron Paul being shut out by the media and very significantly artificially reduced in the polls, I thought of this exact same system...

It's really a wonder why our system isn't fraud proof like this! How can you have a democracy without a sound voting system. You can't. It's called totalitarianism.

After I wrote my blog post I happened to search online and find your post.

Here's mine: http://theworldplan.com/?a-fraud-proof-voting-system-the-people-must-demand-it-2012