Keeping Electronic Voting Honest
Notes for a panel discussion at the
AAAS Annual Meeting
Voting Technology: Current Assessment and Future Prospects, A Post-2004 Election Update
Feb 18, 2005
Elections are complicated unless all voters fit comfortably in one room. The problem is simple, sum all of the votes for each candidate or position on an issue, but the integrity and security constraints are extremely difficult to solve when any part of the process takes place out of the view of some of the participants. Questions of who you can trust come to dominate the entire process.
Most election officials know very little about computer technology. This should surprise nobody. Most of those charged with administering any technology in the United States, or for that matter, the world at large, know very little about the technologies they administer. In 1832, Charles Babbage complained eloquently that "Those who possess rank in a manufacturing country, can scarcely be excused if they are entirely ignorant of principles, whose development has produced its greatness" (Preface to On the Economy of Machinery and Manufactures). Unfortunately, this has not changed, and unfortunately.
Therefore, election officials depend on expert advice when technological questions arise. Like many who depend on complex technologies, they tend to develop very close working relationships with their system vendors. Like most computer users, they call tech support, and the vendors of voting systems have become very good at sustaining this trusting relationship even when the systems perform poorly. Officials also have the option of hiring outside experts, either from the academic research community or from the much larger community of certified computer professionals of various sorts.
Election officials have strong reasons to turn a blind eye to failings in their voting systems. In general, public officials who have invested many dollars of public money are better off denying that the money was misspent. To acknowledge error imposes a burden of guilt. To avoid looking into the shortcomings of the systems they administer imposes, at worst, a burden of incompetence. I am convinced that this chain of reasoning is almost always unconscious, serving primarlily to channel the election officials attention away from critics and toward those experts who are willing to back their decisions.
Scientific ethics can prevent scientists from being heard. As academics, if we are good at it, we will be painfully honest, stating the extent of our ignorance, forthrightly saying "I don't know" when we don't. And then, when asked a question where we do know the answer, we tend to answer at length, giving all the relevant details. Compare this with the advice from the Diebold Election Systems Election Support Guide (2002): "You will generally be considered ... a paragon of knowledge ... , which may be disconcerting when things go wrong. Do not promote your ignorance - in case of doubt, call a designated contact ... Offer the minimum amount of information necessary. ... Do not to offer damaging opinions of our systems, even when their failings become obvious." (Section 3.2).
Most exams for certified computer professionals are at the junior college level. There is an alphabet soup of such certification schemes, and on paper, to someone not knowledgable in the subject matter, they are almost impossible to evaluate. To an election official, such certification may sound comparable to the certification we demand of lawyers or physicians or civil engineers, but it is not. The Ordre des ingenieurs du Quebec (OIQ) sued Microsoft over the use of the use of the term Microsoft Certified Systems Engineer (MCSE), holding that the use of the term engineer violated Quebec law, and on April 7, 2004, the case was decided in favor of the OIQ.
Many reputable computer security experts know little computer science. Many people have risen through the ranks to positions of high repute on the basis of undergraduate educations, almost entirely devoid of theory. The truth is, large parts of security are indeed matters of good craftsmanship. This was driven home to me when two students of mine sent preprints of a paper they were submitting to an applied security conference to people he thought were representative of the program committee. Half of them said they did not understand the subject. The problem is, the paper was relating computer security to issues of automata theory and formal language theory, core areas of computer science.
Many defenses of electronic voting technology rest on impossible claims. We are told that independent third-party source code evaluation, use of antivirus software, and use of industry-standard third-party components should all make us feel secure.
There is no such thing as effective antivirus software. By effective, we mean, it never declares innocent code to be a virus, never declares viruses to be safe, and always reaches a decision in a finite time. The proof follows from Alan Turings 1938 proof of the undecidability of the halting problem. Assume the existance of such software. Build it into your application as a component, having it examine your application itself. Complete the application with code that is benign if the virus detector claims there is a virus present, but that behaves like a virus if the virus detector claims that the code is safe. We now have a contradiction, so our initial assumption must be false. Therefore, the best we can do is produce approximations, and any reliance on these approximations must be questioned.
Source code inspection cannot offer any guarantees. Ken Thompson proved this in 1984 ("Reflections on Trusting Trust, CACM, August 1984). The proof was by construction of a compiler that attached a virus to all programs compiled by itself. Once this was completed, it was used to compile an honest version of the compiler, creating a covertly dishonest version with honest source code. Having completed this step, a dishonest person would have deleted the source code of the virus instead of publishing the result. Of course, this does not mean that source code inspection is not valuable, it is, but it is not perfect.
Antivirus software is itself a security threat. Antivirus software, by design, detects that a program is in some set of forbidden programs, so that the system can interfere with their correct execution. Without such software, the computer's behavior is fairly simple, executing all programs according to the same rules. With this software, the situation is far more comples; we have the possibility, for example, that the system will detect and attack any application, even election software.
Proprietary software that is not open to inspection is a security threat. If you cannot inspect the product, how can you know that it does not contain unacceptable code? Proprietary software protected by copyright or patent law is quite different! The marketplace, however, has not been willing to insist on open disclosure as a condition for retaining proprietary rights, and so long as one vendor does not disclose, nobody will be able to know what that vendor is stealing from vendors who disclose. This is a public policy issue in the area of intellectual property law.
The security of a system is proportional to the number of distinct and separately carried secrets required for its secure operation. If we must bribe a minimum of ten people to break a system, the system is more secure than a system that can be broken by bribing only one person.
The security of a secret declines as more people share the secret. This hardly requires comment, except to note that, in conjunction with the previous note, this strongly suggests that what we need to do is minimize our reliance on secrets, of any kind, for the security of our vote counting systems while making sure that those we do rely on are divided between many people, not closely held by any one person, party or corporate participant.
The purpose of an election is not to name the winner, it is to convince the losers that they lost. Dan Wallach surprised many of us by saying this in the spring of 2004. While not intuitive, it is obviously true. The winner rarely contests an election, the winner has little reason to investigate discrepancies. It is the looser that will always do this.
Public oversight of a process that is not easily understood is almost meaningless. I have observed vote counting done with computers, where all the action occurred on computer screens that I could not clearly see because the people operating the computers were in the way. Furthermore, even if I had been able to see, the relevant documentation was proprietary and unavailable to any of the observers.
The ideal security proof for an election system should therefore be accessible to a bright high-school student. (David Chaum has been calling this Jones's Rule.) If the level of education required to understand the security proof limits the population that can understand the proof to a class of people the loser doesn't trust, the proof will fail to convince.
Discussion of weaknesses in security technology endangers public trust. This argument has been made repeatedly by supporters of current election technology. In fact, there is an element of truth to this, and critics of election technology must be careful to avoid driving people away from the democratic process they hope to improve.
Discussion of weaknesses in security technology are necessary to strengthening that technology. This was eloquently said by Charles Tomlinson, in his Rudimentary Treatise on the Construction of Locks, written in 1853. His answer is as relevant now as it was then. Without public discussion of the strengths and weaknesses of the technology, only scoundrels will know what is secure and what is not.
Historians generally agree that there have been many crooked politicians in the past who were never convicted. Chicago in the bad old days of machine politics was notorious but hardly an isolated example.
Routine error is fairly common in elections, no matter the technology used. Too frequently, these are not reported, even when state law requires it, simply because it is inconvenient. Otherwise honest election officials sometimes delete files, shred paper, conduct undocumented recounts and otherwise commit technically illegal acts simply because it is less work than properly documenting what is obviously an isolated and unimportant incident.
Sunshine laws are expensive and inconvenient. Every public request for documentation concerning the proper conduct of an election is a nuisance, and even if the requestor is charged the real cost of answering the request, each such request exposes the establishment to possible embarrassment when honest mistakes are uncovered and blown out of proportion. Therefore, public officials naturally resist disclosure and preferentially disclose information in inconvenient and expensive forms. I have seen an election official in Miami say this to an observer, for example: "I have to let you watch, I don't have to explain what I'm doing." This was from an official that I respect!
A crook who has rigged an election can easily masquerade as a routine bungler responding normally. This follows from the frequency of routine error and the normal reluctance of election officials to expose such errors to public scrutiny.
There is no silver bullet. The campaign for voter verified paper ballots addresses a large number of the facts described above, but it does not address others. End-to-end cryptographic models also address many of these issues, but not others. Open source voting systems address many other issues, and if we can combine these with either voter-verified paper or with end-to-end cryptographic models, we will indeed make progress.
But this will not be enough. We face a legacy problem, where carelessness has been institutionalized. Our democracy really is at risk because the only difference between routine conduct and criminal election fraud today, all too frequently, is a matter of intent and bias. Criminals make systematic errors in favor of one candidate, while honest mistakes tend to cancel. Legacies like this are very hard to grapple with, and as a technologist, I find it difficult to know where to begin.
Everything I have written about elections is on the world-wide web. See