International Association
for Cryptologic Research

We introduce a new way to conduct post-election audits using untrusted scanners. 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 employ automated consistency checks, augmented by manual checks of only a small number of ballots. Our protocols scan each ballot twice, shuffling the ballots between the scans. This gives strong statistical guarantees even for close elections, as long as (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. In practice, ballots often have distinguishing features, of course; but we argue that reasonable measures can limit their detection by scanners under controlled conditions. Our techniques drastically reduce the time, expense, and labor of auditing close elections, which we hope will facilitate 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 allow (1) more than two candidates; (2) processing of ballots in batches; and (3) tolerating imperfect scanners, as long as scanning errors are too infrequent to affect the election outcome. Finally, we propose and discuss an alternate scheme that reduces the trust assumptions placed on the shuffling mechanism at the expense of adding an additional scan. 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.