Making Every E-Vote Count

A noted cryptographer has a system that works

With high-profile contests in Missouri, Montana, Virginia, and Wyoming decided on 7 November by margins as small as a few 10ths of 1 percent, the 2006 U.S. elections showed why many voters have feared their votes would not be accurately counted by electronic voting machines. Problems that day ranged far and wide—from touch screens that reportedly registered Democratic votes as Republican ones in Florida, Missouri, Pennsylvania, and South Carolina, to electronic ballots in several New Jersey counties that were allegedly premarked for the Democratic Senate candidate.

In Virginia’s Senate race—the contest that, in the end, determined that the Democrats would control Congress for the next two years—poorly written software truncated the name of the winning candidate, James Webb, so that his surname did not appear on computer screens in three cities.

And in a variety of jurisdictions spanning more than a dozen states, e-voting machines simply failed to boot up or crashed soon after the polls opened [see photo, ”But Did It Count?”].

Help may be on the way. A group of graduate computer engineering students from universities in the United States and Canada, working under the direction of David Chaum, introduced a complete voting system in November that it says avoids all the flaws and limitations of the commercial ones. Chaum is a leading cryptography researcher who works independently in Southern California.

The system, called Punchscan, seems at first blush to be complex, even Rube Goldbergesque. Yet its operation can be explained to voters in just a few minutes, and the ballots resemble nothing so much as the cards used in bingo, the charity game played in church basements every week across the United States.

The system Chaum’s group has devised addresses the key concerns raised by academic critics of commercial electronic voting systems. Experts accused commercial companies of selling systems that generated ballots that could not be recounted in disputed elections, that were vulnerable to hackers and viruses, and that might even contain secret computer code that could be used to hijack an entire election.

More than 20 years ago, Chaum made waves with the first practical system for electronic cash, a decade before there was a commercial Internet on which to buy or sell things. His ideas and patents, if not his products, have made their way into all walks of eâ''commerce, including electronic banking and Internet gambling. His eâ''cash inventions preserved the anonymity that is a key feature of physical cash transactions, an important feature. He hopes now to provide a similar privacy—and security—to electronic voting.

A Punchscan ballot is a long sheet of paper with a perforation in the middle. Printed on each half is a unique number identifying the ballot. When the ballot is folded over, the top part has the candidates’ names for each position being contested; each candidate is assigned a letter of the alphabet. Separately, for each position, there is a set of holes with the letters corresponding to the candidates showing through them [see photo, ” Bingo!”].

When the voter chooses a candidate with a special orange highlighter-style daubing pen, the mark appears around the hole on the top sheet as well as on the letter on the bottom sheet. After making their choices, voters tear the ballot at the perforation and file one half—or the other—by passing it through a small portable scanner, similar to those sold in computer stores for about US $100. The other half is destroyed in a paper shredder.

Punchscan can figure out the voter’s choices, but no database connects ballot and voter

Here’s the really clever part: the assignment of letters to candidates is random and is not necessarily the same on any two ballots. So, even though either half of the ballot can represent the voter’s choices, you cannot discern the voter’s selections by looking at just one of them. This is because the marked letters on the one sheet appear without the names of the candidates, and on the other sheet, the colored hole doesn’t have a letter corresponding to the candidate’s name.

The Punchscan system can figure out the voter’s choices, because that random assignment is recorded in a database keyed to the ballot number. But the voter’s personal choices are private, because no database is kept that associates the ballot number with the voter’s name. Absentee voters can mail in either half of the ballot. And if scanners, or the personal computers they are attached to, fail to work for some reason, election officials can simply put the half sheet in an oldâ''fashioned ballot box to be counted later.

A significant virtue of the Punchscan system, Chaum says, is that it can be implemented with off-the-shelf equipment. The sophisticated scanning software devised by his student associates lets ballots be read under poor lighting conditions and at odd angles, so that inexpensive readers would suffice. But should election officials opt for robust, large-paper scanners costing $2000, Chaum claims the expense of outfitting a precinct would still be less than buying optical-scan voting machines at $6500 apiece, a typical price.

In the Punchscan system, security comes cheaper, too. For example, machines don’t have to be physically sequestered and guarded, because at no point in the voting process do the computers have more than half the information needed to know how a voter voted.

”From a security perspective, it’s very clever,” says Dan Wallach, a computer scientist and e-voting expert at Rice University, in Houston. But Wallach worries that the Punchscan system could put excessive demands on voters. ”Because of the random way the system correlates candidates with letters and their position on the ballot,” he says, ”voters would have to do several things where they now do only one: after finding the candidate’s name, they mark a circle next to it. With Punchscan, they have to figure out the symbol for that candidate and find its location, as well as put an ink blotch over it. Voting systems have to be usable by the broad population—and more steps mean more chances for errors.”

Chaum introduced Punchscan a week before the 2006 general election with informal demonstrations in Washington, D.C. The graduate students who created key parts of the system conducted the demos, along with two of their professors, Poorvi Vora, in the department of computer science at George Washington University, in Washington, D.C., and Alan Sherman, in the department of computer science and electrical engineering at the University of Maryland, in Baltimore. There were also two students from the University of Ottawa, Canada.

A real-world test for Punchscan could come this spring in a student election, which will probably be held at one of the researchers’ home schools. ”This first version was designed for university campus elections,” Chaum says, ”though obviously we had federal and local general elections in mind.”

At around the same time, students will enter Punchscan in a new National Science Foundation–funded challenge called the University Voting Systems Competition. A $10 000 purse is at stake, and the final face-off between the five best systems is set for July.

In a possible sign of a rapprochement, the prize money was put up by Election Systems & Software, in Omaha, one of the largest of the commercial vendors. Chaum called it ”an olive branch from the manufacturing community to the academics who have been criticizing their systems.”