Slashdot Mirror

For something as important as voting, how about paper only?

We actually have solutions that are much better than that. This wasn't true a few years ago when the whole voting machine fiasco started, but that discussion provoked a fair amount of research into secure voting systems, and security and cryptography experts have proposed a number of systems that provide verifiable end-to-end integrity. Each voter can verify that his or her vote was actually included correctly in the final count -- but without being able to prove to anyone else how he or she voted (important to mitigate vote buying/coercion). Each candidate/party can fully audit the ballots before the vote and the count after the vote, and audit results are provably correct.

The most thoroughly developed system is Chaum and Rivest's (this is the Rivest who is the "R" in "RSA") "Scantegrity" system. It actually does use paper ballots, slightly modified traditional "Scantron" forms. Rather than just filling in the bubble with a #2 pencil (though you can do that, and that will work, and it will only sacrifice one form of verifiability), instead bubbles are filled with a special marker that reveals a code. That code can be recorded by the voter and used by the voter after the election to verify that the voter's vote was counted correctly. Ballots are counted by normal Scantron scanners, and can easily be verified by hand.

But, thanks to the additional auditing steps (which rely on serial numbers on ballots and some carefully-defined processes) it's not possible to inject additional ballots into the process (no ballot box stuffing), nor to "lose" ballots, without detection. The system does make allowances for absentee and mail-in ballots, and has been used in a real election to verify that it's fully practical.

For more details about Scantegrity, see http://scantegrity.org./

And another thing, we should really do vote-by-mail nationwide just like Washington state does it.

There are signficant risks in that. OTOH, it doesn't seem like Washington is actually seeing them. Still, I'd move very carefully on that one.

FFS, doesn't anyone do any research before posting stories? 60 seconds of research would turn up the Wikipedia entry on End-to-end audible voting systems. The problem of being able to verify that your vote is recorded as you intended without revealing the actual content of your vote has been solved by several teams. The ones that seem to have the best handle on things are Scantegrity, Pret-a-Voter, and Punchscan (the predecessor of Scantegrity) .

Using Bitcoin (which in fact has anti-anonymity properties) as an engine for voting is like attaching a tractor to a horse carriage. It may get you where you want to go, but it's nothing like a proper motor vehicle.

--Paul

Only a handful of mathematicians would trust that.

Paper ballots with independents actually conducting the election taking ballots and counting them, etc, with overseers from all political parties welcome to watch the entire proceedings, from start to finish.

Simple and transparent.

No, even the mathematicians wouldn't trust it. See Bruce Schneier's 2006 essay that explains why.

Use paper ballots. Period.

However, crypto can still add value - it can go a long way towards preventing fraud and errors even in a paper ballot election. Scantegrity is an open-source system, invented by Rivest (the "R" in RSA), Chaum, and other researchers, that helps secure a paper ballot election by supplying each voter with a simple verification code that can be written down. The codes in no way compromise the anonymity of the voters, and cannot be used to determine what vote was cast. But they can be used by individual voters to verify that their votes have been counted correctly, and by election officials to verify that ballots have not been tampered with and that the results have been tallied correctly. The overhead cost of the system is low.

Scantegrity has been used successfully in two real elections - municipal elections in the Takoma Park, Maryland in the U.S. But so far it doesn't seem to be catching on very much. I guess it doesn't quite suit the needs of the big money electronic voting industry.

You are playing around with the right concepts.

What exactly would you be taking a hash of, however, and how would you verify the vote totals? Are you hashing the ballot serial number + the vote? Just because the election authority has published a hash that matches your, doesn't mean they used your vote in the announced total.

David Chaum developed the punchscan voting system as an end-to-end verifiable election protocol for paper ballots that allows anonymity and verifiability. Scantegrity is a successor system to that: http://scantegrity.org/.

I wrote up my explanation for how this works here: http://seedsofgenerality.blogspot.com/2010/09/secure-voting-protocols.html

The key concept is that of a cryptographic commitment.

