arXiv CSopen access

Sublinear Risk-Limiting Audits from Direct Ballot Selection and Statistical Ballot Manifests

Sublinear Risk-Limiting Audits from Direct Ballot Selection and Statistical Ballot Manifests Benjamin Fuller, Abigail Harrison, and Alexander Russell {benjamin.fuller,abigail.harrison,acr}@uconn.edu

arXiv:2605.18670v1 [cs.CR] 18 May 2026

Voting Technology Research Laboratory University of Connecticut May 19, 2026

Abstract

polling, and direct selection audits by factors of 400, 20, and 8, respectively.

Risk-limiting audits (RLAs) are post-election auditing procedures that rigorously guarantee a specified maximum probability that an incorrect electoral outcome will not be detected. Aside from ready access to physical ballots, known RLAs require a software-independent accounting of the sizes of each ballot batch, called a ballot manifest. While typical electoral procedures automatically provide rough estimates for batch sizes, even slight inaccuracies (commensurate with the margin of the contest under audit) completely invalidate conventional RLAs (Lindeman et al., EVT 2012). Thus, establishing a sufficiently accurate manifest often requires handling every ballot and can be the dominant cost of conducting the RLA. With the goal of providing audits with sub-linear efficiency across the full spectrum of election architectures, we propose two new risk-limiting techniques. The first is a statistical mechanism for ensuring that the batch sizes reported by an untrusted tabulation are, in fact, an accurate manifest; this effectively “bootstraps” from a rough manifest to an accurate one with sublinear effort. Secondly, to handle election architectures that do not provide efficient indexing of ballots by identifier (such as is provided by typical voter-facing tabulators), we propose a new class of RLAs called direct ballot selection. This method reverses the traditional comparison procedure and compares uniformly selected ballots against their cast vote records, therefore requiring a new statistical test for identifier duplication. Taken together, these techniques provide a striking reduction in the complexity of RLAs across a wide swath of election configurations and margins. Our two main findings are as follows:

(2) Direct ballot selection provides substantial improvement over state-of-the-art polling for small margins. For Connecticut (29th in population) at a 1% margin, it beats Minerva (USENIX Security 2022)/Providence (USENIX Security 2023) by 55% in ballot sample complexity.

1

Introduction

Large-scale elections are fundamental civic processes that are unusually challenging to analyze from a security perspective. They are complex hybrid systems, combining software, hardware, paper records, and human procedures at scale. Among the most important advances in election security has been the development of risk-limiting audits (RLAs), which provide strong guarantees in a natural security model. RLAs are post-election auditing procedures that provide rigorous statistical guarantees of election outcomes [1–17]: If the reported outcome of an election is incorrect, an RLA establishes a known, pre-specified maximum chance—called the risk limit—that the audit will fail to detect the error. A critical, defining property of RLAs is that they are software independent; in particular, they make no trust assumptions on ballot tabulators or other electronic equipment. This can be achieved by assuming that auditors have access to physical ballots that reflect the intent of the voters. RLAs are typically designed to further guarantee transparency; in other words, a third party observing the audit proceedings can verify the outcome of the audit. RLAs call for auditors to hand count a collection of ran(1) The time to create a manifest can be drastically re- domly selected ballots, with results that are incorporated duced with a modest increase in the number of bal- into an appropriate statistical test. Thus, an important lots sampled in the audit. For California (1st in pop- metric for evaluating the efficiency of an RLA is samulation in the United States) at a 3% margin, there is ple complexity: the total number of ballots that must be a reduction in the overall audit time for comparison, counted by hand in order to guarantee the desired risk 1

limits. This topic has been given extensive attention in supplied manifest or results in a manifest with both the literature and depends on both the audit method and high confidence and high accuracy. We integrate the the margin µ of the contest. (For a conventional tworisk of this statistical manifest test with a convencandidate, first-past-the-post election, the margin is the tional RLA, significantly reducing the total burden difference between the vote totals for the candidates as a of the audit. fraction of the total number of ballots cast.) • Comparison RLAs via Direct Ballot Selection. The prevailing methods have a further requirement: a In circumstances with high-accuracy manifests that ballot manifest. In the typical case where the ballots are do not support in-order identifiers for ballot comparorganized into physical batches, a ballot manifest proison audits, we propose a new RLA method. Procevides a determination of the size of each batch. Sampledurally, these new audits—which we call direct ballot efficient RLA methods are extremely sensitive to ballot selection audits—reverse the conventional doctrine manifest inaccuracies: in particular, multiplicative inacfor ballot comparison audits by randomly selecting a curacies in the declared batch sizes of order 1 ± δ where physical ballot from a selected batch and comparing δ ≈ µ are sufficient to completely invalidate the audit the votes appearing on the ballot against its declared (Lindeman et al., EVT 2012; see Appendix D). As the deCVR, as provided by the tabulator. Direct ballot mand for strict software independence rules out the use of selection audits require the introduction of new staelectronic devices for manifest creation and high accuracy tistical tests to address the possibility of identifier is mandatory, hand counting is the standard for maniduplication, discussed in detail below. For this reafest creation. The time to create a manifest scales linson, direct ballot selection exhibits a rather differearly with the total number of ballots in the election. In ent scaling from that of existing audits. These new circumstances where the underlying statistical tests have audits provide striking efficiency improvements over moderate sample complexity, creating the ballot manifest state-of-the-art polling and batch comparison audits, dominates the time to conduct the audit. which are the only suitable alternatives when identiAn additional challenge arises for ballot comparison fiers are not in order. audits, which provide the best sample efficiency among known audit methods. These audits require a detailed “ballot-by-ballot” tabulation of the election, consisting 1.1 The Risk-Limiting Auditing Landof a comprehensive table of “cast vote record” (CVR) scape entries; an individual CVR declares the votes appearing on a particular ballot. Ballots are sampled by uniformly Traditional RLAs can be roughly organized into three picking a CVR, identifying the individual cast ballot as- methods: sociated with it, and lastly retrieving and interpreting the • Ballot polling audits randomly sample ballots and ballot. While modern tabulators can imprint identifiers test whether their empirical statistics support the
onto ballots as they are cast, voter-facing tabulators— reported winner. Polling requires O log(1/α)/µ2 that is, tabulators that interact directly with voters at the sampled ballots, where α is the risk limit and µ is moment of ballot casting—intentionally randomize ballot the tabulated margin. order to preserve voter privacy [18]. As a result, even in • Batch comparison audits assume that ballots are election architectures that provide authoritative accountorganized into batches, each of which has been sepaing for batch sizes, such ballots must be reprocessed after rately tabulated. The audit selects and hand counts casting to establish an index that can be used to swiftly random batches, comparing these subtotals against locate individual ballots. (If batch sizes are known, a the corresponding tabulator output. This requires costly alternate method is to hand interpret the whole O (B log(1/α)/µ) sampled ballots, where B is the avbatch, called batch comparison; see below.) erage batch size. We propose two new techniques for risk-limiting audits that address these challenges. They improve RLA effi• Ballot comparison audits assume that the tabciency across a wide spectrum of election architectures ulation includes a CVR for each tabulated ballot— and auditing methods. a CVR is a declaration of how a ballot was interpreted by the voting equipment. The audit ran• Statistical Accuracy Testing for Ballot Manidomly selects CVRs and compares them to human fests. Coarse ballot manifests—merely providing acinterpretations of the corresponding ballots. This curacy to within, say, 10%—can be obtained by bulk requires O (log(1/α)/µ) sampled ballots and requires methods with low effort, such as weighing or meaa method to efficiently find a specific ballot within a suring ballots. On the other hand, electronic tabulabatch. tion provides an untrusted, but typically highly accurate, manifest. We provide a statistical test that “bootstraps” the trusted, coarse manifest into a sta- Ballot manifests. An essential component of all these tistically guaranteed, high-accuracy manifest: the procedures is an authoritative ballot manifest—a determimethod either rejects the veracity of a tabulator- nation of the total number of ballots in the election and, 2

are sufficiently close (with error ≈ ∆) to those appearing in the coarse manifest, batches are repeatedly drawn with probability proportional to sizes given by the coarse manifest and then accurately counted (by hand). These totals are compared against the size declared by the tabulation, permitting a small margin ≈ δ of error. Despite the fact that the sampling distribution has low accuracy, we show that if the declared manifest survives sufficiently many iterations of this test, then, except with small failure probability, the true size-proportional distribution has small distance in total variation to the declared distribution. (Looking forward to the formal audit, it will be convenient to slightly adapt both the procedure and the conclusion, but this discussion communicates the basic statistical framework.) We then establish the soundness of polling, comparison, and direct methods when the ideal uniform sampling distribution is replaced by one whose distortion is controlled through this procedure.

in the typical circumstances when ballots are organized into batches, the number of ballots in each batch. As mentioned above, accurate, software-independent manifests are critical for correctness; as a result, establishing a ballot manifest requires handling every ballot in the election. There are certain electoral settings where such exhaustive handling of ballots is unavoidable, such as unpacking mailed envelopes and updating the corresponding voter’s record in the pollbook; however, in settings where voters cast ballots directly into a voter-facing tabulator, manifest creation is an additional step that scales linearly with the overall size of the election. In these cases, manifest creation is a dominant factor in the overall effort. Lindeman et al. [8] point out the necessity of an accurate ballot manifest and demonstrate that small errors (significantly smaller than margin) can be tolerated in conventional RLAs.

1.2

Statistically Approximate Manifests 1.3

We say that a manifest is δ-accurate for a δ > 0 if every batch size is correct to within a multiplicative factor of 1 + δ. Obtaining a “coarse” manifest that is accurate to within, say, 10% can be achieved by efficient bulk methods. For example, weighing ballots—even in storage boxes with known tare weights—can reliably produce such estimates; weighing stacks of ballots themselves can produce even better estimates: for example, standard counting scales can simultaneously accommodate 100 lb. capacity while providing accuracy exceeding 1%. Similarly, counting the number of issued ballots or voters can provide an upper bound on the number of cast ballots. Ballot comparison requires an upper bound on the number of cast ballots to prevent eliding ballots, see Appendix D. Polling requires a lower bound as well. (We remark that comparison audits, however, make other demands on the manifest—a means for locating individual identified ballots.) A typical election setting, then, provides the following:

Direct Ballot Selection

The asymptotic scalings of current RLAs appear to establish ballot comparison audits as the dominant approach, especially since audits must typically be planned and provisioned under a worst-case assumption of small µ (e.g., ≈ 0.5%). However, ballot comparison audits make the strong assumption that auditors can efficiently locate the ballot associated with a specific CVR. Locating a particular ballot is a noted challenge in settings with voter-facing tabulators, which allow voters to cast ballots directly into the tabulation system. This procedure improves both the chain of custody of ballots and the forensic record of the election, as it requires no storage of untabulated ballots. However, such tabulators intentionally randomize ballot order (by dropping them into a large collection bin), which is crucial to protect voter privacy (see, e.g., Crimmins et al. [18]). For this very same reason, rows in the CVR table generated by the tabulator are intentionally exported in random order (rather than the order in which ballots were cast). Thus there is no natural association between the CVRs in the table and resulting physical order of ballots. Many modern tabulators can imprint identifiers on ballots as they are cast, which provides a ready method for associating a particular ballot with a particular CVR entry. We remark that such identifiers must be suitably random to protect voter privacy and maintain RLA transparency. Therefore, as ballots are randomly reordered during casting, the ordering of imprinted identifiers is unrelated to the resulting physical order. These circumstances lead to two natural approaches to locate ballots associated with particular CVR entries:

• An immediate means to obtain “coarse manifests” which establish batch sizes with accuracy ∆ in this 1%-10% range; • A tabulation total, providing an untrusted declaration for batch sizes; this is claimed to have very high accuracy δ ≪ µ. In order to prepare for an RLA, it is necessary to establish a trusted manifest with accuracy δ ≪ µ, the margin of the election. Of course, an audit must support the case when µ < ∆, so the coarse manifest is not directly useful for a general RLA. We observe that it can, however, provide a sampling distribution that bootstraps a rigorous high-accuracy test: in particular, a simple statistical test can use the coarse ∆-accurate manifest to check the veracity of the declared manifest given by the tabulation. Specifically, after ensuring that the tabulated sizes

• Linear search. In settings with imprinted identifiers, linear search can locate a particular ballot. Of course, on average, locating a single ballot requires reading the identifiers of half of the batch. 3

• Transitive tabulation: Ballots can be re-tabulated duplicate identifier detection. Ultimately, the audit calls by a process that preserves order. Physical position for randomly selecting k ballots uniformly at random, and itself can then act as a method for locating ballots. invokes two statistical tests: If the (re-)tabulator can imprint (or read previously • Comparison. Ballots are compared against the corimprinted identifiers), the physical ordering is now responding CVR to establish consistency; consistent with a known ordering of identifiers and can be used to quickly locate ballots according to • Uniqueness testing. Ballots identifiers are coma requested identifier. This approach handles every pared against each other to establish uniqueness (and ballot. appearance) of identifiers. We provide a detailed analysis establishing explicit risklimits for the procedure (as functions of margin and sample complexity). The total sample complexity of the procedure is asymptotically s !   N log(1/α) log(1/α) , +O O µ µ

In these settings, sample complexity is not a comprehensive measure of efficiency, and a full accounting must reflect additional factors such as time to locate ballots, audit preparation, and the availability of appropriate equipment. As a result, jurisdictions with imprinting often use batch comparison and polling audits, which require significantly more ballot interpretations. For example, in the United States, the average precinct size in the 2020 presidential election was 900.1 Auditing a race with a 1% margin and 5% risk limit in Connecticut via batch comparison requires over 500,000 interpretations according to Harrison’s auditing simulation tool—orders of magnitude more than ballot comparison, which requires around 1,200 ballots per McBurnett’s RLACalc. We propose a new approach to ballot comparison audits in settings with voter-facing tabulators and imprinted ballots: direct ballot selection. The approach avoids linear searches through batches or retabulation. Direct ballot selection can be implemented with random ballot selection in the style of a polling audit. The high-level principle reverses the indexing of a standard comparison audit:

As the basic procedure calls simply for drawing a ballot uniformly, this avoids the operational challenges associated with locating a particular, distinguished ballot in a large collection. An immediate concern about this high-level approach is that identifier duplication can undermine risk guarantees. Fuller, Harrison, and Russell showed that duplicated identifiers do not impact risk if one samples CVR rows uniformly [15]. However, if duplicates are common (relative to the margin), it is easy to show that, when sampling ballots, by manipulating CVRs that list identifiers that appear on no ballot—which will never be examined by such an audit—election outcomes can be changed undetectably. Thus, direct ballot selection must introduce additional statistical testing in order to deliver a rigorous risk limit. We establish that if duplicate (or blank) identifiers are sufficiently rare, this “reverse” indexing yields a RLA; motivated by this, we develop a simple statistical test for

