Scan, Shuffle, Rescan: Two-Prover Election Audits With Untrusted Scanners
Sunoo Park (Columbia University)
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 could drastically reduce the time, expense, and labor of auditing close elections, which we hope will promote wider deployment. Joint work with Douglas W. Jones, Ronald L. Rivest, and Adam Sealfon.
Mathematics
Audience: general audience
Comments: Sunoo Park is a postdoctoral fellow at Columbia University and visiting fellow at Columbia Law School. Her research is in security, cryptography, privacy, and related law/policy issues. She received her J.D. at Harvard Law School, her Ph.D. in computer science at MIT, and her B.A. in computer science from the University of Cambridge.
NYU CDS Math and Democracy Seminar
Series comments: The Math and Democracy Seminar features research on contact points between the mathematical sciences and the structure of democratic society. The purpose of the seminar is to stimulate mathematical activity on problems relating to democracy, and to foster interdisciplinary collaboration between mathematicians and other scholars and democratic stakeholders.
Examples of topics of interest include detection of gerrymandering, fairness and accountability of algorithms used in social decision-making, voting and apportionment theory, applications of statistics to discrimination law and the census, and mathematical modeling of democratic processes. The scope is not limited to these and is expected to expand as further applications emerge.
Seminars currently conducted via Zoom (with some events also in person). Look for links in individual talk descriptions.
| Organizers: | Ben Blum-Smith*, Jonathan Niles-Weed |
| *contact for this listing |
