ARC-IISP Colloquium: Richard DeMillo (Georgia Tech)

Algorithms & Randomness Center (ARC) and

Institute for Information Security & Privacy (IISP)  Colloquium

Richard A. DeMillo (Georgia Tech)

Monday, May 13, 2019

MiRC Pettit 102 -- 11am

Powerpoint of slides from Rich DeMillo's May 13, 2019 colloquium

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.

Except that:

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.

----------------------------------

Speaker's Webpage

Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836

Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu

Event Details

Date/Time:

  • Monday, May 13, 2019
    11:00 am - 12:00 pm
Location: MiRC 102