The Perils of Polling
Electronic voting may avert a repeat of the 2000 Florida debacle, but it also creates new problems

By Steven Cherry

This November, people all over the United States will cast ballots using methods that span centuries of technological development. In fact, in this technologically advanced country, more than half of the voters will mark their choices by hand on paper ballots, just as their great-great-great-grandparents may have done.

But for the first time in history, more than 25 percent of U.S. ballots will be cast using equipment that directly records votes only on electronic media, such as chips, cartridges, or disks, with no paper or other tangible form of backup. That's nearly triple the number of electronic votes in 2000. Twenty-five years in the making, electronic voting is finally being widely adopted in the United States.

Unfortunately, recent evidence suggests that although we may be ready for electronic voting, the technology is not ready for us. True, these electronic systems eliminate many of the problems with paper-based ballots?Florida's hanging chads and poorly aligned print layouts being the most notorious. But in their hurry to eliminate paper and avoid another Florida-style fiasco, some equipment makers and election officials are rushing to deploy systems that have known flaws or that have been poorly tested?or not tested at all. Much the same story is playing out not only in the United States but also in Australia, Brazil, India, the United Kingdom, Venezuela, and elsewhere.

Officials are knowingly giving up the ability to perform an independent recount?a fundamental requirement for ensuring the integrity of the votes recorded by a voting machine, and for reconstructing the tally if an election is contested. People using these direct-recording systems will have no assurance that their ballots were cast at all, let alone as intended. And it's likely that some machines will fail, if the record of recent local and other elections is any guide.

Astonishing as it may seem, a world with automated teller machines that dispense cash flawlessly and ticket-selling kiosks that accept and count bills and coins of every denomination still hasn't produced electronic voting machines that are robustly reliable and with counts independently verifiable. Computer scientists, such as David Chaum, the inventor of digital cash, are working on the problem, but solutions are years away.

Fair and honest elections are a cornerstone of any modern democracy, and yet the democracies that dominate technology development?the United States chief among them?have been surprisingly unsuccessful to date in their attempts to design and deploy electronic voting machines that are free of fundamental defects. This situation is all the more amazing when you consider that over the past couple of years the U.S. government has spent some US $1 billion and allocated almost $3 billion more to subsidize the purchase of new electronic voting machines. Despite this enticement, some 20 percent of U.S. election districts have chosen to continue using their existing systems, including some 1950s-era lever machines that were used to vote Dwight D. Eisenhower into the White House.

Now, as the United States prepares for the first presidential election in which electronic voting will play a substantial role, a growing group of technologists is asking whether the problems of electronic voting are endemic. States getting ready to deploy machines are finding that they have been sadly ill informed about them?and that in some cases they will be fielding systems that comply only with obsolete federal guidelines from 1990.

 

WHY HAS SUCH A SEEMINGLY STRAIGHTFORWARD design challenge proved so baffling? The causes are several?putting together an honest election isn't as simple as it appears. In the United States, one major complication is that elections are run individually by each of the 50 states. Another is the misplaced trust of the state and local bureaucrats responsible for choosing and deploying election equipment; they have been insufficiently skeptical of the claims made by equipment manufacturers?and have in some instances rejected the advice of outside engineers and specialists. Then there's the way the profit-driven vendors themselves rushed some of their machines to market. Finally, there is the system-design challenge itself, which is much more difficult for voting machines than most people realize.

Let's start with the practice, which originated in the U.S. Constitution, of entrusting states and smaller jurisdictions with the responsibility for buying election machines and running elections, including national ones. Many countries, such as India and Brazil, have central election authorities that choose machines for the whole nation.

The United States doesn't have just 50 different decision makers; it has hundreds. Some states choose voting equipment statewide, while others leave such decisions up to counties or municipalities. For years, many voters have been using systems that are partially electronic. Voters fill out a paper ballot that will be optically scanned, much as a standardized test is. Machines count the ballots and a winner is announced. If an election is contested, the ballots can be rescanned or counted by hand.

