Science | DOI: 10.1145/1400181.1400188

Cyrus Farivar

clean elections

With end-to-end auditable voting, a voter can verify whether his or her vote was tallied correctly and whether all of the votes were properly tabulated.

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 voting—which uses paper ballots or electronic voting—is 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

sample invisible ink ballot.

 

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 sci-

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

PHO TOGRAPH BY JOE HALL