High hopes for unscrambling the vote

Beneath the viridian green glow of a viewfinder flowed an inch-wide strip of paper that inventor David Chaum says will prove with mathematical rigor whether a vote cast on a computer in a ballot box has been tampered with after the fact.

The system was demonstrated publicly for the first time at a Rutgers University voting conference late last month. The technology builds on the increasingly popular notion that computerized voting machines need to leave behind a paper trail to safeguard against fraud--something that's lacking in most current models and the subject of furious debate.

Chaum has raised the concept to an entirely new level, according to electronic-voting experts, by including breakthrough cryptographic techniques that will provide instant feedback on irregularities while ensuring voter anonymity. While still a clunky prototype, the system could represent the next evolutionary step in improving the security and reliability of the voting process, some believe.

"The math is fine," said Ron Rivest, a professor of computer science at the Massachusetts Institute of Technology and the co-creator of the popular RSA encryption algorithm. "I view this as the early days of the practical applications...The paradigm is a new and interesting one. I'm optimistic."

Chaum is not alone among researchers vying to better voting's state of the art. Fed up with what they view as antediluvian punched cards and mechanical lever systems--and with an eye to the problems of the 2000 Florida recount--scientists are borrowing from decades of academic work to invent systems that are probably secure against malfeasance. Their inventions are also designed to one-up current electronic voting machines that have limited audit capabilities and may include bugs that surreptitiously alter vote totals.

"I'd like to think that we have some" influence, said Josh Benaloh, a cryptographer at Microsoft Research. "All acting en masse, maybe we'll have an impact."

Encrypted receipts
The leading contenders so far, independently created by Chaum and mathematician Andrew Neff, represent two variants of a voting technology that uses encrypted printed receipts to solve many of the problems that have bedeviled existing hardware. These prototypes work in the lab. But one obstacle may be whether notoriously conservative voting officials can be convinced to try something new.

The idea of having computerized voting machines produce paper receipts, providing a physical record that can be audited, is belived among voting experts to be a useful safeguard against fraud. But some counties that have already installed printerless, computerized voting systems oppose any requirement that they add new equipment to provide paper receipts of any kind.

Other proposals for providing paper receipts in computerized voting systems include attaching printers to voting machines that spit out a hard copy of votes recorded below a glass barrier. Once voters reviewed the receipts and confirmed that they were accurate, the receipts would be placed in a secure box. If a recount were required, voting officials would open the boxes and proceed to tally up the results by hand.

Critics of this type of receipt argue that the end product is little better than a punch card ballot, subject to many of the same kinds of miscount problems that plagued the Florida election in 2000. Encrypted systems like Chaum's, on the other hand, would not be vulnerable to many of those flaws, because only the records that were tampered with would be subject to verification in a recount. In addition, tampering could be detected the moment a voter left the polling station.

Chaum, who declines to give his age for privacy reasons, boasts a dazzling resume as one of the brightest computer scientists of the 1980s, whose ideas led to the creation of anonymous remailers, privacy-protecting Web browsing techniques and secure electronic cash. He returned to the topic of secure voting four years ago and came up with his crucial innovation--encrypted receipts on plain paper--in late 2003. Chaum owns patents covering the use of the technology.

After the Florida recount debacle, "I decided that maybe there was a chance that these systems would be used," Chaum said. "But I needed to find a way to make them practical."

Chaum's insight was to invoke the logic of cryptography to prove that votes can't be changed after the voter leaves the polling booth. For each voter, his machine prints bar code-like dots on two strips of paper that, when combined under the carefully angled lens of a custom viewfinder, reveal the name of the candidate in plain English. The voter can keep only one encrypted strip as a receipt for use in post-election auditing--but without its mate, an individual strip will not reveal which candidate was chosen.

For cryptographers, the inherent beauty of such a system is that it safeguards privacy and security--and doesn't require voters to trust the government or untested software on a voting machine. "The next real issue is, 'When can I buy it?'" said Chaum, who created a company called Votegrity to develop and sell the hardware. "That's why we have to aggressively push forward with the company at this stage to make it an option." He is looking for investors and a CEO to bring his system to market.

This isn't the first time that Chaum has launched a start-up with a clever idea and a sheaf of patents. A decade ago, he founded the pioneering DigiCash company, but it ended up filing for Chapter 11 bankruptcy protection in 1998. Chaum said voting systems are an easier sell because digital cash wasn't attractive until many people were using it--a catch-22 that ultimately doomed the plan.

