Improving the Security of United States Elections with Robust Optimization

• URL: http://arxiv.org/abs/2308.02306v2
• Date: Mon, 30 Sep 2024 01:45:18 GMT
• Title: Improving the Security of United States Elections with Robust Optimization
• Authors: Braden L. Crimmins, J. Alex Halderman, Bradley Sturt,
• Abstract summary: We introduce the first formal approach to designing test decks with rigorous security guarantees. Our approach has since been piloted in real-world elections by the Michigan Bureau of Elections.
• Score: 5.454428371457422
• License:
• Abstract: For more than a century, election officials across the United States have inspected voting machines before elections using a procedure called Logic and Accuracy Testing (LAT). This procedure consists of election officials casting a test deck of ballots into each voting machine and confirming the machine produces the expected vote total for each candidate. We bring a scientific perspective to LAT by introducing the first formal approach to designing test decks with rigorous security guarantees. Specifically, our approach employs robust optimization to find test decks that are guaranteed to detect any voting machine misconfiguration that would cause votes to be swapped across candidates. Out of all the test decks with this security guarantee, our robust optimization problem yields the test deck with the minimum number of ballots, thereby minimizing implementation costs for election officials. To facilitate deployment at scale, we develop a practically efficient exact algorithm for solving our robust optimization problems based on the cutting plane method. In partnership with the Michigan Bureau of Elections, we retrospectively applied our approach to all 6928 ballot styles from Michigan's November 2022 general election; this retrospective study reveals that the test decks with rigorous security guarantees obtained by our approach require, on average, only 1.2% more ballots than current practice. Our approach has since been piloted in real-world elections by the Michigan Bureau of Elections as a low-cost way to improve election security and increase public trust in democratic institutions.

Related papers

• Improving the Computational Efficiency of Adaptive Audits of IRV Elections [54.427049258408424]
  AWAIRE can audit IRV contests with any number of candidates, but the original implementation incurred memory and computation costs that grew superexponentially with the number of candidates. This paper improves the algorithmic implementation of AWAIRE in three ways that make it practical to audit IRV contests with 55 candidates, compared to the previous 6 candidates.
  arXiv  Detail & Related papers  (2024-07-23T13:28:00Z)
• Publicly auditable privacy-preserving electoral rolls [0.32498796510544625]
  We study the problem of designing publicly auditable yet privacy-preserving electoral rolls. The audit can detect polling-day ballot stuffing and denials to eligible voters by malicious polling officers. The entire electoral roll is never revealed, which prevents any large-scale systematic voter targeting and manipulation.
  arXiv  Detail & Related papers  (2024-02-18T13:11:48Z)
• Efficient Weighting Schemes for Auditing Instant-Runoff Voting Elections [57.67176250198289]
  AWAIRE involves adaptively weighted averages of test statistics, essentially "learning" an effective set of hypotheses to test. We explore schemes and settings more extensively, to identify and recommend efficient choices for practice. A limitation of the current AWAIRE implementation is its restriction to a small number of candidates.
  arXiv  Detail & Related papers  (2024-02-18T10:13:01Z)
• The Decisive Power of Indecision: Low-Variance Risk-Limiting Audits and Election Contestation via Marginal Mark Recording [51.82772358241505]
  Risk-limiting audits (RLAs) are techniques for verifying the outcomes of large elections. We define new families of audits that improve efficiency and offer advances in statistical power. New audits are enabled by revisiting the standard notion of a cast-vote record so that it can declare multiple possible mark interpretations.
  arXiv  Detail & Related papers  (2024-02-09T16:23:54Z)
• Adaptively Weighted Audits of Instant-Runoff Voting Elections: AWAIRE [61.872917066847855]
  Methods for auditing instant-runoff voting (IRV) elections are either not risk-limiting or require cast vote records (CVRs), the voting system's electronic record of the votes on each ballot. We develop an RLA method that uses adaptively weighted averages of test supermartingales to efficiently audit IRV elections when CVRs are not available.
  arXiv  Detail & Related papers  (2023-07-20T15:55:34Z)
• Logic and Accuracy Testing: A Fifty-State Review [4.596972309626531]
  Pre-election logic and accuracy (L&A) testing is a process in which election officials validate the behavior of voting equipment. We present the first detailed analysis of L&A testing practices across the United States. We find that while all states require L&A testing before every election, their implementations vary dramatically in scope, transparency, and rigorousness.
  arXiv  Detail & Related papers  (2022-07-28T22:21:37Z)
• Towards Secure Virtual Elections: Multiparty Computation of Order Based Voting Rules [5.156484100374059]
  One of the main challenges in e-voting systems is to certify that the computed results are consistent with the cast ballots. We propose a secure voting protocol for elections governed by order-based voting rules. Our protocol offers perfect ballot secrecy, in the sense that it issues only the required output, while no other information on the cast ballots is revealed.
  arXiv  Detail & Related papers  (2022-05-21T12:17:21Z)
• Expected Frequency Matrices of Elections: Computation, Geometry, and Preference Learning [58.23459346724491]
  We use the "map of elections" approach of Szufa et al. (AAMAS 2020) to analyze several well-known vote distributions. We draw the "skeleton map" of distributions, evaluate its robustness, and analyze its properties.
  arXiv  Detail & Related papers  (2022-05-16T17:40:22Z)
• A First Approach to Risk-Limiting Audits for Single Transferable Vote Elections [27.102139020324678]
  Risk-limiting audits (RLAs) are an increasingly important method for checking that the reported outcome of an election is, in fact, correct. This paper presents the first approach to risk-limiting audits for single transferable vote (STV) elections.
  arXiv  Detail & Related papers  (2021-12-18T12:36:39Z)
• Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules [58.8640284079665]
  We study the problem of bribery in multiwinner elections, for the case where the voters cast approval ballots (i.e., sets of candidates they approve) We consider a number of approval-based multiwinner rules (AV, SAV, GAV, RAV, approval-based Chamberlin--Courant, and PAV) In general, our problems tend to be easier when we limit out bribery actions on increasing the number of approvals of the candidate that we want to be in a winning committee.
  arXiv  Detail & Related papers  (2021-04-19T08:26:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.