Slashdot Mirror
A Secure and Verifiable Voting System
meese writes "The cryptographer David Chaum, through discussion with top cryptographers such as Ron Rivest, has designed a secure and verifiable voting system. One of the goals of his design is that anyone can verify that votes were tabulated correctly. It's good to see real security/crypto people working on this problem. They also have a press release."
...is an awesome mathematician/cryptographer. I'm working on a project (on SourceForge, but it's not nearly far enough along for me to announce anything on /. yet) based on his digital cash system, and some other things he's done. Yes, I know it's patented, but it's really meant as a proof-of-concept type deal.
I just hope that if Chaum starts a company for his e-voting solution, it fares better than Digicash. IIRC, he wouldn't sell to M$ for $100M or to Visa for $40M, but ended up bankrupting Digicash and having to leave it. I'm not sure if I've got all the details right, so anyone's welcome to correct me.
I claim first use of "Error No. 0B" - or "No. 0B error." It'll be the new ID 10T!
in an workshop held here in Brazil (Alfred Menezes and Darrel Hankerson were the other lecturers). Folks, the system is perfect. There's nothing to complain about it -- laymen can check that their votes were counted through so-called `visual cryptography' (an idea of Adi Shamir IIRC), while everything else you'd expect from a secure and reliable voting system is provided. One can only hope that this is deployed somewhere, but I'm not holding my breath.
Read the paper, it's really jawdropping. Cryptography at its finest.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
Folks can' still vote multiple times if they get more than multiple registration cards. Dead people can still vote. Illegal aliens can still vote(i.e. someoen can get a drivers license with Mexican ID-and then get a voter registration card).
The main thing the Chaum proposal handles is fraud by a few people via voting machines. Fraud by election officials using lower tech mechanisms would be more difficult-but still possible.
The point of the two-receipt system is that it's easily verifiable in the booth, but impossible to verify outside. That means that any random voter can look and, instead of a long number to verify, they just see the text of who they voted for.
The single receipt cannot be decoded as you suggest -- each pixel is utterly random. There will be no pattern to detect, within the limits of pseudorandom numbers.
That works because the two receipts basically perform an XOR. Each pixel is either
XO or OX
OX XO
Call the first '1' and the second '0'. Then 0^0 = partially clear, and 1^1 = partially clear. 0^1 or 1^0 = fully black. When you're printing a pixel, then, you completely, utterly randomly select 1 or 0 for one receipt. You then print either the same, or the opposite, on the other. There is no pattern whatsoever from pixel to pixel, and once half the receipt is destroyed, it is quite impossible to read the other half.
The problem with the system you propose, by the way, is that anyone who had your SSN and MD5 hash could relatively quickly determine the choices you made just by trying all the combinations. If I was buying votes, I could tell you what choices to make, and then demand my money back if I couldn't reproduce your MD5.
Well, it is broke. Lots of recent elections have proved this, including the last presidential election. The hanging chads were not even close to the only issue either.
That said, there are many things that truly weren't broke about the last system that need to be preserved.
1. Your receipt should not include a way to find out how you voted. If your vote doesn't stay completely in the voting booth then some people will try to coerce your vote because they will be able to ask you to "prove" how you voted. Picture your boss asking everyone to print out their receipts on line and show him that you voted for his pet project. This is very important and the old system preserved this confidentiality.
2. You should be able to easily, visually verify how you voted and THE EXACT SAME verification paper should be used to tabulate the vote. In other words, you should be able to look at a paper receipt listing all your choices with a big check mark next to them and that receipt goes straight in the ballot box which then electronically tabulates from the paper, just like the old system.
Folks, this is ridiculously simple. Vote on screen, print the vote, put the printout in a privacy envelope. Take the vote to the ballot box. The ballot box sucks in the vote, tabulates and encrypts it on the spot, then electronically sends it to the polling database. You take a receipt stub out with you and you can check online that it was valid, and you can track it to its final storage place much like the FedEx tracking system, but you can't find out details of the vote online. If there is impropriety, the ballots have already been neatly stacked by the ballot boxes (they work kind of like ATMs do with your deposit) so they can be reread at high speed by recount machines and everyone could check online to be sure their vote was recounted. In special circumstances the votes could be visually recounted and, yes, you could check online to make sure your ballot got the visual recount as well.
The important point here is that no one can do any funny business with the paper because it's in that secure box and no one can coerce you to vote their way. But most importantly, if the computer is messed up, fixes could be made and a second, third or fourth vote can take place from the original ballots almost as rapidly as what happened with the first ones. Finally, it's very simple for any non-technical person to understand, so regular people will have faith in the process. And don't we all need faith for the system to truly work?
TW
You did not read the paper very carefully. The receipt can be proven to have the proper 'signature' (think public key cryptography), and it can be proven to have been tallied. But it CANNOT be proven to correspond to a specific vote, thus it cannot be used for coercion. The paper makes that explicitly clear in the first couple pages of the report.
"I will trust Google to 'do no evil' until the founders no longer run it." Hello Alphabet.
The only way I can think of to keep vote you made readable would be to take into the booth a bogus second layer and then hand it to the poll worker to shred--leaving your vote intact and readable.
As far as not verifiable, you have to be able to tell if this random hash you have in your hands is the one on the screen--how would you do that? It's not like you can print it, all .pdf viewers are different and even if they weren't only a very few printers have the precision to print exactly to scale to the precision that would be required... Consider that even printing machines have errors on the scale that they would require.
Actually, I was asking about how you would verify that the random hash piece of paper you took home from the election is the same as what is on the screen. I imagine a vote would look very complex (if you look at how complex even a simple character looked in the paper when it was encripted). You may note that this paper does not propose a humanly readable vote, just a human readable id number. That way you can't prove who you voted for, but you can (if you try hard) verify your vote.