It is election day. You step into the polling booth and place a mark against your chosen candidate on the ballot form. You then take your ballot to a machine that scans the paper and displays it on-screen for you to confirm. It appears as if everything has gone smoothly, but how can you be sure the computer has awarded your vote to the right candidate?
When US voters go to the polls for mid-term elections on 7 November, the vast majority will rely on software to tally their votes, either by using an optical scanner like this or a touch-screen machine. Electronic vote-counting is attractive in the US, where complex ballot forms typically contain dozens of different choices, making them difficult to sort by hand.
The question is: can these e-voting machines be trusted? Over recent years voters have come to doubt it. In July 2003 computer scientist Avi Rubin at Johns Hopkins University in Baltimore, Maryland, claimed that flaws in touch-screen voting machines built by Diebold Election Systems of McKinney, Texas, meant that a single voter could cast many votes without leaving any evidence of their fraud. As a result, over half of all states now insist that votes cast electronically are accompanied by a paper copy that is deposited in a box to be checked if vote-rigging is suspected.
Advertisement
More and more experts argue this is not enough. Paper votes can be lost or become illegible, either through faulty printers or foul play, while software bugs and malicious programs that delete or flip votes could go undetected. âItâs a black box,â says Rick Carback, a computer scientist at the University of Maryland, Baltimore County. âOnce you give the machine your vote you donât know whether it has been counted or not.â
Carback and others believe the future lies in voting systems that use cryptography to protect voter privacy, while allowing a voter to verify that their vote has been counted correctly. âCryptography can shoot dead the voting problem,â says David Chaum, a cryptographer based in Los Angeles who pioneered the field of crypto e-voting.
âThe future lies in systems that allow a voter to verify their vote has been counted correctlyâ
As well as preventing fraud, such systems could also help avoid disputes over election results, such as the protests that followed Mexicoâs presidential election in July, by reassuring voters that the election is above board. By increasing voter confidence in the system, they could also encourage more people to vote, Chaum says.
The main difficulty with all voting systems is finding a way to allow people to confirm that their vote has been counted without also allowing them to prove to someone else how they voted. For example, hard copies of ballots that can be taken away from the polling booth are a big no-no, because giving people proof of how they have voted makes it possible for them to sell their vote to anyone hoping to rig the election, or be intimidated. This is where cryptography can help, because it allows a voter to verify their vote online without revealing who they voted for.
A number of such systems have been designed (see âYour next ballot paper could look like thisâ), all of which use a series of encryption steps, each undertaken by a different election teller. Firstly, a template of the ballot paper for each voting district is created electronically, with a list of candidates and spaces for the voters to mark their choice. This is then copied so that there are enough individual electronic papers for all the districtâs registered voters, and the copies are passed to the tellers. The first teller electronically shuffles both the order of candidates on each paper and the order of the papers, and then for each paper generates a unique code that describes what shuffling has been done. This code is encrypted and added to the bottom of the paper.
The ballot papers â still in electronic form â are then passed to a second teller, who shuffles the order of candidates on each paper and the order of papers once more, and creates their own encrypted code for each paper, which is added to the first. More tellers can be used to add further layers of shuffling before the ballot papers are printed out.
When the voter goes to the polling station on the big day, they take one of these coded papers and mark their chosen candidate, as usual. Then they rip their ballot paper up.
This is not a political protest. The ballot paper is designed to be torn into two pieces, neither of which on its own can show an unauthorised third party which candidate the voter chose. One or both of the pieces, however, carries the tellersâ code, which holds the secret of deciphering that individual ballot paper and the mark the voter made on it. The voter puts one piece into a shredder and takes the other, now inscrutable slip to a machine that scans it. The voter takes this half-ballot away with them.
The ballotâs scanned image data is sent to the second tellerâs computer, which decrypts the second tellerâs segment of the code and uses it to unshuffle the order of candidates and papers. The resulting data is then sent to the first teller, who in turn undoes their shuffling to reveal the order of candidates that the voter saw. The vote can then be awarded to the matching candidate. In this way, the second teller knows the full code on the ballot sheet, which ties the vote to the voter, but not the name of the chosen candidate. The first teller, in contrast, knows the chosen candidate, but with only a fragment of the code has no way of finding out who cast the vote. To prevent tellers sharing their codes to connect the voter with their vote, cryptographers such as Chaum recommend tellers come from opposing political parties.
What makes the system tamper-proof, however, is that the voter can check that their vote has been counted correctly. They simply go to a public website and key in the encrypted code from the part of their ballot paper that they marked, scanned and took away. If their vote has been registered properly, this will bring up an image of that same ballot, with the mark in the correct box, but crucially will not reveal the name of their chosen candidate.
If such schemes are to succeed in preventing fraud, voters must be proactive, either in checking their ballot themselves or giving it to an organisation such as the American Civil Liberties Union for checking. Only a few would need to do this, however, to ensure the integrity of the election.
Persuading the public to accept such complex schemes may be tough. Rubin, however, is optimistic. âWe need to get to the point where the public trusts that these systems work, the way they trust that an airplane will work,â he says, âdespite the fact that they donât have a degree in aeronautical engineering.â
Your next ballot paper could look like this
Cryptographic electronic voting systems were first proposed four years ago, but the schemes were far too complicated for practical use.
In recent months a new generation of much simpler schemes has appeared. âResearchers are making progress in taking the basic concept and turning it into something closer to a real system that could be deployed in practice,â says David Wagner at the University of California, Berkeley.
One such system, called PrĂȘt Ă Voter, has been developed in the UK by Peter Ryan, a cryptographer at the University of Newcastle upon Tyne. PrĂȘt Ă Voter ballots consist of a sheet of paper perforated down the centre, with candidate names in random order on the left and a column of boxes on the right. Voters mark the ballot in almost the same way as British voters do today, putting a cross in the box next to the candidate they select. They then tear the sheet in two, shred the side with the candidate names and scan the column of boxes. An encrypted code on each paper is used to reconnect the marked box with the candidate.
Meanwhile David Chaum, a cryptographer based in Los Angeles, has developed a similar system called Punchscan. This uses two overlaid sheets of paper. On the top sheet is the list of candidates, and alongside each are two holes, above which is printed âa=yes, b=noâ, or vice versa, though the holes themselves are not labelled. On the bottom page, printed so they show through the holes, are the letters âaâ and âbâ, in random order. On both sheets is an encrypted code that, when decrypted, reveals the order of âaâ and âbâ for each candidate.
The voter makes a selection by marking around one hole with a large felt-tip pen. The pen marks both sheets, and the voter pulls the sheets apart, shreds one â it doesnât matter which â and scans and keeps the other.
In both systems, the marked ballot paper is torn apart so that neither part reveals which candidate the user has voted for, but either can be used to reconstruct the personâs vote if you can decrypt the code.
Chaum says the main advantage of Punchscan is that, unlike PrĂȘt Ă Voter and other systems, tellers use secret keys to encrypt and decrypt the code, rather than using public-key cryptography, a widely used technique in which a publicly available key is used to encrypt a code and a secret key is used to decrypt it. âPublic-key encryption is wonderful but very few people have any deep understanding of it,â he says. âEven a 10-year-old can relate to secret codes,â he says.
