{ End Bracket }

Election Results Even Voters Can Trust

Josh Benaloh

Cryptography has numerous important and familiar applications including data privacy, identity authentication, and message integrity. But one surprising application is to the electoral process. I'm not merely speaking about encrypting voting data to preserve voters' privacy and ensuring that only authorized personnel have access to sensitive systems. Cryptography can be used to change the game completely—to allow every individual voter to check the accuracy and integrity of an election tally. What's most surprising is that this can be done entirely without trust in election equipment, software, or personnel.

But how is this possible? Don't I need to trust programmers, hardware vendors, system managers, or someone or something? Actually, no. To see this, imagine using Web postings for an open-ballot election. Voters post their names and votes to a public Web site which is frozen at the close of the election. The final contents of this site remain readable and are also published in local newspapers and other widely available media. All voters then have the opportunity to check that their own votes are properly listed, that all votes are from eligible voters, and that the tally matches the actual votes cast. The accuracy of the tally can be verified without having to trust anyone or anything. (Of course, denial-of-service attacks could prevent the successful completion of this or any election, but denial-of-service and other forms of cheating are public and easily detectable. The claim is simply that voters can tell whether or not an election is fair and accurate.)

The one thing that is missing from this simple, fully verifiable election is privacy, and this is where cryptography shines. Imagine that we modify the election process described above by asking voters to post their names and encryptions of their votes. We have now restored privacy, but we seem to have lost verifiability. With a little effort, however, we can also restore the elusive verifiability property. The goal will be to create a mathematical proof that the set of posted encrypted votes corresponds to a claimed election tally. If this can be done so that the proof can be checked by anyone, then we will have a secret-ballot election with full end-to-end verifiability—any voter or even a casual observer would be able to check the accuracy of the tally (something which can't be done with an ordinary paper trail or any other method in current use).

Simple encryption techniques do not have all the properties necessary here: we need the encryption function to be public; we need a robust, distributed decryption process so that no single entity can decrypt individual votes; and we need some special homomorphic properties that allow basic computations such as addition or multiplication to be performed directly on encrypted values without requiring intermediate decryption and re-encryption. Fortunately, the research literature contains several thoroughly studied encryption functions with exactly these properties. With such a function, we can build a system that allows individually encrypted votes to be combined or transformed to produce a tally together with a proof that the tally is correct. Voters would be able to check and see for themselves that their secret votes had been properly counted.

One question remains. How are voters to encrypt their votes? It might seem as though the publication of a public key should be enough to allow voters to encrypt their votes using their own equipment. But this would subject voters to coercion and vote buying—not to mention the possibility that their home machines may have been corrupted in order to change their votes.

A coercion-free election is best conducted by having votes cast in person at monitored poll sites. The monitoring forces voters to cast their votes in private—away from any undue influences. But this also forces voters to use equipment out their control. Several methods have been developed to allow voters to check that untrusted equipment is encrypting their votes properly—without enabling voters to prove how they voted to third parties. The difficulty is keeping things simple for voters by not forcing them to do anything more complicated than what is ordinarily required in current elections. One fairly simple approach is to unobtrusively provide voters with the option to either challenge or cast (but never both) any votes that have been encrypted on their behalf. This provides some confidence that the cast votes are also correct. The voter interface is the most active area of research on the subject, and newer and better methods for ordinary humans to verify the accuracy of an encryption are appearing with great rapidity. To learn more, visit research.microsoft.com/en-us/projects/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."