Electronic voting machines go one small but critical step further by storing the vote digitally instead of on paper. The AccuVote-TSX, a touch-screen system made by Diebold Inc., North Canton, Ohio, is typical. When a voter signs in at the local polling station, a card similar to a modern hotel-room key is activated. The voter s it into the machine and makes his ions. When the voter touches a "Cast Vote" area on the screen, the vote is recorded on the machine's hard disk and the access card is deactivated, preventing the voter from voting a second time. Each AccuVote machine has a built-in printer, not to reproduce individual ballots but to record the machine's vote totals when the polls close. The AccuVote also has a modem; election officials can choose to have it encrypt the vote totals and transmit them over ordinary phone lines.

Though there are at least a dozen manufacturers of electronic voting machines, the three largest?Diebold; Election Systems & Software Inc., Omaha, Neb.; and Sequoia Voting Systems Inc., Oakland, Calif.?share 80 percent of the market.

ES&S, which claims to be the largest maker of electronic voting machines in the world, was formed in 1997 by a merger of two smaller companies, one of which was founded by two brothers, Todd and Bob Urosevitch. Todd is still with ES&S, but Bob was until recently president of Diebold.

Electronic voting machines have some important advantages over traditional optical-scan systems and their preprinted ballots. For example, machines can be programmed to keep the voter from voting for two candidates for a single office. And text on the screen can be read by voice-synthesis software?useful for illiterate voters as well as the visually impaired. These and other special features are continually refined by the different vendors.

The diversity of manufacturers and machines is a problem, though, because voting officials are having a hard time keeping up with a shifting cast of companies and with often-flawed, early-generation equipment. Time-consuming testing and certification requirements can't keep up now that elections are suddenly under the force field of Moore's Law. And then there's the problem of springing new machines on the many one- or two-day-a-year volunteer workers needed to run a modern election. The inevitable result is compromised elections.

 

THE NUMBER OF PROBLEMS IN RECENT YEARS defies listing in a magazine article, but what better place to start than Florida, whose tribulations made the 2000 presidential election infamous? Just two years later, in a 2002 gubernatorial primary, a state of emergency had to be declared because, in two counties, some of the new equipment failed to boot up in time for the start of the election. Or we could start with a November 2003 election in Boone County, Indiana, where 144 000 votes were reported for only 5352 voters.

Or perhaps we should begin with California, which has endured a plenitude of problems commensurate with the state's size and population. Indeed, election officials in California soured on their new e-voting machines only after a lengthy series of missteps culminated in spring 2004 primary elections that were marred by voting catastrophes throughout the state, across a wide variety of different machines.

In San Diego County, precincts opened as much as 4 hours late; in some areas nearly half failed to open on time. Here and there, voting machines, made by Diebold, rebooted themselves and voters saw generic Microsoft Windows screens instead of ballots. Those problems were traced back to the voter access card encoders. Faults in the power switches drained them of battery power. In northern Alameda County, one in five Diebold encoders had similar problems.

Hearings were held after the primary elections, and on 20 April, California Secretary of State Kevin Shelley released a report charging that Diebold marketed, sold, and installed its AccuVote systems in Kern, San Diego, San Joaquin, and Solano counties prior to full testing, prior to federal qualification, and without complying with the state certification requirements. These and other discoveries were subsequently turned over to the California attorney general's office for possible criminal investigation against Diebold.

Ten days later, Shelley issued a controversial decertification notice, withdrawing approval for all direct-recording electronic voting systems in California, deeming them defective or unacceptable. Because of this, the state required nearly 16 000 AccuVote machines in the four counties involved to be recertified to comply with tighter security and auditability measures or replaced with optically scanned balloting in time for next month's election.

 

PROBLEMS RELATED TO THE INSTALLATION OF UNCERTIFIED COMPONENTS and the coverup of malfunctioning products have occurred with manufacturers other than Diebold. Earlier this year, a June 2003 ES&S memo came to light that indicated flaws in the auditing software for a $24.5 million installation of its iVotronic voting machines in Miami-Dade County, Florida. ES&S also manufactured voting systems previously used in Venezuela (sold through Indra Sistemas SA, Madrid, Spain) that suffered a 6 percent malfunction rate in actual use.

