Communications of the ACM
News
Clean Elections
Photograph by Joe Hall
Despite the renewed calls for improved voting systems after the debacle in Florida during the 2000 presidential election, little has changed in the way that America votes eight years later. Today, the country still has a veritable mishmash of voting standards and methods. Some counties use lever machines, some use paper ballots, some use electronic voting machines, and still others, after having tried electronic voting, have reverted to the paper ballots that they previously used.
While the debate about the merits of electronic voting versus paper ballots continues in public policy and technology circles, one approach might put the entire controversy to rest: end-to-end (E2E) auditable voting. Also known as E2E verifiable voting, E2E auditable voting ensures the transition from the accurately recorded single ballot to the tally of collected ballots is preserved and maintained in a publicly auditable manner, and enables voters to verify that their individual votes were recorded accurately as well as the ability to show, with a high degree of probability, that all of the ballots were properly tabulated.
(For a debate about electronic voting, see the Point/Counterpoint column on p. 29.)
E2E auditable voting is different from voter-verified paper trail ballots, which addresses the problem of whether each single ballot was recorded correctly, but do not ensure that all of the votes were tallied accurately. The idea behind E2E auditable votingwhich uses paper ballots or electronic votingis that the entire voting system utilizes cryptography to accurately count votes while at the same time preserving the voters' privacy.
"The basic concept, which is almost miraculous, is that a voter can cast a ballot, check that the ballot was counted, and verify that the totals are accurate, without anyone else knowing how they voted, even if the voter wants to prove how they voted to a third party," says David Dill, a professor of computer science at Stanford University.
Computer scientists, mathematicians, and cryptographers in the United States and abroad have spent years working on E2E auditable voting systems. One early contender was VoteHere, an E2E electronic system developed by Andy Neff, but VoteHere changed its name to Dategrity Corp. in 2005, with the goal of reaching a wider market for its auditing and verification software.
Private Data, Public Verification
After years of research, one approach has captured the most attention in the world of E2E auditable voting and is the farthest along in terms of actually being implemented anytime soon in the United States.
Scantegrity II (the "II" stands for "invisible ink") was developed largely by independent cryptographer David Chaum in collaboration with other scientists in the field, including Ron Rivest, a professor of computer science at MIT; Peter Ryan, a professor of computer science at the University of Newcastle upon Tyne; and Stefan Popoveniuc, a graduate student in the computer science department at George Washington University.
Scantegrity II relies upon a technique of cryptography known as a "cut and choose protocol," which enables zero-knowledge proofs. This technique of cryptography relies on zero-knowledge proofs to show that the information has been encrypted without revealing what the original piece of information is. In this case, it proves that the results were accurately tabulated without revealing how each vote was cast.
A Scantegrity II ballot is similar to a traditional ballot with a list of candidates and an adjacent row of fill-in bubbles. In order to vote, each person uses a special pen to reveal a unique, hidden three-character code that is printed in invisible ink in each bubble. The three-character code serves as a cryptographic marker to indicate the voter's preference. However, without the decryption key, the code is meaningless.
The code effectively encrypts, or locks in, the voter's preference. Then, each possible code for each ballot is randomized and displayed publicly on a Web site.
Once the codes are randomized, a set of tables are used to map each code to a particular candidate. However, the precise path of the trails is concealed under a two-step procedure that connects the location of the coded vote to how that translates to its location on the results board.
After voting, each voter receives a small tear-off receipt containing the serial number of the ballot. The voter can, if he or she chooses to, write down the revealed three-character code, which, when entered in a public Web site, can verify their vote was recorded correctly.
In order to audit a ballot, an auditor or a voter would use the original ballot key to disclose all possible codes for all candidates, thus revealing the entire computational chain to prove whether the votes were recorded and tabulated accurately. And to verify that a person hasn't cheated during any step of the process, one of the pointers can be revealed to assure that the proper connection between the results and the anonymized encoded ballots is maintained.
Scantegrity II is not a replacement voting system, but works with either precinct-based or central scan systems, a feature that Chaum says makes it attractive to public officials. The printing of ballots, however, requires the capability to print with invisible ink and to print each ballot differently.
Scantegrity II might be used in an upcoming municipal election in Takoma Park, MD, a suburb of Washington, D.C., but the city council has not yet made a final determination.
Different Approaches, Same Goal
While Scantegrity II appears to be the most public election-ready system, there are several replacement systemsmost notably Prêt a Voter (or Ready to Vote), Scratch & Vote, and ThreeBallotthat use different cryptography-based approaches to achieve the same goal of end-to-end voter verifiability.
Developed by Peter Ryan of University of Newcastle upon Tyne, Prêt à Voter does not rely upon the voted values to be encrypted and randomized, but uses a random candidate order that varies from ballot to ballot. Once a vote is cast, the side of the ballot with the list of candidates is destroyed.
End-to-end auditable voting systems could put the controversy about the merits of electronic voting versus paper ballots to rest.
The bottom of the non-discarded side of the Prêt à Voter ballot contains a cryptographic string with information on the discarded candidate list order. In order to decrypt the candidate list order and determine the value of a vote, voting officials or party representatives use a series of secret keys to decrypt the ballots.
Prêt à Voter was successfully used in student elections at the University of Surrey last year, and Ryan plans to test Prêt à Voter again in upcoming student elections at the University of Newcastle upon Tyne.
Scratch & Vote was developed by Ben Adida, a research fellow with the Center for Research on Computation and Society at Harvard University, and Ron Rivest, a professor of computer science at MIT, and its format is similar to Prêt à Voter.
A Scratch & Vote ballot is perforated down the middle, and the left side has a list of candidates' names and the right side has a series of corresponding check boxes. Beneath the check boxes is a 2D-barcode. A scratch surface is positioned below the barcode, and a perforation separates the scratch surface from the rest of the right half of the ballot.
If the voter wants to audit the voting process, she selects a second ballot and removes the scratch surface, thereby voiding the ballot, which the voter gives to a trusted party on the premises. The trusted party scans the barcode, reads the randomization data previously hidden under the scratch surface, and can confirm the ballot is correctly formed.
The voter now makes her selection on the first ballot, discards the left side of the ballot (which contains only the randomized candidate order), and gives the ballot to an election official. The election official ensures the scratch surface is intact and detaches the scratch surface for the purpose of discarding it. The voter enters the ballot's remaining checkmark (to indicate her vote) and barcode, which is effectively the encrypted ballot, into a scanner.
The voter can take the remainder of the ballot home and check on a public Web site that her ballot was correctly tabulated, and if it wasn't, she still possesses the remainder of the ballot. In addition, the voter can audit the tally process and the verifiable decryption conducted by the election officials.
With Scratch & Vote, each vote is recorded as an encrypted value by using the box that was checked to determine which encrypted value to use. The values are tallied using homomorphic encryption, which allows for the sum of two encrypted values to be equal to the encrypted sum of that value. In other words, by adding the encrypted ballots together and decrypting them all at once, the candidates for whom the votes were cast can be determined.
"I'm not actively pursuing [Scratch & Vote] for implementation, though I use it regularly to teach the concepts," Adida said via email. "I think it might be a useful system for certain simple elections, but it might simply be more useful as a teaching tool. It's helped a number of folks understand the power of open-audit voting, even if they quickly forget the details."
Invented by Rivest, the ThreeBallot Voting System entails giving a voter three identical ballots. To vote for a candidate, a voter must select that candidate on two of the three ballots. To vote against a candidate, the voter must select that candidate on one ballot. At the polling station, the voter makes a copy of any one of the three ballots, which he or she retains, and the three original ballots are placed in the ballot box.
At the election's conclusion, all of the ballots are published. As each ballot contains a unique seven-digit identifier, a voter can independently verify that his or her vote was counted by searching for the identifier among the published ballots.
Scratch & Vote has helped people "understand the power of open-audit voting, even if they quickly forget the details," says Ben Adida.
ThreeBallot offers some of the advantages of a cryptographic voting system without actually using cryptography. MIT students have conducted a field test with ThreeBallot, however, and discovered problems in terms of usability, privacy, and security.
While many academic experts say that the science behind E2E auditable systems is promising, they also note the need for further research and usability studies.
"We are at the stage where we need to try many different techniques for open-audit voting, and we just don't know what's going to work better in a real-world setting," Adida said via email. "Deciding on a single system now would be putting the cart before the horse."
David Wagner, a professor of computer science at the University of California at Berkeley, suggests that a widespread, multiyear study could be the best way to advance E2E verifiable voting research. "The next step is that you need a system that is very concretely worked out," Wagner says. "One of the things about cryptography is that the devil's in the details. When you're using this fancy mathematics, there's all these details to get right and any one little slip-up can compromise the security of the whole system."
©2008 ACM 0001-0782/08/1000 $5.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2008 ACM, Inc.
No entries found