March 29, 2024

Analysis of Fancy E-Voting Protocols

Karlof, Sastry, and Wagner have an interesting new paper looking at fancy voting protocols designed by Neff and Chaum, and finding that they’re not yet ready for use.

The protocols try to use advanced cryptography to make electronic voting secure. The Neff scheme (I’ll ignore the Chaum scheme, for brevity) produces three outputs: a paper receipt for each voter to take home, a public list of untabulated scrambled ballots, and a final tabulation. These all have special cryptographic properties that can be verified to detect fraud. For example, a voter’s take-home receipt allows the voter to verify that his vote was recorded correctly. But to prevent coercion, the receipt does not allow the voter to prove to a third party how he voted.

The voting protocols are impressive cryptographic results, but the new paper shows that when the protocols are embedded into full voting systems, serious problems arise.

Some of these problems are pretty simple. For example, a voter who keeps his receipt can ensure that crooked election officials don’t alter his vote. But if the voter discards his receipt at the polling place, an official who notices this can change the voter’s vote. Or if the voter is coerced into handing over his receipt to his employer or union boss, then his vote can be altered.

Another simple problem is that the protocols allow some kinds of vote-counting problems to be detected but not corrected. In other words, we will be able to tell that the result is not the true vote count, but we may not be able to recover the true vote count. This means that somebody who doesn’t like the way the election is going can cause the technology to make errors, thereby invalidating the election. A malicious voting machine could even do this if it sees too many votes being cast for the wrong candidate.

There are also more subtle problems, such as subliminal channels by which malicious voting-machine software could encode information into seemingly random parts of the voter’s receipt. Since some information from the voter’s receipt is posted on the public list, this information would be available to anybody who was in cahoots with the malicious programmer. A malicious voting machine could secretly encode the precise time a vote was cast, and how it was cast, in a way that a malicious person could secretly decode later. Since most polling places allow the time of a particular voter’s vote to be recorded, this would allow individual voter’s votes to be leaked. Just the possibility of this happening would cause voters to doubt that their votes were really secret.

Interestingly, many of these problems can be mitigated by adding a voter verified paper ballot, which is generated by the voting machine and dropped into an old-fashioned ballot box. (This is in addition to the cryptographically-generated paper receipt that the voter would take home.) The paper ballots provide an additional check against fraud, an audit mechanism to guage the accuracy of the cryptographic system, and a fallback in case of failure. Perhaps the best solution is one that uses both cryptography and voter-verified paper ballots, as independent anti-fraud measures.

The take-home lesson of this paper is cryptographic protocols are promising but more work is needed to make them ready for use. It seems likely that cryptographic protocols will help to improve the accuracy of elections some day.

[Thanks to Joe Hall for pointing me to the paper.]