Indeed, electronic voting has had its share of problems outside of the United States as well. India deployed more than a million electronic voting machines in its national election this past spring, eliminating the need for 8000 tons of paper ballots. The BBC and CNN claimed the equipment, produced by two government-owned companies, Bharat Electronics Ltd. and the Electronics Corporation of India Ltd., led to a reduction in the violence common to elections there, yet local papers were "full of reports of thugs taking away voting machines and tampering with booths," according to The Associated Press. [See also "Electronic Voting Eases India Elections," IEEE Spectrum Online, 10 May 2004.] Revoting was required at 1879 stations, and it is unclear whether tampering contributed to the surprising Congress Party victory.

In Ireland, plans to use electronic voting in local and European parliamentary elections in June 2004 were scuttled, partly over concerns about the lack of independent auditability. Also, constant s by its vendors?Nedap NV, Groenlo, the Netherlands, and Powervote Ltd, Wisteria, England?meant that the software could not be reviewed in a timely fashion. Nedap recently made some of its online e-voting software, used in Netherlands elections, available as open source, but critics have noted that the released code set cannot be compiled and run, nor is it possible to verify that the code that runs during the election is identical to what was released for review.

Physically securing a system's hardware and software was also a problem in Fairfax County, Virginia, where 1 percent of the county's new WINvote touch-screen machines, made by Advanced Voting Solutions Inc., of Frisco, Texas, had serious malfunctions. Some of the machines were repaired outside the polling place and then returned to the precincts and put back in use, despite the fact that security seals had been broken or removed?in apparent violation of state law.

Worse, at day's end, about half of the vote totals couldn't be electronically transmitted to the county headquarters because the system flooded itself with messages, in effect creating its own denial-of-service attack on the server. One election for the school board was particularly flawed. A still unexplained anomaly in a number of machines apparently subtracted votes at random from Republican school board candidate Rita S. Thompson, resulting in a possible miscount of 1 percent or 2 percent of her votes?close to the margin by which she lost the election.

There were known problems with the WINvote machines. The Web site for the electoral board of nearby Arlington County even included instructions for poll workers on what to do if: the "voting machine freezes during boot-up," the "master unit does not 'pick up' one of the units in the polling place when opening the polls," or "when closing the polls, the tally fails to pick up a machine."

Knowledgeable advice had been offered and spurned. Information-security expert Jeremy Epstein gave Fairfax officials a three-page list of questions after he attended a pre-election training session. A letter from Margaret K. Luca, who was then electoral board secretary, said that she couldn't respond on the grounds that "release of that information could jeopardize the security of that voting equipment." Critics say that Epstein's experience is typical of the way in which the election community has shut out scientists and engineers and made it impossible to independently test electronic voting systems.

 

THE SPORADIC EXCLUSION of technologists and academics is especially unfortunate because the design of electronic voting machines is far more difficult than most people?election officials included?realize. At the core is the ion and counting process, which at face value appears simple: here are the candidates, pick one. In fact, the machines must also be able to handle votes for candidates not on the ballot (so-called write-ins) or more than one candidate (when voters choose, say, two out of a list of five people running for council), and "none of the above." The bigger problem, though, is anonymity.

Voting systems must never link an individual to his or her vote, or else it would be possible for the voter to sell a vote or a politico to coerce one. In short, voting machines need to produce transactions that are auditable. Officials need to be able to recount ballots, trace problems, and eliminate errors. All the while, they must never be able to identify who created which ballot. This problem has engaged some of the brightest minds in computer science and mathematics for a few years now, with no agreement yet about how it can best be solved.

Another big challenge, mentioned above, is independent verifiability. California, for example, audits all its elections by requiring that 1 percent of all paper ballots be manually recounted, whether or not an election is contested. But without the paper, such recounts are not possible. As unpleasant as the Florida 2000 election was, at least there was paper to recount. With paperless electronic voting, on the other hand, a catastrophic malfunction, such as a memory-wiping freeze, can irretrievably lose all the votes collected by the machines.

