Paper 2022/960

Scan, Shuffle, Rescan: Machine-Assisted Election Audits With Untrusted Scanners

Abstract

We introduce a new way to conduct election audits using untrusted scanners. Post-election audits perform statistical hypothesis testing to confirm election outcomes. However, existing approaches are costly and laborious for close elections---often the most important cases to audit---requiring extensive hand inspection of ballots. We instead propose automated consistency checks, augmented by manual checks of only a small number of ballots. Our protocols scan each ballot twice, shuffling the ballots between scans: a ``two-scan'' approach inspired by two-prover proof systems. We show that this gives strong statistical guarantees even for close elections, provided that (1) the permutation accomplished by the shuffle is unknown to the scanners and (2) the scanners cannot reliably identify a particular ballot among others cast for the same candidate. Our techniques drastically reduce the time, expense, and labor of auditing close elections, which we hope will promote wider deployment. We present three rescan audit protocols and analyze their statistical guarantees. We first present a simple scheme illustrating our basic idea in a simplified two-candidate setting. We then extend this scheme to support (1) more than two candidates; (2) processing of ballots in batches; and (3) imperfect scanners, as long as scanning errors are too infrequent to affect the election outcome. Our proposals require manual handling or inspection of 10--100 ballots per batch in a variety of settings, in contrast to existing techniques that require hand inspecting many more ballots in close elections. Unlike prior techniques that depend on the relative margin of victory, our protocols are to our knowledge the first to depend on the absolute margin, and give meaningful guarantees even for extremely close elections: e.g., absolute margins of tens or hundreds of votes.