Field NotesEnsure Election Accuracy

Josh Benaloh

In this U.S. presidential election year, public attention is focused upon voting technologies. As we struggle with options, the pendulum swings between hand-counted paper, which is cumbersome and subject to mishandling; lever machines, which can be manipulated by knowledgeable insiders; punch cards with their now-famous hanging chad; optically scanned ballots, which can easily be misread by poorly calibrated scanners; touch-screen systems, which can be compromised by sloppy or malicious software; and various hybrids, which often create more problems than they solve.

Indeed, this is just a small sampling of the vulnerabilities in these systems. Further, the techniques in common use throughout the world depend upon honest and skilled election administrators to maintain election integrity.

But there's a better way, one in which the integrity of the election does not depend on either administrators or equipment. Elections can be run so that their accuracy can be verified end-to-end by officials, individual voters, and even interested observers.

To see this, imagine that eligible voters are provided with codes that allow them to post their votes next to their names on a publicly readable Web site. Voters can check the Web site to see that their own votes are accurately recorded, and anyone can perform an independent audit to check that all voters are legitimate and that the count matches the announced tallies.

But hold on—the one missing element from this "open-faced" election is privacy. Yes, and cryptography can be used to fill this gap—thereby enabling fully verifiable secret-ballot elections. Instead of posting raw votes, the posted votes are encrypted with public keys whose encryption keys are shared by election officials so as to require cooperation to decrypt. Once voting has been completed, election officials engage in a cooperative process to produce both an election tally and a cryptographic proof that the tally corresponds accurately to the posted set of encrypted ballots.

Individual voters can check that their encrypted ballots correspond to their intentions, and anyone can examine the cryptographic proof to check that the encrypted ballots have been correctly tallied. In this way, the election tally can be verified end-to-end.

Is it really this simple? No. This is a faithful overview, but there are numerous details that must be carefully managed to get it all right. For instance, we must still depend upon traditional methods to ensure that voting devices maintain adequate voter privacy. And just how are voters supposed to translate their intentions into encrypted ballots? Voters must feel confident that the inscrutable encrypted values posted beside their names really do correspond to their intentions without needing to show third parties the correspondence (lest they become susceptible to coercion or vote-buying). And we must do all this without requiring voters to do anything more complex than they do today in traditional voting systems.

End-to-end verifiable election processes have been studied in cryptographic literature for more than a quarter century, and there are now solid and practical ways to provide the cryptographic proof of a tally's accuracy. Recent attention within the research community has focused upon the front end that is presented to the voter, and much progress has been made there as well.

The commercial demand for election technology is large, but it's not enormous. Vast conglomerates with widespread interests may be viewed with suspicion in this market since some of their interests may benefit from certain election outcomes. Thus, this market may be best filled by smaller niche players whose entire business depends upon getting elections right. For more information and links to end-to-end verifiable election methods, go to research.microsoft.com/crypto/voting.

Josh Benaloh is Senior Cryptographer in Microsoft Research. He served eight years on the Board of Directors of the International Association for Cryptologic Research, and his extensive publications include his 1987 doctoral dissertation, "Verifiable Secret-Ballot Elections."

© 2008 Microsoft Corporation and CMP Media, LLC. All rights reserved; reproduction in part or in whole without permission is prohibited.