DEPARTMENT OF COMPUTER SCIENCE
|CPSC 461b: Foundations of Cryptography||Notes 15 (rev. 1)|
|Professor M. J. Fischer||March 5, 2009|
Lecture Notes 15
Secret ballot elections are an important real-world problem that combines security issues with significant social and political issues. As an introduction to Ron Rivest’s 2009 Perlis Lecture on Security of Voting Systems, I want to say a little about what the election problem is and why how it differs in fundamental ways from other superficially similar problems such as e-commerce.
Briefly stated, each eligible voter casts a vote for one of a set of candidates for an office. The election system counts the number of votes for each candidate. The candidate with the most votes wins. What could be simpler?
It only becomes hard when we add real-world constraints. We must assume that some voters and election officials are dishonest and are motivated to corrupt the election in favor their preferred candidate, if possible. Already we can see many possible opportunities for corruption. Voters might cast multiple votes. Ineligible voters might cast votes. Voters might not vote for their preferred candidate because of intimidation or for financial gain. Eligible voters might be denied the opportunity to vote. Ballots might be counted incorrectly, and vote totals might be misreported.
Yale computer science Ph.D. and Duquesne University J.D. Michael Ian Shamos, now at Carnegie-Mellon University, came up with a list of requirements for voting systems that attempt to reflect some of these real-world constraints. The Six Commandments in Figure 37.1 are taken from his paper, CFP’93 – Electronic Voting – Evaluating the Threat, 1993, which appears on the Computer Professionals for Social Responsibility (CPSR) web site at http://www.cpsr.org/prevsite/conferences/cfp93/shamos.html.
These are a tough set of requirements to meet in practice. Let’s see how our existing voting systems work.
Vote-selling is discouraged by the inability of a voter to provide evidence of how she voted, so a party interested in buying votes cannot know whether or not a voter complied with their wishes. This implies that voting systems must not issue receipts that would allow a voter to prove to another how she voted.
Mechanical voting machines and many direct-recording computerized voting terminals lack the ability to provide a voter-verified audit trail. With such machines, the votes are stored internally in the machine until the polls close, at which point election workers read out the totals. Here, there is no way for a voter to know that her vote was counted correctly. Obviously, the total votes cast on a machine can be compared with the number of people who voted on that machine, but there is no way to connect the votes recorded with the votes cast by the voter. With mechanical machines, the linkages between levers and counters are relatively simple and visible. One can have some degree of confidence that the machine is working as intended just through a visual inspection of its innards and some simple testing of its operation.
With computerized voting terminals, all such transparency is lost. One cannot look at a computer and know what is going on inside. Testing is insufficient since computers can easily be programmed to respond normally except when given some kind of coded signal, which might be nothing more than a ballot being cast for a particular unlikely collection of candidates. Such a machine might perform flawlessly during testing, yet corrupt the vote on election day after a malicious voter, in the privacy of the voting booth, cast the coded ballot that triggered the embedded malware. Some confidence might be gained by an examination of the source code, but most voting machine companies consider their code to be proprietary and require through their contracts that it be kept confidential.
An interesting question, especially for a cryptography class, is how one might carry out elections completely electronically, on the internet for example. This is not just a hypothetical. The Department of Defense planned to allow troops overseas vote via the internet in the 2004 presidential election. This idea was later scrapped after much protest. (See American Forces Press Service News Article, Pentagon Decides Against Internet Voting This Year by Jim Garamone, Feb. 6, 2004.) But such ideas die hard. Bill HB 5903 is now pending in the Connecticut General Assembly to permit electronic submission of absentee ballots for troops stationed overseas.
Internet elections pose serious challenges to almost all of Shamos’s commandments. How can an electronic ballot be both private and countable? How can voting be restricted to authorized voters in a way that prevents the tabulating authority from being able to match voters to ballots? How does one prevent tampering with the software used to implement the system, both on the user’s computer and also at the central authority? How does one prevent a voter from selling her voter credentials to a third party? How does one prevent a voter from voluntarily letting a third party cast her ballot on her behalf? How can one decentralize an internet voting system so as to obtain some of the robustness that our current decentralized system enjoys? How can one prevent targeted denial-of-service attacks that could disable internet voting for certain groups of voters on election day? What kinds of electronic audit trails are possible, and how can they be verified?
Several election protocols have been devised that attempt to address some of these questions. While none is entirely satisfactory from a practical point of view, they do employ some clever cryptographic ideas that might eventually be useful.