To date, efforts to add verifiability have focused on adding paper back into the process. In fact, a paper ballot serves two key roles. It gives election officials something to recount in a contested election. In addition, when voters mark?or at least get to look at?a paper ballot when voting, they can be sure the ballot correctly represents their intended votes. Getting electronic voting machines to generate this so-called voter-verified paper audit trail is a key goal of many critics of the current technology. [See, for example, "A Better Ballot Box?" by Rebecca Mercuri, Spectrum, October 2002.]

The electronic tally stored in the machine can be taken to be the official vote; in this case the separately printed ballots are scanned only when an election is contested. Alternatively, the paper ballots can be scanned immediately, and that result is the official one. In either event, if something goes wrong with the election, the paper ballots can then be counted, and recounted?by hand if necessary.

Next month, Nevada will use electronic voting machines made by Sequoia that produce paper ballots. It will be the first U.S. state to do so, though only in some counties. Unfortunately, the Sequoia machines use a continuous paper roll, so voter confidentiality could conceivably be compromised by matching ballots to the order in which people voted. Simply cutting the roll after each vote and letting the slips of paper fall into a box at random would be an improvement.

The importance of backing up the electronics with a paper trail was underscored in the 20 April report by California Secretary of State Shelley, in which he mandated the addition of an accessible, voter-verified, paper audit trail for all newly purchased direct-recording electronic systems and a retrofit for existing ones by July 2006.

 

THESE FUNDAMENTAL ISSUES?how to verify electronic votes, how to test e-voting hardware and software, and how to maintain the security and integrity of e-voting systems?logically fall under the province of legislative authorities and standards bodies. Yet the United States has tied its own hands in this regard.

One logical legislative opportunity was in the language of the Help America Vote Act (HAVA) of 2002, which fueled the rush to electronic voting throughout the United States, with more than $3 billion to be used by state and local governments to replace their old punch-card and lever systems. An additional $30 million of HAVA money was supposed to have been allocated to the National Institute of Standards and Technology, Gaithersburg, Md., to support the development of more stringent election system examination criteria than those developed by the Federal Election Commission in 1990 and 2002.

Unfortunately, the NIST funding was not distributed, and technical commission appointments were stalled. Even if a more timely standard had been produced, the cart was put before the horse: receipt of HAVA monies for equipment purchases was not linked to compliance with any new HAVA requirements. As a consequence, no machine currently in use has HAVA certification, since no such certification actually exists, nor, once it does exist, is it likely to be enforceable by 2006, the deadline set by HAVA for all the new systems to be in place.

Although HAVA requires that newly purchased voting units "produce a permanent paper record with a manual audit capacity for such system," election officials and vendors have let this clause be satisfied by just a paper strip on which vote totals are printed at the end of the election. That strip would be useless if a real recount were required. U.S. Representative Robert Wexler, of election-impaired Palm Beach, Fla., refers to this printed summation as a "reprint" rather than a "recount."

In the absence of a voter-verified paper audit trail, the security of a voting system rests squarely on there being some kind of certification process. Yet certifying equipment even to the 2002 standard is proving to be problematic, since it is voluntarily adopted by the states, and not all have signed on yet. Only three companies are authorized to perform the commission's examinations, which are paid for by the vendors?an arrangement that many critics say compromises the testing.

Even after a system is certified, election officials must strive to ensure that the system that voters use on Election Day is the same as the system that was tested. Yet federal guidelines don't require any kind of electronic or digital signature to track software from certification to installation (although HAVA commissioners have lately said this would be a good idea).

This security hole and many others were identified by experts several years ago, in comments on the earlier 2002 Federal Election Commission certification guidelines. To address these problems, the IEEE Standards Association had formed a working group on voting standards. The importance of this work was recognized in the HAVA bill, where the IEEE was named as a representative body to the federal Technical Guidelines Development Committee of the U.S. Election Assistance Commission.

The IEEE working group has had its share of controversy, largely over the question of voter-verified paper audit trails. During the fall of 2003, Herb Deutsch, a longtime ES&S employee, was appointed to chair the IEEE Voting Equipment Standards primary working group (P1583), and an attempt was made to push a draft of the standard through the acceptance process.

