June 8, 2004 4:00 AM PDT

High hopes for unscrambling the vote

PISCATAWAY, N.J.--Computer scientists gathered here recently and bobbed their heads into an odd-looking contraption for a glimpse of emerging technology that might just help make the digital world safer for democracy.

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.

News.context

What's new:
Computer scientists are developing cryptography techniques that promise powerful new tools for verifying computerized voting results.

Bottom line:
The technology is still in its prototype stage--but a bigger obstacle may be whether notoriously conservative voting officials can be convinced to try something new.

More stories on this topic

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. E-voting 2004: Part 1 of an occasional series 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.

Quantum voting?

Today's electronic voting systems rely on the arcane science of cryptography to guarantee that votes aren't altered or intercepted.

But what if encryption stopped being secure one day?

That's not likely to happen anytime soon, but a still-to-be-invented quantum computer could do just that. When working at Bell Labs in 1994, a mathematician named Peter Shor demonstrated that a quantum computer could break popular public-key encryption algorithms.

As its name implies, such a computer would adhere to the laws of quantum mechanics. That means it could be in multiple states at once (rather than limited to the on-off binary state of today's processors), making it far more adept at handling the permutations of any encryption scheme.

Researchers are already working on bringing quantum encryption closer to reality, and start-up Magiq Technologies last year said it had begun shipping commercial data-scrambling devices that draw on the technology.

"Sometime this century, a quantum computer will be readied," said Tatsuaki Okamoto, a researcher at NTT Labs in Japan. "Then (all existing electronic voting systems) will disappear."

Okamoto has a potential solution: a quantum voting system. It would rely on untappable quantum channels, "blank quantum pieces" and complex mathematics, but Okamoto says it works in theory. If quantum computing is decades away, he should have plenty of time to make it work in practice, too.

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.

E-voting

An occasional series on the controversy surrounding electronic voting.

Part 1: Fight over e-voting leaves election plans as casualties

Part 2: High hopes for unscrambling the vote

Part 3: Evoting: Nightmare or nirvana?

Part 4: Global lessons in e-voting

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.

An encrypted ballots' two halves (graphic)

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

2 comments

Join the conversation!
Add your comment
Huh?
Am I missing something here? I thought the purpose of the
printed ballot was to 1) allow the voter to check the that his or
her vote was tabulated as intended and 2) to give a paper trail
for election officials to perform a recount. The article here
makes it sound like the results will be encrypted and then the
voter leaves the voting area with the key. If that were the case it
would make a recount impractical - you cannot depend on
voters returning with the paper based key to the election. People
will toss those papers or not come back and then you have no
recount. A valid system should keep a paper recount, in the
similar to a ballot for recount purposes. There would be little
opportunity for tampering and any tampering scheme would
require tampering in both the computer count and paper count,
a very difficult hurdle.
Posted by (1 comment )
Reply Link Flag
Occam's Razor says skip crypto, just print
The big obstacle is NOT "whether notoriously conservative voting officials can be convinced to try something new." On the contrary, too many have been craftily manipulated by voting-machine vendors into hasty purchases of dangerous paperless electronic voting machines that dont' even have HAVA standards yet!
No the big obstacle is PRINTERS! They are all refusing to record votes on tangible physical artifacts, and rushing to put as much of the election process as they can into invisible bits handled by concealed circuits running trade-secret programs; under the guise of such arguments as "economy," "speediness," "efficiency," etc., but never "verifiability," nor "accountability."
So here comes Chaum's Votegrity and Neff's VoteHere with printers and cryptography and mathematics and yet another layer of programs and computer electronics, and you know what I think? Let Occam's Razor slice off the cryptography, and let's keep just the printers. If you have two systems to give voters confidence that their votes are verified, and one is so complex that PhD's are still arguing, and the other is as simple and understandable as dropping pebbles in a jar, and both systems do the job, then choose the simpler one.
Just print a ballot, on the same stock and in the same format as any hand-marked or mail-in ballots, and quit trying to complexificate it! No flimsy hard-to-count "receipts," no different scanners for these ballots than for the absentee ballots you already have to scan and count anyway, and now you have a pile of physical, recountable, verified artifacts in case of dispute. Paper ballots, get it?
Posted by PKlammer (1 comment )
Reply Link Flag
 

Join the conversation

Add your comment

The posting of advertisements, profanity, or personal attacks is prohibited. Click here to review our Terms of Use.

What's Hot

Discussions

Shared

RSS Feeds

Add headlines from CNET News to your homepage or feedreader.