Injecting encryption into elections, central to both the Chaum and Neff systems, began receiving serious attention after a group of top scientists convened a small workshop in Tomales Bay, Calif., nine months after the Florida recount. At the May 26 and 27 conference sponsored by Rutgers University's DIMACS computer science center this year, experts in the field seemed ready to accept that the Chaum and Neff systems were secure enough to be used in a real-world election.

"It's an important step forward," Moti Young, a professor of computer science at Columbia University, said of Chaum's design. "I don't see any bugs. It's technically very sound."

Poorvi Vora, an assistant professor of computer science at George Washington University, is also enthusiastic. Vora and her graduate students wrote their own software, based on Chaum's two-strip concept, and demonstrated it at the Rutgers conference. Instead of using a custom viewfinder, they printed on transparencies that can be laid on top of each other on an overhead projector.

But not everyone in the e-voting community is so enthusiastic about the Chaum and Neff systems. Rebecca Mercuri, who wrote her Ph.D. dissertation on electronic vote tabulation, said she remains skeptical.

"I can read the math," Mercuri said. "I am holding the bar very very high...I will continue to serve as a skeptic. I have not been convinced yet. It does not exist in the form where people can use it yet."

VoteHere's take on encryption
Chaum isn't the only contender seeking to bring encryption to the voting verification process. A similar cryptographic system was invented by Neff, who holds a doctorate in theoretical mathematics from Princeton University and is now the chief scientist at VoteHere in Bellevue, Wash. Neff's invention also draws from mathematics but does not require a viewfinder that combines two receipts into a human-readable ballot.

Instead, VoteHere's patented system prints personalized, encrypted receipts for each voter. A vote for president could be represented as "DGA1," and governor as "3QLK." After the election, voters can confirm that their vote was counted by checking the county Web site to make sure the encrypted sequence corresponds to what's posted. Or, if they choose, they can hand their receipt to a trusted organization like the League of Women Voters and ask them to do the verification.

"It's conceptually easy," Neff said during an interview at the conference sponsored by Rutgers University's theoretical computer science center. "But it has to be plugged into the process that (voting machine) vendors use."

Concocting arcane mathematical formulae is almost trivial, compared with the arduous process of convincing vendors and state election officials to adopt verifiable, encrypted systems. Neither group is known as an aggressive early adopter of new technologies.

Hundreds of millions of dollars are at stake. State governments are racing to install electronic voting machines as a result of the federal Help America Vote Act, which was enacted after the 2000 election and gives states hefty federal grants if they meet certain deadlines.

One key date: Any state accepting those grants must replace all its punch card and lever machines by Nov. 2, 2004. Because of that looming deadline, many states have already bought replacements for their oldest systems and are reluctant to write a second set of checks to add encrypted receipt technology. In addition, Chaum's system won't be in production until after the November election.

Neff expressed frustration at the difficulty of convincing voting vendors such as Diebold Election Systems to license VoteHere's technology and produce encrypted receipts. "They're just not technically savvy," Neff said. "They've got incredibly limited technical abilities, and they're desperately clinging to the hope that all this (concern about e-voting) will blow over. They want to sing the praises of the little box they plop on someone's table and not worry about it. The other conjecture is that somewhere, they appreciate the fact that, moving toward the future, the verification technology follows what Microsoft did to hardware in the early days. It becomes more important than the box."

So far, Neff's VoteHere company has inked a deal with Sequoia Voting Systems to license its encrypted receipt technology, though it's nonexclusive. Unlike Chaum's system that requires a special viewfinder, any electronic voting machine equipped with a printer can produce the receipts. State election officials aren't exactly biting, but Neff says "it looks very realistic that we can do a pilot in California or Maryland for the November election."

Diebold has attracted the most criticism of any e-voting machine maker. In April, the California Secretary of State took the drastic step of banning Diebold-made systems from being used in some counties. Last November, California began investigating allegations of illegal vote tampering with Diebold machines. An earlier blow came in June 2003, when university researchers concluded that a voter could cast unlimited ballots without detection.

Neff of VoteHere acknowledged that encrypted ballots aren't a complete solution for all voting problems. For instance, election officials must be trusted to prevent people from voting twice under different names or at multiple voting locations. "We've addressed 80 percent of the threats and 100 percent of the really bad threats," Neff said. "We can't (seem to) get beyond that remaining 20 percent."

But skeptic Mercuri argued that even that number is optimistic. "I don't agree you've addressed 80 percent of the threats," she said. "It depends on your threat model."