where N is the size of the total population of ballots. The two terms here correspond to the two statistical tests (which can be run in parallel with each other, using the same ballot samples). The first term is exactly the asymptotic sample complexity of a conventional comparison audit. The second term—reflecting the sample complexity of ensuring sufficiently few duplicate identifiers— involves the total population size, a factor that does not appear in any of the conventional audit approaches. The √ favorable dependence on N (for uniqueness testing) arises from the classical “birthday paradox,” which asserts that the probability of observing no collisions among k objects sampled with replacement is exp(−θ(k 2 )/N ), scaling quadratically in k. Compared against polling, these asymptotics indicate that direct ballot selection audits perform advantageously for total ballot populations N = O(log(1/α)/µ3 ). While such asymptotic statements are useful for intuition and understanding large-scale behavior, an evaluation suitable for practical RLA demands explicit numerics for concrete parameters. Since polling and direct ballot selection require the same setup and conventions for sampling random ballots from prescribed batches, one can decide which method to use after computing the margin µ for any races to be audited. This is in contrast to ballot comparison, where one needs to place infrastructure ahead of time to find identifiers or distribute transitive tabulators to auditors. Finally, we remark that by externalizing duplicate (collision) detection, the analysis of direct ballot selection can be framed with the familiar notion of “discrepancy.” In particular, it follows that the extension of such audits to more complex electoral contexts—e.g., contests involving multiple races, multiple candidates, or alternative voting rules—follows directly from existing techniques (see, e.g., Stark [6]) that suitably (re-)define discrepancy for these settings.

1 There were 158M cast votes as per Cook Political Vote Tracking, while there were 176K precincts according to the EAC 2020 report.

Summary of Results We focus on 6 sizes, motivated by the electoral landscape in the United States: 456,000

(1) Randomly select a physical ballot (e.g., using k cut [19]), (2) Read its imprinted identifier, (3) Compare against the corresponding CVR.

4

ballots, the average size of a US Congressional district; 1M ballots; and number of in person cast ballots in 2024 in 4 states: Connecticut, Georgia, Florida, and California, which had 1.7M, 5M, 8M, and 16M votes cast in-person. For the Congressional-sized districts, direct ballot selection shows general improvement over the first round of Minerva [14]/Providence [20] polling audits for margins between 0.5%–2.5%, specifically by over 75% for margins between 0.5%–1%. Minerva and Providence have the same sample complexity for the first round and are state-of-the-art ballot polling methods. Sub-1% margins are where the 1/µ2 asymptotic behavior of polling audits drastically increases the sample size. This expensive scaling, despite the relative infrequency of such margins, is what pushes many election officials to prefer ballot or batch comparison over polling. We observe that manifests with accuracy δ < µ suffice for both direct ballot selection and ballot comparison and show that the total time to conduct these audits can be dramatically improved by creating a statistically approximate manifest. In polling and ballot comparison for large states at moderate margins, the manifest is 95 − 99% of the total audit time. For example, using a statistically accurate manifest at a 3% margin reduces the total time to conduct a comparison and polling audit in CA by a factor of 403 and 23 respectively. Gains are more modest for direct ballot selection, as one does not √ eliminate time dependence on N , but rather reduces it to N , achieving a speed-up of 8x. Our techniques can be immediately incorporated into stratified RLAs [7, 10]: For example, at small margins, one can adopt direct ballot selection for ballots with outof-order identifiers and ballot comparison for ballots with in-order identifiers (e.g., cast by mail). For large margins, one can adopt polling.

concepts

modifiers

Notation S W L b, B D µ cvr Manifest α k m ∆ δ act tab cvr S Sample dup β

Description size tabulated winner tabulated loser ballot, set of ballots discrepancy diluted margin Cast vote record table ballot manifest risk limit samples number of batches large inaccuracy bound small inaccuracy bound on ballots in tabulation results in CVR size bounding audit duplicate detection batch index

Table 1: Summary of Notation.

2

Preliminaries

For simplicity, we consider an audit of a single plurality race with two candidates, denoted W and L. By our naming convention, the candidate W is reported to have received more votes in the race. Throughout, we use boldface to refer to “physical” objects, such as individual ballots (typically denoted b) or the set of all ballots (typically B). Variables determined by these physical objects are typically denoted with a super- or subscript (X b ), indicating their dependence on the physical object. We define N = {0, 1, . . .} to be the natural numbers (including zero). For a natural number k, we define [k] = {1, . . . , k} (and [0] = ∅). We let Σ = {−2, −1, 0, 1, 2}, a 1.4 Related Work set that will play a special role in our setting. In general, ∗ Risk-limiting audits were first articulated in 2008 by for a finite set X, we define X to be ∗the set of all finiteStark [21], followed by Stark and Lindeman’s seminal length sequences over X; that is, X = {(x1 , . . . , xk ) | of work [1]. Following this, a body of work laid down k ≥ 0, xi ∈ X}. Note that this includes a sequence N length 0 which we denote ⊥. Finally, we define X to be the foundations, including key assumptions and guarantees [1,4,22,23]. There has been a long line of work on op- the set of all sequences {(x0 , x1 , . . .) | xi ∈ X}. timizing practical efficiency [1, 6, 8, 21, 24, 25]. Significant literature has also developed around various generaliza- 2.1 Election Definitions tions and refinements, including (1) choice functions beyond plurality [11,13], (2) combining p-values from multi- We now set down the definitions of elections, manifests, ple jurisdictions [5–7,9,26], (3) reducing sample complex- and CVRs. We build on the notation and formal modeling ity [7, 8, 10, 12, 21, 24, 27, 28] and (4) addressing practical of [15], though certain aspects are adapted to account for the details of our setting. implementation challenges [4, 15–17, 22, 23, 29]. Definition 1 (Ballot family; ballot conventions). A ballot family is a collection of physical ballots partitioned into disjoint sets denoted B1 , . . . , Bm . As a matter of notation, the ballot family is denoted B = (B1 , . . . , Bm ) and the sets are referred to as “batches.” For the S sake of brevity, we use b ∈ B as shorthand for b ∈ Bβ and P use |B| as shorthand for |Bβ |. Throughout, we reserve

Organization The remainder of this article is organized as follows: Section 2 lays out the modeling and main definitions, Section 3 introduces our auditor and proves it is risk limiting, Section 4 presents our simulation results for ballots examined and time to conduct common RLA methods. 5

the variable m to refer to the number of batches. Physical The tabulated totals refer to the pair Wtab and Ltab ; the ballots, typically denoted b, have the following properties: tabulated size refers to Stab . An election E is a pair E = (B, T ) where B is a ballot family organized into m (1) There is an immutable interpretation of the votes batches and T is a m-tabulation. contained on the ballot: Each b ∈ B determines a We assume throughout the convention that Stab ≥ pair (Wb , Lb ), where each Wb , Lb ∈ {0, 1}. tab W > Ltab ≥ 0, so that the names W and L are re(2) Each ballot b ∈ B is associated with an indelible served for the tabulated winner and loser of the election, identifier idb ∈ {0, 1}∗ . If idb = ⊥ (the empty string respectively. in {0, 1}∗ ), we say that b is unlabeled; otherwise We remark that while we insist on unique identifiers b is labeled. LB ⊂ {0, 1}∗ denotes the set of all across the CVRs in a tabulation, this is merely a conidentifiers appearing on ballots in B. venience. By augmenting the identifiers of a tabulation that does not have this promise (and may have repeated (3) Each ballot b is associated with an indelible batch i identifiers across batches) with an appended batch idenfor 1 ≤ i ≤ m. We let batch(b) denote the batch tifier, a tabulation can be transformed to one with global number, so that b ∈ Bbatch(b) . distinctness; as batch identifiers can be determined from It is convenient to discuss physical ballots with such im- ballots, this presents no difficulties for associating ballots mutable votes (Wb , Lb ) before they are partitioned into with identifiers. batches or assigned labels; we refer to this ungrouped colDefinition 4 (Actual vote totals; ballot manilection as “raw ballots.” fests). Let E = (B, T ) be an election. Let Definition 2 (Cast-Vote Record Table (CVR)). A Castact act act act act (Sact ; W , L ), . . . , (S ; W , L ) denote the actual m m m 1 1 1 Vote Record Table (CVR) is a sequence of triples cvr = = |Bβ | is size and vote totals where, for each β, Sact β ((ι1 , W1 , L1 ), . . . , (ιs , Ws , Ls )) where ιr are distinct bitthe actual size of the set B and β strings in {0, 1}∗ \ {⊥} and each Wr , Lr is an element of X X {0, 1}. We use the following language: Wβact = Wb and Lact Lb β = (1) The elements ιr are identifiers. b∈Bβ b∈Bβ (2) The number s is the size of the CVR.

are the total number of actual votes received by the candidate W and candidate L over the ballots in batch β. As above, we define the aggregate quantities

(3) The rth row is the triple cvrr = (ιr , Wr , Lr ). (4) We use rι to refer to the (unique) row with identifier ι.2 (Recall that CVR identifiers are distinct.)

Sact =

X

Sact β ,

Wact =

X

Wβact ,

and

Lact =

X

Lact β .

β β β Remark In the Introduction, we used CVR as an abbreviation for cast vote record. We now switch to using act act = (Sact 1 , ..., Sm ) are referred to CVR as an abbreviation for the table. The term CVRs The values Manifest as the ballot manifest of E. We occasionally refer to are used to refer to both. tab Manifesttab = (Stab 1 , ..., Sm ) as the declared sizes of the Definition 3 (Tabulation; Election). We define a m- batches. Finally, we define |T | = Stab . tabulation to be a tuple T = (cvr(1) , . . . , cvr(m) ) of CVRs with globally unique identifiers. Thus a tabulation de- Definition 5 (Diluted margin; valid and invalid elecclares the results of a ballot family organized into m tions). The tabulated diluted margin of an election E is batches, with cvr(β) providing a tabulation of those bal- µtab = (Wtab − Ltab )/Stab . An election E is invalid if the lots in batch β. We simply use the word tabulation tabulated winner is incorrect: Lact ≥ Wact ; otherwise, we when m can be inferred from context. Writing cvr(β) = say that E is valid. The actual diluted margin is defined ((ιβ1 , W1β , Lβ1 ), . . . , (ιβsβ , Wsββ , Lβsβ )), such a tabulation im- to be µact = |Wact − Lact |/Sact , which is determined only plicitly determines, for each 1 ≤ β ≤ m the batchwise by the physical ballots. quantities Definition 6 (Discrepancy). Let E = (B, T ) be an elecX β X β Stab Wβtab = Wj , Ltab Lj tion. The discrepancy of E is D = (Wtab − Ltab ) − β = sβ , β = j j (Wact − Lact ) .

and the aggregate quantities X X Stab = Stab Wtab = Wβtab , β , β

β

2 An auditor can use the identifiers ⊥

Ltab =

X

For invalid elections Lact ≥ Wact and thus µact = −(Wact − Lact )/Sact . In this case

Ltab β .

β

D = (Wtab − Ltab ) − (Wact − Lact ) = µtab · Stab + µact · Sact .

i to transform a CVR to

one with unique labels; such labels would not appear on CVRs generated by tabulators. See discussion in Fuller, Harrison, and Russell on CVR transforms [15].

Definition 7 (Ballot Discrepancy). Let (B, T ) be an election, let b ∈ Bβ be a ballot, and let cvr be the CVR in T 6

