Slashdot Mirror
Punchscan Wins Open Source Voting Competition
An anonymous reader writes "Punchscan emerged victorious at the open source university voting systems competition, VoComp. For their efforts, they will receive the US$10,000 prize provided by ES&S (which has recently been named in a scandal in Florida). The second-place team put up a good fight: 'Per Ron Rivest, one of the contest's judges, the runner-up team, the Pret-a-Voter team from the University of Surrey in the UK, gave Punchscan a tough run for the first-place money until the Punchscan team dug through Pret-a-Voter's source code and found a significant security flaw in their random number generation. Oops.' It will be interesting to see if these systems ever make it into the mainstream. Kudos to ES&S for showing their forward thinking in this area, as the other voting machine vendors, such as Diebold, did not support the competition."
A system with a significant flaw in security comes second?
Does this explain the last two presidential elections?
Intron: the portion of DNA which expresses nothing useful.
Take home receipts are vulnerable to exploits that make them seem useless. Any random voter could go home and make a fake receipt to claim the results were tampered with. Sure, you could combat that by keeping record of which ballots, with their identifying numbers, were passed out, but if you're going to tamper with the election results, you could delete the vote from the count and the list, then when the voter complains their vote wasn't counted you could claim they faked their ballot...
The only problem I see with this system, as it was with the hanging chads, is that people with poor vision or low brain power will be easily confused by the way the choices are out-of-order. Maybe they could use colored letters to make it easier to match them up, or even use pictures, e.g. a dog for Clinton, a snake for Giuliani.
To quote a now dead, but once very powerful man: "He who votes decides nothing. He who COUNTS the votes decides everything."
It's charming to see people coming up with Open Source voting and other governmental tools, but extremely naive to think that they'll ever be implemented. Even if they make their way into governmental dialog, they'll be co-opted by Diebold, et.al. in the 11th hour before any policy is changed.
I want to delete my account but Slashdot doesn't allow it.
We need more than preaching to the choir - everyone should link to this from their blogs, post it as a bulletin to their friends on Myspace, etc. etc. etc.... the more people hear about these things, the more likely it will be that we actually start using OSS-based voting machines on a large scale.
3 2 1, GO!
It is pitch black. You are likely to be eaten by a grue.
I think it was a comment here that once suggested a voting system where users could ensure that their vote counted.
Every registered voter has a public / private key.
Votes are digitally signed by the voters.
Then after the election (or during), the signed messages are posted online.
Voters would be able to see that their vote counted in the right direction, and unless someone else knows your private key, nobody would be able to tell who you voted for.
The non-digital analog to this went something like this. Think of it like a system where you write down who you vote for on the top of a piece of paper. Then you tear off the top and place it in a sealed box. The bottom half is your receipt. After the election, you can compare your bottom half to every top half out there until you find the one that matches the tear pattern.
It's called oversight. Punchscan makes it easy for every single voter to ensure that the items they marked are exactly what was entered into the database. People can even download large randomly-selected chunks of the database to help ensure integrity. Read Wikipedia for more of the security features.
After seeing the machines, the 6 judges cast their votes electronically. The votes were 2 for Pret-a-voter, 3 for Punchscan and 107,345 for Diebold.
Just wanted to mention that one of the graduate students behind Punchscan, Richard Carback, was/is a grad student in Computer Science at the University of Maryland, Baltimore County. Way to get UMBC mentioned on Slashdot, Rick!
It was a pharoh who said to take everything with a grain of salt?
I prefer the "u" in honour as it seems to be missing these days.
How did they count the votes to determine who won?
Punchscan handles this scenario. It means you can prove that you voted for A, A, D and C (and validate that this set of votes was counted correctly) -- but you can't prove who option A on item #1 was on your ballot (as opposed to someone else's ballot), so even when knowing that you voted for A on #1, Vinnie can't tell whether you voted for Enzo or not.
Bloody hell, people, learn how this works before you trash it.
I would like to have had the chance to put my mailclad.com idea into the running on that one.
Anyhow I need to actually get my code up on sourceforge first I guess.
Anyone want to help get this thing off the ground.
John
I am always doing that which I can not do, in order that I may learn how to do it. - Pablo Picasso
I guess they figured that, for PR reasons, it was better to silently throw out votes than inform the voter that the ballot box was stuffed^w full.
Sometimes boldness is in fashion. Sometimes only the brave will be bold.
For something that is literally the heart of democracy, i.e., voting, proprietary systems are anathema. May Diebold act in accordance with its name, dying a bold and noble death, in searing flames....
'He who has to break a thing to find out what it is, has left the path of wisdom.' -- Gandalf to Saruman
as the other voting machine vendors, such as Diebold, did not support the competition.
Of course they didn't support it. The first or second place projects in the competition are both better than the crappy voting system marketed by Diebold and they are *free*. If your competition is free and it is better then you are in a world of hurt. Diebold is the classic example of a company which didn't make a very good transition of expertise in physical real world security products to software products.
While the Punchscan system appears to resolve the problems of auditability and vote tampering quite well, the issuance of a ballot receipt - no matter how indirect - allows verifiable vote buying.
The system also does not resolve one of the key points of HAVA - which, while deeply flawed, addresses some very deeply held concerns of disabled voters. That problem is one of ballot access - Punchscan is not disabled-friendly.
Let us live so that when we come to die, even the undertaker will be sorry -- Mark Twain
... my first thought was, "So what kind of voting machine did they use to count the votes for best voting machine? Was is the Punchscan machine?"
Prov 9:8 Do not rebuke mockers or they will hate you; rebuke the wise and they will love you.
...if your vote didn't matter, the weasels wouldn't try so hard to mess with the count. Votes matter--never doubt it.
The if the fear of the unlikely chance of voter key compromise is reason enough to put you off on voting freely we've already lost.
Quack, quack.
So, the free and open source solution has won a competition. Is the point now to somehow compel Diebold to seriously consider actually using this open source solution?
"God is dead." - Frederik Nietzsche
A point well made, but not made nearly often enough.
People will complain that it's impossible to individually count ballots, by hand, on a single day, using nothing more than volunteer labor, despite the fact that they are all individually cast, by hand, on a single day, using nothing more than volunteer labor.
The thing about things we don't know is we often don't know we don't know them.
We do it in Canada, and since counting ballots scales perfectly well, no matter how many people you have, there are no problems. The more ballots you have to count, the more people you have to count the votes, the more people you have to watch the counting, to ensure that it's done properly. I don't understand why we need any other way. For hundreds of years (if not longer) paper voting has worked just fine. Why all of a sudden are we trying to fix something that was never broken.
Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
So if all I can verify is that I voted for A, A, D, and C, then how can I actually verify that my vote was counted correctly. I'm not sure of all the details of the system, but it seems to me like it would be possible to show someone a scanned image of their sheet showing A, A, D, C while recording something completely different in the database. Also, am I the only one who thinks that understanding the voting process shouldn't require a PHD in computer science? I like the pen-and-paper-human-counted system because I completely understand how it works. With electronic voting machines, there's some organization saying, trust us, it works, don't worry about how it works, it just works. Diebold says the same thing about their systems, why should I believe one organization over another? What's wrong with a system that's simple enough for everyone to understand.
Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
``a significant security flaw in their random number generation''
Inquiring minds want to know: what was the flaw?
Please correct me if I got my facts wrong.
The voter can then take home the piece they chose, which (in either event) has two of the three pieces of information needed to prove whom they voted for. After the election, they can then compare that physical token which they hold with the publicly available, scanned versions of the non-shredded tokens which were counted.
So -- the way voter validation is done is very easy for anyone to understand, without a heavy cryptography background available. Also, notably, there's no computer needed at all to implement the actual voting process (which is typically implemented with nothing but paper)... though the generation and validation of the ballots is a different matter.
The only thing that requires computers to implement, and a cryptographic background to understand, is the secret kept back at the voting organization describing the item orderings used for the ballots. Now, the election organization can't change these after the fact -- because of the implementation (getting into crypto here) any change to it would effectively randomize the orderings on every ballot in existence, and the 1/2 of people who decided to record and keep the half of their ballot containing that ordering information would notice, making such an attempt futile.
The worst that a corrupt election authority can do under the Punchscan system is release the ordering information to some colluding group, thus allowing a third party to tell how individuals voted; they cannot miscount your vote without being detected. (Without knowing the serial numbers on individuals' ballots, they still could not identify the votes -- so while a corrupt election authority could allow a third party to identify how you voted, they could only do so if you were compelled to show that third party the serial number on your receipt). Compared to a corrupt election authority being able to completely throw an election, this is an extreme and dramatic improvement, and it answers your question (why should I trust one group over another?) in that any election authority implementing the Punchscan doesn't need to be trusted -- the system itself provides for transparency and public oversight.
PunchScan is principally implemented on paper, and adds dramatically to the security and auditability of preexisting paper systems. If I've done a bad job of explaining it, you can walk through the process of voting with PunchScan (or counting the votes) here, here and here.
Well, this flaw found in the second place team's code is the perfect example of why e-voting software should be open source. If it was hidden, odds are that flaw would never be discovered; and might not require a deliberate attack to cause problems in the future.
There is a strong correspondence between e-voting and encryption technology. The assumption for all encryption technology is that evesdroppers will always know your method (i.e., the source code), so instead you make that knowledge useless by using encryption that require a secret key.
One reason an e-voting system would need a random number is to generate some kind of key sequence. So a flawed random number generator is serious indeed.
Hear, hear! Denmark has manual counting from paper votes, too, and it just works. We get the results the same evening. Importantly, the counting (and re-counting next day) are both open to the public. I see *absolutely* no need for machinery.
Link to more info (in English).
I'm still trying to wrap my head around all this and fully understand how the punchscan system really works. And I have a University degree in software engineering. How do we expect the citizens with maybe only a highschool or lesser education to understand the system. Maybe the system is perfect (except that they can figure out who voted for who), but personally, I don't see why they need to make it such a complicated process that the average voter can't understand the details of how it works. I can understand every aspect of how pure paper voting works, and so can everyone else. I've gone through the punchscan site and all the demostrations of counting and auditing. I still don't really understand it fully. I understand the process, but I don't really understand how it makes voting any more secure.
Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
For the complex parts, this thing won a contest where Ron Rivest was one of the judges. It's been audited by some seriously big names. For the simple parts, which is everything but the way the sequencing is generated and the votes are actually counted (as opposed to the slower way which requires knowing the sequences for each ballot)... they really should be intuitively understandable. I explained it to my wife, and she has no computing background whatsoever. (Mind you, though most of the explanation she was looking at me like I was on crack, but eventually it all fit together).
Here's the thing: You may understand how existing paper ballots work, but that doesn't mean they have adequate security guarantees. They're a whole lot better than some of the existing electronic systems, without question, but there are still plenty of cases of voter fraud going on where paper ballots are in use.
Punchscan provides mathematically provable guarantees (with quantifiable but very small allowance for error) that an election cannot be tampered with. The exact allowance for error depends on the percentage of voters who choose to verify their ballots after-the-fact, but in any event it makes election rigging an activity which is much more likely to be successfully detected after-the-fact than it has been at any point in history.
Now, getting back to a simplified version of how it makes an election more secure:
You can validate that your ballot is part of the archive of recorded ballots which is made accessible to the public (so you can be confident that your ballot was recorded when cast -- this itself is a big improvement), and that 2/3 of the data involved hasn't been tampered in such a way as to change your vote. (Understanding how tampering with the other 1/3 is prevented means getting into the math; however, while I haven't studied this implementation well enough to grok it, I know enough similar ways of getting to the same end that I trust [with the level of expert and competitive review involved] that they didn't FUBAR it. I prefer to think of it as using a value stream off a single, established PRNG key -- which is close enough for completely nonprofessional horseshoes, though it doesn't explain some of their nifty properties [such as being able to perform and verify the count based only on the publicly released data without seeing the mappings which represent the hidden ballot piece]).
Individuals can validate that their own ballots made it into the counted data (as this is published to the public), and 3rd parties can validate the count itself off this published data using some magic. There you are -- oversight, and a massive improvement over what traditional election methods have to offer.
Denmark and Canada have parliamentary democracies where ballots often contain only one race, that for the national legislature. In the United States, most elections includes half-a-dozen or more races at a time, not to mention ballot measures. In most presidential years, voters are choosing in at least a presidential and a legislative election (the House of Representatives) and sometimes a third election for Senate. In "off"-years, there won't be a presidential election, but there could easily be races for a dozen or more different state and local officials. On top of this there could be half-a-dozen or more ballot "questions" (referenda) to tabulate as well. Hand-tabulating results for all these races takes time.
The evidence on voting machines I've read (projects at CalTech, MIT, Berkeley, and Stanford, for instance) usually find that traditional paper ballots and optical-scan ballots are among the most reliable technologies. Both offer post-election physical ballots for recounting, and optical scanning addresses the problem of tabulating multiple offices quickly.
When Louisiana upgraded our voting machines, we sold our old voting machines to Mexico. Let me tell you, the Mexicans were really pissed when Edwin Edwards won the election for President of Mexico!
Don't believe all the bad things you have read about Lousiana politics. In all reality, it is much much worse!
I only look human.
My mother is a halfling and my dad is an ogre, so that makes me an Ogreling
To quote a now dead, but once very powerful man: "He who votes decides nothing. He who COUNTS the votes decides everything."
Quite true. At least we can get a fair count with this system, or a verifiable count. I expect an OSS system would be first used by small towns in low tax areas. Chaum's desire for licensing revenue could scuttle the whole ship, though. Can somebody please give him a grant to keep him happy? He's done good work, but a patent on this kind of think can do bad things for democracy.
Speaking of democracy, and the reason I bothered to hit reply, I see lots of folks talking about OSS systems, but nobody talking about how those systems count votes. We have a very primitive system in place with lots of people trying to game a broken system. Since our countries were founded, better counting systems have come about, specifically the Condorcet method. The basic idea is this.
Say in our next election the votes break down like this:
44.88% - Barak Obama
44.87% - Newt Gingrich
8.2% - Mike Bloomberg
OK, so who's the President? Barak Obama. What percent of the population care for that? 28% if we have a high-side-of-average turn-out. Fewer if Obama voters really would have rather voted for Kucinich or Nader, but were gaming the system.
Now, imagine instead of having a 'pick one' system we have a Condorcet ballot:
Please rank the candidates in the order of your preference
Now, then, 44.88% of the people may list Barak Obama first, and 44.87% of the people may list Newt Gingrich first, but, wait, what's this? 72.5% of the people put Ron Paul down in the #2 spot (and so on). Now who best represents the person the most people would really want to have in the Oval Office? Even voters in Palm Beach County can see what the right choice is.
Math and CS geeks will want to check out the Schulze method for resolving ties and optimizing fairness. This particular variant is only 10 years old, so it's not like Jefferson could have implemented it, but it's about time we bowed out for the Renaissance era.
My God, it's Full of Source!
OUTSIDE_IP=$(dig +short my.ip @outsideip.net)