The Difficult Problem of Simply Voting - Algorithms & Randomness Center (ARC) and Institute for Information Security & Privacy (IISP) Colloquium featuring Rich DeMillo
featuring Richard A. DeMillo (C21U)
Monday, May 13, 2019
MiRC Pettit 102 A&B – 11:00am
Title: The Difficult Problem of Simply Voting
Abstract: Elections seem pretty simple: People show up on election day to vote for one candidate or another. A good election system has to accurately count the number of votes for each candidate and report the totals to the public while ensuring that
V1 Elections are fair
V2 Everyone's votes are secret,
V3 Only eligible votes are counted
V4 No one votes more than once
V5 Ballots, once cast, are not altered, lost, or destroyed
Many people believe that, in an Internet-enabled world, secure, safe voting should be easy to achieve. For example, using known cryptographically secure protocols (maybe even blockchains), a secure website might be developed to relieve voters of the burden of driving to a polling place on election day. While we're at it, we can probably improve on the election algorithm itself, since there is a rich literature on fair voting schemes that more accurately and reliably reflect actual voter preferences.
E1 There is no one in charge of elections. The U.S. Constitution delegates that authority to states and localities. A national election is more than 10,000 independent elections, each one operating autonomously, using its own rules.
E2 Because casting, recording and counting votes is an error-prone human process, the losing candidate is often not convinced that the result is accurate. Although no one trusts anyone else, elections should generate public evidence to convince those who voted for the loser that another candidate won.
E3 The scale and complexity of American elections require computerization of the voting process, and computers can be hacked or misprogrammed
E4 The only known methods for protecting voting computers rely on math and technology, but the average voter does not understand math or technology
We now know that there are active, well-funded adversaries who are trying to disrupt elections with information and cyber attacks on election systems. E1-E4 prohibit many security-enhancing simplifications and therefore complicate the problem of conducting modern elections in such an environment.
The most widely accepted method for ensuring that errors in tabulating votes (whether malicious or inadvertent) is the Risk-Limiting Audit (RLA), a post-election, sequential sampling process that for some predetermined risk limit α: confirms an error-free tabulation with probability 1 and fails to confirm an incorrect tabulation with probability at least 1-α. The most widely accepted necessary condition for securely marking and tabulating ballots is software independence (an undetected error in voting software cannot result in an undetectable change in reported vote totals).
Two competing election systems purport to be auditable and software independent: hand-marked paper ballots and paper ballots printed by machines called Ballot Marking Devices (BMDs). In this talk, I will discuss recent work with Andrew Appel and Philip Stark, arguing that BMDs are neither software independent nor meaningfully auditable by RLAs. We also introduce two new conditions called contestability and defensibility that are necessary for an audit to confirm election results.