Definition 9 (Stopping time). Let Σ = {−2, −1, 0, 1, 2}. A stopping time is a function Stop : Σ∗ → {0, 1} so that for any sequence x1 , x2 , . . . of values in Σ there is a finite ( (Wr − Lr ) − (Wb − Lb ) if idb is in cvr row r (ιr =prefix idb ), x1 , . . . , xk for which Stop(x1 , . . . , xk ) = 1. DT (b) = 1 − (Wb − Lb ) if idb does not appear in cvr. For a sequence of random variables X1 , . . . taking val(1) ues in Σ, let τStop (X1 , . . .) be the random variable given by the smallest t for which Stop(X1 , . . . , Xt ) = 1. This A positive value for discrepancy d is called a d-vote naturally determines the random variable X1 , . . . , Xτ , Stop overstatement; likewise, a negative value of −d is a d- the prefix of the Xi given by the first time Stop() = 1. vote understatement. A d-vote overstatement for a ballot b, for example, indicates that the reported difference, Definition 10 (Adaptive Audit Test [15]). An adaptive Wr − Lr , is d votes larger than the ground truth value audit test, denoted T = (Stop, R), is described by two Wb − Lb . Observe that Equation (1) assigns a notion families of functions, Stopσ,α and Rσ,α . For each 0 < of discrepancy to a particular ballot, which always takes α ≤ 1, 0 < σ ≤ 2, a value in the set Σ = {−2, −1, 0, 1, 2}. Note that there may be multiple ballots with the same identifier but yield- (1) Stopσ,α is a stopping time, as in Definition 9, and ing different values of discrepancy. (2) Rσ,α : Σ∗ → {0, 1} is the rejection criterion. for batch β. Then the discrepancy DT (b) of the ballot b (with respect to T ) is defined to be the value

Statistical Tests A standard approach for designing RLAs is to consider the discrepancy DT (b) of a uniformly selected row r from the CVRs in a tabulation T in comparison with some ballot b with the drawn identifier rι . If the election is invalid, one has that E

b matching random row

[DT (b)] =

Let D be a probability distribution on ΣN ; for such a distribution, define ασ,α [D] = E[Rσ,α (X1 , . . . , Xτ )] where X1 , . . . are random variables distributed according to D and τ is determined by Stopσ,α . The test T is α-risklimiting if sup ασ,α [D] ≤ α , (2)

act D tab act S ≥ µ + µ ≥ µtab . Stab Stab

0<σ≤2 σ⊴D

where this supremum is taken over all σ ∈ (0, 2] and over all probability distributions D for which σ ⊴ D.

(One needs to handle labels ι that don’t appear on any ballot [15]; this is straightforward by treating the missing ballot as the worst interpretation for the audit.) Independently carrying out such observations results in a seobs quence of discrepancy observations Dobs 1 , D2 , . . . taking values in {−2, . . . , 2}. An RLA can then be given by a (single-tailed) statistical test for the null hypothesis that E is invalid and hence E[Dobs i ]≥

The Kaplan-Markov test from the “super simple” ballot comparison audit [5,6,26,27] is an adaptive audit test [15, Claim 3] which is used in all of our ballot comparison experiments. Finally, we set down the two notions of distance between probability distributions that will be most convenient for reasoning about the auditor.

D ≥ µtab Stab

Definition 11. Let A be a probability distribution on a finite set X and δ > 0. We say that A is δ-close to uniform if for all x ∈ X,

(which is guaranteed when the election is invalid); the alternate hypothesis is that the election is indeed correct. In this language, the risk of the audit is the probability that the null hypothesis is rejected when it is in fact true. Observe that, in contrast, the quantity Eb←B [DT (b)] arising from the natural “discrepancy of a randomly selected ballot” experiment is not necessarily greater than, say, D/Stab . One goal of the full analysis below is to establish a sufficient connection between these quantities (and hence to µtab ). Ultimately, as mentioned above, we will be able to rely on standard one-sided statistical tests, which we define and discuss below.

1+δ 1 ≤ A(x) ≤ . |X|(1 + δ) |X| Definition 12 (Contaminated reweighting). Let A and B be probability distributions on a finite set X, and let 0 ≤ δ ≤ ∆ and p ∈ [0, 1]. We say that B is a (p, δ, ∆)contaminated reweighting of A if there exist a (weight) function w : X → (0, ∞) and a set Bad ⊆ X such that A(x)w(x) y∈X A(y)w(y)

B(x) = P

Definition 8 (σ-dominating distributions and random 1 ≤ w(x) ≤ 1 + δ variables). A sequence of bounded (real-valued) random 1+δ variables X1 , . . . are said to be σ-dominating if, for each 1 ≤ w(x) ≤ 1 + ∆ t ≥ 1, E[Xt | X1 , . . . , Xt−1 ] ≥ σ . We also use this termi1+∆ nology to apply to the distribution D corresponding to the and A(Bad) ≤ p. random variables, writing σ ⊴ D. 7

for all x ∈ X , for all x ∈ X \ Bad , for all x ∈ X ,

2.2

The Formal Model

Auditor–Adversary the election that are not assumed trustworthy or fixed in advance, the resulting guarantee applies in any practical setting adequately reflected by the model.

We build on the formal auditing model of [15], adapted to our setting to account for random ballot selection and approximate manifests. The model introduces an abstract party—the adversary A—responsible for labeling ballots, grouping them into batches, and producing tabulations (and CVRs). The model does not require the adversary to assign unique identifiers to ballots; moreover, it permits the adversary to form batches after observing the ballots. As a result, the adversary may induce highly irregular allocations of votes across batches. Once the adversary has chosen identifiers and formed batches, these assignments are permanent throughout the audit. Then, a coarse manifest is provided to the Auditor. Concretely, this coarse manifest gives an approximate size

The Auditor–Adversary Game The Auditor, denoted by C, and the Adversary, denoted by A, together interact with a family of ballots reflecting the results of the election to be audited. Figure 1 formalizes the game. An important feature of the game is the mechanism by which the auditor obtains random ballot samples. As discussed above, statistical audits require sampling accuracy commensurate with the margin of the contest under audit. While the model allows the auditor to sample uniformly within any chosen batch, it does not directly allow sampling batches with probability proportional to their true sizes. Instead, the auditor is given a coarse manifest—which may induce a distribution on batches coarse coarse coarse that is substantially nonuniform—together with a mechManifest = (S1 , . . . , Sm ) anism for determining the true size of any batch on request. for the batches: it must satisfy, for every batch β, A straightforward solution would be to determine the # " act S exact sizes of all batches, and thereby recover the correct β , (1 + ∆0 )Sact . (3) size-proportional distribution; ballots could then be samScoarse ∈ β β 1 + ∆0 pled accordingly. The practical obstacle is that obtaining This reflects the practical point emphasized in the intro- the exact size of a batch has cost linear in that batch’s duction: rough batch-size information can often be ef- size. Thus a key challenge is to limit the total size of the ficiently obtained through bulk methods such as weigh- batches whose true counts are requested while still ensuring or stack measurement. Within the constraints given ing that the resulting sampling distribution is sufficiently by (3), the coarse manifest may be chosen adversarially. close to uniform to support the desired risk bound. The quantity ∆0 is determined from a parameter of the Definition 13 (Risk; soundness). For auditor C, elecmodel (∆) by the rule (1 + ∆0 )2 = 1 + ∆; see below. tion E, and adversary A let RLA∆ C,A (E) denote the ranThe model does place one important structural condom variable equal to the conclusion of the audit as destraint on the tabulation (CVRs) produced by the adverscribed in Figure 1. An auditor C has α-risk (or αsary: each identifier only occurs once in the CVRs. This soundness) if, for all invalid elections E and all adverreflects the practical fact that CVRs are available to the saries A, Pr[RLA∆ C,A (E) = Consistent] ≤ α . (The probauditor and can therefore be checked for duplicate identiability here is taken over random choices of the auditor fiers. (Such duplicates can alternatively be handled with and the adversary.) “CVR transformations” that do not increase risk [15].) Beyond this, however, the tabulation produced by the adversary is not assumed to satisfy any accuracy 3 The Direct Ballot Selection Auconditions. Instead, the auditor may compare the ditor batch sizes induced by the tabulation, Manifesttab = tab , . . . , S ), against the coarse manifest. In par(Stab m 1 to operate for ticular, if the auditor verifies that, for every batch β, The direct ballot selection RLA is designed tab any tabulated diluted margin µ := (W − Ltab )/Stab , tab coarse coarse Sβ ∈ [Sβ /(1 + ∆0 ), (1 + ∆0 )Sβ ], then, considerwhich is computed from the tabulation provided to the act ing that Scoarse ∈ [Sact β β /(1 + ∆0 ), (1 + ∆0 )Sβ ], it follows auditor. The auditor is parameterized by the tuple that (δ, ρtv , ρdup , α, αtv , αdup ), where: " # " # Sact Sact β β tab 2 act act (1) δ ∈ [0, ∆] is the sharper multiplicative manifestSβ ∈ , (1 + ∆)Sβ . , (1 + ∆0 ) Sβ = (1 + ∆0 )2 1+∆ accuracy threshold that the auditor seeks to certify for all but a small exceptional set of batches;

Thus a successful comparison against the coarse manifest certifies that the batch sizes arising from T constitute a ∆-accurate manifest. Our final auditing procedure provides guarantees against any adversary satisfying these conditions. Because the adversary represents exactly those aspects of

(2) ρtv ∈ [0, 1] is the fraction of µ reserved to absorb the loss arising from nonuniform ballot sampling caused by residual manifest inaccuracy; (3) ρdup ∈ [0, 1] is the fraction of µ reserved to absorb the loss arising from duplicate or unlabeled identifiers; 8

fact, much more accurate for most of the tabulated mass. In particular, the auditor samples batches according to tab rβtab := Stab and checks whether the tabulated size β /S of each sampled batch is within a multiplicative factor 1+δ of the true size. If enough such checks succeed, then, except with failure probability (αtv ), the set of batches on which the tabulated sizes fail the sharper δ-criterion has small tabulated mass ptv . Combined with the global ∆-accuracy guarantee from CheckManifest, this certifies that the uniform distribution over ballots U is a (ptv , δ, ∆)-contaminated reweighting of the tabulationinduced sampling rule Sample. The auditor next performs duplicate detection. Because the ballot-sampling rule used here is not exactly uniform, the duplicate-detection routine is calibrated using the full triple (ptv , δ, ∆) describing the distributional distortion. It then guarantees that except with small failure probability αdup , the excess identifier multiplicity rate κ is no more than κdup . (The additional convention that any sampled unlabeled ballot causes the “Collision” outcome is conservative and affects completeness only.) If either preliminary stage fails, the audit returns Inconclusive. Otherwise, the remaining risk budget αSample := α − αdup − αtv is allocated to the adaptive audit test, which is run at effective margin µSample := (1 − ρtv − ρdup )µ. The conclusion of the procedure is either Consistent or Inconclusive. The formal description appears in Figures 2 and 3. To see the necessity of the DetectDuplicates step, consider an extreme example in which each vote pattern that appears on a ballot is assigned a separate identifier, along with a single CVR row. All ballots with the same vote pattern are assigned the same identifier. Then, the rest of the CVR is arbitrarily populated by the adversary with identifiers and vote patterns of their choosing. Obviously, the CVR can be made consistent with nearly any tabulation. The final risk-limit guarantees arise from controlling three distinct losses:

Auditor (C)–Adversary (A) game for the raw ballots B. (1) Formation of a Full Ballot Collection. The adversary A may inspect the raw physical ballots B and determines the following: (a) Batches. A partition of the ballots into m batches, for a parameter m determined by A. (b) Labels. A label assignment for each ballot. (The adversary may choose to leave some ballots unlabeled, that is, assign the label ⊥.) (2) Coarse Manifest. A generates a coarse manifest Manifestcoarse = (Scoarse , . . . , Scoarse ) for m 1 which   act Scoarse ∈ Sact β β /(1 + ∆0 ), (1 + ∆0 )Sβ (where ∆0 satisfies (1 + ∆0 )2 = 1 + ∆). Manifestcoarse is provided to C. (3) Tabulation. A generates a tabulation T = (cvr(1) , . . . , cvr(m) ). T is provided to C. (4) The Audit. (a) Count Batch. C repeatedly requests a batch β (1 ≤ β ≤ m) and is provided with Sact β = |Bβ |. (b) Sample Ballot. C repeatedly requests ballots to be drawn uniformly from selected batches: specifically, C issues a batch number β and is provided with a ballot b sampled uniformly from Bβ (with replacement). (5) Conclusion. C returns one of the two values: Consistent or Inconclusive.

Figure 1: The RLA∆ C,A (B) auditing game with param ∆.

(1) Residual manifest distortion. After CheckManifest and BoundSize, the auditor has certified that the uniform ballot law U is a (ptv , δ, ∆)-contaminated reweighting of the tabulation-induced ballot distribution Sample. Theorem 7 of Appendix H converts this certificate into the quantitative sampling-error bound used in the discrepancy analysis.

(4) α is the overall risk limit; (5) αdup is the portion of the risk budget allocated to duplicate detection; and (6) αtv is the portion of the risk budget allocated to manifest certification. We assume throughout that 0 ≤ δ ≤ ∆, ρtv + ρdup < 1, and αdup + αtv < α.

(2) Duplicate identifiers. DetectDuplicates is parameterized by the same certificate (ptv , δ, ∆). Except with probability at most αdup , the loss caused by repeated or missing identifiers is at most the budgeted quantity ρdup µ. (Unlabeled sampled ballots are treated conservatively by immediate failure of DetectDuplicates; this can only reduce the chance of acceptance and therefore does not contribute to risk.)

Structure of Auditor The auditor uses the coarse manifest only to certify a global ∆-accuracy bound on the tabulated batch sizes. Once this check succeeds, all statistical sampling in the manifest-certification step is carried out using the tabulated batches sizes; the auditor statistically verifies that the tabulated batch sizes are, in 9

Auditor C[(Stop, R)](δ, ρtv , ρdup , α, αtv , αdup ) for E

Auditor C[(Stop, R)](δ, ρtv , ρdup , α, αtv , αdup ) routines CheckManifest(Manifestcoarse , Manifesttab ):

(1) Receive the coarse manifest Manifestcoarse = (Scoarse , . . . , Scoarse ) and tabulation T = m 1 (1) (cvr , . . . , cvr(m) ). tab (2) Let Manifesttab := (Stab 1 , . . . , Sm ) be the batch sizes induced by T , and let Wtab , Ltab , Stab denote the corresponding tabulated totals. Define µ := (Wtab − Ltab )/Stab . (3) Run CheckManifest(Manifestcoarse , Manifesttab ). If it returns Error, return Inconclusive. (4) Define αSample := α − αdup − αtv , µSample := (1 − ρtv − ρdup )µ, and κdup := ρdup µ/2. (5) Compute (ptv , ktv ) ← Ψ(µ, ρtv , αtv , ∆, δ). If ptv ≤ 0, return Inconclusive. Define ϵ = (ptv ∆ + (1 − ptv )δ). (6) Run BoundSize(Manifesttab , ktv , δ). If it returns Error, return Inconclusive. (7) Let Sample be the ballot-sampling rule obtained by:

(1) If there is a batch β ∈ [m] for which  coarse  Sβ coarse Stab ∈ ̸ , (1 + ∆ )S , 0 β β 1 + ∆0 then output Error; otherwise output NoError. BoundSize(Manifesttab , ktv , δ): (1) For i = 1 to ktv : (a) Sample a batch j according to the tabutab lated batch law Pr[j = β] = Stab . β /S (b) Invoke Count Batch on batch j and obtain its true size Sact j . tab (c) If Sact ∈ ̸ [S /(1 + δ), (1 + δ)Stab j j j ], output Error. (2) Output NoError.

(a) sampling batch j with probability tab Stab , and j /S (b) sampling a ballot uniformly from batch j.

DetectDuplicates(Sample, ptv , δ, ∆, κdup , αdup , N ): (1) Compute ηdup ← ηdup (ptv , δ, ∆), kdup ← Φ(ηdup , κdup , αdup , N ). (2) Draw kdup ballots using the ballot-sampling rule Sample, forming a collection C. (We treat these as drawn without replacement by resampling if necessary.) (3) Note the identifiers appearing on the ballots in C. (4) If any two ballots in C have the same identifier, or if any of the ballots are unlabeled, return Collision; otherwise return NoCollision.

(8) Run DetectDuplicates(Sample, ptv , δ, ∆, κdup , αdup , (1 + ϵ)Stab ). If it returns Collision, return Inconclusive. (9) Initialize iter = 0. Repeat: (a) Increment iter := iter + 1. (b) Diter := BasicExperiment(Sample, T ). until StopµSample ,αSample (D1 , . . . , Diter ) = 1. (10) If RµSample ,αSample (D1 , . . . , Diter ) = 1, return Consistent; otherwise return Inconclusive.

BasicExperiment(Sample, T ): (1) Use Sample to select a batch β, and invoke Sample Ballot on β to obtain a ballot b ∈ Bβ uniformly at random. (2) Let ι be the identifier appearing on b. := 0. Other(3) If ι ∈ / T or ι = ⊥, set Wιcvr := 1, Lcvr ι wise let r be the unique row of T with identifier ι, and set Wιcvr := Wr , Lcvr := Lr . ι (4) Let Wact , Lact ∈ {0, 1} denote the votes on b for the reported winner and loser, respectively. act (5) Return (Wιcvr − Lcvr − Lact ). ι ) − (W

Figure 2: The auditor C[(Stop, R)], parameterized by the sharp manifest threshold δ, margin fractions ρtv , ρdup , and risk allocations αtv , αdup . (3) Comparison risk. The final adaptive audit test is then run at the reduced margin µSample = (1 − ρtv − ρdup )µ with the remaining risk budget αSample .

3.1

Overview of Auditor Analysis

We now analyze a single execution of BasicExperiment(Sample, T ) from Figure 3. Fix Figure 3: Auditor C[(Stop, R)] subroutines. an election E = (B, T ), where T is the tabulation tab tab tab provided to the auditor, and let µ := (W − L )/S denote its tabulated diluted margin. Recall Def. 7, that for a ballot b ∈ B, its signed ballot BasicExperiment(Sample, T ) is determined by drawing a ballot b ∼ Sample according to the sampling rule prodiscrepancy with respect to T is defined by duced by BoundSize; the value returned by is DT (b) ∈ ( (Wr − Lr ) − (Wb − Lb ), if idb appears in T at r, Σ = {−2, −1, 0, 1, 2}. DT (b) := 1 − (Wb − Lb ), if idb does not appear in T .To articulate the guarantees of the auditor, we set down 10

some notation. Let κ :=

Combining Equation (7) with Equation (8), we conclude that whenever both preliminary checks are sound and the audit reaches the comparison stage,

(|B| − |LB |) 1 X (|{b ∈ B | idb = ι}| − 1) = |B| |B| ι∈LB

E [DT (b)] ≥ (1 − ρtv )µ − ρdup µ = (1 − ρtv − ρdup )µ.

denote the excess identifier multiplicity rate: after retaining at most one ballot for each identifier value, a κfraction of ballots remain unpaired. Let    act Bad := i ∈ [m] : Stab ∈ / Sact i i /(1 + δ), (1 + δ)Si denote the set of δ-inaccurate batches, and let X tab p := Stab i /S i∈Bad

denote their total tabulated ballot mass. Finally, define ε(p) := (1 − p)δ + p∆, −1  p 1−p + − 1, τ (p) := 1+δ 1+∆ and δ (1 + δ)p∆ Γtv (p) := + . 2+δ 1 + δp

Sample

Recalling the notation from Figure 2, µSample := (1 − ρtv − ρdup )µ, so the observations returned by BasicExperiment are µSample -dominating. We summarize this as follows. Theorem 2. Fix an invalid election E = (B, T ). Suppose that the manifest-certification step and duplicatedetection step are both sound and that the auditor proceeds to the comparison stage. Then each execution of BasicExperiment(Sample, T ) returns a random variable DDuplicate ∈ Σ satisfying

(4)

E[DDuplicate | previous executions] ≥ µSample ,

(5) where µSample = (1 − ρtv − ρdup )µ. Consequently, the resulting sequence of observations is µSample -dominating. Corollary 1. Let αSample := α − αdup − αtv . If (Stop, R) is an αSample -risk-limiting adaptive audit test, then the (6) auditor C[(Stop, R)](δ, ρtv , ρdup , α, αtv , αdup )

The informal theorem below summarizes Theorem 7 from Appendix H.

has risk at most α. Theorem 1 (Informal Main Theorem). If the uniform distribution on ballots is a (p, δ, ∆)-contaminated Proof. By Theorem 2, conditioned on the event that reweighting of the ballot law induced by the tabulation the two preliminary checks are sound and the auditor reaches the comparison stage, the sequence of outputs then, for any invalid election, from BasicExperiment is µSample -dominating. Therefore,   µ the final adaptive audit test returns Consistent with E [DT (b)] ≥ min , µ(1 + τ (p)) − τ (p) −2κ−4Γtv (p). Sample 1 + ε(p) probability at most αSample . (7) The manifest-certification step can fail to detect a bad manifest with probability at most αtv , and the duplicateThe two preliminary routines in the auditor are caldetection step can fail to detect an excess of duplicate ibrated precisely so that the right-hand side of Equaidentifiers with probability at most αdup . A union bound tion (7) is at least the effective margin used by the final therefore gives total risk at most αSample + αdup + αtv = adaptive audit test. α. (1) The duplicate-detection routine is parameterized by κdup := ρdup µ/2. Except with probability at most 3.2 Duplicate Detection – Φ αdup , either the test DetectDuplicates returns The duplicate-detection step is parameterized by the Collision or else κ < κdup . Thus, on the event that risk allocation αdup and by a duplicate budget κdup := duplicate detection is sound and the audit continues, ρdup µ/2, where µ is the diluted margin of the tabulation. 2κ ≤ 2κdup = ρdup µ. The role of κdup is discussed above (and treated formally (2) The manifest-certification routine is parameterized in the proof of Theorem 7): if the fraction of ballots carby µ, ∆, δ, ρtv and αtv , and ensures that except with rying repeated identifiers is at most κdup , then the loss in probability at most αtv , either BoundSize returns the discrepancy lower bound arising from duplicate idenError or else the accepted manifest satisfies tifiers is at most 2κdup = ρdup µ. The manifest-certification step supplies a certificate   µ (p , δ, ∆) with the property that the uniform ballot tv min , µ(1 + τ (ptv )) − τ (ptv ) − 4Γtv (ptv ) 1 + ε(ptv ) law U is a (ptv , δ, ∆)-contaminated reweighting of the ≥ (1 − ρtv )µ. tabulation-induced sampling law Sample. For simplicity, (8) we present a duplicate detector that uses this certificate 11

through a conservative reduction that just depends on Thus Ek is the event that no duplicate value f (X) is detected among the k draws. Then, for k ≤ n(1 + c), closeness in the sense of Def. 11. Let ε(p) := (1 − p)δ + p∆ (as in Eq (4)). By Lemma 3   2 ! −k from Appendix G, if U is a (p, δ, ∆)-contaminated (10) Pr[Ek ] ≤ 2 exp −ℓ 1 − exp reweighting of Sample, then Sample is ηdup -close to unin(1 + c)   form, where k2 ℓ . (11) ≤ 2 exp − 2 4n (1 + c)2 ηdup = ηdup (p, δ, ∆) := (1 + ∆)(1 + ε(p)) − 1. (9) The proof of Lemma 1 is deferred to Appendix F. In the Applying this with p = ptv , we obtain that Sample is ηdup (ptv , δ, ∆)-close to uniform. Accordingly, the proce- setting given by the auditor, we take A = B and define f (b) := idb , restricted to the event that all sampled baldure lots are labeled. If some sampled ballot is unlabeled, then DetectDuplicates(Sample, ptv , δ, ∆, κdup , αdup , N ) DetectDuplicates immediately returns Collision, so no further analysis is needed. Otherwise, ℓ = |B| − |LB |, takes as input the ballot-sampling rule Sample, the manand the event ∀i ̸= j, f (Xi ) ̸= f (Xj ) is exactly the event ifest certificate (ptv , δ, ∆), the duplicate budget κdup , a that no duplicate identifier is observed in the sample. Acrisk allocation αdup , and an upper bound N ≥ |B| on the cordingly, total number of ballots (which will arise from the statistiΦ(ηdup , κdup , αdup , N ) cal manifest; see (12) below). It first computes ηdup from may be defined as the smallest integer value k for which Equation (9), and then draws the right-hand side of Equation (11) is at most αdup for kdup := Φ(ηdup , κdup , αdup , N ) n = N and ℓ = κdup N . Invoking the weaker bound of (11), k can be taken to be ballots without replacement according to Sample, records s r their identifiers, and returns Collision if either ln(2/αdup ) N ln(2/αdup ) = 2(1 + ηdup ) 2N (1 + ηdup ) (1) some sampled ballot is unlabeled, i.e., has identifier ℓ κdup ⊥, or (2) some pair of sampled ballots have the same identifier. (with the understanding that this cannot exceed N ). When generating the concrete bounds, we use the slightly Otherwise it returns NoCollision. stronger bound given by (10). Thus if the excess identifier multiplicity rate satisfies κ ≥ κdup , the procedure returns Collision with proba- Refinements. We emphasize that duplicate detection bility at least 1−αdup . The additional rule that unlabeled can, in principle, exploit the full certificate (ptv , δ, ∆) ballots also cause immediate failure is conservative: it which mandates that most of the distribution has tighter can only decrease the probability that the audit returns (δ) multiplicative guarantees. For simplicity, the develConsistent, so it affects completeness but not sound- opment here depends only on ηdup . ness. (Ballots that aren’t run through a tabulator are organized in hand counted batches with a manual cvr.) 3.3 Manifest Accuracy – Ψ We calibrate Φ using the following bound. The purpose of BoundSize is to certify that the ballotLemma 1 (Simple duplicate detection under sequential sampling rule induced by the tabulated batch sizes is sufsampling). Let A be a finite set with |A| = n, let f : A → ficiently accurate for the final ballot-discrepancy test. (As B be a function with |B| = n−ℓ, and let Π be a probability noted above, the accuracy also affects the number of samdistribution on A such that ples drawn for duplicate detection.) The certificate we 1+c 1 want is stated in terms of the two batch probability laws ≤ Π(x) ≤ for all x ∈ A, n(1 + c) n that matter downstream: for some c ≥ 0. Let X1 , . . . , Xk be sampled without replacement according to the sequential law X1 ∼ Π, and for t ≥ 1, Pr(Xt+1 = x | X1 , . . . , Xt ) =

1−

Π(x) Pt j=1 Π(Xj )

for every x ∈ / {X1 , . . . , Xt }. Define the no-collision event n o Ek := ∀i ̸= j ≤ k, f (Xi ) ̸= f (Xj ) .

rβact :=

Sact β , Sact

rβtab :=

Stab β . Stab

Here ract is the true size-proportional batch probability law and rtab is the tabulation-induced batch probability law. (The coarse manifest is used only in CheckManifest to certify the global ∆-accuracy condition.) Define the set of bad batches #) ( " Sact β tab act Bad := β ∈ [m] : Sβ ∈ / , (1 + δ)Sβ , 1+δ 12

In summary, except with probability at most αtv , acceptance of BoundSize implies that the bad set has tabulated mass at most ptv = p⋆tv and that the true batch law ract is a (p⋆ , δ, ∆)-contaminated reweighting of the tabulated batch law rtab , as desired.

and define their total tabulated ballot mass by p :=

X β∈Bad

rβtab =

X Stab β β∈Bad

Stab

.

Because BoundSize samples batches directly from the tabulated batch probability law rtab , a sampled batch lands in the bad set Bad with probability exactly p. Therefore, for a particular target threshold p⋆ , the probability that BoundSize accepts after k independent samples when p ≥ p⋆ is at most

Completeness The above test returns Inconclusive if it encounters a single batch with size distortion beyond δ. We focused on the strict test as the number of ballots examined for the manifest is ktv multiplied by the average size of the sampled batch. If a small batch of size 100 is sampled, our setting of δ demands that the actual size is (1 − p⋆ )k ≤ exp(−kp⋆ ). the same as the tabulated size. Other statistical methods (e.g., Wald’s SPRT) can soften the strict demand that When p ≤ p⋆ , it is immediate that the true batch proba- the tabulated manifest is δ-accurate on each batch. bility law ract is a (p⋆ , δ, ∆)-contaminated reweighting of Appendix C discusses how to analyze polling and the tabulated batch probability law rtab . The remaining comparison audits using the concept of contaminated question is what p⋆ should be selected in order to estab- reweighting (Def. 12). lish the distributional guarantees necessary for auditor’s later invocations of Sample. Efficiency Improvements Over It is shown in Theorem 6 of Appendix H that if the bad 4 set has tabulated mass at most p then

Existing Methods

Sact 1 ≤ tab ≤ 1 + ε(p) 1 + τ (p) S

(12) Our efficiency numbers focus on evaluating two primary questions:

and

(1) Does direct ballot selection avoid the high cost of ballot polling—both Minerva and Providence methods—for small margins?

dTV (ract , rtab ) ≤ Γtv (p) ,

where dTV (·, ·) denotes the distance in total variation (see Def. 14 of Appendix G). Consequently, the retained mar- (2) Does the use of a statistically accurate manifest yield gin in the final ballot-discrepancy lower bound is conmeaningful savings in the time to conduct a direct trolled by the functions ε(p), τ (p), and Γtv (p) defined ballot selection, ballot comparison, and ballot polling above in equations (4), (5), and (6). audit?3 For a fixed tabulated diluted margin µ define the reFor all methods, we assume the goal is a 90% probability tained margin under manifest error p by of completion in a single round.   µ We build on the election simulation of Fuller, Harrison, Lµ (p) := min , µ(1 + τ (p)) − τ (p) − 4Γtv (p). and Russell [15], which supports ballot polling and com1 + ε(p) parison. As input, it takes in specified margins (µ), risks As each of ε(p), τ (p), and Γtv (p) is nondecreasing in p, (α), discrepancy rates (o1, u1, o2, u2), and the ballot popthe function Lµ (p) is nonincreasing. ulation (S). We use this tool to store the 90th percentile Thus, the manifest-certification routine should ensure of a Kaplan-Markov super-simple ballot comparison authat the total tabulated mass of the bad set does not ex- dit across 1, 000 simulations. To calculate Minerva sample ceed the largest amount consistent with the retained mar- sizes, we use the approximation of sample size found in gin remaining above the budget allocated for the manifest Arlo [31]: step. Define  !2  p 1 p(1 − p) − z z · 2 b ,  a p⋆tv := sup {p ∈ [0, 1] : Lµ (p) ≥ (1 − ρtv )µ} .   p − 12  

If p⋆tv = 0, then the manifest step cannot certify enough accuracy at the chosen budget split and the auditor should return Inconclusive. It follows that if ktv := ⌈ln(1/αtv )/p⋆tv ⌉ , then, except with probability at most αtv , acceptance of BoundSize implies p ≤ p⋆tv . Accordingly, we define    ln(1/αtv ) ⋆ . Ψ(µ, ρtv , αtv , ∆, δ) := ptv , p⋆tv

3 We do not take into account batch comparison audits in our analysis, because they require too many ballots. For example, for the 2024 General Election, Georgia conducted a (MACRO) batch comparison audit of the presidential race, which had a 2.2% margin, and audited a total of 5,297,262 ballots [30]. At our presumed 25 seconds per ballot, this would take a total of 36,787 hours before we factor in manifest creation. We adopt the stance that batch comparison is most effective for small ballot populations in which you are likely to pivot to a full hand recount, as you have already completed a majority of the work to hand recount.

13

(1) The maximum of {kdup , kSample },

200 Sample Size k

where p = (1 + µ)/2, za is the value of the normal distribution with parameters (0, 1) where the CMF is 0.90, and zb is where the CMF is µ ∗ 0.90. The simulation parameters for one-vote under and overstatements are 0.1% and two-vote under and overstatement rates are 0.01%, standard in the literature. Our ballot populations are 456K, 1M, and the number of ballots cast on Election Day in the 2024 General Election for Connecticut (1.7M), Georgia (5.0M), Florida (8.0M), and California (16.1M). Generating results for direct ballot selection requires splitting µ and α between the duplicate detection and Kaplan-Markov test. Additionally, when considering a statistically accurate manifest, we have to split µ and α into three components: bounding size (ρtv , αtv ), duplicate detection (ρdup , αdup ), and finally, bounding (µSample , αSample ). We only compute sample sizes for Kaplan-Markov for a set of αSample , µSample , so in some cases we overestimate the number of ballots needed to audit. For each S, µ, and α combination, we consider three possible optimizations when dividing risk and margin:

(3) The time to conduct a ten-race audit of plurality races. We report on the best solution according to the above metrics with different allocations of µ and α. We assign different constant fractions to ρtv , αtv /α, ρdup , αdup /α and keep the best solution in terms of the above objective. Let kS := ktv BSample . We set limits of kS ≤ 3S/4 and kdup ≤ min{106 , S}. Times adopted are as follows: (1) 35 seconds to pull a ballot (median time using the scale method [32]), (2) 10 seconds to check for duplicated identifiers, and (3) 25 seconds to interpret one race. We make a few assumptions when it comes to the practical time to create an accurate ballot manifest. We imagine a setting where auditors need to set up stacks of ballots for efficient manifest creation. Ballots are often transported in ballot bags; while many of these ballots remain stacked neatly and can be pulled out in one large stack, some get scattered throughout the bag and will need to be picked up individually. We assume 90% of the ballots remain stacked and 10% of the ballots become scattered within the bag. We assume an auditor can remove a stack of 50 ballots within 60 seconds, and it takes 6 seconds to retrieve a scattered ballot and add it to the stack. Saputra et al. [33] report 1.43 seconds to manually count a sheet of A4 paper. Using our assumptions and 1.43 seconds per ballot, we arrive at 1,538 ballots/hr for setup and accurate manifest creation time. This is faster

150 100 50 0

0.5

1

1.5

2

Margin (%) Figure 4: Direct ballot selection max{kdup , kSample } samples compared to Minerva. than Connecticut’s pilot time of 895-1,469 ballots/hr [34] but significantly slower than Rhode Island’s pilot time of 4,800 ballots/hour [32], which was not software independent. We assume the average size BSample of selected batches is 900, the average precinct size in 2024 election.

4.1

(2) The time to conduct a one-race audit of a plurality race, and

CA FL GA CT 1M Cong. Minerva

Results

Direct Ballot Selection and Polling We present three items that compare direct ballot selection to ballot polling with an accurate manifest. Figure 4 shows the number of sampled ballots for Minerva and direct ballot selection for different sizes. In the Appendix, Table 2 shows the ballots sampled per batch across different methods and Table 3 contains the total sample sizes. All three items report on optimizing the tradeoff between kdup , kSample by minimizing the total number of sampled ballots. We stress that polling is particularly problematic for small elections and small margins. According to Table 2 (in the Appendix), at a .5% margin, a Congressional election conducting a Minerva audit will need to pull 700 ballots on average per batch (recall that the average batch size is 900). Direct ballot selection reduces the number of ballots per batch to 64; roughly 7% of the ballots. At larger sizes, the improvements are not as drastic but still significant. At a .5% margin, direct ballot selection reduces the ballots sampled by a factor of 3 in Florida and a factor of 2 in California. At a 1% margin in Connecticut (29th ranking in population), it reduces the ballots pulled by 55%. The main drawback of polling is its poor performance at small margins, which is drastically improved for sizes of practical interest. Of course, audit software can still choose to revert to polling audits for large margins without the need for additional setup or equipment. Making manifests accurate without a full hand count. We now discuss how one can build an accurate enough manifest for direct ballot selection and ballot comparison without a full hand count of the ballots. Creating

14

Improvements for direct ballot selection with an inaccurate over accurate manifest are more modest. These can be seen in Figure 5b and Table 4. Note that for large states, there is still an improvement by a factor of 4 for margins < 5%. This allows all aspects of the audit to scale with the margin, rather than manifest creation dominating the time to conduct an audit (regardless of margin). For example, at a 2% margin, Georgia can decrease their audit time from 4,000 hours to 1,200 hours by hand counting kS = 387K ballots (instead of 5M) for their manifest. This causes kdup to increase from roughly 48K to 73K and kSample to increase from roughly 6K to 11K as part of the direct ballot selection audit. For direct ballot selection, we see the method resort to a full manifest at < .5% margin for almost all population sizes. We see a full manifest created at < 1% margin for ballot polling for population sizes less than 2M. Ballot comparison, which is very efficient regarding ballots examined, still retains an 42x reduction in time for California at a .5% margin. Statistically accurate manifests accomplish the goal that all aspects of the audit scale with µ.

Ratio

102 CA FL GA CT

101 2

4

6

8

10

Margin % (a) Ballot comparison (log scale). Details in Table 5.

15 Ratio

For ballot comparison, an accurate manifest can be made by examining very few ballots. Figure 5a shows the time savings and accounting of the number of selected ballots is in the Appendix in Table 5. At a 3% margin, California can count kS ≈ 21K ballots instead of the full manifest of 16M. As a result, the number of ballots to audit increases from 252 to 744, making the overall audit take 26 hours. For Connecticut at a 1% margin, kS ≈ 83K ballots (instead of 1.7M), which results in a sample that increases from 924 to 2454 and an audit that takes 95 hours. Polling behaves similarly but with less graceful degradation with margin.

103

10

CA FL GA CT

5 0 2

4

6

8

10

Margin % (b) Direct ballot selection. Details in Table 4.

102 Ratio

an accurate manifest dominates the time of every audit method, especially for larger states. For California, the manifest requires over 10,000 hours to prepare. Even for smaller states like Connecticut, the manifest is roughly 1,000 hrs of work. Meanwhile, the time difference for ballot sampling and analysis between a 3% and 0.5% margin is only 36 hours.

101

CA FL GA CT

100 2

4

6

8

10

Margin % (c) Minerva polling (log scale)

Comparison to Lindeman et al. [8] In addition, we run Lindeman et al’s technique for supporting statistically accurate manifests. The technique treats each CVR as having S(1 + ∆) entries and records a discrepancy of 2 whenever one of the S∆-added rows is selected. Across our experiments, this technique converges when ∆ < µ/5. One can use our BoundSize technique to produce tighter estimates for the statistical size bounds. Lindeman et al’s technique does not naturally extend to polling or direct ballot selection. In addition, we find that for comparison removing rows with discrepancy 1 and subtracting them from the margin produces better results, see Appendix C. 15

Figure 5: Ratio of time to conduct audit with full manifest versus statistical manifest across audit methods.

Acknowlegments The work of all authors was supported through grants by the Connecticut Secretary of State’s Office and the Department of Homeland Security. In addition, the work of B.F. was supported by NSF Grants #2141033 and #2232813.

References [1] Mark Lindeman and Philip B Stark. A gentle introduction to risk-limiting audits. IEEE Security & Privacy, 10(5):42–49, 2012.

[14] Filip Zagórski, Grant McClearn, Sarah Morin, Neal McBurnett, and Poorvi L Vora. Minerva–an efficient risk-limiting ballot polling audit. In USENIX Security Symposium, pages 3059–3076. USENIX Association, 2021.

[2] Jennifer Morrell. Knowing it’s right, part two. risklimiting audit implementation workbook., 2019.

[15] Benjamin Fuller, Abigail Harrison, and Alexander Russell. Adaptive risk-limiting comparison audits. In IEEE Symposium on Security and Privacy, pages [3] Jennie Bretschneider, Sean Flaherty, Susannah 2002–2019, Los Alamitos, CA, USA, may 2023. Goodman, Mark Halvorson, Roger Johnston, Mark Lindeman, Ronald L. Rivest, Pam Smith, and [16] Douglas W Jones, Sunoo Park, Ronald L Rivest, Phillip B. Stark. Risk-limiting post-election audits: and Adam Sealfon. Scan, shuffle, rescan: MachineWhy and how, 2012. assisted election audits with untrusted scanners. In Financial Cryptography, 2024.

[4] Matthew Bernhard. Risk-limiting audits: A practical systematization of knowledge. In International Joint Conference on Electronic Voting, 2021.

[17] Benjamin Fuller, Rashmi Pai, and Alexander Russell. The decisive power of indecision: Low-variance risk-limiting audits and election contestation via [5] Philip B Stark. Auditing a collection of races simulmarginal mark recording. In USENIX Security, 2024. taneously. arXiv preprint arXiv:0905.1422, 2009. [18] Braden L Crimmins, Dhanya Y Narayanan, Drew Springall, and J Alex Halderman. {DVSorder}: Ballot randomization flaws threaten voter privacy. In [7] Michael J Higgins, Ronald L Rivest, and Philip B 33rd USENIX Security Symposium (USENIX SecuStark. Sharper p–values for stratified election audits. rity 24), pages 6525–6541, 2024. Statistics, Politics, and Policy, 2(1), 2011. [19] Mayuri Sridhar and Ronald L Rivest. k-cut: A sim[8] Mark Lindeman, Philip B Stark, and Vincent S ple approximately-uniform method for sampling balYates. Bravo: Ballot-polling risk-limiting audits to lots in post-election audits. In International Conferverify outcomes. In EVT/WOTE, 2012. ence on Financial Cryptography and Data Security, pages 242–256. Springer, 2020. [9] Kellie Ottoboni, Philip B Stark, Mark Lindeman, and Neal McBurnett. Risk-limiting audits by stratified union-intersection tests of elections (SUITE). In [20] Oliver Broadrick, Poorvi Vora, and Filip Zagórski. Providence: a flexible round-by-round risk-limiting International Joint Conference on Electronic Voting, audit. In 32nd USENIX Security Symposium pages 174–188. Springer, 2018. (USENIX Security 23), pages 6753–6770, 2023. [10] Kellie Ottoboni, Matthew Bernhard, J Alex HalderConservative statistical postman, Ronald L Rivest, and Philip B Stark. Bernoulli [21] Philip B. Stark. election audits. The Annals of Applied Statistics, ballot polling: a manifest improvement for risk2(2):550 – 581, 2008. limiting audits. In International Conference on Financial Cryptography and Data Security, pages 226– [22] Lynn Garland, Neal McBurnett, Jennier Morrell, 241, 2019. Marian K. Schneider, and Stephanie Singer. Prin[6] Philip B Stark. Super-simple simultaneous singleballot risk-limiting audits. In EVT/WOTE, 2010.

ciples and best practices for post-election tabulation [11] Philip B Stark. Sets of half-average nulls generate audits, 2018. risk-limiting audits: Shangrla. In Financial Cryptography and Data Security, pages 319–336. Springer, [23] Joseph Lorenzo Hall, Luke W Miratrix, Philip B 2020. Stark, Melvin Briones, Elaine Ginnold, Freddie Oakley, Martin Peaden, Gail Pellerin, Tom Stanionis, [12] Ian Waudby-Smith, Philip B Stark, and Aaditya and Tricia Webber. Implementing risk-limiting postRamdas. Rilacs: Risk limiting audits via confielection audits in California. In EVN/WOTE, Mondence sequences. In International Joint Conference treal, Canada, 2009. on Electronic Voting, pages 124–139. Springer, 2021. [13] Michelle Blom, Jurlind Budurushi, Ronald L Rivest, [24] Stephen Checkoway, Anand Sarwate, and Hovav Philip B Stark, Peter J Stuckey, Vanessa Teague, Shacham. Single-ballot risk-limiting audits usand Damjan Vukcevic. Assertion-based approaches ing convex optimization. In Proceedings of the to auditing complex elections, with application to 2010 International Conference on Electronic Voting party-list proportional elections. In International Technology/Workshop on Trustworthy El ections, Joint Conference on Electronic Voting, pages 47–62. EVT/WOTE’10, pages 1–13, USA, 2010. USENIX Springer, 2021. Association. 16

[25] Philip B. Stark. Cast: Canvass audits by sam- on the necessity of accurate ballot manifests in currently pling and testing. IEEE Transactions on Informa- used risk-limiting audits. Vendors (and previous literation Forensics and Security, 4(4):708–717, 2009. ture) already stress the need for an accurate manifest, so we do not believe this exposes a vulnerability in current [26] Philip B Stark. Efficient post-election audits of mul- systems. tiple contests: 2009 california tests. In CELS 2009 4Th annual conference on empirical legal studies paper, 2009. C Polling and Comparison Audits

with Statistical Manifests [27] Philip B. Stark. Risk-limiting postelection audits: Conservative P -values from common probability inequalities. IEEE Transactions on Information Statistical manifests yield a “(p, δ, ∆)-contaminated” accounting for the sizes of the batches, which is to say that Forensics and Security, 4(4):1005–1014, 2009. all batches are within a (1 + ∆) factor of their true size, [28] Jorge H Banuelos and Philip B Stark. Limiting and all but a p-fraction of them are in fact within a (1+δ) risk by turning manifest phantoms into evil zombies. factor of their true size. Considering the efficiency improvements afforded by permitting this uncertainty, it is arXiv preprint arXiv:1207.3413, 2012. of interest to explore how conventional polling and com[29] Douglas W Jones, Sunoo Park, Ronald L Rivest, parison audits fare in this setting. and Adam Sealfon. Scan, shuffle, rescan: Machineassisted election audits with untrusted scanners. In Polling. A standard polling audit is defined by introFinancial Cryptography, 2024. ducing the function A : B → R given by A(b) = Wb −Lb . [30] Secretary of the State of Georgia. Georgia’s 2024 Then Wact − Lact statewide risk limiting audit confirms voting system , E[A(bU )] = |B| accuracy, 2024. where bU is drawn from the uniform distribution U on [31] Risk limiting audits with Arlo, 2021. B. Standard results from probability theory guarantee that if b1 , . . . , bk are drawn uniformly (with replacement, [32] Brennan Center for Justice and Rhode Island say) from B, then the empirical mean converges to the RLA Working Group. Pilot implementation study expected value, of risk-limiting audit methods in the state of Rhode 1X Island, 2019. A(bi ) ≈ E [A(b)] , b←B k i [33] Zanu Saputra, Andreas Lie Alviero, Dimas Setiawan Nugroho, and Yudhi. Automatic paper counter ma- and, furthermore, the error in this approximation satisfies chine using internet of things and arduino. In 2023 suitable tail bounds; for example, 3rd International Conference on Electronic and Elec" #   1X λ2 k trical Engineering and Intelligent System (ICE3IS), Pr A(bi ) − E [A(b)] ≥ λ ≤ 2 exp − , pages 41–46, 2023. b←B k i 2M 2 [34] Connecticut Risk Limiting Audit Working Group. where M = max{|A(b)|}. Risk-limiting audit recommendations for connectiAs statistical manifests immediately yield (p, δ, ∆)cut, 2022. contaminated sampling distributions on the underlying ballots, the natural question is what can be said about this expectation when sampling is performed with the A Open Science distorted distribution. Specifically, observe that if ballots Code to reproduce our efficiency experiments is avail- are instead drawn from a distorted distribution π on B, able online at: https://github.com/VoterCenter/ the same tail bounds apply to the expected value direct-rla. This code allows for the complete reproduction of the results in this paper.

B

Ethical Considerations

E[A(bπ )] , where bπ denotes a ballot drawn from π (rather than the uniform distribution). In light of Lemma 4,

|E[A(bπ )] − E[A(bU )]| ≤ 2 · M · dTV (π, U ) . This work proposes new risk-limiting audits for elecRecalling Theorem 4, this distance in total variation tions that are usable in various municipalities throughout dTV (π, U ) is no more than the world. Some statistical data is used from publicly available sources on various Secretary of State websites (1 + δ)p∆ δ + . throughout the United States. In addition, we remark 2+δ 1 + pδ 17

This provides an immediate means for adapting a conven- So instead of computing on the expanded cvr′ , we use tional polling audit to a setting with a distorted sampling Kaplan-Markov to test whether distribution given by a statistical manifest. tab E [DB (1 + ϵ(p)) − ϵ(p). cvr (r)] ≥ µ r∈cvr Comparison. A standard comparison audit draws CVR rows uniformly from the tabulated CVR. A con- This provides satisfactory results as long as µtab > ϵ(p). clusion of Fuller, Harrison, and Russell [15] is that this As discussed in the body, our technique can be seen process is risk-limiting so long as that the total number of as controlling the margin “sacrificed” by adding these CVR rows is at least the total number of ballots. (In par- rows so they do not unduly cause the audit to output ticular, duplicated identifiers cannot compromise risk.) In Inconclusive. this setting, the only quantity of direct relevance is the total number of ballots, an upper bound for which is directly provided by Theorem 6 in the context of an approx- D Prior Audits are not Riskimate manifest. Specifically, for a (p, δ, ∆)-contaminated Limiting with Highly Inaccureweighting,

rate Manifest

|B| ≤ Stab (1 + ϵ(p)) = Stab (1 + [(1 − p)δ + p∆]) . Lindeman et al. [8] suggested adding dummy rows and marking them when sampled with the maximum discrepancy. This is a risk-limiting audit with parameters that depend on the gap between the size of the CVR and the upper bound on the size of the ballot population. As discussed in the body, for standard parameterization of Kaplan-Markov, obtaining a comparison audit that terminates requires µ ≈ ϵ(p)/5. Kaplan-Markov is designed for nonzero values to be rare, and so adding items that cause a discrepancy of 2 causes the audit to greatly inflate the number of samples required to complete. Instead, for a CVR cvr and a row r of cvr, consider the value DB cvr (r) defined to be the minimum—taken over all ballots b that match the CVR row identifier—of Dcvr (b); following Harrison, Fuller, and Russell [15], in the event that there is no matching ballot (or this is a “dummy” row of the CVR), define the discrepancy as though the row r is matched with a ballot holding a vote for the loser, which is to say that Lb − Wb = 1. It is easy to argue [15] that by this convention

We provide simple examples showing that polling, ballot comparison audits, and direct selection audits are not risk-limiting when the size of each batch is distorted by ∆ of comparable size to the margin µ. This discussion applies to methods that uniformly sample ballots to compute the batch size. This is true for most methods in each class, but does not apply to taint tracking methods [7]. In all discussion below batch sizes are manipulated by less than the ∆ = .1 considered in our experimental results.

Ballot polling. Consider an election with Wact votes for the true winner and Lact for the true loser. Furthermore, the declared margin is µtab . In simplified terms, a polling audit bounds the probability that Pr [(Wact − Lact )/S c. Recall P< µ/c] for some constant P that since Wact = b∈B Wb and Lact = b∈B Lb one can estimate these quantities by uniformly sampling (without) replacement a b ∈ B computing Wb − Lb . With an accurate manifest each b is selected with probability 1/S as S = |B|. Define µobs := (Wbobs − Lobs b b )/S. The goal of the statistical test is to lower-bound the expectab E[DB , cvr (r)] ≥ µ . This expectation is highly sensitive to tation Eb←B µobs b the sampling of b ← B which can be adjusted by mafor any invalid election. (Here r is drawn uniformly from nipulating the size of batches. We use U to denote the the CVR rows.) Assuming, for simplicity, that the ballots are organized proper uniform sampling of ballots. Consider the followinto a single batch, let cvr′ be a tabulated CVR expanded ing simplified example where there are two batches of size by adding Stab ·ϵ(p) additional dummy rows. As described 49 and 51 denoted as L and W respectively, where all balabove, this ensures that the size of the CVR is, at least, lots in L have a vote for candidate L and all ballots in W have a vote for W. The correct Eb←BU µobs = −.02 for the total number of ballots. Then b this election. One can adjust the diluted margin from .02 µtab ≤ E[DB for the W to .02 for the loser by adjusting the sizes to 51 cvr′ (r)] r and 49 respectively. This creates a new distribution of B = E [Dcvr′ (r)] Pr[r ∈ Added Rows] sampled ballots DA where Eb←BDA µobs r|r∈ Added Rows b = .02 . B The above example is very simplified; the quality of the + E [Dcvr (r)] Pr[r ∈ cvr] r|r∈cvr manipulation is proportional to the number of batches that have strong margins for one candidate or another. Er|r∈cvr [DB ϵ(p) cvr (r)] + ≥1· However, the polarization displayed does mirror current 1 + ϵ(p) 1 + ϵ(p) electoral trends in the United States. Often, large cities ϵ(p) + Er|r∈cvr [DB cvr (r)] have overwhelming Democratic preferences while rural ar= . 1 + ϵ(p) eas have overwhelming Republican preferences. Taking 18

the 2024 Presidential Election in Connecticut as an example, 26% of batches had a margin that was 30% different than the overall statewide margin.

State

Ballot comparison. The goal of traditional ballot comparison is to determine with statistical confidence whether D/|B| = ((Wtab − Ltab ) − (Wact − Lact ))/|B| ≥ µtab . However, discrepancy is defined differently. In Fuller, Harrison, and Russell it is defined with respect to the rows of the CVR instead of over ballots (identifiers are again assumed to be unique in the CVR). In the case of an inaccurate estimate on |B|, the cvr can have too few rows, which can bias sampling. We continue with the same example of two batches from the ballot polling above. By reporting the Wact batch as having 47 ballots instead of 51 the diluted margin becomes 2.1% for the Lact . Since the above measure of discrepancy only considers identifiers in the cvr one can simply create a correct cvr for the 49 ballots from the Lact batch, and one can never observe a non-zero discrepancy. Unlike ballot polling, it isn’t clear how to inflate the sizes of desirable batches for the adversary, as creating a cvr with identifiers that don’t exist on physical ballots only increases discrepancy [15]. However, this example does not depend on the distribution of ballots between batches, the adversary can directly suppress votes for the actual winner in any batch.

Cong.

1M

CT

GA

Direct ballot selection. Direct ballot selection without BoundSize is also vulnerable in a similar way to ballot comparison. However, instead of reducing the size of the cvr the adversary increases it. So the adversary increases the size of the loser batch to size 53 by creating cvr rows with identifiers that don’t correspond to any ballot. Because these can never be sampled, they are not identified as having a positive discrepancy. This shows the dual risk of sampling from ballots (which allows creation of CVR rows that don’t correspond to a ballot) and from CVR rows (which allows not listing the CVRs for undesirable ballots).

E

Additional Concrete Results

Figure 5c shows the time ratio for the ballot polling (Minerva) method when creating a statistically accurate and full manifest across California, Florida, Georgia, and Connecticut. The findings are very similar to that of Figure 5a, which are discussed in detail in Section 4. Table 2 and Table 3 show the main results of our election simulation; the total ballots needed to conduct a direct ballot selection audit and the average ballots sampled per batch respectively. These results are also discussed in detail in Section 4.

FL

CA

Margin % 0.50 0.75 1.00 1.50 2.00 2.50 3.00 0.50 0.75 1.00 1.50 2.00 2.50 3.00 0.50 0.75 1.00 1.50 2.00 2.50 3.00 0.50 0.75 1.00 1.50 2.00 2.50 3.00 0.50 0.75 1.00 1.50 2.00 2.50 3.00 0.50 0.75 1.00 1.50 2.00 2.50 3.00

Direct Ballot Selection dup Sample k α k α 63 63 64 38 50 90 51 10 43 55 28 45 34 65 31 35 29 90 18 10 26 88 15 12 23 88 19 12 42 65 29 35 33 60 31 40 28 85 21 15 22 65 14 35 19 88 9 12 17 95 15 5 15 88 9 12 32 65 17 35 25 63 17 38 21 63 17 38 17 90 14 10 14 88 12 12 13 95 9 5 12 88 5 12 18 95 17 5 14 98 11 2 12 95 11 5 10 95 5 5 8 93 5 8 7 95 3 5 7 93 2 8 14 95 11 5 11 98 7 2 9 98 7 2 8 98 7 2 6 98 5 2 6 98 2 2 5 98 2 2 10 98 5 2 8 98 4 2 7 98 4 2 5 98 4 2 5 98 2 2 4 95 1 5 4 98 4 2

Minerva [14] 700 311 175 78 44 28 19 319 142 80 35 20 13 9 190 84 47 21 12 8 5 64 28 16 7 4 3 2 40 18 10 4 3 2 1 20 9 5 2 1 1 1

Table 2: Simulated sample sizes per batch for direct ballot selection and Minerva [14]. αdup , αSample are normalized percentages of overall risk α. Direct ballot selection optimization minimizes the max of kdup , kSample . Raw ballots pulled is in Table 3.

F

Simple duplicate detection

We return to the proof of Lemma 1. We begin with a simpler version adopting a sampling distribution with replacement; the lemma then follows by a simple monotonicity argument. Theorem 3 (Simple duplicate-detection bound under

19

State

Cong.

1M

CT

GA

FL

CA

Margin % 0.50 0.75 1.00 1.50 2.00 2.50 3.00 0.50 0.75 1.00 1.50 2.00 2.50 3.00 0.50 0.75 1.00 1.50 2.00 2.50 3.00 0.50 0.75 1.00 1.50 2.00 2.50 3.00 0.50 0.75 1.00 1.50 2.00 2.50 3.00 0.50 0.75 1.00 1.50 2.00 2.50 3.00

Direct Ballot Selection dup Sample k α k α 32 63 32 38 26 90 26 10 22 55 14 45 17 65 16 35 14 90 9 10 13 88 8 12 12 88 10 12 46 65 32 35 37 60 35 40 32 85 23 15 25 65 16 35 22 88 10 12 18 95 17 5 17 88 10 12 60 65 32 35 48 63 32 38 40 63 32 38 32 90 26 10 27 88 23 12 24 95 17 5 22 88 10 12 101 95 95 5 80 98 64 2 67 95 64 5 54 95 29 5 46 93 29 8 41 95 17 5 38 93 10 8 127 95 95 5 100 98 64 2 84 98 64 2 66 98 64 2 58 98 44 2 52 98 17 2 47 98 17 2 180 98 95 2 142 98 64 2 120 98 64 2 94 98 64 2 82 98 44 2 74 95 17 5 65 98 64 2

Minerva [14] 354 158 89 39 22 14 10 354 158 89 39 22 14 10 354 158 89 39 22 14 10 354 158 89 39 22 14 10 354 158 89 39 22 14 10 354 158 89 39 22 14 10

Table 3: Simulated sample sizes in thousands for direct ballot selection and Minerva [14]. αdup , αSample are normalized percentages of overall risk α. Direct ballot selection optimization minimizes the max of kdup , kSample .

N

Cong.

1M

CT

GA

FL

CA

Margin % 0.50 1.00 2.00 3.00 5.00 8.00 10.00 0.50 1.00 2.00 3.00 5.00 8.00 10.00 0.50 1.00 2.00 3.00 5.00 8.00 10.00 0.50 1.00 2.00 3.00 5.00 8.00 10.00 0.50 1.00 2.00 3.00 5.00 8.00 10.00 0.50 1.00 2.00 3.00 5.00 8.00 10.00

kdup 36 24 16 13 9 7 7 52 34 22 18 13 11 9 61 42 29 23 17 13 12 105 69 48 37 29 23 20 132 87 60 47 36 28 25 175 124 83 66 51 39 35

Accurate kSample kS 10 456 5 456 3 456 2 456 2 456 2 456 1 456 10 1000 6 1000 4 1000 3 1000 3 1000 1 1000 2 1000 16 1680 7 1680 4 1680 3 1680 3 1680 2 1680 1 1680 16 5008 10 5008 6 5008 6 5008 3 5008 2 5008 2 5008 16 7964 10 7964 6 7964 6 7964 3 7964 3 7964 3 7964 33 16141 10 16141 7 16141 6 16141 3 16141 3 16141 3 16141

kdup 35 23 16 22 15 11 10 52 33 38 31 22 15 14 61 88 47 37 26 19 17 105 129 73 58 41 31 26 132 157 90 67 50 39 33 609 199 127 92 68 51 45

Inaccurate kSample kS 10 456 6 456 3 456 4 176 3 111 2 73 2 61 10 1000 6 1000 6 327 5 176 3 111 3 85 2 61 16 1680 16 659 7 327 4 218 3 138 3 92 2 66 16 5008 33 719 11 387 6 237 4 165 3 110 4 94 16 7964 33 789 10 426 10 284 5 165 3 110 4 94 33 4023 33 1107 11 426 11 315 5 203 5 137 4 117

Table 4: Direct selection concrete parameters of accurate versus inaccurate manifest. Used to compute time savings in Figure 5b. All sizes are in thousands. collision event n o Ekiid := ∀i ̸= j ≤ k, f (Yi ) = f (Yj ) =⇒ Yi = Yj .

Thus Ekiid is the event that no duplicate identifier is detected among the k draws, where repeated draws of the same element are not counted as collisions. If k ≤ n(1+c) then   2 ! i.i.d. sampling). Let A be a finite set with |A| = n, let −k iid f : A → B be a function with |B| = n − ℓ, and let Π be a Pr(Ek ) ≤ 2 exp −ℓ 1 − exp (13) n(1 + c) probability distribution on A such that   k2 ℓ ≤ 2 exp − 2 . (14) 1+c 1 4n (1 + c)2 ≤ Π(x) ≤ for all x ∈ A, n(1 + c) n Proof. For each b ∈ B, let for some c ≥ 0. Let Y1 , . . . , Yk be i.i.d. from Π, and define the noFb := f −1 (b), sb := |Fb |. 20

Method

Comp.

Polling

Margin % 0.50 1.00 2.00 3.00 5.00 8.00 10.00 0.50 1.00 2.00 3.00 5.00 8.00 10.00

Accurate kSample kS 2.4K 16.1M 924 16.1M 395 16.1M 252 16.1M 133 16.1M 83 16.1M 65 16.1M 355K 16.1M 89K 16.1M 23K 16.1M 10K 16.1M 4K 16.1M 2K 16.1M 1K 16.1M

Inaccurate kSample kS 6.1K 220K 2.5K 83K 839 44K 744 21K 496 11K 197 9K 176 7K 355K 16.1M 191K 1.3M 44K 387K 20K 218K 8K 104K 4K 54K 3K 40K

Fix b ∈ B+ . The event that the fiber Fb causes no detected collision is ( ) X Ab := Ix ≤ 1 . x∈Fb

This is a coordinatewise decreasing event in the family (Ix )x∈Fb . Since each Ix stochastically dominates a Bernoulli(r), monotonicity of product measures implies   Pr[Ab ] ≤ Pr Bin(sb , r) ≤ 1 . Now   Pr Bin(sb , r) ≤ 1 = (1 − r)sb + sb r(1 − r)sb −1
= (1 − r)sb −1 1 + (sb − 1)r .

Using 1 + mr ≤ (1 + r)m for every integer m ≥ 0, we Table 5: Ballot comparison and polling concrete param- obtain eters of accurate versus inaccurate manifest for the CA size. The only size dependence on these methods is when Pr[Ab ] ≤ (1 − r)sb −1 (1 + r)sb −1 = (1 − r2 )sb −1 . to resort to a full count of size or a full hand recount. Used Because different fibers involve disjoint collections of to compute time savings in Figure 5a and Figure 5c. independent variables, the events (Ab )b∈B+ are independent. Therefore Let Y Y Pr[E P ] = Pr[Ab ] ≤ (1 − r2 )sb −1 = (1 − r2 )ℓ̃ . B+ := {b ∈ B : sb > 0} be the set of nonempty fibers. Then X X sb = n, (sb − 1) = n − |B+ | b∈B+

b∈B+

b∈B+

Using 1 − u ≤ e−u and ℓ̃ ≥ ℓ,
2 2 Pr[E P ] ≤ e−ℓ̃r ≤ e−ℓr = exp −ℓ(1 − e−kL )2 .

b∈B+

= n − | im(f )| ≥ n − |B| = ℓ. Step 2: De-Poissonization. For each m ≥ 0, let

Define ℓ̃ :=

X

(sb − 1),

iid pm := Pr[Em ],

b∈B+ iid denotes the no-collision event for exactly m where Em i.i.d. draws from Π. The sequence (pm ) is nonincreasing in m, since adding more draws can only create more 1 L := . opportunities for collision. n(1 + c) Because N ∼ Pois(k), X Step 1: Poissonization. Let N ∼ Pois(k), independent Pr[E P ] = pm Pr[N = m]. of everything else, and let Z1 , . . . , ZN be i.i.d. from Π. m≥0 Let E P denote the event that no duplicate identifier is detected among these N draws. Since pm ≥ pk for all m ≤ k, it follows that For each x ∈ A, let Pr[E P ] ≥ pk Pr[N ≤ k]. Mx := #{i : Zi = x}. Hence Pr[E P ] Then the random variables (Mx )x∈A are independent and . pk ≤ satisfy Pr[N ≤ k] Mx ∼ Pois(kΠ(x)). Combining this with the bound from Step 1 yields

so that ℓ̃ ≥ ℓ. Further define

Now define

exp −ℓ(1 − e Pr[Ekiid ] = pk ≤

−kL 2

) Pr[Pois(k) ≤ k]

Ix := 1{Mx >0} . Then the Ix are independent Bernoulli random variables with

.

Recalling that Pr[Pois(k) ≤ k] ≥ 1/2, we conclude that
Pr[Ekiid ] = pk ≤ 2 exp −ℓ(1 − e−kL )2 .

Pr[Ix = 1] = 1 − e−kΠ(x) ≥ 1 − e−kL =: r. 21

Finally, if kL ≤ 1, then 1 − e−kL ≥

f (Yi ) = f (Yj ). Those two distinct elements have both appeared by time k, so they are among the first k distinct e1 , . . . , X ek . Hence E seq also fails for X e1 , . . . , X ek . values X k Therefore

kL . 2

Thus

e1 , . . . , X ek ) ⊆ Ekiid (Y1 , . . . , Yk ), Ekseq (X

Pr[Ekiid ] ≤ 2 exp −ℓ



kL 2

 ! 2

 = 2 exp −

k2 ℓ 4n2 (1 + c)2



which gives

,

Pr[Ekseq ] ≤ Pr[Ekiid ]. The stated bounds now follow from Theorem 3.

which is (14).

Lemma 1 follows immediately.

We now prove Lemma 1 as a corollary of the previous theorem. Corollary 2 (Reduction to sequential weighted sampling without replacement). Assume the hypotheses of Theorem 3. Let X1 , . . . , Xk be sampled without replacement according to the sequential law X1 ∼ Π, and for t ≥ 1, Pr[Xt+1 = x | X1 , . . . , Xt ] =

G

In this section, we focus on showing the soundness of the BoundSize procedure. Recall Definition 12 from the main text: if P and Q are probability distributions on a finite set X, then Q is a (p, δ, ∆)-contaminated reweighting of P if there exist a function w : X → (0, ∞) and a set Bad ⊆ X such that

Π(x) Pt 1 − j=1 Π[Xj ]

for every x ∈ / {X1 , . . . , Xt }. Define Ekseq := {∀i ̸= j, f (Xi ) ̸= f (Xj )}.

Q(x) = P

Then, for k ≤ n(1 + c),   Pr[Ekseq ] ≤ 2 exp −ℓ 1 − exp  ≤ 2 exp −

2

k ℓ 4n2 (1 + c)

−k n(1 + c)  . 2

(15) (16)

P (x)w(x) y∈X P (y)w(y)

1 ≤ w(x) ≤ 1 + δ 1+δ 1 ≤ w(x) ≤ 1 + ∆ 1+∆

2 !

Proof. Let Y1 , Y2 , . . . be an infinite i.i.d. sequence with law Π. Define stopping times τ1 := 1,

Bounding Contaminated Reweighting of Induced Ballot Distribution

for all x ∈ X, for all x ∈ X \ Bad, for all x ∈ X,

and P (Bad) ≤ p, where 0 ≤ δ ≤ ∆. This section records the quantitative consequences of this notion that are used in the analysis of the auditor and in the manifest-certification step. Recall the definition of distance in total variation.

τm+1 := min{t > τm : Yt ∈ / {Yτ1 , . . . , Yτm }}.

Definition 14 (Total variation distance.). Let P and Q be probability distributions on a finite set X. Then Since Π(x) > 0 for every x ∈ A, these stopping times are the distance between P and Q in total variation, denoted almost surely finite for m ≤ n. Set dTV (P, Q), is given by the quantity e Xm := Yτm , m = 1, . . . , k. 1 X |P (x) − Q(x)| . 2 x∈X e1 , . . . , X ek ) has exactly the sequential withoutThen (X e1 = x1 , . . . , X et = Lemma 2 (General reweighting estimates). Let P be a replacement law above: conditional on X xt , the next accepted value is the first future i.i.d. draw probability distribution on a finite set X, let w : X → that lands outside {x1 , . . . , xt }, so for x ∈ / {x1 , . . . , xt }, (0, ∞), and define X P (x)w(x) et+1 = x | X e1 = x1 , . . . , X et = xt ] Pr[X m := P (x)w(x), Q(x) := . m  m−1 x∈X t X X  = Π(xj ) Π(x) Then j=1 m≥1 1 X dTV (P, Q) = P (x) |w(x) − m|. Π(x) 2m x∈X = . Pt 1 − j=1 Π(xj ) Moreover, X iid Now, if Ek fails for the first k i.i.d. draws Y1 , . . . , Yk , dTV (P, Q) ≤ P (x) |w(x) − 1|. then there exist i ̸= j ≤ k such that Yi ̸= Yj but x∈X 22

Proof. Since Q(x) = P (x)w(x)/m, 1 X dTV (P, Q) = |P (x) − Q(x)| 2

Proof. By Lemma 2, dTV (P, Q) =

x∈X

w(x) 1 X P (x) 1 − = 2 m x∈X 1 X = P (x) |w(x) − m|. 2m x∈X

1 X P (x) |w(x) − m|. 2m x∈X

Also m ∈ [α, β], since m is a P -average of values in [α, β]. Fix m ∈ [α, β]. The function y 7→ |y − m| is convex on [α, β], so by convexity it lies below its secant line on that interval:

β−y y−α This proves the identity. For the inequality, define the |y − m| ≤ (m − α) + (β − m) (y ∈ [α, β]). β − α β −α finite measure P Averaging with respect to P and using x P (x)w(x) = M (x) := P (x)w(x) (x ∈ X), m, we obtain P so that x M (x) = m and Q = M/m. By the triangle X m−α β−m inequality, (m − α) + (β − m) P (x)|w(x) − m| ≤ β−α β−α x∈X ∥P − Q∥1 ≤ ∥P − M ∥1 + ∥M − Q∥1 . 2(β − m)(m − α) = . Now β−α X ∥P − M ∥1 = P (x)|1 − w(x)|, Hence x∈X (β − m)(m − α) . dTV (P, Q) ≤ and m(β − α) X M (x) Consider ∥M − Q∥1 = M (x) − m x∈X (β − m)(m − α) α + β − m − αβ/m f (m) := = . 1 X m(β − α) β−α = 1− M (x) = |m − 1|. m x∈X Then −1 + αβ/m2 Also, , f ′ (m) = β−α X X √ |m − 1| = P (x)(w(x) − 1) ≤ P (x)|w(x) − 1|. so f is maximized at m = αβ. Evaluating there gives x∈X x∈X √ √ p β− α f ( αβ) = √ √ . Hence β+ α X 2 dTV (P, Q) = ∥P − Q∥1 ≤ 2 P (x)|w(x) − 1|, This proves the first claim. x∈X For the special case α = 1/(1 + η) and β = 1 + η, we which proves the lemma. get √ √ Corollary 3 (Total variation under bounded reweight1 + η − 1/ 1 + η (1 + η) − 1 η √ √ = = . ing). Let P be a probability distribution on a finite set X, (1 + η) + 1 2+η 1 + η + 1/ 1 + η let w : X → (0, ∞), and define m :=

X

P (x)w(x),

Q(x) :=

x∈X

P (x)w(x) . m

Assume that for some 0 < α ≤ β, α ≤ w(x) ≤ β Then

for all x ∈ X.

√ √ β− α dTV (P, Q) ≤ √ √ . β+ α

In particular, if 1 ≤ w(x) ≤ 1 + η 1+η then dTV (P, Q) ≤

for all x ∈ X,

Remark. The bound in Corollary 3 is optimal. Equality is attained on a two-point space when w takes√ the two values α and β with P -masses proportional to β and √ P √ α, so that x P (x)w(x) = αβ. Theorem 4 (Elementary bounds for contaminated reweightings). Let P and Q be probability distributions on a finite set X. Suppose that Q is a (p, δ, ∆)-contaminated reweighting of P , witnessed by a function w : X → (0, ∞) and a set Bad ⊆ X. Define !−1 X λ := P (x)w(x) , x∈X

η . 2+η

so that Q(x) = λ P (x)w(x). 23

Since v = w on X \ Bad and v = 1 on Bad,

Also define ε(p) := (1 − p)δ + p∆,

A = (1 − p)mG + p.

and  τ (p) := Then

p 1−p + 1+δ 1+∆

−1

Also, because v(x) ∈ [1/(1 + δ), 1 + δ] for every x ∈ X, Corollary 3 gives

− 1.

1 ≤ λ ≤ 1 + τ (p) ≤ 1 + ε(p). 1 + ε(p)

dTV (P, V ) ≤

Moreover,

V (x) :=

r(x) :=

w(x) . v(x)

P (x)v(x) . A

Define dTV (P, Q) ≤

δ (1 + δ)p∆ + . 2+δ 1 + δp Then

Proof. Since Q is witnessed by w and Bad, we have

r(x) = 1

X 1 = P (x)w(x). λ x∈X

(x ∈ X \ Bad),

V (x)r(x) . y∈X V (y)r(y)

Applying Lemma 2 with source law V and reweighting function r, we obtain X X dTV (V, Q) ≤ V (x)|r(x) − 1| = V (x)|w(x) − 1|.

Using the lower bounds on w, 1 1−p p ≥ + , λ 1+δ 1+∆

x∈X

x∈Bad

Since v(x) = 1 on Bad, we have V (x) = P (x)/A there, and therefore

1 ≤ λ ≤ 1 + τ (p). 1 + ε(p)

dTV (V, Q) ≤

Since x 7→ 1/(1 + x) is convex on [0, ∞),

By the triangle inequality,

and therefore 1 + τ (p) ≤ 1 + ε(p). If p = 1, then w(x) ∈ [1/(1 + ∆), 1 + ∆] for all x ∈ X, so Corollary 3 gives ∆ , 2+∆

ΓBad 1 X P (x)|w(x) − 1| = . A (1 − p)mG + p x∈Bad

p 1 1 1−p + ≥ = , 1+δ 1+∆ 1 + (1 − p)δ + p∆ 1 + ε(p)

dTV (P, Q) ≤ dTV (P, V ) + dTV (V, Q) δ ΓBad ≤ + . 2+δ (1 − p)mG + p Since |w(x) − 1| ≤ ∆ on Bad, we have ΓBad ≤ p∆, so

which is at most

dTV (P, Q) ≤ δ (1 + δ)p∆ + . 2+δ 1 + δp

δ p∆ + . 2+δ (1 − p)mG + p

Also mG ≥ 1/(1 + δ), hence

Now assume 0 ≤ p < 1. Define (1 − p)mG + p ≥

P (x) PG (x) := (x ∈ X \ Bad), 1−p X mG := PG (x)w(x),

dTV (P, Q) ≤

and X

1−p 1 + δp +p= . 1+δ 1+δ

Therefore

x∈Bad /

ΓBad :=

(x ∈ Bad),

Q(x) = P

1 ≤ (1 − p)(1 + δ) + p(1 + ∆) = 1 + ε(p). λ

dTV (P, Q) ≤

r(x) = w(x)

and

Using the upper bounds on w,

hence

δ , 2+δ

P (x) |w(x) − 1|.

δ (1 + δ)p∆ + . 2+δ 1 + δp

This completes the proof of Theorem 4.

x∈Bad

Next define ( w(x), x ∈ X \ Bad, v(x) := 1, x ∈ Bad,

A :=

X x∈X

P (x)v(x).

Uniformity bounds from contaminated reweightings. For duplicate detection, we will need a pointwise closeness-to-uniform guarantee, rather than only a totalvariation bound. 24

Lemma 3 (Reverse-direction max-divergence from contaminated reweighting). Let P and Q be probability distributions on a finite set X, and let

H

Bounding Ballot Discrepancy; the Analysis of the Auditor

This section proves our main theorem (Theorem 7). The structure proceeds as follows:

ε(p) := (1 − p)δ + p∆. Assume that either

(1) Assuming a uniform sampling distribution law, the average discrepancy can be lower bounded in terms of the total tabulation error, up to additive losses from two sources: duplicate ballots (captured by the duplicate rate κ) and added CVR rows that don’t correspond to any ballot.

(1) Q is a (p, δ, ∆)-contaminated reweighting of P , or (2) P is a (p, δ, ∆)-contaminated reweighting of Q. Then for every x ∈ X, Q(x) 1 ≤ ≤ (1 + ∆)(1 + ε(p)). (1 + ∆)(1 + ε(p)) P (x)

(2) For an arbitrary sampling distribution, we show the expected discrepancy change is bounded by the total variation distance shown in Theorem 4. The expectation can decrease by at most 4 dTV (π, U ), since discrepancies lie in [−2, 2].

Consequently, if either P or Q is uniform on X, then the other is ηrev -close-to-uniform, where ηrev (p, δ, ∆) := (1 + ∆)(1 + ε(p)) − 1.

(3) Finally, we apply the above result to a distribution induced by batchwise sampling and bounding the contaminated reweighting of the induced ballot distribution.

In particular, since ε(p) ≤ ∆, ηrev (p, δ, ∆) ≤ (1 + ∆)2 − 1.

Setup and notation. Fix S a tabulation T = Proof. We first consider case (1), where Q is a (p, δ, ∆)(cvr(1) , . . . , cvr(m) ) and let B = β Bβ be a set of physicontaminated reweighting of P . Then there exist a funccal ballots. Write tion w : X → (0, ∞) and a set Bad ⊆ X such that X M  −1 . N := |B|, M := Stab = Stab λ := β , N X β Q(x) = λ P (x)w(x), λ :=  P (y)w(y) , y∈X

For a ballot b, we let

with

m(b) ∈ {−1, 0, 1} 1 ≤ w(x) ≤ 1 + ∆ 1+∆

for all x ∈ X.

denote its contribution to the winner–loser margin: m(b) = 1 if b is a vote for the reported winner but not the reported loser, m(b) = −1 if b is a vote for the reported loser but not the reported winner, and m(b) = 0 otherwise. Likewise, for a CVR row r, let

By Theorem 4, 1 ≤ λ ≤ 1 + τ (p) ≤ 1 + ε(p). 1 + ε(p)

m(r) ∈ {−1, 0, 1} Therefore, for every x ∈ X,   denote the corresponding quantity of that row. For a 1 Q(x) = λw(x) ∈ , (1 + ∆)(1 + ε(p)) . dummy row (with no corresponding ballot) d, set m(d) := P (x) (1 + ∆)(1 + ε(p)) 0. Now consider case (2), where P is a (p, δ, ∆)contaminated reweighting of Q. By the argument above,   1 P (x) ∈ , (1 + ∆)(1 + ε(p)) , ∀x ∈ X. Q(x) (1 + ∆)(1 + ε(p))

Ballot discrepancy. Recall the definition of discrepancy from Def. 7: For each physical ballot b ∈ B, let rb be the CVR row returned by the lookup rule for ballot b, if such a row exists. The discrepancy is defined to be ( Taking reciprocals yields exactly the same interval for D (b) := m(rb ) − m(b), if lookup returns a row rb , T 1 − m(b), if lookup returns no row. Q(x)/P (x). The close-to-uniform conclusion is immediate when one of the two distributions is uniform on X. The final in- Thus equality follows from ε(p) ≤ ∆. DT : B → [−2, 2]. 25

If π is any probability distribution on Proof. Choose one representative ballot for each label and call all remaining ballots with that label extra duplicates. There are exactly κN such ballots. bπ ∼ π Construct an injective “repaired assignment” of ballots denote a ballot drawn from π. In particular, let U denote to genuine CVR rows and (new) dummy rows as follows: the uniform distribution on B, and write bU ∼ U . • if a representative ballot b has a matching CVR row Total discrepancy and tabulated margin. Define under the lookup rule, assign it to that row; the total signed discrepancy • if a representative ballot b has no matching CVR row, assign it to an unused genuine CVR row if one ∆T := (Wtab − Ltab ) − (Wact − Lact ). is available, and otherwise to a (new) dummy row; As elsewhere in the paper, let • assign each extra duplicate ballot similarly to an unWtab − Ltab used genuine CVR row if one is available, and othertab µ := wise to a (new) dummy row. M

Sampled ballot. B, let

denote the tabulated diluted margin. If the reported outcome is wrong, then

Let e T (b) D

∆T ≥ µtab M.

denote the discrepancy of b under this repaired injective assignment. e T (b) for any representaOf course, one has DT (b) = D Duplicate rate. Let bid denote the label of ballot b. tive ballot, as the assignment is unchanged. For a ballot Define b with no matching CVR row, we see that 1 X κ := (#{b ∈ B : bid = ι} − 1) . e T (b) , N DT (b) = 1 − m(b) ≥ m(r) − m(b) = D ι∈LB

Equivalently, κN is the number of ballots discarded after where r is the row assigned to b in the repaired correspondence. Finally, for an extra duplicate ballot b we keeping at most one ballot of each label. e T (b)| ≤ 2; in particular, can only promise |DT (b) − D Lemma 4 (Total-variation comparison for bounded funce T (b) − 2 . tions). Let f : Ω → R, and let P, Q be probability distriDT (b) ≥ D butions on Ω. If |f (x)| ≤ Mf for all x ∈ Ω, then Thus only extra duplicates can increase discrepancy unE[f (XP )] − E[f (XQ )] ≤ 2Mf dTV (P, Q), der repair, and we conclude that X X where XP ∼ P and XQ ∼ Q. e T (b) − 2κN. DT (b) ≥ D b∈B

Proof. By definition, E[f (XP )] − E[f (XQ )] =

X

b∈B

Let S ⊆ T be the set of genuine CVR rows used by the repaired assignment. Then X X e T (b) = D m(r) − (Wact − Lact ),

(P (x) − Q(x))f (x).

x∈Ω

Therefore

r∈S

b∈B

E[f (XP )] − E[f (XQ )] ≤

X

|P (x) − Q(x)| |f (x)|

while

x∈Ω

≤ Mf

X

∆T =

|P (x) − Q(x)|.

dTV (P, Q) =

Thus

1X |P (x) − Q(x)|, 2

∆T −

X b∈B

x∈Ω

the claim follows.

e T (b) = D

X

m(r) ≤ |T \ S|,

r∈T \S

where the suggestive notation T \ S indicates the set of those rows of T that are not in correspondence with a ballot. Because the repaired assignment uses as many genuine CVR rows as possible,

Lemma 5 (Uniform-ballot lower bound). Under the uniform ballot law U , E[DT (bU )] ≥

m(r) − (Wact − Lact ).

r∈T

x∈Ω

Since

X

∆T − 2κ − (λ − 1)+ . N

|S| = min{M, N }, 26

For λ ≤ 1, we have g(λ) = µtab λ, so the minimum on [1/(1 + ε), 1] is attained at λ = 1/(1 + ε), giving

so |T \ S| = (M − N )+ . Therefore X

µtab . 1+ε

DT (b) ≥ ∆T − 2κN − (M − N )+ .

b∈B

For λ ≥ 1, we have g(λ) = µtab λ − (λ − 1), which is decreasing because µtab ≤ 1. Thus the minimum on [1, 1+τ ] is attained at λ = 1 + τ , giving

Dividing by N gives E[DT (bU )] =

1 X DT (b) N

µtab (1 + τ ) − τ.

b∈B

∆T (M − N )+ − 2κ − N N ∆T = − 2κ − (λ − 1)+ . N ≥

Theorem 5 (Lower bound under an arbitrary ballot law). Let π be any probability distribution on B. Then

Taking the smaller endpoint value proves the claim. Application to sampling from the tabulated batch sizes. Let n1 , . . . , nK > 0 be the actual batch sizes and m1 , . . . , mK > 0 the tabulated batch sizes. Define the corresponding batch laws ui :=

∆T − 2κ − (λ − 1)+ − 4 dTV (π, U ). E[DT (bπ )] ≥ N If the reported outcome is wrong, then E[DT (bπ )] ≥ µtab λ − 2κ − (λ − 1)+ − 4 dTV (π, U ). Proof. Apply Lemma 4 with f = DT ,

Mf = 2,

XP = bπ ,

ni , N

ri :=

mi . M

Let πu be the ballot law obtained by first choosing batch i with probability ui and then choosing a ballot uniformly from that batch; this is exactly the uniform distribution on physical ballots. Let πr be the analogous ballot law obtained from the tabulated batch law r. A direct calculation shows that

XQ = bU . dTV (πr , πu ) = dTV (r, u).

Since DT (b) ∈ [−2, 2] for all b, E[DT (bπ )] ≥ E[DT (bU )] − 4 dTV (π, U ). Now apply Lemma 5. If the reported outcome is wrong, then ∆T ≥ µtab M, hence

∆T M ≥ µtab = µtab λ. N N

Corollary 4 (Comparison bound from total variation and size control). Assume that

Thus, once we have bounds on dTV (r, u) and on the size ratio M/N , Corollary 4 immediately yields the desired lower bound for the comparison stage. We now establish these bounds in the batchwise setting relevant to manifest certification. Batchwise sampling model. We now apply our results to the specific setting of distorted batch sizes rather than an arbitrary distribution. Theorem 6 (Batchwise contaminated reweighting). Let n1 , . . . , nK > 0 be actual batch sizes and m1 , . . . , mK > 0 be reported batch sizes. Define

dTV (π, U ) ≤ γ N :=

and

1 ≤λ≤1+τ 1+ε for some γ, τ, ε ≥ 0. Then, if the reported outcome is wrong,   tab µ tab E[DT (bπ )] ≥ min , µ (1 + τ ) − τ − 2κ − 4γ. 1+ε

i=1

ni ,

M :=

K X

mi ,

i=1

ui :=

ni , N

Let Bad ⊆ [K], and define its tabulated mass by X p := ri . i∈Bad

Assume 0 ≤ δ ≤ ∆, and that

Proof. By Theorem 5, E[DT (bπ )] ≥ µtab λ − (λ − 1)+ − 2κ − 4γ.

K X

1 ni ≤ ≤1+δ 1+δ mi

(i ∈ / Bad),

1 ni ≤ ≤1+∆ 1+∆ mi

(1 ≤ i ≤ K).

while

Define g(λ) := µtab λ − (λ − 1)+ . 27

ri :=

mi . M

Then the actual batch law u is a (p, δ, ∆)-contaminated reweighting of the tabulated batch law r. More explicitly, if we define w(i) := then

Assume the tabulation T is uniquely labeled, and let b be the random ballot obtained by first choosing batch i with probability ri = mi /M and then choosing a ballot uniformly from that batch. Suppose that the reported outcome is wrong and that the actual batch law u is a (p, δ, ∆)-contaminated reweighting of the tabulated batch law r. Define ε(p), τ (p), and Γtv (p) as in Equations (17), (18), and (19). Then   µtab tab , µ (1 + τ (p)) − τ (p) E[DT (b)] ≥ min 1 + ε(p)

ni , mi

ri w(i) ui = PK j=1 rj w(j)

(1 ≤ i ≤ K),

the function w satisfies the δ- and ∆-bounds above, and r(Bad) = p.

− 2κ − 4Γtv (p).

Consequently, defining ε(p) := (1 − p)δ + p∆,  −1 1−p p τ (p) := − 1, + 1+δ 1+∆ and Γtv (p) = we have

δ (1 + δ)p∆ + . 2+δ 1 + δp

Proof. Let πr denote the ballot law induced by the tabulated batch distribution r, and let πu denote the ballot law induced by the actual batch distribution u. As noted (18) above, dTV (πr , πu ) = dTV (r, u),

(17)

and πu is exactly the uniform ballot law U . By Theorem 6,

(19)

dTV (r, u) ≤ Γtv (p)

M 1 ≤ ≤ 1 + τ (p), 1 + ε(p) N

and

M 1 ≤ ≤ 1 + τ (p). 1 + ε(p) N

and dTV (r, u) ≤ Γtv (p).

Applying Corollary 4 with

Proof. Define w(i) := ni /mi . Then X

ri w(i) =

X mi

i

i

M

·

λ=

ni N , = mi M

− 2κ − 4Γtv (p).

Thus u is a (p, δ, ∆)-contaminated reweighting of r, witnessed by the function w and the set Bad. Applying Theorem 4 to r and u gives 1 M ≤ ≤ 1 + τ (p). 1 + ε(p) N The same theorem yields δ (1 + δ)p∆ + . 2+δ 1 + δp

This yields dTV (r, u) ≤ Γtv (p). Theorem 7 (Ballot-discrepancy lower bound under contaminated reweighting). Let B be partitioned into batches 1, . . . , K, with actual sizes n1 , . . . , nK > 0 and reported sizes m1 , . . . , mK > 0. Let K X i=1

ni = |B|,

ε = ε(p),

τ = τ (p),

  µtab tab , µ (1 + τ (p)) − τ (p) E[DT (b)] ≥ min 1 + ε(p)

r w(i) ni (mi /M )(ni /mi ) Pi = = ui . = N/M N r w(j) j j

N :=

γ = Γtv (p),

yields

and therefore

dTV (r, u) ≤

M , N

M :=

K X

mi = |T |.

i=1

28