Your independent source for Harvard news since 1898

Your independent source for Harvard news since 1898

Right Now | Bollixed Ballots

Voting into Vapor

November-December 2004

Fully electronic systems will record about one-third of the votes cast this November. But "Until and unless everyone understands NP-completeness and cryptographic theory," computer-security expert Rebecca Mercuri is "adamantly opposed to the use of any fully electronic or Internet-based systems for use in anonymous balloting and vote tabulation applications." The Radcliffe Institute fellow, a computer scientist who has studied electronic voting since 1989, believes that it is "incumbent upon all concerned with elections to refrain from procuring any system that does not provide an indisputable paper ballot which can be checked by the voter visually before deposit and used by the election board in case of a recount."

In a 2002 article in IEEE [Institute of Electrical and Electronics Engineers] Spectrum and many more recent publications, Mercuri argues that electronic voting is problematic in three ways: computer security, auditability, and transparency. All of these, she says, may pose insoluble difficulties.

The computer-security issues stem from a class of conundrums known to logicians and computer scientists as "NP-complete." ("NP" stands for "nondeterministic polynomial-time.") NP-complete problems are part of complexity theory, an aspect of computer science that deals with the resources needed to solve problems, if solving them is indeed feasible at all. Computers cannot solve NP-complete problems, except, theoretically, over an infinitely long time. Take, for example, the problem of optimizing a stock portfolio. "If computers could solve this problem, we'd all be very wealthy!" says Mercuri, with a laugh. "But computers can only approximate an answer. The problem with voting is that we need a non-approximate answer."

In an electronic election, an NP-complete problem arises when one asks if the computer software has been properly constructed to register and tabulate votes. "Can we prove that?" asks Mercuri. "If we could prove that computers had no viruses, then the machines could test themselves. But the fact is that computer scientists have not figured out a way to prove that the software is perfect: doing only what we want and nothing else. We could do it if we had infinite time and every possible input and output, but the permutations quickly become astronomical. And if you change one line of code in the software, you have to run the test again."

Voting by secret ballot also conflicts with the need for auditability. "The way we audit something like banking or healthcare precludes anonymity, since we have to track each individual transaction, end-to-end," Mercuri explains. "But anonymous voting requires privacy, so we shut off this kind of tracking during the most critical part of the process: the balloting. With this [fully electronic] equipment, you cannot perform an independent recount. It's like asking Enron to give you a printout of their accounting data." (Only one state, Nevada, requires electronic polls to be accessible to audit via voter-verified paper ballots. "Ironic, but it makes sense, " Mercuri explains. "They have to audit all these casino gaming machines, so they know how to audit computers.")

Third, says Mercuri, electronic voting "is still not sufficiently transparent for citizens of a democracy to have confi dence in the system." Since computer voting involves advanced technology and complex software, "it provides an opportunity for an intellectual elite to control the system. Do you want cryptographers in control of the electoral process?"

Even so, electronic balloting is going ahead. The 2002 Help America Vote Act authorized $3.8 billion in spending though 2006; $3 billion of that is going to voting-systems vendors. Non-auditable, fully electronic voting technology will record 30 percent of 2004 presidential votes. Optically scanned paper ballots will tally another 50 percent, and mixed systems like lever machines and punch cards will record the remaining 20 percent. The balloting business is so concentrated, reports Mercuri, that two companies founded by two brothers will ultimately tabulate 80 percent of all votes cast.

"The equipment is extraordinarily expensive — small counties are paying as much as $25 million for electronic voting machines — and frankly, unnecessary," she asserts. "These machines are only used a couple of times a year, and the rest of the time have to sit in dark, air-conditioned warehouses. Their batteries run down and need replacement. Furthermore, people are now buying obsolete machines, since the money from the Help America Vote Act wasn't tied together with technical standards. I don't see that you'll be getting much bang for your buck."

The difficulties of electronic voting reappear even more clearly in on-line Internet voting, a novelty in which France, Germany, Australia, and Estonia have announced initiatives. On-line voting poses severe problems of voter identification, as well as offering vast potential for disruption by spoofing and denial-of-service attacks. "A secure Internet voting system is theoretically possible," wrote cryptographer Bruce Schneier, founder of Counterpane Internet Security, "but it would be the first secure networked application ever created in the history of computers."

Mercuri worries, too, about the expanded scale of potential abuses. "Whereas earlier technologies required that election fraud be perpetrated at one polling place or machine at a time," she wrote in her IEEE Spectrum piece, "the proliferation of similarly programmed e-voting systems invites opportunities for large-scale manipulation of elections." She closed with a comment from an unnamed observer of voting technology: "'If you think technology can solve our voting problems,' he said, 'then you don't understand the problems and you don't understand the technology.'"

~Craig Lambert

 

Rebecca Mercuri website: www.notablesoftware.com/evote.html