E&T on a new - secure and verifiable voting system for the USA.
It was the first US election of a new millennium, a golden era of technological innovation and white-hot Internet stocks. It should have been a celebration of the democratic might of the world's only remaining superpower. Instead, the decision of who should lead the most powerful country on the planet was made by bewildered lawyers poring over tiny scraps of cardboard.
When Floridians went to the polls in November 2000, they cast their votes on archaic IBM punch-cards, using machines that had first been conceived over 100 years earlier. With a stylus pen, voters punched their choices into pre-scored punch cards which were then fed into antiquated readers to tally the results. And they were hardly alone. In 1996, well over a third of all Americans voted on ageing Votomatic and Data-Punch devices that looked as though they belonged in computing museums rather than polling stations.
The results are, quite literally, history. With only a few hundred votes separating Al Gore and George W Bush, the outcome of Florida's popular vote would decide the identity of America's 43rd president. In recount after recount, the balance swung back and forth until Bush was finally declared the victor, by a margin of just 537 votes out of nearly six million cast.
The modern punched-card voting machine was first suggested in 1890 by Kennedy Dougan of Missoula, Montana, whose US patent describes a device not vastly dissimilar from the Votomatics of post-millennial Florida. Sporting a simple printed over-sheet, a sharp stylus and security against multiple votes, both seemed to provide a fairly resilient and fool-proof method of mechanising elections. There were no power supplies to short, no software to crash and no touchscreens to fail. There were, however, other technical challenges, including those in 2000 that had the whole world talking of hanging, dimpled and pregnant chads.
What is a chad?
A chad is the small fleck of cardboard forced out when a machine-readable card is punched. However, simple as it sounds, a chad is not always a binary event. Some chads do not open up cleanly, leaving them hanging by one or more edges, or bulging in the middle. This makes them difficult to read automatically, necessitating the bitter month-long round of manual recounts in Florida. Nationwide, almost two million ballots cast in the 2000 US election were disqualified after registering blank or multiple votes in vote-counting machines.
There had to be a better way of running elections, and the Help America Vote Act (HAVA) of 2002 was passed to discover it. Its first obstacle was that elections in the sprawling country are not managed centrally but by individual states - sometimes even individual counties - each of which has its own electoral laws and preferred voting technology. Under HAVA, the federal government would provide over $3bn of funds in a one-off push to replace that clutter of outdated machines with the latest in digital technology.
According to private election data company Election Data Services Inc, residual rates - the percentage of spoiled or unreadable ballots in an election - vary considerably with technology. For instance, switching from punch cards to paperless directing recording electronic (DRE) machines could have resulted in hundreds of thousands more votes being counted in the 2000 election. The data also suggested that switching to old-fashioned paper ballots would give the lowest possible residual rates - albeit at a financial and logistical cost no state was prepared to stomach.
It seemed as though expensive, high-tech DRE voting machines were the answer to everyone's prayers. Not only would the ATM-like touchscreen devices mean that more people's votes actually counted, they could also tally ballots instantly and transmit the results electronically, saving time and money. Moreover, blind, non-English speaking and disabled voters could have ballots spoken digitally or presented in different languages and fonts, allowing them to cast a truly private vote for the first time.
In the 2004 presidential elections, use of punch card machines had halved and DRE technology had reached a third of all polling stations. By 2006, half of all US voters were using touchscreen DRE machines. But as their popularity grew, so did complaints. From all over the country came reports of machines malfunctioning, registering votes incorrectly, deleting ballots and flipping votes from one candidate to another. Even more worryingly, computer scientists were becoming increasingly vocal about vulnerabilities of the DRE machines to serious fraud.
Professor Edward Felten is director of the Centre for Information Technology Policy at Princeton University. He says: 'One issue is that the machines store only electronic records. There are concerns about possible tampering with the voting. Less spectacular but more likely are errors that lead to incorrect results or results being lost. There is a whole body of evidence about these problems. We studied two leading DRE machines and had three main conclusions. First, malicious software code on the machine can shift from one candidate to another in ways that are very difficult to detect. Second, it takes only one minute to install that malicious software and, thirdly, it's possible to make a computer virus that spreads itself automatically between machines.'
Dan Wallach, director of Rice University's Computer Security Lab, was part of a top-to-bottom review of three manufacturers' DRE machines for California election authorities. 'We found all kinds of problems,' he says. 'Not malware, not deliberately engineered to corrupt results, but different bugs and vulnerabilities to serious attacks. We also showed that you only need to apply an evil voting patch to one machine, and you can arrange for the patch to spread to every machine in the system. It takes a relatively modest effort to corrupt every voting machine in the county.'
There is no evidence that widespread election fraud ever occurred but by the time of the presidential race in 2008, DRE machines were rapidly falling out of favour. Thousands of votes were found to have been erroneously switched or lost entirely in elections from South Carolina, California and Florida to Ohio and even Washington DC. Lawsuits and legal challenges led states from Alaska to Mexico to abandon DRE machines altogether. Following decades of growth, nearly 10 million fewer voters used electronic equipment in the 2008 election compared to 2006.
At the root of many DRE problems, thinks Wallach, is the fact that most device manufacturers keep their source code private. Some of his early discoveries of DRE vulnerabilities only happened because he was able to analyse proprietary voting software after it was accidentally left online. 'Is it appropriate to have trade secrets in elections?' asks Wallach. 'No, it's fundamentally at odds with transparency. Increased publicity doesn't reduce security, disclosure simply reveals security flaws that were already there.'
His team at Rice University has been busy developing a prototype DRE-style voting machine called VoteBox that runs on open source software visible to anyone - even potential attackers. 'If the product is well-engineered, disclosing the software will cause no additional security problems,' says Wallach, 'If the product is poorly engineered, then lack of disclosure only delays the inevitable.'
VoteBox is an end-to-end (e2e) verifiable voting system that also uses powerful encryption to resist tampering or fraud. Although VoteBox looks and feels like a standard DRE touchscreen machine, at the end of the voting process the voters are given the chance to 'challenge' their digitally-signed vote, to check whether the system has accurately recorded their choices.
This smart VoteBox
In a challenge, the voter is given a key code that can be used to decrypt the vote at any point in the future, perhaps on an official website. To avoid coercion or vote-selling, the code does not show how one voted. VoteBox also uses a cryptographic technique called homomorphic tallying to add up votes. This allows any number of independent observers to confirm the final vote count for themselves, based only on the anonymous and encrypted records.
Although Rice University is keen to commercialise VoteBox, Wallach is realistic about the chances of it coming to market. 'So far as we can tell, equipment vendors are no longer developing paperless DRE-style machines,' he says. 'Given that we won't have a repeat of HAVA, where the federal government doled out money for new equipment, election officials really have no choice but to go for lower cost solutions. If the money runs out, we're heading back to paper.'
In effect, that means optical scanning. Optical scan devices use pre-printed ballots that are filled in by hand then scanned by high-speed machines. The systems are cheap to make and buy, have no complex software to go wrong (or attack) and the paper ballots can be recounted and audited by hand if required.
Returning to bulky, analogue paper might be a retrograde step, if it were not for advances like Scantegrity, an open-source research project with contributions from universities across the US and Canada. Scantegrity is an e2e system that adds a verification step to optical scan voting, again using strong encryption. Whenever a voter selects a candidate, the process of blacking out a box with an 'invisible ink' pen reveals an apparently random series of characters. These characters form the key code receipt that the voter can use to verify the ballot later on.
Here is where America having a multitude of electoral authorities finally pays off. Last November, the city of Takoma Park in Maryland chose Scantegrity for its mayoral elections, the first time an end-to-end verifiable voting system had been used to elect a public official, anywhere in the world. On 3 November, almost exactly nine years after the Florida chad fiasco, Bruce Williams was returned as mayor of Takoma Park by a margin of just 330 votes - half the size of Bush's razor-thin victory over Gore. If Williams's opponent had been unhappy with the result, he would not have had to demand a lengthy manual recount or resort to the courts, he could have carried out one himself in minutes . (Admittedly, an upset would be unlikely - in this small suburb of Washington, 330 votes represented nearly a fifth of all votes cast).
The implications for America are huge. Moving the country to a secure, verifiable e2e voting system could allow millions more people to have their voices heard and remove nagging doubts over close-run elections. And who knows? In two years' time, e2e systems might even be helping to decide the resident of the country's most famous house, just seven miles and 130 million votes down the road from Takoma Park, on Pennsylvania Avenue.