Stories
Slash Boxes
Comments
Search

News for nerds, stuff that matters

Slashdot Log In

Log In

Create Account  |  Retrieve Password

Verifiable Elections Via Cryptography

Posted by kdawson on Sun Nov 05, 2006 09:13 PM
from the but-suppose-they-don't-want-to-make-cheating-impossible? dept.
Security Government Politics
An anonymous reader writes, "Cryptographer David Chaum and his research team have invented a new voting protocol which allows voters to verify that their vote has been correctly cast and counted. This is enabled using a surprisingly low-tech technique of cryptographic secret sharing. The secret — your marked ballot — is split into two halves using a hole punch" You take half home and can verify later via a Web interface how your particular ballot was counted.
+ -
story
This discussion has been archived. No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

Verifiable Elections Via Cryptography 50 Comments More /

 Full
 Abbreviated
 Hidden
More
Loading... please wait.
  • Okay, I've watched the video and read the article.

    I still don't understand it. Why does their video have two different types of hand writing on it? Is the voter supposed to write in all the options when s/he votes?

    What's to stop someone from getting a copy of the form and threatening you unless you vote the way they want you to? Unless every form is different (is this the part why the hand writing is different?), any attempt to match the vote online can be used to verify that you voted the way you were told
  • Doesn't this method require a government willing to hold itself up to scrutiny? I love the fact that people are coming up with excellent ways to ensure a secure vote, but the fact of the matter is, nothing has been done to fix the existing holes that have been found in the voting machines that are being used, even after widespread media coverage. New methods of voting aren't going to solve things, getting the existing government out of power so that we can actually implement these ideas will.

  • Many people here have pointed out the uselessness of this method, not to add the
    social pressures it may cause in communities or groups where things have a
    to happen a certain way if you know what I mean...

    To add to that I can see no place where cryptography is used other than possibly
    trying to determine the probability that on any particular ballot card Party A
    was on the right or the left, thats just simple probability theory nothing else.

  • Everyone has so far completely missed the point! (Score:5, Informative)

    by X-treme-LLama (178013) on Sunday November 05 2006, @10:22PM (#16730907) Homepage
    Good lord! How is it that 70% of people have completely missed the point?

    This system DOES NOT allow ANYONE to see WHOM you voted for.

    That's right. NO ONE short of the people in charge can see who you voted for. You boss can't make you prove it, nor can your spouse, or whoever else.

    All the ballot half you keep records is that you voted A, B, B, A. All you can verify online is that your vote was recorded as A, B, B, A. Because the ballot choices are randomized, no one can tell who A was for your particular ballot. Ahh, but I already hear the tin-foil brigade saying: "But the people in charge can check!!" Really, how? The ID # of your ballot isn't recorded next to your name in the voter rolls, I suppose someone who had access to all the decryption keys could fingerprint each and every ballot, but anyone who can get ahold of any of the paper ballots can do that now. Is it no less secure than any traditional method of voting, and superior in a vast number of ways. As long as a few percent of people check that their votes match what they recorded, elections will be a lot closer to tamper-proof.

    How did so many people fail to figure all that out?

      • Re: (Score:3, Informative)

        by ralphbecket (225429)

        But how do I know that the cheating doesn't happen at this stage? It would be very easy for the machine to count all votes as being for George Bush regardless of what the bottom half of the ballot says (because the bottom half of the ballot has been destroyed).

        No, because...

        It claims to get around this by some auditing process.

        If you READ THE POXY PAPER you would understand the auditing process. The candidates can audit 50% of the votes to check that they were counted correctly without violating voter anon

                  • Re: (Score:3, Interesting)

                    by swillden (191260) *

                    Sure, by opening up the right side of 50% of all votes, and the left side of the other 50% you can verify that the tables are indeed correct.

                    No, you open up the right side of 100% of the votes and the left side of 100% of the votes -- but you permute the votes so that they can't be lined up. This is why multiple mapping tables are used.

                    But that still does not mean they are counted correctly.

                    Yes, it does. All of the tables with the decrypted vote sides opened provide everything you need to tally the

  • Handcounting: How Slow Is It? (Score:5, Insightful)

    by kthejoker (931838) on Sunday November 05 2006, @11:43PM (#16731453)
    My district has roughly 650,000 voters in it.

    Let's assume we have the best turnout in a non-Presidential election in the past 40 years: 54%. That's highly unlikely - no one's really contesting in my district (our guy's an old time shoo-in) - but who knows? People might show up.

    54% of 650,000 = 350,000, give or take a few.

    How long would it take to count 350,000 votes for something?

    Let's assume a person can count 1 vote every 3 seconds. Count it out loud. "1. 2. 3." It's pretty slow, actually, but let's be fair: some of our more civic-minded people are also some of our eldest, and they're a bit slow.

    So 1 vote every 3 seconds, that's 20 votes a minute, which is 1200 votes an hour.

    350,000 / 1200 = 291 man hours.

    In 8 hour shifts, that's 37 people. And considering my district is spread out over 30 towns, that's roughly 1 person per city - 2 for some of the larger ones. Find 37 more people and you've even got redundancy.

    And that's if you want it done in one day.

    How about the Presidential election? 2004 was considered a banner year for turnout. Number of voters? 122,294,978. We'll round it down to 120 million. Again, 1200 votes an hour: that's 100,000 man hours.

    8 hour shifts, that's 12,500 people. Again, that's in 8 hours, reading 1 vote every 3 seconds. If you got it down to 1 vote every 2.5 seconds (and trust me, when things are repetitive, it's easy to speed through), suddenly you only need 10,417 people.

    You've just laid off 2,100 poll workers in half a second.

    There is no reason at all for a backlash against paper balloting. It is quick enough. In fact that should be the motto for all paper balloting:

    PAPER Balloting: It's Quick Enough.(TM)
    • I'll sell my vote for $500, you can even verify it with this hole thingy.


      $500? Sorry bud, if you want to keep your job, you will vote the way that the company tells you to.
      • $500? Sorry bud, if you want to keep your job, you will vote the way that the company tells you to.

        Can you say "unlawful termination?" I knew you could.

        All it takes is one employee willing to fork over the $250 to file a court case, and they get to own the small business they work for. Governments and publicly traded businesses already have pretty strong employment rules against that, leaving only the "small business" as a bastion of that kind of stupidity.
    • Exactly. Voter-verifiable voting is not the issue. Ideally, you want to be able to verify your vote but not prove your verified result to a third party. This is a very difficult problem, and I don't know of any solutions.
      • Voter-verifiable voting is not the issue. Ideally, you want to be able to verify your vote but not prove your verified result to a third party. This is a very difficult problem, and I don't know of any solutions.


        The solution is to physically see your physical vote dropping into a one-way tamper-proof container.

          • Re: (Score:3, Informative)

            by Fahrenheit 450 (765492)
            I love it when people talk loudly about things they don't understand. There are a number of information-theoretic secure constructs in cryptography that are unbreakable no matter how much computational might you bring to bear on the problem. One simple example is Shamir secret sharing (and the many variants) where you essentially have a system of equations with fewer equations than unknowns, thus like one time pads, every assignment is equally likely to be the correct solution to the problem.

      • Re:Start your biding... (Score:5, Informative)

        by aprilsound (412645) on Sunday November 05 2006, @09:24PM (#16730479) Homepage
        Actualy if we all went and RTFA first, we would see that they have solved the problem. You can't prove how you voted to someone who didn't see the other half of the ballot you voted with.
        • You can't prove how you voted to someone who didn't see the other half of the ballot you voted with.

          Unless the voter is expected to write in the various options (that's stupid), or the ballot forms are randomly generated (that's expensive), it would be easy for anyone who voted to check whether your receipt matched his/her's.

          Unfortunately, from the video, I cannot tell which approach they are advocating.
          • They don't need to be very random, just have as many variants as contenders. So there is a ballot version where each candidate gets to be 'A'.

            That also takes care of biases towards the person at the top.
            • Remember, the ballots are numbered. So the printing process has to run off X variations where X is the sum of every candidate running for every office listed on that ballot.

              And the ballots cannot be numbered sequentially. Or it would just be a matter of checking what version of the ballot was in that sequence. This can be done with friends and family who are already going to vote the way you do. Just stagger their voting throughout the day.

              This system also depends upon a computer to remember which windows w

              • Re:And numbered non-sequentially. (Score:4, Insightful)

                by Catskul (323619) * <andy@somerville.gmail@com> on Sunday November 05 2006, @10:56PM (#16731159) Homepage
                This is stupid. Rather than go through all of that, why not just focus on getting the basics done and done right? Leave "verified" voting until after we've managed to identify who can vote and that their votes are actually counted.
                You are so right... how stupid for those cryptographers to be doing research that might improve voting verification when we haven't even cured cancer yet.
          • It's not at all expensive to randomly produce two separate forms and shuffle them together. That's enough to take care of the most straightforward forms of ballot fraud. The system still seems defeatable to me, but it is not stupid, and does take care of the worst of the problems implicit in receipt-based voting.

          • Re:Start your biding... (Score:4, Informative)

            by ralphbecket (225429) on Sunday November 05 2006, @10:28PM (#16730945)
            If you had read the paper (it isn't complicated) you would know that
            - you can only verify that the mark you made was the mark that was recorded, you cannot verify which option you marked
            - the auditors (normally the candidates) randomly sample the ballots before and after the election in such a way that they can verify statistically that counting proceeded fairly without violating voter anonymity. The chance of k miscounted votes going undetected is 1/2^k, so just thirty miscounted votes will have less than one in a billion chance of going unnoticed.

            What on Earth does this system have to do with touch screens?

            • Re: (Score:3, Insightful)

              by neoform (551705)
              Funny how in a government with a GDP of $11,000,000,000,000 it takes programmers working for free to make a system that is actually secure in order to maintain democracy..

              Shame is the only thing I feel right now.
      • How about a hash on the selections in combination with a passphrase.

        Sorta PGP/GPG signed and encrypted.
        • Says on my Social Security Card that the card is not to be used for ID purposes, yet I am forced to show it to register a car in Ohio.

          (No, additional ID will not suffice according to the Batavia, Ohio BMV)

          Just because something is illegal does not stop it from being abused on a large level.

          Or are you not from the USA? That might explain you missing the last 6 years here.
        • if it's made into federal law that it's illegal to force anyone to show their vote

          That's retarded. If it can be done, someone will do it.

          Trust me, you are far better off with a system where "they" can't know that you didn't vote against them. They may still break your legs anyhow, but they'll never know how you voted.

          BTW, I think breaking your legs is against the law too. Lots of things are against the law.

          Laws solve no problems. Laws only provide the means to legally punish offenders, if they are c

    • What's worse:

      Votes that may be bought, but if the buyer is successful enough to sway an election, it's completely obvious to all parties involved?

      Or, votes that may be electronically flipped, without anyone even knowing it happened?
      • No no, what is better:

        Vote, and get stuck with a bad government for four years, or

        Get paid to vote, and get stuck with a bad government for four years
    • Yeah, I haven't RTFA but it sure sounds like snakeoil. You can't have a scheme which allows each individual to verify their vote and do so in a way which doesn't allow them to prove how they voted (and thus sell their vote).

      But one could imagine more robust schemes which allow voters to verify the total tally of the vote without allowing any individual to prove how they voted. But I seem to remember that it has actually been proven that even this is impossible. Or perhaps it is just believed to be inpossi
      • Here's how it works:
        Top sheet of paper says, "Do you want A. The Simpleton B. The Communist", but on the next ballot they are reversed, e.g. "Do you want B. The Simpleton A. The Communist"
        The bottom sheet just has the options "A or B" you mark one and keep the bottom half that just shows you voted for 'B'. No one is going to pay you/beat you up for voting for an arbitrary letter.

        You can then go home and lookup your ID number and it will show you the bottom half, again confirming that you voted for 'B'. Bu
        • But then you can't verify that your vote was counted for the correct candidate, making the entire idea pointless. You can't have a secret ballot with verification, its just not possible.
        • ...and the person that reverse engineers/has access to and leaks the random number generator/sequence.
          I'm not sure whether that's an acceptable risk or not. I've been an election judge, I'm not sure I would trust the system not to have leaks...I certainly had enough access that I could have take such a sequence had it been used. Whomever has access to the ballots before the voters use them, can write down the mapping.
    • I'll sell my vote for $500, you can even verify it with this hole thingy.

      The slideshow is a little opaque, but the concept is you can't. The only way you can tell how the voter voted is by having both pieces of paper. (Look closer at the paper being shredded. While there is a mark on it, it was the piece of paper the voter kept that indicated whether that mark was for A or B.)

      Their website has a .pdf on it that explains how it works [punchscan.org] better than I can...particularly because I'm still trying to wrap my head a
    • If you're talking about a vote in the US elections, you have severely overpriced it.
    • You can have a system where a person can verify their vote, but not prove to a third party that they voted a particular way. Consider... each ballot has a sequential number on it. The voter remembers (or writes down) this number when they vote. Later they can look up their ballot and see that it was tallied correctly.

      Since the valid ballot numbers are known you could just sift through for a ballot and claim it is yours if you want to collect your voting selling payment, but then the vote buyers would know t
    • I'll post without reading the article, reading the FAQ, or viewing the sample video; you can even verify it by my stupid comment.

      RTFA.
    • I'll sell my vote for $500, you can even verify it with this hole thingy

      Maybe you should RTFA. The receipt can't be used to prove your vote to a third party.

    • The hole thingy only says if your vote was counted or not as you voted.

      So, just a yes or no answer.

      You'd ask the webserver to send you a text and you do some computation with your portion of it. Then, your computer tells you yes or no.

      • You just KNOW Unions will be doing this.

        Probably some churches too.

        Finkployd

      • This system prevents that problem (Score:4, Informative)

        by billstewart (78916) on Sunday November 05 2006, @10:19PM (#16730883) Journal
        David Chaum [wikipedia.org]'s done a lot of work on the topic of secure voting, and this is a really cool simplification of some of his earlier work. It's nice and low-tech, and still does the job. If you go read the Punchscan.org FAQ [wikipedia.org], the second item is about preventing coercion and verifiable-vote-buying.


        Of course, this doesn't prevent traditional vote-tampering methods from working, like

        • TV commercials scaring voters about the other parties, or
        • politicians making bogus promises, or
        • dead people voting (as long as people with their names show up to vote), or
        • election departments not providing enough voting machines or ballots at heavily-one-party-dominated precincts, or
        • election officials invalidating registrations of people in the wrong party, or
        • police harassing motorists in black areas on the way to the polls, etc.
        But at least it's better than Diebold.

        • Re: (Score:3, Informative)

          by buswolley (591500)
          Yeah... This is one reason why we have a SECRET BALLOT. Its hard to sell your vote if you haven't got a receipt.

            • Re: (Score:3, Interesting)

              by QuantumG (50515)
              Nah, see, what's really scary is the people who modded me up to +4 without reading the article. That's democracy.
      • I agree. If your vote was counted wrong, there isn't anything that can be done about it. If you believed your vote was counted wrong and it could be changed if in error, there would be the problem of folks claiming their vote was counted wrong to tie up the process of acting on the election results. For example, if vote verification was implemented today in California, and people had the ability to contest the election, Proposition 85 (which would require parental notification 48 hours prior to performi
    • It would be interesting to come up with a receipt system that could be used to prove that you voted for whoever you wanted to prove you voted for. For instance, a square card, rotate it 90 degrees and you voted Democratic instead of Republican, or flip it upside down and rotate 180 for third party. As long as you remember which way was up, you'd be able to figure out who you voted for.

      Of course, using such a system where the machine gives candidate A 100000 votes and candidate B -5000 votes doesn't help m
    • You are of course correct in principle, but not necessarily for this method. It seems to allow the ballots to be mixed so that picking the first choice on one is not the same as the first choice on another. The vote-buyer will never know how you voted. (Watch the flash movie at the link.) However, this presents a problem just as bad as you describe... the non-secret ballot. The vote counting people now know how you voted. Well, they would if they tracked the ID number that you keep. That's unacceptable.
      • The vote counting people now know how you voted. Well, they would if they tracked the ID number that you keep. That's unacceptable.
        I think the point of the paper is that you can just have a box full of these things and let the voter pick one at random so they don't know what your ID number is. They could log access to the web site, but you could always go to the library.
      • I dunno about Leftpondia, but us UKians have had unsecret "secret" ballots for decades. Every ballot paper has a serial code written on it, and when you turn up to vote, they write that serial code beside your name in a ledger and hand you your ballot paper. There have been reports by vote counters, going back 60 years now, of Special Branch officers (our secret political police AND the people who look into electoral fraud) removing the boxes of left wing candidates for further examination. They then have 6

    • Re: (Score:3, Interesting)

      by mrcaseyj (902945)
      I was thinking that it was an important goal that votes not be verifiable by vote buyers or extortionists like bosses and husbands, but then I realized that the current absentee system has no secrecy anyway. In my area I'm not even allowed to vote any other way but absentee. Absentee balots could ruin the election even for people who don't vote absentee.

      By the way, why are so few posts getting modded up the last couple of days? In the article about melting arctic ice only 7 out of 250 posts got modded above

    • Bah, the public is a push over. How do you think we got into our electronic voting situation as it is? We've already broadcast all the fears of electronic voting. All we need is a couple "hanging chads" style incidents involving electronic voting systems then have some "experts" (marketers) present this solution to the public shortly after. They'll all be clamoring for it and it'll be installed in time for the 2008 election.
    • Well chances are at this point that your vote is just being tossed, ignored, destroyed, miscounted, or spoofed. Might as well make a few bucks since if it doesn't mean anything anyways.
    • Like counting people barred from voting as part of the population in redistricting calculations isn't cheating? Or imposing burdensome ID requirements? Or barring people from voting on the basis of *similar* names to those of felons? Or changing the distribution of voting booths to make your supporters able to vote faster then your opponents supporters? Or how about confusing ballots? When it comes to elections, the appearance of impropriety is improper itself. Or what about approving voting machines which

      • Re: (Score:3, Insightful)

        by frdmfghtr (603968)
        Go read their faq. This system is better and simpler. It even allows potentially for ballots to be reconstructed from the receipts if the polling place was blown of the face of the earth.


        Simpler? How do you get simpler than putting a big black "X" next to your selection on a ballot and dropping it in a locked box? Lining up holes, encrypted receipts, there is NO NEED to make things this complicated.

        Remember: KISS

All trademarks and copyrights on this page are owned by their respective owners. Comments are owned by the Poster. The Rest © 1997-2009 Geeknet, Inc.