This is a well-researched topic and there are already good solutions. One way to do it is print a random number on every ballot (random for each individual ballot that is) underneath each candidate and have the voter copy down the numbers corresponding to the candidates they voted for. Afterwards, the codes that correspond to the recorded vote for each ballot are posted online and you can verify that the vote they recorded matches the one you wrote down. That way you can check that your vote was recorded successfully but no one (not even you if you can't remember) can know which candidate you voted for.

To make sure that the codes actually correspond to the correct candidates you have the voting authority cryptographically commit to all the code-candidate relationships. You then allow voters to "spot check" the ballot they were given and request that all the codes be decommitted and published (they would get a new ballot afterwards). Add in a mix-net which allows anyone to verify the final tally from the published codes, without revealing any individual votes, and you have http://scantegrity.org./

This problem has already essentially been solved. There are several secure cryptographic voting systems (some with open source implementations) which provide the ability to verify to your vote without it being linked back to you. For instance, Scantegrity has a set of randomly generated codes on each ballot, one per candidate. When you vote, you copy the code corresponding to the candidate you selected and write it at the bottom on a detachable receipt. When you get home, you go to the website, put in your serial number and check that the published code matches the code that you wrote down. This way you can verify that the system recorded your vote as you cast it, but nobody but you can be sure of which candidate it was for. Additionally, there is a mixnet structure that links these codes to candidates and actual votes in a way that allows for verification of the final tally without compromising individual votes. This system has been used for several municipal elections already. Check out the paper if you are interested.

You have changed the topic, despite the fact that you quoted me.

If your belief is that technology can only make things worse, then you are, by definition, a Luddite.

The fact that technology cannot solve one particular problem does not make you a Luddite.

As I stated, being a Luddite is about belief. Take a look at Scantegrity. Does it solve every problem? No. Does it measurably improve results? Yes. Is it expensive or difficult to understand? No. Clearly this is something on the path to what will some day be a perfect system, but I'm sure if you present the concept to the folks at BBV, they will just poop all over it, just like they do everyone who attempts to find solutions to the issues with voting that BBV is so happy to publicize. And if you spend the time going through the BBV website, you will not find any suggestions, only problems.

Everyone deserves mathematical assurances that his vote is counted and confidential. There's lots of systems out there, but one has already been successfully deployed. It's called Scantegrity II by Ron Rivest of MIT. It's already been tested in an election in Takoma Park. If you are using optical scan machines the marginal cost to add Scantegrity was only a few hundred bucks per voting machine.

This exists, and it's called Scantegrity. At USENIX Security last week (where the Pac-Man demo was unveiled), there was a paper reporting on their experience deploying Scantegrity in a real binding government election.

This exists, and it's called Scantegrity. At USENIX Security last week (where the Pac-Man demo was unveiled), there was a paper reporting on their experience deploying Scantegrity in a real binding government election.

Scantegrity is the successor to Punchscan, developed by the same people (David Chaum et al). The only detailed analyses that I can find about their differences are behind journal paywalls like this one at the IEEE.

Finally!!!

So now that you understand the issue, and the fact that ALL elements needed to identify you AND your vote are in the hands of the voting authority will you go back and re-read the paper http://www.scantegrity.org/papers/ScantegrityII-EVT.pdf with a more critical eye?

But the whole system wouldn't work at all if there was not a linkage between your three letters and the Candidate's name SOMEWHERE.

Incorrect. Those letters have nothing to do with your vote selection, they're just an integrity check.

Again, read the paper.

Read what he's saying. I have ballot 24664971 in my hand. I download apache.log and find the IP address of the person who accessed votecheck.net/check?ballot=24664971 and I trace that back to you. I now know who you voted for. It has nothing to do with the three-digit numbers.

Now, in my opinion, that's not a big deal, but I thought I'd explain it to you anyway.

But the whole system wouldn't work at all if there was not a linkage between your three letters and the Candidate's name SOMEWHERE.

Incorrect. Those letters have nothing to do with your vote selection, they're just an integrity check.

Again, read the paper.

Clearly you understand the SOMEONE knows exactly which candidate those letters on your specific ballot refer to?

No, the system is carefully design to ensure that NO ONE knows who those letters refer to.

Read the paper.

I'm far more concerned about phantom votes being counted than real votes not being counted.

Both are real issues. There are plenty of examples of ballot boxes getting "lost", so those are real problems. Dead people voting, multiple votes, systematic exclusion of voters (not losing their ballots, but preventing them from voting), all of these things are problems.

This system doesn't solve all of those other problems, but it does solve the problem of votes getting lost, altered or counted incorrectly. And it does it in a mathematically-provable fashion.

See the paper.

And if they have access to the actual ballots, who you voted for. A non-transparent system with a way to match voters with their votes that has been "verified to be secure by the brightest minds at MIT". Every dictators wet dream.

There's nothing to connect the information displayed with the physical ballot. The linkage to vote selection cannot be made.

Read the paper.

But the practical implementation could provide a way to prove that they voted for someone. My cynical suspicion is that by the second or third election, they'll use mass-produced ballots ballots that only have three or four different sets of codes on them to reduce the cost of ballot printing.

See section 4.9 of the paper (actually, read the whole thing). Auditing is done both by candidates and by independent auditors.

How exactly do we verify that the choices we didn't pick on the form don't have the same set of verification characters as the candidate we did choose?

That's handled by pre-election auditing. There's more information on how at http://scantegrity.org./

Or, go straight to the research paper at http://www.scantegrity.org/papers/ScantegrityII-EVT.pdf

How exactly do we verify that the choices we didn't pick on the form don't have the same set of verification characters as the candidate we did choose?

That's handled by pre-election auditing. There's more information on how at http://scantegrity.org./

Or, go straight to the research paper at http://www.scantegrity.org/papers/ScantegrityII-EVT.pdf

but does not provide them with any way to prove to anyone who they voted for.

But can I check to make sure not just that my vote "was counted" but that my vote was for the right person?

Yes:

Voters make their selections on a paper ballot using special pens with ink designed by Chaum. When a voter fills in an oval on the ballot, the ink in the pen, which is similar to the yellow ink in highlighter pens, reacts with invisible ink in the oval and turns most of the oval black. At the same time, a unique three-letter code pre-printed on the ballot inside each oval is revealed to the voter.

After making their choices, voters use a form to write down the serial number that is printed on their ballot as well as the three-digit codes inside the ovals they’ve chosen. The codes are generated cryptographically and are different on every ballot to prevent someone from deciphering the voter’s choices and engaging in vote-buying.

So that's the "verify that it was recorded correctly" part. For the "verify it went to the right candidate part":

Voters can also see, based on the three-letter codes, that the system seems to have recorded their selections accurately. But voters can’t be sure just by looking at their ballot image that the system interpreted the codes accurately to apply the vote to the correct candidate. That’s where independent auditors come in.

Scantegrity uses a process called “zero knowledge” that allows skilled, independent auditors to verify that the codes result in votes going to the right candidates, without actually revealing an individual voter’s selections.

I don't know how it works exactly, but I assume it's similar to a public/private keypair given that they describe it as a cryptographic mechanism. The interesting thing is that anyone can audit the election results to demonstrate that votes were counted accurately: https://scantegrity.org/svn/data/takoma-nov3-2009/PUBLIC/PUBLIC/

This is a crude proposal. There are probably much better ones out there.

Yes, quite a few. They tend to run along the same lines, but with different approaches for ensuring, with high probability, that your ballot ID can't be tied to you.

See ThreeBallot (and variants), for example. Others include Scantegrity II, which has gotten a fair amount of attention recently.

I think everyone who is interested in electronic voting should take a look at this website. This group was originally just a bunch of computer scientists trying to apply theory to practice. In my opinion, they succeeded quite well, and I wish more people had heard of them.

Scantegrity.org

Every optical-scan voting system should use scantegrity.

Just saw your comment hit on my google feed reader. Thanks for the vote of confidence! :-) You might want to check out Scantegrity. That's what we've been up to lately.

A solution is to obscure the information by giving each voter not one, but a list of ID numbers and told which one is theirs privately. That way, nefarious organizations wouldn't be able reliably say they've been given the correct number, which should kill their scheme. It's not a perfect solution, though, and I can already see flaws in it, but that just means it needs a bit more work before it's ready for prime time.