This first P1583 draft omitted any mention of requirements pertaining to voter-verified paper audit trails. The draft also included what some say is a major security loophole: a blanket exemption for all commercial off-the-shelf components, including operating systems such as Windows or Unix and standard hardware modules such as modems and wireless transceivers. The 2002 Federal Election Commission's guidelines have the same exemption. "The 2002 FEC standard was our starting point," Deutsch notes. "So our first draft was built on that, and we thought major improvements were made."

Protests by IEEE members, academicians, and other concerned individuals led to the submission of more than 1000 specific comments, which have taken nearly a year to resolve. The IEEE new draft does cover the issue of voter-verified paper audit trails, though it does not require them.

Should every electronic voting machine include a paper audit trail? "That's a question of policy," says Deutsch. "This is a requirements standard, it's not a design standard. Policy will be set by governmental agencies. California has made a paper audit trail mandatory, some other jurisdictions haven't, so the standard has to cover both."

Proponents of paper audit trails still fear, however, that if a direct-recording electronic voting machine has no paper output, there will be nothing to audit an election with. Deutsch believes that the standard will have provisions for adequately dealing with security and auditability for direct-recording systems that don't have a paper audit trail. Even among those who don't agree, there seems to be a growing acceptance of the idea of letting the standard treat paper audit trails as an option, for now. Since the original draft didn't mention paper audit trails at all, proponents can certainly feel some progress has been made. Deutsch, for his part, says that a standard, once it exists, can always be improved, but if the P1583 committee doesn't approve this version in the next few months, the Election Assistance Commission may look elsewhere for a standard.

 

MEANWHILE, COMPUTER SCIENTISTS continue to argue about whether sufficient auditability can be provided without paper. Certainly, many electronic funds transactions are conducted without paper, using encryption techniques to track the communications. To date, though, no one has come up with the rigorous mathematical proofs necessary to fully justify assertions of their implementation's correctness.

The cryptographer David Chaum, an inventor of electronic cash, among other things, has demonstrated a unique approach to voting and auditing elections, using multiple layers of encryption. Basically, Chaum's system lets election officials post electronic ballots to the Internet. Voters can then check that their votes were included in the election tally.
[See diagram, "A Glimmer of Hope."]

Although paper is still needed, Chaum's proposal is important because it is the first system whose electronic tallies are as reliable as a count of the paper ballots, while still preserving voter anonymity. But it is not likely to be adopted soon, because of its theoretical complexity. It also creates a potential new problem: one of its stages involves using trusted intermediaries to scramble the votes in a way that preserves anonymity. If these third parties were to collude with one another, anonymity could be compromised.

Even after the mathematical problems are solved, fully securing the vote will still require the active involvement of a well-educated and even skeptical citizenry. Voting is a complicated social phenomenon whose difficulties cannot be resolved simply by throwing technology at it. Voting machines have to be physically secure before, during, and after Election Day. Election workers need to be well trained and able to deal with the problems inherent in any technology. (As the saying goes, To really screw things up, you need a computer.)

It's unusual and more than a bit surprising that in the short term, technologists want to slow down the move to electronic systems while many election officials are ready to speed ahead. If the officials started down the electronic voting path by underestimating the problems of deploying the technology, computer scientists may have underestimated the long-standing difficulties of conducting traditional all-paper elections. Election officials now seem to be coming to understand the merits and demerits of electronic voting systems. Overall, the current debate over electronic voting has certainly raised the bar for election equipment. And every year, we get a chance to do better.

The writer gratefully acknowledges Rebecca Mercuri's invaluable help in the preparation of this article.

TO PROBE FURTHER

There are a number of sites devoted to improving electronic voting security and reliability. Among them are those of the nonprofit Verified Voting Foundation Inc. (http://verifiedvoting.org); Black Box Voting, a site created by Bev Harris, author of a self-published book of the same name (http://www.blackboxvoting.com); and Rebecca Mercuri's Notable Software Inc. (http://www.notablesoftware.com).

The Organization for Security and Co-operation in Europe, in Vienna, a 55-nation consortium that plans to send observers to monitor the 2004 U.S. presidential election, can be found at http://www.osce.org. In addition, the Verified Voting Foundation is also organizing and training technology experts to monitor the election. As of August, more than 700 volunteers had signed up. For details, see http://vevo.verifiedvoting.org/techwatch/.