Comments

  1. Any portion of a voting system that is hidden will is an Achilles heel. And attacks will only get more sophisticated as time goes by.

    Even open source software is not the solution: There’s no practical way to guarantee that this or that particular machine is running only the specified software.

    Sure, we can have people run tests on each machine just before the elections. But then we’re put in a position of trusting the people doing the testing, and trusting that they have been given the proper software tools, etc.

    Our nation is built precisely on the principle of distrust, not trust. That’s
    why our nation adheres to strategies of “checks and balances,” “open meetings,” and “freedom of information.” Humans–and machines–are fallible. We need to be able to detect mistakes and to correct them.

    The solution to accurate ballots and accurate vote counts is to require paper ballots, as dete suggests, and to publish the ballots, as Fitch suggests.

    Once the voter verifies that the paper ballot is correct, he is entirely relieved of any concerns about the political connections of the voting machine manufacturer, the criminal records of the software engineers, or transient computer glitches from cosmic rays. 😉

    That leaves only the vote counting as a concern. And that is resolved by publishing the ballots, so that anyone and everyone can verify the count.

    The simplest way to publish the ballots is to use videocameras to copy the entire set of ballots in each polling place, after the polls close; and to post all sets of ballots on the Internet.

    A system for doing this economically and efficiently is described at http://e-grapevine.org/citizensaudit.htm .

    This system addresses Ganesan’s concerns about “wholesale theft of ballots” and “coercion of the vote counters.”

    It also addresses seaan’s concern about voter anonymity, if the paper ballots are shuffled before they are videotaped.

    The system does not address Ganesan’s issue of ballot-box stuffing, though videocameras might be applied in this area as well.

    (More on the necessity of paper ballots is at http://ballot-integrity.org .)

  2. I don’t know about the U.S. but, from my experience with Indian elections, I would say that electronic voting has been quite helpful, although that is not to say that the concerns on e-voting are unfounded.

    There are two reasons why e-voting has helped:
    (a) the size of the Indian population is such that counting paper ballots is a long and arduous process spread over days;
    (b) more important, paper ballots are subject to low-tech assaults, typically involving “ballot-box stuffing” with fake votes, wholesale theft of ballots, or coercion of the vote counters. Some of these problems have been mitigated by the more “high-tech” electronic voting machines which require more sophisticated attacks for the most part although not always. I think the short window between the end of voting and the declaration of results is also helpful in limiting attacks.

  3. I tried talking about the problem of designing a digital vote counting system with a good friend of mine and his response was simply: What’s wrong with paper ballots?

    At first, I thought he was being flippant, but the more I thought about it, the more I realized that there is absolutely nothing wrong with hand counted, paper-marked-with-pencil ballots. The only clear advantage of computerized systems is accuracy (HA!) and speed. I won’t touch accuracy question, ’cause there’s no point.

    As for the speed issue, how is this an issue? The more voters you have, the more potential counters you have. I’ve never heard of an election where the results are needed RIGHT AWAY. There’s always lots of time. And I’ve always assumed that the brunt of the work is done by volunteers, so cost can’t be much of an issue.

    Before I ever listen to another argument about *how* digital voting should be accomplished, I want to here a cogent argument as to *why* its even being considered in the first place. Paper ballots aren’t broken, so why are we trying to fix them?

  4. Unless I’m missing something, I think it would be pretty easy to discover how an individual voted if Crosbie Fitch’s scheme was in use.

    First, I don’t think step 1 can easily be performed – how do you distribute anonymous certifiicates to voters, while still making sure everyone has just one certificate. It gets a little easier if we distribute the certificate on a token, or requiring every voter to be part of a PKI system. But there is lots of potential for determining a voter serial number, even if they are masked (encrypted or protected by token) and random (non-sequential).

    Once you know how to identify a voter with a serial number, the counting application becomes an oracle that can reveal what the vote contained. See the vote count, apply the new vote, and than examine the system again. Now there are probably some procedural methods of reducing this risk (for example: require a minimal size batch of votes to be counted, carefully control the ability to count votes, etc.).

  5. The problem is that the votes are not open.

    If votes are closed transactions, it’s closed to scrutiny.

    What you need is a ‘show of hands’ kind of voting system.

    This means that the electorate is able to perceive itself – a crucial aspect
    for demonstrating transparency.

    So, ideally every voter publishes their vote – for all to see.

    This means that anyone can count the votes.

    1) Each time a vote is called for, a digital voting card/certificate is
    issued to all entitled registrants. This function is performed by open
    source software such that it is clear that the certificate is anonymised (no
    record is kept as to what recipient received which certificate). However,
    each one does have a serial number.

    2) A voter then uses the certificate in conjunction with their own digital
    signature to create a specific vote. The resulting vote reveals its serial
    number and the vote selection, it also demonstrates that it could only have
    been produced in conjunction with a proper voting certificate and a proper
    (but untracable) digital signature. This enables the voter to assure
    themselves that it is their vote in the open ballot box and not an
    impostor’s – and also that the vote is correct.

    3) The votes may then be dropped in anonymously via any Cafe wifi access
    point, USB dongle, or even e-mail. These will be conveyed to the publicly
    hosted p2p/distributed system representing the national ballot box – which
    may be freely read by anyone.

    It is a civil offense to claim ownership of a particular vote (anonymity
    should be compulsory).

    It is up to each citizen to ensure that their vote has arrived in the ballot
    box.

    4) The ability to read a vote’s serial number is always possible. However,
    the vote itself is only visible with a decrypt code. This is published by
    the voting system at such time as it is decided that a count is permissible
    (will not greatly sway the minds of those who have yet to vote).

    5) At some point the vote is closed – a count is fixed (in association with
    the serial numbers of votes that were available at the time of the count),
    and any subsequent votes are ignored.

  6. spellingsnob says

    guage -> gauge

    thanks