The Turing Machine in the Voting Booth
Princeton University Computer Science Professor Andrew Appel summarized the inherent difficulties of voting technologies and pressed for a solution, the need for Voter-Verified Paper Ballots and computer counting with random by-hand audits of selected precincts.
It’s actually hard, noted Appel at the September 26 Lunch ‘n Learn seminar, to guarantee an accurate vote count, even if no individual election officialis trusted on both sides, and to have a secret ballot. A voting protocol must permit each person to vote (just) once, it must accurately record the votes, and it must accurately count the votes. Voters need to sure that their votes are counted, even if the other side’s people are election officials. We also require secrecy; we must not be able to learn how a person voted with or without their consent.
In his talk, Dr. Appel noted that voting procedures and technologies have changed considerably during the past 250 years. New technologies were often introduced in response to abuse and manipulation of one procedure or technology. Widespread, repeated, brazen vote fraud in the 19th century led to political and technological reforms. To improve voting procedures, states introduced re-countable ballots, a secret ballot to reduce coercion and bribery, and they eliminated paper ballots that encouraged candidates and parties to pre-print all of the selections.
The Australian ballot in 1890 enabled relatively fair elections. County election officials created pre-printed ballot that included all of the candidates’ names. Voters would go into the polling place and, as today, mark and then submit a ballot into a box that was carefully watched by several people. By the end of the century, the first mechanical voting machines were introduced. But that technology was imperfect. Registers could jam, even without tampering.
Use of punched cards began in the 1960s. Optical scan readers were introduced in the 1970s. And direct-recording computerized voting machines appeared in the 1980s. By the 1990s, a few voices began to be heard about the possibility of cheating in electronic voting.
In her doctoral dissertation, Rebecca Mercuri argued that it was impossible to know what the computer program was actually doing inside the machine. Roy Saltman predicted as early as 1968 that hanging chads would someday be a problem. Of course, few paid attention to the inherent problems of the new voting technology until 2000 with Bush v Gore.
While states have since rushed to buy electronic voting machines, computer scientists have finally began to appreciate what Mercuri had predicted. The key, emphasizes Appel, is that there’s just no way to provide a guarantee against cheating in the computer programs inside the voting machines. The program that controls the operation of the machine is stored in the machine’s own memory, along with the data on which it operates. Thus it is a general-purpose computer: the program can be easily modified.
To commit election fraud, one only needs to write a computer program that counts accurate on non-election days but cheats on election day. Pre-election testing will reveal no errors, and voters will see nothing amiss. Appel concludes that Voter-Verified Paper Ballots and computer counting with random by-hand audits of selected precincts are essential steps.
A podcast of the talk is available.