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.]