**Abstract.** Stratified sampling can be useful in risk-limiting audits (RLAs), for instance, to accommodate heterogeneous voting equipment or laws that mandate jurisdictions draw their audit samples independently. We combine the union-intersection tests in SUITE, the reduction of RLAs to testing whether the means of a collection of lists are all ≤ 1/2 of SHANGRLA, and the *nonnegative supermartingale* (NNSM) tests in ALPHA to improve the efficiency and flexibility of stratified RLAs. A simple, non-adaptive strategy for combining stratumwise NNSMs decreases the measured risk in the 2018 pilot hybrid audit in Kalamazoo, Michigan, USA by more than an order of magnitude, from 0.037 for SUITE to 0.003 for our method. We give a simple, computationally inexpensive, adaptive rule for deciding which stratum to sample next that reduces audit workload by as much as 74% in examples. We also present NNSM-based tests that are computationally tractable even when there are many strata, illustrated with a simulated audit stratified across California's 58 counties.

**Keywords:** Risk-limiting audit · Election integrity · Supermartingale test · Intersection hypothesis · Multi-armed bandit

# **1 Introduction**

Most U.S. jurisdictions use computers to tabulate votes. Like all computers, vote tabulators are vulnerable to bugs, human error, and deliberate malfeasance—a fact that has been exploited (rhetorically, if not in reality) to undermine trust in U.S. elections [3,4,9,10].

To deserve public trust, elections must be trustworthy, despite relying on untrustworthy software, hardware, and people: they should provide convincing affirmative evidence that the reported winners really won [1,2,20]. Risk-limiting audits (RLAs) are a useful tool for conducting such *evidence-based elections*. RLAs have a specified maximum chance—the *risk limit* α—of not correcting the reported outcome if it is wrong, and never change the reported outcome if it is correct. Below we present methods to reduce the number of ballots that must be manually inspected in an RLA when the reported outcomes are correct, for stratified audit samples.

In a ballot-level *comparison* RLA, manual interpretations of the votes on randomly sampled ballot cards are compared to their corresponding *cast vote records* (CVRs), the system's interpretation of the votes on those cards. In a *ballot-polling* RLA, votes are read manually from randomly selected cards, but those votes are not compared to the system's interpretation of the cards. All else equal, ballot-level comparison RLAs are more efficient than ballot-polling RLAs, but they require the voting system to export CVRs in a way that the corresponding card can be uniquely identified. Not all voting systems can.

Stratified random sampling can be mandatory or expedient in RLAs. Some states' laws require audit samples to be drawn independently across jurisdictions (e.g., California Election Code § 336.5 and § 15360), in which case the audit sample for any contest that crosses jurisdictional boundaries is stratified. Stratifying on the technology used to tabulate votes can increase efficiency by allowing *hybrid audits* [7,11], which use ballot-level comparison in strata where the voting technology supports it and ballot-polling elsewhere. Another reason to use stratification is to allow RLAs to start before all ballots have been tabulated [17].

The next section briefly reviews prior work on stratified audits. Section 3 introduces notation and stratified risk measurement, then presents our improvements: (i) sharper P-values from new risk-measuring functions; (ii) sequential stratified sampling that adapts to the observed data in each stratum to increase efficiency; and (iii) a computationally efficient method for an arbitrary number of strata. Section 4 evaluates the innovations using case studies and simulations. Section 5 discusses the results and gives recommendations for practice.

# **2 Past Work**

The first RLAs involved stratified batch comparison, using the maximum error across strata and contests as the test statistic [5,13–15], a rigorous but inefficient approach. Higgins et al. [6] computed sharper P-values for the same test statistic using dynamic programming. SUITE [7,11] uses *union-intersection tests* to represent the null hypothesis that one or more reported winners actually lost as a union of intersections of hypotheses about individual strata; it involves optimization problems that are hard to solve when there are more than two strata.

More recently, SHANGRLA [18] has reduced RLAs to a canonical form: testing whether the means of finite, bounded lists of numbers (representing ballot cards) are all less than 1/2, which allows advances in statistical inference about bounded populations to be applied directly to RLAs. Stark [18] showed that union-intersection tests can be used with SHANGRLA to allow *any* riskmeasuring function to be used in any stratum in stratified audits.

Stark [19] provided a new approach to union-intersection tests using nonnegative supermartingales (NNSMs): *intersection supermartingales*, which open the possibility of reducing sample sizes by adaptive *stratum selection* (using the first t sampled cards to select the stratum from which to draw the (t + 1)th card). Stark [19] does not provide an algorithm for stratum selection or evaluate the performance of the approach; this paper does both.

# **3 Stratified Audits**

We shall formalize stratified audits using the SHANGRLA framework [18], which unifies comparison and polling audits. We then show how to construct a stratified comparison audit using SHANGRLA, how to measure the risk based on a stratified sample, and how adaptive sequential stratified sampling can improve efficiency.

# **3.1 Assorters and Assertions**

Ballot cards are denoted {bi}N i=1. An assorter A assigns a number A(bi) ≡ xi ∈ [0, u] to ballot card bi [18] and the value A(ci) to CVR i. The value an assorter assigns to a card depends on the votes on the card, the social choice function, and possibly on the machine interpretation of that card and others (for comparison audits). Stark [18] describes how to define a set of assorters for many social choice functions (including majority, multiwinner majority, supermajority, Borda count, approval voting, all scoring rules, D'Hondt, STAR-Voting, and IRV) such that the reported winner(s) really won if the mean of every assorter in the set is greater than 1/2. The claim that an assorter mean is > 1/2 is called an *assertion*. An RLA with risk limit α confirms the outcome of a contest if it rejects the *complementary null* that the assorter mean is ≤ 1/2 at significance level α for every assorter relevant to that contest.

In a stratified audit, the population of ballot cards is partitioned into K disjoint *strata*. Stratum k contains Nk ballot cards, so N = - k Nk. The *weight* of stratum k is wk := Nk/N; the weight vector is *w* := [w1, ..., wK] T . For each assorter A there is a set of assorter values {xi}N i=1. Each assorter may have its own upper bound uk in stratum k. 1 The true mean of the assorter values in stratum k is μk; *μ* := [μ1, ..., μK] T . The overall assorter mean is

$$\mu := \frac{1}{N} \sum\_{i=1}^{N} x\_i = \sum\_{k=1}^{K} \frac{N\_k}{N} \mu\_k = w^T \mu.$$

Let *θ* = [θ1, ..., θK] T with 0 ≤ θk ≤ uk. A single *intersection null* is of the form *μ* ≤ *θ*, i.e., ∩K k=1{μk ≤ θk}. The *union-intersection form* of the *complementary null* that the outcome is incorrect is:

$$H\_0: \bigcup\_{\theta: w^T \theta \le \frac{1}{2}} \bigcap\_{k=1}^K \{\mu\_k \le \theta\_k\}. \tag{1}$$

1 The notation we use does not allow u to vary by draw, but the theory in Stark [19] permits it, and it is useful for batch-comparison audits.

From stratum k we have nk samples Xnk k := {X1k, ..., Xnkk} drawn by simple random sampling, with or without replacement, independently across strata. Section 3.3 shows how to use single-stratum hypothesis tests (of the the null μk ≤ θk) to test (1). First, we show how to write stratified comparison audits in this form.

## **3.2 Stratified Comparison Audits**

In SHANGRLA, comparison audits involve translating the original assertions about the true votes into assertions about the reported results and discrepancies between the true votes and the machine's record of the votes [18, Section 3.2]. For each assertion, the corresponding *overstatement assorter* assigns ballot card bi a bounded, nonnegative number that depends on the votes on that card, that card's CVR, and the reported results. The original assertion is true if the average of the overstatement assorter values is greater than 1/2.

We now show that for stratified audits, the math is simpler if, as before, we assign a nonnegative number to each card that depends on the votes and reported votes, but instead of comparing the average of the resulting list to 1/2, we compare it to a threshold that depends on the hypothesized stratum mean θk.

Let uA k be the upper bound on the original assorter for stratum k and ωik := A(cik) − A(bik) ∈ [−uA k , uA k ] be the *overstatement* for the ith card in stratum k, where A(cik) is the value of the assorter applied to the CVR and A(bik) is the value of the assorter for the true votes on that card. Let A¯b k, A¯c k, and w¯k = A¯c k − A¯b k be the true assorter mean, reported assorter mean, and average overstatement, all for stratum k.

For a particular *θ*, the intersection null claims that in stratum k, A¯b k ≤ θk. Adding uA k − A¯c k to both sides of the inequality yields

$$
u\_k^A - \bar{\omega}\_k \le \theta\_k + \boldsymbol{u}\_k^A - \bar{A}\_k^c.$$

Letting uk := 2uA k , take Bik := uA k −ωik ∈ [0, uk] and B¯k := 1 Nk -Nk i=1 Bik. Then {Bik} is a bounded list of nonnegative numbers, and the assertion in stratum k is true if B¯k > βk := θk + uA k − A¯c k, where all terms on the right are known. Testing whether B¯ ≤ βk is the canonical problem solved by ALPHA [19]. The intersection null can be written

$$
\bar{B}\_k \le \beta\_k \quad \text{for all} \quad k \in \{1, \dots, K\}.
$$

Define *u* := [u1,...,uK] T . As before, we can reject the complementary null if we can reject *all* intersection nulls *θ* for which **0** ≤ *θ* ≤ *u* and *w*T *θ* ≤ 1/2.

#### **3.3 Union-intersection Tests**

A union-intersection test for (1) combines evidence across strata to see whether any intersection null in the union is plausible given the data, that is, to check whether the P-value of any intersection null in the union is greater than the risk limit.

Consider a fixed vector *θ* of within-stratum nulls. Let P(*θ*) be a valid Pvalue for the intersection null *μ* ≤ *θ*. Many functions can be used to construct P(*θ*) from tests in individual strata; two are presented below. We can reject the union-intersection null (1) if we can reject the intersection null for all feasible *θ* in the half-space *w*T *θ* ≤ 1/2. Equivalently, P(*θ*) maximized over feasible *θ* is a P-value for (1):

$$P^\* := \max\_{\theta} \left\{ P(\theta) : \mathbf{0} \le \theta \le u \right\} \text{ and } \left. w^T \theta \le 1/2 \right\}.$$

This method is fully general in that it can construct a valid P-value for (1) from stratified samples and any mix of risk-measuring functions that are individually valid under simple random sampling. However, the tractability of the optimization problem depends on the within-stratum risk-measuring functions and the form of P used to pool risk. So does the efficiency of the audit.

We next give two valid combining rules P(*θ*). Section 3.6 presents some choices for within-stratum risk measurement to construct P(*θ*).

#### **3.4 Combining Functions**

Ottoboni et al. [11] and Stark [18] calculate P for the intersection null using Fisher's combining function. Let pk(θk) be a P-value for the single-stratum null H0k : μk ≤ θk. Define the pooling function

$$P\_F(\theta) := 1 - \chi\_{2K}^2 \left( -2 \sum\_{k=1}^K \log p\_k(\theta\_k) \right),$$

where χ2 2K is the CDF of the chi-squared distribution with 2K degrees of freedom. The term inside the CDF, −2 -K k=1 log pk(θk), is Fisher's combining function2. Because samples are independent across strata, {pk(θk)}K k=1 are independent random variables, so Fisher's combining function is dominated by the chi-squared distribution with 2K degrees of freedom [11]. The maximum over *θ*, P∗ F , is a valid P-value for (1).

#### **3.5 Intersection Supermartingales**

Stark [19] derives a simple form for the P-value for an intersection null when supermartingales are used as test statistics within strata. Let Mk nk (θk) be a supermartingale constructed from nk samples drawn from stratum k when the null μk ≤ θk is true. Then the product of these supermartingales is also a

2 Other combining functions could be used, including Liptak's or Tippett's. See Chap. 4 of Pesarin and Salmaso [12].

supermartingale under the intersection null, so its reciprocal (truncated above at 1) is a valid P-value [19,23]:

$$P\_M(\theta) := 1 \wedge \prod\_{k=1}^K M\_{n\_k}^k(\theta\_k)^{-1}.$$

Maximizing PM(*θ*) (equivalently, minimizing the intersection supermartingale) yields P∗ M, a valid P-value for (1).

# **3.6 Within-Stratum** *P* **-values**

The class of within-stratum P-values that can be used to construct PF is very large, but PM is limited to functions that are supermartingales under the null. Possibilities include:

We compare the efficiency of these risk-measuring functions in Sects. 4.1 and 4.2.

# **3.7 Sequential Stratum Selection**

The use of sequential sampling in combination with stratification presents a new possibility for reducing workload: sample more from strata that are providing evidence against the intersection null and less from strata that are not helping. To set the stage, suppose we are conducting a ballot-polling audit with two strata of equal size and testing the intersection null *θ* = [0.25, 0.75]T . We have drawn 50 ballot cards from each stratum and found sample assorter means of [0.5, 0.6]T . Given the data, it seems plausible that drawing more samples from the first stratum will strengthen the evidence that μ1 > 0.25, but additional sampling from the second stratum might not provide evidence that μ2 > 0.75: to reject the intersection null, it might help to draw disproportionately from the first stratum. Perhaps suprisingly, such adaptive sampling yields valid inferences when the P-value is constructed from supermartingales and the stratum selection function depends only on past data. We now sketch why this is true.

For t ∈ N and a particular vector of hypothesized stratum means *θ*, let

$$\kappa\_t(\theta) \in \{1, \ldots, K\}$$

denote the stratum from which the t-th sample was drawn for testing the hypothesis *μ* ≤ *θ*. We call κ(*θ*) := (κt(*θ*))t∈N the *stratum selector* for null *θ*. Crucially, κ(*θ*) is a *predictable sequence* with respect to (Xt)t∈N in the sense that κt(*θ*) can depend on Xt−1 := {X1,...,Xt−1} but not on Xi for i ≥ t; it could be deterministic given Xt−1 or may also depend on auxiliary randomness.

For example, a stratum selector could ignore past data and select strata in a deterministic round-robin sequence or at random with probability proportional to stratum size. Alternatively, a rule might select strata adaptively, for instance picking a stratum at random with probability proportional to the current value of each within-stratum supermartingale, so that strata with larger Mk tk (θk) are more likely to be chosen—an "exploration–exploitation" strategy. In what follows we suppress the dependence on *θ* except when it is explicitly required for clarity.

Now, let Mκ t (*θ*) := t i=0 Zi be the test statistic for testing the null hypothesis that the vector of stratumwise means is less than or equal to *θ*. This is a supermartingale if the individual terms Zi satisfy a simple condition. Let Z0 = 1 and Zi ≥ 0 for all i. If

$$\mathbb{E}\_{\theta} \left[ Z\_t | X^{t-1} \right] \le 1,\tag{2}$$

then (Mκ t (*θ*))t∈N0 is a nonnegative supermartingale starting at 1 under the null. By Ville's inequality [21], the thresholded inverse (1 ∧ Mκ t (*θ*)−1)t∈N0 is an anytime P-value sequence when *μ* ≤ *θ*.

Condition (2) holds if the Zi are terms extracted from a set of within-stratum supermartingales using a predictable stratum selector: Let

$$\nu\_t^\kappa := \#\{i \le t : \kappa\_i = \kappa\_t\}\tag{3}$$

be the number of draws from stratum k as of time t. Suppose that for k ∈ {1,...,K}, Mk t (θk) := t i=1 Y k i (θk) is a nonnegative supermartingale starting at 1 when Xik is the ith draw from stratum k and the kth stratum mean is μk ≤ θk. Then if

$$Z\_i := Y\_{\nu\_i^{\kappa}}^{\kappa\_i}(\theta\_{\kappa\_i}), \tag{4}$$

condition (2) holds and the interleaved test statistic Mκ t (*θ*) is an intersection supermartingale under the null. We compare two stratum selection rules in Sect. 4.1.

# **4 Evaluations**

### **4.1 Combination and Allocation Rules**

We simulated a variety of two-stratum ballot-level comparison audits at risk limit α = 5%, with assorters defined as in Sect. 3.2. The strata each contained Nk = 1000 ballot cards, all with valid votes. Cards were sampled without replacement. The stratum-wise true margins were [0%, 20%], [0%, 10%] or [0%, 2%], corresponding to global margins of 10%, 5%, and 1%, respectively. Stratum-wise reported margins were also [0%, 20%], [0%, 10%] or [0%, 2%], so error was always confined to the second stratum. Each reported margin was audited against each true margin in 300 simulations. Risk was measured by ALPHA or EB combined either as intersection supermartingales (P∗ M) or with Fisher's combining function (P∗ F ), with one of two stratum selectors: proportional allocation or lower-sided testing.

In proportional allocation, the number of samples from each stratum is in proportion to the number of cards in the stratum. Allocation by lower-sided testing involves testing the null μk ≥ θk sequentially at level 5% using the same supermartingale (ALPHA or EB) used to test the main (upper-sided) hypothesis of interest. This allocation rule ignores samples from a given stratum once the lower-sided hypothesis test rejects, since there is strong evidence that the null is true in that stratum. This "hard stop" algorithm is unlikely to be optimal, but it leads to a computationally efficient implementation and illustrates the potential improvement in workload from adaptive stratum selection.

Tuning parameters were chosen as follows. ALPHA supermartingales were specified either with τik as described in Stark [19, Section 2.5.2] (ALPHA-ST, "shrink-truncate") or with a strategy that biases τik towards uk: (ALPHA-UB, "upward bias"). The ALPHA-UB strategy helps in comparison audits because the distribution of assorter values consists of a point mass at uk A = uk/2 and typically small masses (with weight equal to the overstatement rates) at 0 and another small value. This concentration of mass makes it advantageous to bet more aggressively that the next draw will be above the null mean; that amounts to biasing τik towards the upper bound uk. Before running EB, the population and null were transformed to [0,1] by dividing by uk. The EB supermartingale parameters λik were then specified following the "predictable mixture" strategy [22, Section 3.2], truncated to be below 0.75. Appendix A gives more details of the ALPHA-ST and ALPHA-UB strategies and the computations.

Sample size distributions for some combinations of reported and true margins are plotted in Fig. 1 as (simulated) probabilities of stopping at or before a given sample size. Table 1 gives estimated expected and 90th percentile sample sizes for each scenario and method. Table 2 lists aggregate scores, computed by finding the ratio of the workload for each method over the smallest workload in each scenario, then averaging over scenarios by taking the geometric mean of these ratios.

Intersection supermartingales tend to dominate Fisher pooling unless the stratum selector is chosen poorly (e.g., the bottom-right panel of Fig. 1 and the

**Fig. 1.** Probability that the audit will stop (y-axis) at or before different given sample sizes (x-axis) under different allocation rules (indicated by line color: orange for lowersided testing and blue for proportional allocation) for different combining functions (indicated by line type: solid for Fisher's combining function and dashed for the intersection supermartingale) at risk limit α = 5%. The true margins are in the rows (1% or 5%) while the reported margin is always 10%. Overstatement errors are confined to one stratum. ALPHA-ST = ALPHA with shrink-truncate τ*ik*; ALPHA-UB = ALPHA with τ*ik* biased towards u*k*.

last row of Table 2). Stratum selection with the lower-sided testing procedure is about as efficient as proportional allocation for the ALPHA supermartingales, but far more efficient than proportional allocation for EB. The biggest impact of the allocation rule occurred for EB combined by intersection supermartingales when the reported margin was 0.01 and the true margin was 0.1: proportional allocation produced an expected workload of 752 cards, while lower-sided testing produced an expected workload of 271 cards—a 74% reduction. Table 2 shows that ALPHA-UB with intersection supermartingale combining and lower-sided testing is the best method overall; ALPHA-UB with intersection combining and proportional allocation is a close second; EB with intersection combining and lower-sided testing is also relatively sharp; ALPHA-ST with Fisher combining is least efficient.

We also ran simulations at risk limits 1% and 10%, which did not change the relative performance of the methods. However, compared to a 5% risk limit, **Table 1.** Expected and 90th percentile sample sizes for various risk-measurement functions, reported margins, and true margins, estimated from 300 simulated audits at risklimit α = 5%. The best result for each combination of reported margin, true margin, and summary statistic is highlighted. Comparison audit sample sizes are deterministic when there is no error, so the expected value and 90th percentile are equal when the reported and true margins are equal.

a 10% risk limit requires counting about 17% fewer cards and a 1% risk limit requires about 38% more, on average across scenarios and methods.

**Table 2.** Score for each method: the geometric mean of the expected workload over the minimum expected workload in each scenario. A lower score is better: a 1.00 would mean that the method always had the minimum expected workload. The best score is highlighted. A score of 2 means that workloads were twice as large as the best method, on average, across simulations and scenarios.

## **4.2 Comparison to SUITE**

SUITE was used in a pilot RLA of the 2018 gubernatorial election in Michigan [7]. Three jurisdictions—Kalamazoo, Rochester Hills, and Lansing—were audited, but only Kalamazoo successfully ran a hybrid audit. We recalculated the risk on audit data from the closest race in Kalamazoo (Whitmer vs Schuette) using ALPHA with the optimized intersection supermartingale P-value P∗ M, ALPHA with the optimized Fisher P-value P∗ F , EB with P∗ F , and EB with P∗ M, and compared these with the SUITE P-value. Because we could not access the original order of sampled ballots in the ballot-polling stratum, we simulated Pvalues for 10,000 random ballot orders with the marginal totals in the sample. We computed the mean, standard deviation, and 90th percentile of these P-values for each method.

To get the ALPHA P-values, we used ALPHA-UB in the CVR stratum and ALPHA-ST in the no-CVR stratum. For EB P-values, we used the predictable mixture parameters of Waudby-Smith and Ramdas [22] to choose λik, truncating at 0.75 in both strata. Sample allocation was dictated by the original pilot audit: 8 cards from the CVR stratum (5,294 votes cast; diluted margin 0.55) and 32 from the no CVR stratum (22,732 votes cast; diluted margin 0.57).

Table 3 presents P-values for each method. For ALPHA, the mean P∗ F is about half the SUITE P-value; for P∗ M, the mean is more than an order of magnitude smaller than the SUITE P-value. The P-value distributions for ALPHA are concentrated near the mean. On the other hand, the EB P∗ M and P∗ F Pvalues are both an order of magnitude larger than the SUITE P-value and their distributions are substantially more dispersed than the distributions of ALPHA P-values.

**Table 3.** Measured risks (P-values) computed from the 2018 Kalamazoo MI audit data. For SUITE, the original P-value is shown. For replications, the mean, standard deviation (SD), and 90th percentile of P-values in 10,000 reshufflings of the sampled ballot-polling data are shown.

### **4.3 A Highly Stratified Audit**

As mentioned in Sect. 3.6, many within-stratum risk-measuring functions do not yield tractable expressions for PF (*θ*) or PM(*θ*) as a function of *θ*, making it hard to find the maximum P-value over the union unless K is small. Indeed, previous implementations of SUITE only work for K = 2. However, the combined log-Pvalue for EB is linear in *θ* for P∗ M and piecewise linear for P∗ F . Maximizing the combined log-P-value over the union of intersections is then a linear program that can be solved efficiently even when K is large.

To demonstrate, we simulated a stratified ballot-polling audit of the 2020 presidential election in California, in which N = 17, 500, 881 ballots were cast across K = 58 counties (the strata), using a risk limit of 5%. The simulations assumed that the reported results were correct, and checked whether reported winner Joseph R. Biden really beat reported loser Donald J. Trump. The audit assumed that every ballot consisted of one card; workloads would be proportionately higher if the sample were drawn from a collection of cards that includes some cards that do not contain the contest. Sample sizes were set to be proportional to turnout, plus 10 cards, ensuring that at least 10 cards were sampled from every county. Risk was measured within strata by EB with predictable mixture λik thresholded at 0.9 [22]. Within-stratum P-values were combined using P∗ F (P∗ M did not work well for EB with proportional allocation in simulations). To approximate the distribution of sample sizes needed to stop, we simulated 30 audits at each increment of 5,000 cards from 5,580 to 100,580 cards. We then simulated 300 audits at 70,580 cards, roughly the 90th percentile according to the smaller simulations.

In 91% of the 300 runs, the audit stopped by the time 70,580 cards had been drawn statewide. Drawing 70,580 ballots by our modified proportional allocation rule produces within-county sample sizes ranging from 13 (Alpine County, with the fewest voters) to 17,067 (Los Angeles County, with the most). A comparison or hybrid audit using sampling without replacement would presumably require inspecting substantially fewer ballots. It took about 3.5 s to compute each P-value in R (4.1.2) using a linear program solver from the lpSolve package (5.6.15) on a mid-range laptop (2021 Apple Macbook Pro).

# **5 Discussion**

ALPHA intersection supermartingales were most efficient compared to the SUITE pilot audit in Michigan and in simulations. Lower-sided testing allocation was better than proportional allocation, especially for EB. Fisher pooling limits the damage that a poor allocation rule can do, but is less efficient than intersection supermartingales with a good stratum selection rule. For comparison audits, it helps to bet more aggressively than ALPHA-ST by using ALPHA-UB or EB. However, EB was not efficient compared to SUITE when replicating the Michigan hybrid audit due to poor performance in the ballot-polling stratum.

Our general recommendation for hybrid audits is: (i) use an intersection supermartingale test with (ii) adaptive stratum selection and (iii) ALPHA-UB (or another method that can exploit low sample variance to bet more aggressively) as the risk-measuring function in the comparison stratum and (iv) ALPHA-ST (or a method that "learns" the population mean) as the riskmeasuring function in the ballot-polling stratum. When the number of strata is large, audits can leverage the log-linear form of the EB supermartingale to quickly find the maximum P-value, as illustrated by our simulated audit spread across California's 58 counties.

In future work, we hope to construct better stratum allocation rules and characterize (if not construct) optimal rules. The log-linear structure of the EB supermartingale may make it simpler to derive optimal allocation rules.

While stratum selection is not an instance of a traditional multi-armed bandit (MAB) problem, there are connections, and successful strategies for MAB might help. For instance, stratum selection could be probabilistic and involve continuous exploration and exploitation, in contrast to the "hard stop" rules we used in our simulations here.

# **A Computational details**

The following describes details of the allocation simulations in Sect. 4. Within each stratum, we computed null means along an equispaced grid of (2 max{N1, N2}) points3 for θ1 ∈ [ε1, θ/w1 − ε1] with θ2 = (θ − w1θ1)/w2. The

3 The cardinality was chosen so that a null mean was computed for every possible (discrete) value of θ*k*. A finer grid is unnecessary; a coarser grid may not find the true minimum.

null means were then adjusted to β1 := θ1 + 1 − A¯c 1 and β2 := θ1 + 1 − A¯c 2. The conditional null means βi1 and βi2 were computed as:

$$\beta\_{ik} = \frac{N\_k \beta\_k - \sum\_{j=1}^{i-1} X\_{ik}}{N\_k - (i-1)}$$

Tuning parameters for ALPHA-ST were chosen as in Stark [19, Section 2.5.2] with dk = 20 and the initial estimate τ0k set to uA k = 1, the expected mean when there is no error in the CVRs. For ALPHA-UB, we set

$$
\tau\_{ik}^{\mathrm{UB}} := \frac{(d\_k \tau\_{0k} + \sum\_{j=1}^{i-1} X\_{jk})/(d\_k + i - 1) + f\_k u\_k/\hat{\sigma}\_{ik}^2}{1 + f\_k/\hat{\sigma}\_{ik}^2}.
$$

The first term in the numerator of τ UB ik is truncated shrinkage estimator ALPHA-ST. The second term biases τ UB ik towards uk with a weight proportional to the inverse running sample variance ˆσ2 ik. The constant of proportionality fk is a tuning parameter set to fk := .01; higher fk would bias τik towards uk more aggressively. The variance-dependent bias amounts to betting more when the population variance is low, which it tends to be in comparison audits when the voting system works properly. Truncation keeps τik within its allowed range.

For both ALPHA strategies, τik was truncated to be in [βik + εk, uk(1 − δ)], where εk := 1/2Nk was the minimum value of one assorter and δ = 2.220446 × 10−16 was machine precision. If βik + εk ≥ uk, we set the corresponding terms in the supermartingale to 1: that (composite) null is true.

Each stratum selection rule was applied to every supermartingale. For proportional allocation, there was no additional selection: samples were gathered round-robin across strata, omitting any strata that were fully exhausted. For lower-sided testing, the sampling from a stratum ceased when the lower-sided test rejected at level .05. This was implemented by setting all future terms in the supermartingale equal to 1 after rejection. The stratumwise supermartingales were then multiplied to produce 2 max{N1, N2} intersection supermartingales and their minimum (over nulls) was found at each sample size. The reciprocal of this minimized intersection supermartingale was a sequence of P-values corresponding to P∗ M under a particular sample allocation rule. The same strategy, but using Fisher pooling, was used to find P∗ F . The sample size at risk limit α = 5% is the sample size for which the P-value sequence first hits or crosses 0.05, summed across both strata.

# **B Data and Code**

All code used in this paper is available at https://github.com/spertus/sweeterthan-SUITE. SUITE was applied to the Michigan RLA data in a Jupyter notebook available at https://github.com/kellieotto/mirla18. Reported results from California's 2020 presidential election are available at https://elections.cdn.sos. ca.gov/sov/2020-general/sov/csv-candidates.xlsx.

# **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

# **They May Look and Look, Yet Not See: BMDs Cannot be Tested Adequately**

Philip B. Stark1(B) and Ran Xie2

1 University of California, Berkeley, CA, USA<EMAIL_ADDRESS>
2 Stanford University, Stanford, CA, USA

**Abstract.** Bugs, misconfiguration, and malware can cause ballotmarking devices (BMDs) to print incorrect votes. Several approaches to testing BMDs have been proposed. In *logic and accuracy testing* (LAT) and *parallel* or *live* testing, auditors input known test votes into the BMD and check whether the printout matches. *Passive* testing monitors the rate at which voters "spoil" BMD printout, on the theory that if BMDs malfunction, the rate will increase noticeably. We provide lower bounds that show that these approaches cannot reliably detect outcomealtering problems, because: (i) The number of possible voter interactions with BMDs is enormous, so testing interactions uniformly at random is hopeless. (ii) To probe the space of interactions intelligently requires an accurate model of voter behavior, but because the space of interactions is so large, building a sufficiently accurate model requires observing an enormous number of voters in every jurisdiction in every election—more voters than there are in most U.S. jurisdictions. (iii) Even with a perfect model of voter behavior, the required number of tests exceeds the number of voters in most U.S. jurisdictions. (iv) An attacker can target interactions that are intrinsically expensive to test, e.g., because they involve voting slowly; or interactions for which tampering is less likely to be noticed, e.g., because the voter uses the audio interface. (v) Whether BMDs misbehave or not, the distribution of spoiled ballots is unknown and varies by election and possibly by ballot style: historical data do not help much. Hence, there is no way to calibrate a threshold for passive testing, e.g., to guarantee at least a 95% chance of noticing that 5% of the votes were altered, with at most a 5% false alarm rate. (vi) Even if the distribution of spoiled ballots were known to be Poisson, the vast majority of jurisdictions do not have enough voters for passive testing to have a large chance of detecting problems but only a small chance of false alarms.

**Keywords:** Logic and accuracy testing · Parallel testing · Live testing

# **1 Introduction**

BMDs print votes, often as barcodes or QR codes, together with a humanreadable text summary (some BMD printout resembles a hand-marked paper ballot, HMPB). Jurisdictions including the U.S. state of Georgia, Los Angeles County, California, and Philadelphia, Pennsylvania, recently purchased BMDs for all in-person voters to use.

Bugs, misconfiguration, or malware can make the printed votes and QR codes differ from each other and from the voter's selections. Some have argued that this does not compromise election integrity because voters have the opportunity to inspect BMD printout and to start over if the printout does not match their intended selections; and that since voters can make mistakes hand-marking ballots, HMPBs are no more secure or reliable than BMD printout [19]. We find those arguments unpersuasive:

Concerns about BMDs are not merely hypothetical: BMDs have caused scanners to fail to count votes accurately, to allow voters to vote, and to present all voting options to voters, even after passing LAT [4,6,9,15,18,20,23,24,30,33].

BMD advocates also claim BMDs eliminate ambiguous marks, prevent overvotes, and warn about undervotes (e.g., [19]). But that presumes BMDs function correctly; the rate of truly ambiguous handmade marks is minuscule [1]; and precinct-based optical scanners also protect against undervotes and overvotes (the Voluntary Voting Systems Guidelines, VVSG, require it).2 Regardless, elections conducted using BMDs are not trustworthy unless there is a way to ensure that BMD misbehavior did not change any outcome. (If the paper trail itself is not trustworthy, risk-limiting audit procedures do not help because even an accurate full hand count may not reveal who really won.) Elections—and hence BMDs—need to be protected against malicious, technically capable attackers, such as nation states.3 If testing has a high chance of detecting that an outcome

1 See https://rules.sos.ga.gov/gac/183-1-15-.03?urlRedirected=yes&data=admin& lookingfor=183-1-15-.03 (last visited 5 May 2022). Audits in Georgia rely on the human-readable text, but legally cannot correct outcomes, and are conducted only for one contest every two years.

2 Such protection has been required since VVSG 1.0; see Sect. <IP_ADDRESS> of [27].

3 The U.S. Senate Intelligence Committee, the Department of Homeland Security, and the FBI concluded that Russian state hackers attacked U.S. elections in 2016 [31].

was altered by a skilled attacker, it also protects against misconfiguration and bugs—which attackers could mimic.

# **2 Prior Work**

Vulnerabilities of particular BMDs are discussed in depth in expert declarations by J. Alex Halderman in *Curling et al. v. Raffensperger et al.*. Theoretical vulnerabilities of various BMD designs are discussed in [1]. [7,32] discuss testing BMDs; here, we quantitatively investigate their heuristic claims. Three approaches to testing BMDs have been proposed: pre-election logic and accuracy testing (LAT), "live" or "parallel" testing during the election, and "passive" testing by monitoring the spoiled ballot rate. In LAT and parallel testing, auditors make selections on a BMD then check whether the printout accurately reflects those selections. The primary difference is that LAT happens before the election and parallel testing happens during the election. *Passive* testing uses the spoiled ballot rate: if more voters than usual request a do-over, that might be because the machines are malfunctioning.

# **3 How Much Testing is Enough?**

If the paper trail accurately reflects who won, accurate full hand counts and risklimiting audits (RLAs) can catch and correct wrong outcomes. Here, we study whether testing can establish with high confidence that a paper trail printed by BMDs accurately reflects who won. If not, a recount need not show who really won, and a genuine RLA is impossible.

# **3.1 Threats and Defenses**

We make the following assumptions about BMD threats and defenses:

#### **3.2 Jurisdiction Sizes, Contest Sizes, and Margins**

U.S. elections are typically administered by counties, townships, or other political units smaller than states. A *ballot style* corresponds to the collection of contests a given voter is eligible to vote in. Typically in the U.S., some contests are on only a fraction of ballot styles in a jurisdiction, in part because many small political units have elections for various offices and measures. Many contests of all sizes are decided by small margins. For instance, in Georgia, U.S., the reported margin in the 2020 presidential election was about 0.2%.

Few votes need to be changed to alter the outcome of small contests and contests with small margins. Conversely, the number of voters in a jurisdiction is an upper bound on the number of passive tests that can be performed and on the sample size to "learn" voter behavior for efficient parallel testing. Thus, jurisdiction size is an important constraint on BMD testing. Since ballot layout, contests, equipment, demographics, political preferences, and other variables vary across and within jurisdictions and malware could affect only some equipment or ballot styles, it is not possible to pool data across jurisdictions to get more power.

Changing votes on 1% of ballots in a jurisdiction can alter the margin of a jurisdiction-wide plurality contest by 2% if there are no undervotes or invalid votes in that contest. If the undervote rate is 30%, then changing votes on 1% of the ballots can change the margin by 0.02/0.7=2.9%. If a contest is only on 10% of the ballots and the undervote rate in the contest is 30%, altering the votes on 1% of ballots could change the margin in that contest by nearly 29%.

As of 2020, only 1,629 U.S. cities had populations of 100,000 or more, of over 81,363 incorporated places [26]. The 2020 median population of U.S. incorporated areas is 1,201, so about half of the 81,363 incorporated places have turnout of 1,201 or fewer voters. Thus, an attacker does not have to change many votes to alter the outcome of a typical contest for an elected official in a U.S. city or incorporated township. According to [29] the 2020 median turnout in the 6,405 U.S. counties with recorded active voter data was 4,470 voters, and turnout was less than 11,500 voters for more than 2/3 of jurisdictions. In 65.5% of states, more than 50% of counties have fewer than 30,000 active voters. In 85.5% of states, more than 50% of counties have fewer than 100,000 active voters.

#### **3.3 Voting Transactions**

We shall call a voter's interaction with a BMD a *voting transaction* or *transaction* (see Table 1). Transactions are characterized by many variables, including:

**Fig. 1.** 2020 turnout by jurisdiction in 3073 counties [29]. Turnout was below 10,000 in ≈50% of counties.

**Fig. 2.** Median 2020 turnout by jurisdiction in the U.S. [29]

Table 1 lists some of the variables and the number of values they can take.4 The huge number of possible transactions helps an attacker pick a subset large enough to change an outcome but that auditors are unlikely to probe.

4 Table 1 assumes all contests are "vote-for-one." Ranked-choice voting and multiwinner plurality contests yield more possible transactions. Continuous variables were binned into a few options. VVSG 1.1 [28] requires: (a) Alternative language access is mandated under the Voting Rights Act of 1975, subject to certain thresholds (e.g., if the language group exceeds 5% of the voting age population). (b) The voting system shall provide the voter the opportunity to correct the ballot for either an undervote or overvote before the ballot is cast and counted. (c) An Acc-VS with a color electronic image display shall allow the voter to adjust the color saturation throughout the transaction while preserving the current votes.  (e) A voting system that uses an electronic image display shall be capable of showing all information in at least two font sizes. (f) The audio system shall allow the voter to control the volume throughout the voting transaction while preserving the current votes. (g) The volume shall be adjustable from a minimum of 20dB SPL up to a maximum of 100 dB SPL, in increments no greater than 10 dB. (h) The audio system shall allow the voter to control the rate of speech throughout the voting transaction while preserving the current votes. (i) The range of speeds supported shall include 75% to 200% of the nominal rate.

**Table 1.** Some parameters of BMD transactions and their number of possible values.

# **4 Passive Testing**

Passive testing sounds an alarm if the number of spoiled ballots exceeds some threshold, t. To ensure that passive testing has a false negative rate (failing to detect altered outcomes) of at most X%, we need to know that the chance that the number of spoiled ballots is greater than or equal to t is at least X% if BMDs altered any outcome. Conversely, to limit the false alarm rate to at most Y %, we need to know that the chance that the number of spoiled ballots is greater than or equal to t is at most Y % if BMDs function correctly.

Finding such a value of t is impossible in practice because the distribution of spoiled ballots may depend on ballot design, voting rules, the number of contests, and other things that vary from election to election and place to place and when BMDs misbehave, also on the number of altered transactions, and the voters and contests affected. Hence, to lower-bound the difficulty, we will assume (optimistically) that the number of spoiled ballots has a Poisson distribution whether BMDs behave correctly or not; but with a rate that depends on the rate of altered transactions. We assume either that 7% of voters will notice errors and spoil their ballots, consistent with the findings of [3], or that 25% of voters will. We consider contest margins of 1%–5% and rates of false positives (false alarms) and false negatives (failing to notice altered outcomes) of 5% and 1%. Results are in Table 2; software to calculate these numbers is in https:// github.com/pbstark/Parallel19.

Combining Table 2 and Fig. 1 shows that even if the probability distribution of spoiled ballots were known to be Poisson and the spoilage rate when equipment functions correctly were known perfectly, in 2020, in 58.2% of U.S. states fewer than half the counties had enough voters for passive testing to work, even in county-wide contests, on the assumption that 7% of voters whose votes are altered will spoil their ballots.

If turnout is roughly 50%, jurisdiction-wide contests in jurisdictions with fewer than 60,000 voters—22 of California's 58 counties in 2020 [29]—cannot in **Table 2.** Minimum turnout for passive testing with a 5% false negative rate to have at most a 5% false positive rate (cols 3–5) or for passive testing with a 1% false negative rate to have at most a 1% false positive rate (cols 6–8), as a function of the the contest margin (col 1), the percentage of voters who would notice errors (col 2), and the base rate at which voters spoil BMD printout. The number of spoiled ballots is assumed to have a Poisson distribution, with known rate, absent malfunctions. Malfunctions increase the rate by half the margin times the detection rate.

principle limit the chances of false positives and false negatives to 5% for margins below 4%, even under these optimistic assumptions. For contests that involve only part of a jurisdiction, the situation is worse.

# **4.1 Targeting Vulnerable Voters**

The analysis above assumes that all voters are equally likely to detect errors and spoil their ballots. But an attacker can use BMD settings, state history, and session data to target voters who are less likely to notice problems.

*Voters with Visual Impairments.* Approximately 0.8% of the U.S. population is legally blind; approximately 2% age 16 to 64 have a visual impairment [16]. Current BMDs do not provide voters with visual impairments a way to check the printout. If an attacker only alters votes when the voter uses the audio interface or large fonts, detection may be very unlikely.

*Voters with Motor Impairments.* Some BMDs allow voters to print and cast a ballot without looking at it, for instance the ES&S ExpressVote-R with "Autocast," aka "permission to cheat" [1]. The attacker can change every vote cast using Autocast, with zero chance of detection.

*Voters who use Languages other than English.* U.S. law requires some jurisdictions to provide ballots in languages other than English. For instance, Los Angeles County, CA, provides voting materials in 13 languages [14]. In 2013, roughly 26% of voters in Los Angeles County spoke a language other than English at home [14]. It is our understanding that BMDs generally print only in English. If voters who use a foreign language on the BMD are unlikely to check the Englishlanguage printout, an attacker could change the outcome of contests with large margins with little chance of detection.

*Fast and Slow Voters.* An attacker can monitor how long it takes voters to make their selections, whether they change selections, how long they review the summary screen, etc. A voter who spends little time reviewing selections onscreen may be unlikely to review the printout carefully. Conversely, a voter who takes a very long time to make selections or changes selections repeatedly might find voting difficult or confusing and be unlikely to notice errors.

Thus, it is in the attacker's interest to target the same groups of voters BMDs are supposed to help: voters with visual impairments, voters with limited dexterity, voters who use a language other than English, and voters with cognitive disabilities.

### **4.2 FUD Attacks on Passive testing**

Even under ideal circumstances, passive testing does not produce direct evidence of problems; it does not identify which ballots or contests have errors; and it does not provide any evidence about whether problems changed outcomes. Relying on spoiled ballots as a sign of fraud opens the door to a simple, legal way to undermine elections: encourage voters to spoil ballots.

# **5 LAT and Parallel Testing**

Suppose that malware alters one or more votes with probability p, independently across transactions, uniformly across voters—regardless of the voter's selections or any aspect of the transaction that the attacker can ascertain. Then if auditors make n tests, the chance that the BMD will alter at least one of the votes in at least one of the tests—and the attack will be detected—is 1 − (1 − p)*n*. For p = 0.01, n = 300 tests would give a 95% chance of detecting a problem.

A BMD can handle roughly 140 transactions per day. Testing enough to have a 95% chance of detecting a 1% problem on one BMD would leave no time for voters to use that BMD. Even for pre-election LAT, where capacity for actual voters is not an issue, conducting 300 "typical" tests would take about 25 h.

If there were a large number of machines known to have been (mis)programmed identically, tests could be spread across them. But there are many small contests that need to be tested in conjunction with all other contests that appear on any ballot style that contains them, and there is no guarantee that all BMDs in a jurisdiction are programmed identically.

*This threat model is completely unrealistic*. An attacker who wants Alice to beat Bob will not alter votes for Alice: it would needlessly increase the chance of detection. And as discussed in Sect. 4.1, rather than randomly changing votes for Bob into votes for Alice, an attacker can target transactions that auditors are unlikely to probe.

Setting aside specific machines for testing facilitates a "Dieselgate" type attack [11], as does conducting tests on a schedule, as suggested by [7]. Tests need to be unpredictable—with respect to the specific BMDs tested, time, vote pattern, duration, and other characteristics of voting transactions—or attackers can avoid detection by altering only transactions that do not correspond to any test. There may be pressure to reduce testing when BMDs are busy, to reduce waiting times. Because malware can monitor the pace of voting, reducing testing when machines are busy makes it easier to avoid detection.

An attacker need not alter many transactions to change the outcome of small contests and contests with small margins. The fewer votes altered, the more tests required to ensure a large chance of detection. To test efficiently, tests should sample more common transactions with higher probability. Attackers might be able to estimate of the distribution of transactions using malware installed on BMDs in previous elections, but testers will not, since it involves tracking voter behavior at a level of detail that violates voter privacy. See assumptions 4 and 7 and Sect. 5.2.

Auditors do not know which contest(s) and candidate(s) are affected. To have a large chance of detecting interference, there needs to be a large chance of testing a transaction the attacker alters. Attackers can target transactions that are intrinsically expensive to test, e.g., transactions that take longer than 10 min, transactions in which the voter changes some number of selections, transactions that display the ballot in a language other than English, transactions that use the audio interface at a reduced tempo, etc.

#### **5.1 Lower Bounds on the Difficulty of Parallel Testing**

We now study an idealized version of parallel testing, where auditors can tell whether a random sample of BMD printouts accurately show the voters' selections. Suppose a contest has 4,470 voters, the median jurisdiction turnout in 2020. Suppose that malware alters votes in 23 transactions, which could change a margin by more than 1% in a jurisdiction-wide contest. How many randomly selected printouts would need to be checked to have at least a 95% chance of finding at least one with an error? The answer is the smallest n such that

$$\frac{4470 - 23}{4470} \cdot \frac{4469 - 23}{4469} \cdot \dots \cdot \frac{4470 - (n - 1) - 23}{4470 - (n - 1)} \le 0.05,\tag{1}$$

i.e., n = 546 printouts, about 12.2% of the transactions, corresponding to testing each BMD several times per hour.

Conversely, suppose auditors randomly check 13 printouts per day per machine (on average, testing hourly for a 13-hour day, ≈9.2% of BMD capacity). To have at least a 95% chance of detecting that the outcome of a contest with a 1% margin was altered, there would need to be at least 6,580 voters in the contest (almost 150% the median turnout in jurisdictions across the U.S.), corresponding to 47 BMDs, even under these unrealistically optimistic assumptions.

#### **5.2 Building a Model of Voter behavior**

In practice, auditors cannot check whether voters' BMD printout is correct. Instead of sampling voters' actual transactions in the election, they will have to come up with their own test transactions. Testing transactions uniformly at random from all possible transactions is doomed because the number of possible transactions is so large. To mimic voters, auditors might consider sampling from P, the population distribution of voting transactions, i.e., the fraction of voters who use the BMD in each of the S = 6.14 × 106 ways in the optimistic estimate in Table 1. Suppose an attacker wants to change the outcome of a contest with a margin of m, expressed as a fraction of ballots cast (rather than as a number of votes). The attacker only needs to change a fraction m/2 of the transactions to change the margin by m. To have probability at least 1−α of detecting a change to the outcome of any contest with true margin m, auditors must test in a way that has probability at least 1−α of sampling at least once from every subset of transactions that contains a fraction m/2 of the transactions. If auditors could sample transactions independently at random from P, each sample transaction would have probability 1 − m/2 of *not* being one of the altered transactions. The chance that t randomly selected transactions would not include one that is altered would be (1 − m/2)*t* . Thus the number of transactions auditors would need to test is the smallest t for which

$$(1 - m/2)^t \le \alpha, \text{ i.e.,} \tag{2}$$

$$t \ge \frac{\log \alpha}{\log(1 - m/2)}.\tag{3}$$

This is essentially Eq. 1 for sampling with replacement; the two are indistinguishable when t is small compared to the total number of possible transactions. A key difference is that in Eq. 1, auditors are sampling from the actual transactions in the election, while in Eq. 3, auditors are sampling from a model, the frequency distribution of of transactions.

In practice, the auditors do not know P—they will have to estimate it by monitoring voters. In reality, this is impossible to do well: (i) In a given election, P will depend on the particular contests on the ballot and the particular voters who participate, both of which change from election to election. (ii) The variables that characterize a voting transaction include the voter's selections and details about how the voter uses the BMD, so collecting the data would violate voter privacy illegally. To get a sense of the *statistical* difficulty of the problem, we ignore these practical difficulties. If auditors could select voters at random (with replacement) and observe in detail how they use the BMD—all the variables in Table 1—that would yield independent, identically distributed (IID) draws from P, which could be used to make an estimate, Pˆ. If Pˆ differs too much from P, no number of tests will suffice, because Pˆ might estimate that the frequency of a transaction is zero when in fact it is sufficiently frequent that altering it could change an outcome. (By assumption 4, above, the attacker knows P and hence can exploit differences between Pˆ and P.) How many voters would auditors have to observed to ensure (with sufficiently high probability) that Pˆ is accurate enough for parallel testing?

The L1 distance between two distributions bounds the difference in the probability they assign to any set (|Pˆ(A) − P(A)|≤Pˆ − P1/2). If Pˆ − P1 ≥ m, there may be a set A of transactions for which P(A) = m/2 but Pˆ(A) = 0, so changing votes for transactions in A could alter some margin5 by m, with zero chance of detection, no matter how many tests are performed, if the tests are drawn from Pˆ rather than P.

We cannot guarantee that Pˆ − P1 ≤ ε with *certainty*, but by observing enough randomly selected voters, we can ensure that the chance that Pˆ−P1 > ε is at most β. If α ≤ β, even an infinite number of tests drawn from Pˆ may not suffice to guarantee chance at least 1 − α of detecting outcome-changing manipulations. If α>β, to guarantee chance at least 1 − α of catching an outcome-changing error, the minimum number of tests required is

$$\min \left\{ t : (1 + \varepsilon/2 - m/2)^t \le \frac{\alpha - \beta}{1 - \beta} \right\}. \tag{4}$$

*Minimax Lower Bounds.* Suppose auditors draw an IID sample of n transactions from P, a frequency distribution on S possible transactions. Let M*S* denote the collection of all frequency distributions for those transactions. Then the training sample size n must be at least large enough to ensure that the L1 error of the best estimator Pˆ is unlikely to exceed ε, provided P ∈ M*S*:

$$\inf\_{\hat{P}} \sup\_{P \in \mathcal{M}\_S} \Pr\{ \|\hat{P} - P\|\_1 \le \varepsilon \} \ge 1 - \beta. \tag{5}$$

*Theorem.* ([8]) For any ζ ∈ (0, 1],

$$\begin{split} \inf\_{\hat{P}} \sup\_{P \in \mathcal{M}\_S} \mathbb{E}\_P \| \hat{P} - P \|\_1 &\geq \frac{1}{8} \sqrt{\frac{eS}{(1+\zeta)n}} \mathbb{1} \left( \frac{(1+\zeta)n}{S} > \frac{e}{16} \right) \\ &+ \exp \left( -\frac{2(1+\zeta)n}{S} \right) \mathbb{1} \left( \frac{(1+\zeta)n}{S} \leq \frac{e}{16} \right) \\ &- \exp \left( -\frac{\zeta^2 n}{24} \right) - 12 \exp \left( -\frac{\zeta^2 S}{32(\ln S)^2} \right), \end{split} \tag{6}$$

where the infimum is over all M*S*-measurable estimators Pˆ.

*Lemma.* Let X be a random variable with variance VarX ≤ 1, and let β ∈ (0, 1). If Pr{X ≥ EX + λ} ≤ β then λ ≥ −β/(1 − β).

*Proof.* Suppose λ ≥ 0. Then λ ≥ −β/(1 − β). Suppose λ < 0. By Cantelli's inequality and the premise of the lemma,

$$\beta \ge \Pr\{X \ge \mathbb{E}X + \lambda\} \ge 1 - \frac{\sigma^2}{\sigma^2 + \lambda^2} = \frac{\lambda^2}{\sigma^2 + \lambda^2} \ge \frac{\lambda^2}{1 + \lambda^2}.\tag{7}$$

5 The set of undetectable shifts of *m/*2 votes might not include the one that any particular attacker seeks; this bound is worst-case across hypothetical attackers and distributions of transactions.

Solving for λ yields the desired inequality. -.

Now 0 ≤ Pˆ − P1 ≤ 2, so VarPˆ − P1 ≤ 1. By the lemma, we need λ ≥ −β/(1 − β) to ensure that Pr{Pˆ−P1 ≥ EX +λ} ≤ β. If Pˆ−P1 ≥ 2r, there can be a set of transactions τ such that P(τ ) = m/2 but Pˆ(τ ) = 0, so if tests are generated randomly according to Pˆ there is zero probability of testing any transaction in τ , no matter how many tests are performed. Thus if Pr{Pˆ − P1 ≥ m} > α, even an infinite number of tests cannot guarantee chance at least 1 − α detecting that a fraction m/2 of the transactions were altered, enough to wipe out a margin of m. By the lemma, that is the case if m < EPˆ − P1 − α/(1 − α), i.e., if EPˆ − P1 > m + α/(1 − α).

The theorem gives a family of lower bounds on EPˆ − P1 in terms of n. If the lower bound exceeds m +α/(1 − α), testing by drawing transactions from Pˆ cannot protect against all outcome-changing errors. The bound grows with S, the number of possible transactions. To be optimistic, we use an unrealistically small value S = 6.14 × 106 (Table 3).6

To guarantee a 95% chance of detecting that m/2 = 5% of transactions were altered, which could change jurisdiction-wide margins by 10% or more, the training sample would need to include at least 1.082 million transactions, even if auditors could conduct an infinite number of parallel tests. That is larger than the turnout in 99.7% of U.S. jurisdictions in 2020 [29]; it is roughly 0.5% of the U.S. voting population. To guarantee 99% chance of detecting that 0.5% of transactions were altered, which could change jurisdiction-wide margins by 1% or more, would require observing 3.876 million voters in complete, privacyeliminating detail—more than the turnout in 99.9% of U.S. jurisdictions in 2020 [29], roughly 1.9% of the U.S. voting population.

6 Software implementing the calculations is in https://github.com/pbstark/Parallel19.

**Fig. 3.** Minimum training sample sizes as a function of the fraction of altered votes.

# **6 Complications**

Reality is worse than the optimistic assumptions in our analyses:

*Margins are not Known in Advance.* Margins are not known until the election is over, when it is too late to do more testing if contests have narrower margins than anticipated. Testing to any pre-defined threshold, e.g., a 95% chance of detecting changes to 0.5% of the votes in any contest, will not always suffice.

*Tests have Uncertainty.* If the BMD printout reflects the wrong electoral outcome, a perfect full manual tally, recount, or risk-limiting audit based on BMD printout will confirm that wrong outcome. Suppose one could design practical parallel tests that had a 95% chance of sounding an alarm if BMDs alter ≥ 0.5% of the votes in any contest. A reported margin of 1% or less in a plurality contest is below the "limit of detection" of such tests. Would laws require a runoff whenever a reported margin is below the limit of detection of the tests?

*Special Risks for Some Voters.* As discussed above in Sect. 4.1, BMDs can be used to selectively disenfranchise voters with disabilities and voters whose preferred language is not English. Indeed, the attacker's best strategy is to target such voters, in part because poll workers might more likely to think that complaints by such voters reflect voter mistakes rather than BMD malfunctions.

*The only Remedy is a New Election.* If a BMD is caught misbehaving, it should be removed from service and all BMDs in that jurisdiction should be investigated. But there is no way to determine the correct outcome or which votes were affected: BMDs are not *strongly software independent* [21].

# **7 Conclusion**

We show that to protect against outcome-altering BMD malfunctions requires orders of magnitude more testing than is feasible. To our knowledge, no jurisdiction has conducted *any* parallel testing of BMDs of the kind suggested by [7,32], much less enough to reliably detect outcome-changing errors, bugs, or hacks.

Even if it were possible to test enough to get high confidence that no more than some threshold percentage the votes were changed in any contest, fairness would demand a runoff in contests decided by less than that threshold.

Some BMDs may be the best extant technology for voters with particular disabilities to mark and cast a paper ballot independently. But many BMDs are poorly designed. Some have easily exploited security flaws [1] and some do not enable voters with common disabilities to vote independently [22, pp. 68–90]. To our knowledge, no VVSG-certified BMD system provides a means for blind voters to check whether the printout matches their intended selections.

Using BMDs makes elections less trustworthy, less resilient, less transparent, more fragile, and more expensive [1,17]. BMDs have failure modes that handmarked paper ballots do not have, and lack resilience when failures occur [1]. BMDs shift the burden of ensuring that voting equipment functions correctly from officials to voters, but do not provide voters any way to prove that they observed problems, if they do; nor can election officials show that outcomes are correct despite any problems that might have occurred [1]. BMDs undermine the ability of election officials to provide affirmative evidence that outcomes are correct, the fundamental principle of "evidence-based elections" [2,25].

Voters who use BMDs should be urged to bring a written list of their selections to the polls to check against BMD printout, and to request a fresh ballot if the printout does not match their intended selections. Election officials should track spoiled BMD printouts. There should be research on how to encourage voters to check BMD printout and report discrepancies, how to ensure the checks are accurate, and how to ensure that any reported problems are accountably and transparently recorded, addressed, and publicized; these issues also arise in endto-end cryptographically verifiable (E2E-V) voting systems. For the foreseeable future, prudent election administration requires keeping the use of BMDs to a minimum.

**Acknowledgements.** We are grateful to Yanjun Han and Tsachy Weissman for helpful conversations about minimax *L*1 estimation, and to Peter Rønne and anonymous referees for helpful comments and suggestions.

# **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

# **Individual Verifiability with Return Codes: Manipulation Detection Efficacy**

Paul Tim Th¨urw¨achter1, Melanie Volkamer1(B) , and Oksana Kulyk2

1 Karlsruhe Institute of Technology, Karlsruhe, Germany<EMAIL_ADDRESS><EMAIL_ADDRESS>2 IT University of Copenhagen, Copenhagen, Denmark<EMAIL_ADDRESS>
**Abstract.** Researchers advocate for end-to-end verifiable voting schemes to maximise election integrity. At E-Vote-ID 2021, Kulyk et al. proposed to extend the verifiable scheme used in Switzerland (called original scheme) by voting codes to improve it with respect to vote secrecy. While the authors evaluated the general usability of their proposal, they did not evaluate its efficacy with respect to manipulation detection by voters. To close this gap, we conducted a corresponding user study. Furthermore, we study the effect of a video intervention (describing the vote casting process including individual verifiabilty steps) on the manipulation detection rate. We found that 65% of those receiving the video detected the manipulation and informed the support. If we only consider those who stated they (partially) watched the video the rate is 75%. The detection rate for those not having provided the video is 63%. While these rates are significantly higher than the 10% detection rate reported in related work for the original system, we discuss how to further increase the detection rate.

**Keywords:** End-to-end verifiability *·* Usability *·* Individual verifiability *·* Deceptive study *·* Manipulation detection rate

# **1 Introduction**

Cryptographic end-to-end (E2E) verifiability facilitates detection of violations of the election integrity. From a usability perspective, individual verifiability (i.e. the ability to verify that the vote is cast as intended and stored as cast) is particularly challenging, as voters need to verify themselves. This is essential to preserve the secrecy of the vote. Thus, with E2E verifiability, in theory, it is possible to detect if voters are modified at any point in time, but only when voters know how to perform the individual verifiability and actually do so.

A range of manipulation-detection efficacy studies have been carried out to evaluate whether voters would detect if their vote is manipulated, e.g. in [11,22]. The corresponding user studies are conducted with different electronic voting systems in mind as well as with different types of attacks. In the user study, participants are told that the usability of an electronic voting system is evaluated. However, they interact with one (or a corresponding mockup) that an attacker could have set up to make voters believe their vote is not manipulated while it is actually either altered before being sent to the ballot box or not being sent to the ballot box at all. Note, the concrete strategy an attacker could take to do so, depends on the voting system under consideration. Furthermore, not all strategies are the same, but some are more difficult for voters to detect than others. Correspondingly there is a broad range of detection rates being reported in the literature, e.g. in [18], authors report for one system a detection rate of 100% for a more easy to detect manipulation and 10% for a difficult to detect one for another system.

Our focus is on those attacks that are difficult to detect as an attacker is more likely to take those. Furthermore, our focus is on the voting system used in Switzerland (which is based on polling sheets with return and confirmation codes to enable voters to verify their vote) – more precisely, the improvement proposed at E-Vote-ID 2021 by Kulyk et al. [16]. The authors proposed to use QR Codes to enter codes and to use so-called voting codes in order to improve the guarantees with respect to the secrecy of the vote. They also conducted a user study in which they observed that their proposal has no negative impact on the general usability compared to the original scheme. Our research has the following goals:

We conducted a user study with 50 participants. Our improved version of the Kulyk et al. proposal from [16] performed significantly better with respect to manipulation detection (63% detection rate) compared to the original system (10% detection rate, reported in [18]). While the detection rate for those participants who actually (at least partially) watched the video increased to 75%, it did not increase significantly. We discuss our findings in light of related work and deduce research directions for future work.

As a side contribution, our results confirm the conclusions from Kulyk et al. in [16] that, QR-code based code voting should be employed in certain types of election, as it avoids reliance on trustworthy voting clients. While they only argued based on the general usability, we showed that it has a positive effect on the manipulation detection rate too.

# **2 Related Work**

Human aspects of verifiable voting systems have been a subject of several investigation, focusing on different aspects of verifiability, such as voters' attitudes, mental models and misconceptions of verifiability [1,2,4,9,21,22] or the usability of the actual verification process [1–5,9–11,15,17,19,20,22,26,28,30,31].

In particular, several studies focused on the effectiveness of verification procedure in different e-voting systems [2,7,18,24]. These studies show mixed results, showing that in several of the investigated systems, a significant amount of voters is not able to perform the verification correctly, thus being unable to tell whether their votes are being manipulated – e.g. less than half of participants were able to verify their votes using the Helios and the Scantegrity II voting system in the study by Acemyan et al. [2]. Other systems have demonstrated more promising results. In particular, the evaluations of voting systems implementing verification procedures based on the so-called check codes have shown a high level of verification efficiency in the studies that evaluated verification effectiveness by introducing vote manipulations in the experimental procedure and testing whether the participants of the experiment are able to detect these manipulations via the corresponding verification [18,24]. The studies in both of these works have shown a 100% verification efficiency rate with different variants of such code-based systems, meaning that all participants in their experiments were able to successfully verify their vote and detect manipulations. However, when different kinds of attacks were considered – in particular, with the adversary being able to modify the user interfaces with the goal of confusing the voter and preventing them from performing or correctly interpreting the verification results – the success rates for the verification decreased again, with only up to 56% of participants being able to detect such an attack according to the study in [18]. These studies conclude that evaluating verification efficacy via empirical experiments is crucial in understanding the security of proposed e-voting systems.

Aside from evaluating verifiability from the human factors point of view, a number of studies focused on other techniques that are introduced to e-voting systems to enhance their security – namely, to the code-voting approach [6,8, 13,14,27], aimed to decrease the need to trust the voting client with regards to vote secrecy. As such, the usability of such systems has been evaluated in [17,23], showing that code voting in general can be made usable and acceptable by the voters. However, only limited evaluations of the usability of verification in code-voting systems have been conducted; one such system has been the subject of the study by Kulyk et al. [16], showing high effectiveness in terms of voters being able to cast the vote using the system, however, the study only tested the system in absence of vote manipulations.

# **3 Background**

#### **3.1 Swiss Electronic Voting System**

Our focus is on the Swiss voting system from the Swiss Post1. The process to cast a vote with this system2 is as follows: Voters receive an individual code sheet (also called polling sheet) via postal service. This polling sheet contains one initialisation code, check codes for each voting option, one confirmation code, and one finalisation code. All cotes are different for each voter. As there is no electronic ID in Switzerland, the system generates an election specific election key pair for all voters – one pair for each voter. The voters' private key is indirectly provided to them in the polling sheet. The private key can be deduced from the initialisation code.

An overview is depicted in Fig. 1a. To start the vote casting process, voters open the election webpage (the URL is provided on the polling sheet). Next, they manually enter their initialisation code (i.e. by typing the corresponding characters in the corresponding field of the webpage). Afterwards, voters select their voting option using the election webpage, i.e. clicking the option they want to select. Next, the election webpages displays a check code. According to the description on the polling sheet), voters are supposed to compare this code with the one next to their voting option on their polling sheet. The result of this check can be a pass or a fail: If both codes are the same, the voter confirms his by manually entering the confirmation code.

In case, the check was passed and the confirmation code was correctly entered, voters are supposed to receive a finalisation code. According to the polling sheet, voters are supposed to check whether such a code is displayed and whether it matches the one on their polling sheet. Only if this second check is passed, voters can be assured that their vote has been stored as intended (i.e. cast as intended plus stored as cast). The voting scheme provides individual verifiability under the assumption that the printing server and the voting client do not collaborate. Note, we are aware that the implementation when it comes to the universal verifiability had severe shortcomings, see e.g. [12]. We believe that these are issues the company faced when implementing the underlying cryptographic primitives. Thus, it can be fixed and as such it is still worth to study the individual verifiabilty of schemes like the one used in Switzerland.

We refer to this system incl. the election material and user interfaces as **'original system'**.

#### **3.2 E-Vote-ID-2021-Proposal**

At E-Vote-ID-2021, Kulyk et al. proposed in [16] to extend the Swiss voting system by individual voting codes. With this extension, the individual polling

1 https://evoting-community.post.ch/de? ga=2.79449501.804715002.1658647288- 420296842.1658647288.

2 Note, the system is used for polls in which voters select *1 out of n* options. Usually 2–3 of such polls are conducted at the same time. For our research, we assume that there is only one poll.

sheet from the Swiss system also contains one voting code per option. The voting codes are different for each voter. Thus, voters are supposed to enter the voting code representing their chosen option (instead of clicking on the option they want to selection on the election webpage). As the voting client cannot map the voting code to any of the options, the assumption on the trustworthy voting client is no longer needed3.

To address shortcoming of entering long voting codes, the authors proposed that voters use their camera-equipped smartphones, to cast a vote by scanning a corresponding QR code (containing the voting code). Their proposed (simplified) scheme is depicted in Fig. 1b. To integrate these ideas, the authors adopted the voting material and the election webpage from [18] accordingly. In particular, they introduce voting cards which contained on the front page the voting code as QR-code and on the back page the option and the corresponding return code.

(a) Swiss voting scheme (b) E-Vote-ID-2021-proposal

**Fig. 1.** Vote casting

In this paper, we refer to the proposal incl. the election material and user interfaces from Kulyk et al. as **'E-Vote-ID-2021-proposal'**.

# **4 Improvements to E-Vote-ID-2021-Proposal and Descriptive Video**

#### **4.1 Improvements to the Voting Material and User Interfaces**

Based on the feedback Kulyk et al. received from their participants, we deduced the following improvements:

– Providing the URL to the election webpage not only as text but also as a QR-code to make it easier for voters to open the correct election webpage.

3 Note, however, that one needs to ensure that the mapping of the voting codes to options for each voter remains secret to the adversary. Therefore it is important that the printers are operated offline as they need to be fully trustworthy.

The modified voting material and user interfaces are depicted in Fig. 2 and 3. In this paper, we refer to this system as improved-proposal.

# **4.2 Descriptive Video**

We were discussing what additional information voters may receive or have access to, regarding the online voting channel. There might be discussion forums, information about the company who provides the systems, the setup, maybe also about security evaluations in case there are some. In addition, we expect that their are videos describing the vote casting process to give voters an idea of the process and maybe what to particular care about. As we thought the first list might be very much related to the actual system in place, it is worth studying the impact of a video describing the process. Note, we decided to go with a video which provides the necessary information in a one-two lines text field rather than with audio, as we did not want that the audio is an issue when conducting the study (see Sect. 5).

The video therefore shows all the steps from receiving and opening the voting material to checking the finalisation code. The video takes 9 min. It also highlights twice the number of the support to be called. The reason it takes 9 min is that it gives the recipients time to read the text in the polling sheet at the

4 Fore the exact reasons, we refer the reader to [16].

**Fig. 2.** Polling sheet (b–d) with the scratch field being removed in (d); and voting cards (a)

**Fig. 3.** Voting webpage. Note, the steps, we refer to, correspond to those in the polling sheet.

same time, i.e. reading one paragraph or one step before continuing, i.e. actually conducting this step in the video. The video is available online5.

# **5 Methodology**

We first introduce our research questions and corresponding hypotheses, afterwards we describe the study procedure before discussing ethics, how we meet data protection regulations, and how we recruited our participants.

# **5.1 Research Questions, Hypotheses**

The proposal from [16] improves the security level of the original scheme. The general usability was shown to be similar to the original system. An open question remains, however, how this idea perform with respect to the manipulationdetection efficacy - both with and without providing a descriptive video. Correspondingly, we define the following research questions:

5 https://youtu.be/Yj7yz437OEc.

*How does the improved-proposal performs in terms of manipulation-detection efficacy (measured as the rate of participants detecting the manipulation of their vote) with and without watching the video?*

The authors of [16] based their voting material and election webpage on the improvements from [18]. We further improved both based on the feedback the authors reported on in [16]. The improvements of [18] resulted in a significantly higher manipulation detection rate than original system. Therefore, we expect that our improvements of the improved-proposal outperform the original system with respect to manipulation-detection efficacy. We therefore define the following hypotheses:

Note, the validation of this hypotheses come with some limitations as we collected only data for the improved-proposal (with and without the video) while we use for the original system the date from [18]. We discuss this further in the limitation section.

In particular for people using the improved-proposal the first time, the video helps to give them a better idea about the vote casting including scanning and verifying the various codes. The video in particular indicates that the support should be contacted in case the shown codes do not match the expected ones. We therefore define the following hypothesis:

*H*3: The improved-proposal in combination with the watching the video has a significantly higher manipulation-detection efficacy than the improved-proposal without further descriptions or explanations.

#### **5.2 Considered Manipulation-Types**

Kulyk et al. studied two different types of manipulations in [18]. One of their attacks would not be possible in the proposal from Kulyk et al. [16]: Adversaries would need to know the voting code for the option they want to cast a vote for – which is not the case by design of any code voting scheme. In the other one, adversaries attempt to nullify cast votes by not sending the voting code to the election infrastructure and manipulating the voting client with the purpose to convince the voter that their vote has been cast successfully. For this attack after entering the voting-code, the election webpage would confirm the correctness of the check code. Furthermore, it would state that the check code is correct and that one can continue to finish the vote casting process. Note, it is not possible for the adversary to show the finalisation code as they cannot send a valid voting code to the election infrastructure. Therefore, the adversary would need to change these steps, too: Instead of asking voters to compare the displayed finalisation code with the one in the polling sheet, the manipulated voting client could ask voters to enter the finalisation code. Figure 4 shows the content of the manipulated interfaces.

**Fig. 4.** Manipulated webpage, only displaying steps that are different, any only the actual text/UI elements.

# **5.3 Study Procedure**

Figure 5 depicts an overview of the study procedure. The study was conducted in German. Voting material and election webpage were translated for this paper. Furthermore, it was a remote study. The ballot of the election we simulated for our study contained four options. Participants were randomly assigned to one of the two groups: The no-video-group and the video-group. Participants received the study material in an envelope either via postal service or from someone they know. The following content was included:

**Fig. 5.** Study procedure for both groups (with and without the link to the video)

Participants were supposed to open the envelope, and read the study letter and the role card (phase 1). Afterwards, they were supposed to open the inner envelope with the voting material and to read the polling sheet (phase 2a). Participants in the video-group were asked to then watch the video (phase 2b). Afterwards, participants were supposed to start casting their vote (phase 3a). Both groups (the one with and without the link to the video) got the manipulated interfaces as described in Sect. 5.2.

*In the case that participants did not notice the manipulation or have noticed it but did not call the support*, they could just finish vote casting. After having finished the vote casting process, the election webpage displayed the link to the post-survey (phase 4). This survey, first, provides information about the study and data collection. It contained the informed consent. Once consent was provided, participants were debriefed. If they decide to continue with the survey, they were asked whether they detected the manipulation they read about in the debriefing text. Note, the question on the manipulation detection had three options: (1) I noticed it and I called the (study) support, (2) I noticed it but I did not call the (study) support, and (3) I did not notice the manipulation. In case the first option was selected, this had to be confirmed by entering the number 22. Those who called the (study) support got this number on the phone once they have reported the manipulation they observed. In case the second option was selected, participants were asked an additional open text question on why they did not call the support. The survey also asked whether they first read the instructions on the polling sheet before starting the vote casting process and we asked demographic questions. Participants in the video-group got additional questions: Whether they watched the video (entirely) and whether it was helpful (to detect the manipulation).

*In the case that study participants did notice the manipulation and called the (study) support*6 (phase 3b), the support first asked them to provide details about the issues they have. The goal was to first make sure they actually observed the manipulation and to find out to which group they were assigned. The study support took a note of this. Afterwards the participant who called was debriefed on the phone. If they decided to continue with the study, they were provided with the link to the post-survey7 and with the number 22 needed for the post-survey. Finally, the study support thanked the caller.

#### **5.4 Ethics, Data Protection, Recruitment**

The study was announced with the goal to evaluate the usability of an online voting system. Thus, one may call it a deceptive study. Therefore, the study was approved by the ethic committee of our university. Their checks contain legal issues as well. As such the compliance with data protection laws was attested too. We still want to comment on some important aspects: The postal addresses were

6 Note, in case the study support could not answer the call, this person was called back as soon as possible. All telephone numbers were deleted afterwards.

7 The post-survey was the same for those not detecting all participants.

deleted once they were put on the envelopes. For the survey we used SocSciSurvey which is GDPR compliant8. Participants were debriefed either on the phone or through the post-survey. The study material contained a telephone number and an email address to get in touch with us in case of general questions regarding the study or any doubts.

Participants were recruited in various different ways: Public channels, social media, friends of friends (in case they were not aware of our research) as well as through a snow-ball principle, asking those who agreed to participate to announce it to friends and family, too. Due to the remote study setting, we decided to not offer a reimbursement.

# **6 Results**

We sent out the voting instructions to 60 people (30 for each group). Eventually, a total of 50 people completed the post-survey (24 assigned to the no-video-group and 26 to the video-group). Table 1 shows their demographics, as well as of the participants in the study from [18] for the sake of comparison9. All statistical calculations for our hypotheses are performed using *R* packages "stats" and "rstatix". We report our results without corrections for multiple comparisons.

**Table 1.** Demographics of participants for age Mean/SD and gender

### **6.1 Overall Manipulation Detection**

Overall, 32 out of 50 participants reported detecting the manipulation. Of them, 17 were in the video-group and 15 were in the no-video-group, leading to detection rates of 65.4% and 62.5% correspondingly. We used Fischer's exact test [25] for the evaluation of our hypotheses, as commonly recommended for categorical data with 2 *×* 2 contingency tables with small sample sizes. Both of the groups had significantly higher detection rates compared to the original system (which according to [18] had a detection rate of 10%), as shown by Fisher's exact test10 **confirming** *H*1 (*OR* = 13*.*98, 95% CI = [3*.*02*, Inf*], *p* = *.*0004) **and** *H*2 (*OR* = 15*.*83, 95% CI = [3*.*466*, Inf*], *p* = *.*0002). No significant differences were detected between the no-video-group and the video-group (Fisher's test, *OR* = 1*.*13, 95% CI = [0*.*3679725*, Inf*], *p* = *.*532), thus **failing to confirm** *H*3.

8 Data protection policy: https://www.soscisurvey.de/en/data-protection .

9 Note, the authors of [18] do not report the demographics separate for their groups.

10 Note that for all our hypotheses one-tailed tests are used.

#### **6.2 Manipulation Detection for Various Subgroups**

The free-text answers were analysed by two of the authors independently and then discussed. As the provided free-text answers were rather short we took this approach rather than a formal open-coding approach. Eight participants (4 in the no-video-group and 4 in the video-group) answered in the post-survey that they noticed the manipulation, but did not report it to the study examiner. When asked to explain why they did not report it, the following reasons were stated11: Two mentioned that they did not want to call in the late hour, two answered that calling would be too much effort, two believed that the vote casting was successfully completed despite the fact that the steps on the interface did not match the ones on the polling sheet, two thought that they themselves were at fault and one believed that the missing code is displayed later in the process.

Overall 31 participants (17 in the video-group and 14 in the no-video-group) reported reading the voting material before starting with the voting procedure; 21 (ten in the video-group and 11 in the no-video-group) reported reading the materials while voting. Note that two participants reported both reading the materials completely beforehand and reading them again while voting. One participant (from the video-group) reported reading the study instructions and role card beforehand, but only reading the polling sheet while voting. Of the 31 participants who read the voting materials beforehand, 23 (74.1%) detected and reported the manipulation, as opposed to 9 out of 19 (47.4%) of those who did not read the materials beforehand.

#### **6.3 Video Related Statements**

Out of 26 participants assigned to the video-group, nine reported watching parts of the video, 11 reported watching all of it and six reported not watching the video at all. None of the participants reported watching the video more than once. The participants who reported not watching the video gave the following reasons for this: Two answered that the video was too long, one answered that watching the video would be too much effort and three answered that they believed watching the video was not necessary to complete the voting.

From those 20 participants who stated that they fully or partially watch the video, 15 participants reported the manipulation and called the support. In particular, nine out of 11 of participants that watched the video entirely reported the manipulation, compared to six out of nine of participants who watched parts of the video.

Furthermore, one could observe differences between manipulation detection rate depending on whether the participants familiarised themselves with the voting procedure before starting voting, either by watching the video fully (in the video-group) or by reading the voting materials beforehand (in both videogroup and no-video-group). As such, 24 out of 34 participants who either watched the video fully or read the voting materials before voting were able to detect the

11 Note that some of the participants mentioned several reasons for not calling.

manipulation (70.6%) as opposed to 8 out of 16 (50%) participants who did neither of these things.

Out of the participants who reported watching the video either fully or partially, who also have detected the manipulation and called the support (15 participants), the following answers were given regarding to whether the video was helpful to them for detecting the manipulation: nine agreed, four disagreed, and one were neutral.

# **7 Discussion**

Our results clearly show that the E-Vote-ID-2021-proposal outperforms the original system with respect to the detection manipulation rate (62.5% to 10%). As the authors in [16] showed that the E-Vote-ID-2021-proposal outperforms the original system with respect to the provided guarantees for vote secrecy (because it uses voting codes) and that they have a similar general usability performance, it can clearly be recommended to consider the E-Vote-ID-2021-proposal for the elections and polls in Switzerland as well as for any other election contexts with simple ballots. Note, the proposal of Kulyk et al. [16] does also outperform the original one because (1) the assumption that the vote casting device is not violating vote secrecy is not needed and (2) it is only possible to conduct limited election integrity related attacks as one can only remove votes but not change them – thus large scale manipulations would result in a unexpected low turnout.

The findings from the free-text answers (e.g. they thought it is too much effort to call, they thought they made a mistake) indicate that increasing the manipulation rate would need additional measures such as awareness raising for verifiability and why the voting material received via postal service can be trusted but not necessary the election webpage. This is a clear and important direction for future work.

We also found that participants who reported that they read the voting material only as they voted were more likely to follow the instructions on their screen, thus missing the manipulation. Thus, those who familiarized themselves with the process beforehand are more likely to detect the manipulation (between 75% and 77% compared to 62.5% and 65%). Thus, in particular in contexts like in Switzerland in which elections and/or polls happen several times a year, it gets over time more likely that manipulations are detected: If we assume that voters have voted several times with a system that is not manipulated and thus get familiar with the correct process, they might be more likely to detect a manipulation with future elections than if already the first time the system is in place, it got manipulated. The evaluation of such hypotheses is part of our future work.

Our study furthermore detected higher rates of manipulation detection compared to related work evaluating same kind of attacks - as such, the study by Kulyk et al. [18] found 43% manipulation detection rates and the study by Volkamer et al. [29] reported 41% compared to 62.5% of participants in our study (those who did not watch the video). One explanation could be the difference in demographics, in particular, the fact that the participants in our study tended to be younger than in related work, see e.g. Table 1 for the comparison between our participants and those in [18]. A study on the effects of demographic factors, including but not limited to age, gender and education, on the voter's ability to detect manipulations is therefore an interesting direction of future work. An other one might be that less people in [18,29] have read the instructions before starting the vote casting process. Note, a comparison is not possible as the authors do not provide any related information.

**Study Limitations:** Our study has similar limitations to other user studies evaluating the manipulation-detection efficacy in verifiable electronic voting: It is about a mock election and no actual election. Participants cast a vote for the option they were asked to select. Thus, this vote is not very personal to them or important. Participating in a study and, thus, agreeing to take time for it may result in spending more time in reading the instructions compared to casting a vote in an actual election. However, introducing vote manipulations in an actual election to measure manipulation-detection efficacy would pose critical ethical and legal issues. Thus, there is not much one can do about it.

Another limitations of all these studies evaluating manipulation-detection efficacy (including ours) is that we need to trust that those few participants who know each other have not informed others about the manipulation. Furthermore, we evaluated the scheme in Germany with participants who have not cast a vote with the original system. The results may be different for participants who are familiar with the original system.

We studied one implementation of adversaries' attempt to make voters believe their vote was cast as intended while their vote is not considered in the tally. The details can vary, i.e., the text displayed to convince voters that everything is fine. As future work, one could study the attack with different text.

In order to test two of the three hypotheses, we used data from our previous paper, i.e. [18]. This comes with some limitations as the study in the previous paper was a lab study, i.e. the study instructor was in the same room while in this paper, the study instructor could only be reached via phone. However, on the one hand the difference with respect to the detection rates are large and several studies have already shown the issues with the original system. Therefore, we wanted to focus our own data collection on the new proposal and the effect of the video.

# **8 Conclusion**

Verifiable voting schemes are the de-facto standard when considering online voting for political elections. At the same time, the verifiable voting systems in place only provide vote secrecy if the voting client is trustworthy. While this shortcoming can be addressed with code voting, such approaches are currently not considered, as the community and election officials are concerned about the usability implications. Kulyk et al. demonstrated in [16] that a code voting based extension of the original system can be as usable as the original one. We underline their conclusions as we show that such an extension can also significantly increase the manipulation-detection efficacy. Thus, it is worth considering code-voting verifiable voting schemes, as the cumbersome steps of entering voting codes manually can be replaced by easy-enough steps – i.e., scanning QR codes – without significantly reducing the usability while enabling systems with higher security guarantees. Thus, our research should encourage more research on combining code-voting with verifiable schemes.

While the manipulation-detection efficacy is significant higher for the studied scheme compared to the original system one, there is room for improvements. We evaluated whether a video intervention describing the vote casting steps including those to verify can further improve this rate. While we observed some increase, it was not significant. Based on the discussion of our results, we conclude that it is important to study various types of interventions with respect to their effect on manipulation-detection efficacy. In particular, approaches explaining the importance of verifiability should be developed and evaluated.

**Acknowledgements.** This research was further supported by funding from the topic Engineering Secure Systems, subtopic 46.23.01 Methods for Engineering Secure Systems, of the Helmholtz Association (HGF) and by KASTEL Security Research Labs.

# **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

# **Logic and Accuracy Testing: A Fifty-State Review**

Josiah Walker(B), Nakul Bajaj, Braden L. Crimmins, and J. Alex Halderman

University of Michigan, Ann Arbor, USA<EMAIL_ADDRESS>
**Abstract.** Pre-election logic and accuracy (L&A) testing is a process in which election officials validate the behavior of voting equipment by casting a known set of test ballots and confirming the expected results. Ideally, such testing can serve to detect certain forms of human error or fraud and help bolster voter confidence. We present the first detailed analysis of L&A testing practices across the United States. We find that while all states require L&A testing before every election, their implementations vary dramatically in scope, transparency, and rigorousness. We summarize each state's requirements and score them according to uniform criteria. We also highlight best practices and flag opportunities for improvement, in hopes of encouraging broader adoption of more effective L&A processes.

# **1 Introduction**

The vast majority of votes in the United States are counted mechanically, either by optical scanners that read paper ballots or by direct-recording electronic (DRE) voting machines [70]. To validate that these tabulation devices are configured and functioning correctly, jurisdictions perform a procedure called "logic and accuracy testing" ("L&A testing") shortly before each election. It typically involves casting a "test deck"—a set of ballots with known votes—on each machine, then printing the results and ensuring the tally is as expected. Any deviation is a potential indicator that the election equipment has misbehaved.

While more sophisticated mechanisms such as risk-limiting audits [37], and end-to-end verification [15] can reliably detect and recover from both errors and attacks after the fact, they are not yet widely applied in the U.S . Even if they were, L&A testing would remain useful for heading off some sources of error before they affected results. Ideally, L&A testing can protect against certain kinds of malfunction, configuration error, and fraud as well as strengthen voter confidence, but its effectiveness depends on many details of how the testing is performed. In the U.S., L&A testing requirements—like most aspects of election procedure and the selection of voting equipment—are determined by individual states, resulting in a diversity of practices with widely varying utility.

Unfortunately, this heterogeneity means that many states diverge negatively from the norm and makes it difficult to offer the national public any blanket assurances about the degree of protection that L&A testing affords. Moreover, many states do not publish detailed L&A procedures, leaving voters with little ability to assess the effectiveness of their own states' rules, let alone whether any tests they observe comply with them. Yet this decentralized regulatory environment has also allowed a variety of positive L&A testing procedures to evolve, and there are abundant opportunities for the exchange of best practices.

This paper provides the first comparative analysis of L&A testing requirements across the fifty states. To determine how each state performs L&A testing, we conducted an extensive review of available documentation and reached out to election officials in every state. We then assessed and scored each state's policy using criteria designed to reflect its functional effectiveness and suitability as a basis for voter confidence. The results provide a detailed understanding of how states' procedures differ and how well they approach an ideal model of what L&A testing can achieve. Our analysis reveals that several important L&A criteria are absent in many or most states' rules, yet we also highlight specific examples of policies that could serve as models for broader dissemination. We hope this work will encourage the adoption of more effective L&A testing requirements across the United States and help promote policies that better inspire public trust.

# **2 Background**

# **2.1 L&A Testing Goals**

L&A testing was first introduced in the early 1900s s for lever-style voting machines [63], which contained a mechanical counter for each candidate. The counters were susceptible to becoming jammed due to physical failure or tampering, so tests were designed to establish that each counter would advance when voted.

Modern DRE voting machines and ballot scanners can suffer from analogous problems—miscalibrated touch-screens or dirty scanner heads can prevent votes in specific ballot positions from being recorded [31]—but they also have more complex failure modes that call for different forms of testing. These devices must be provisioned with an "election definition" that specifies the ballot layout and rules. If the election definition is wrong—for instance, the order or position of voting targets do not match the ballots a scanner will read—votes may be miscounted.

Problems with election definitions caused by human error are surprisingly common. They contributed to the publication of incorrect initial election results in Northampton County, Pennsylvania, in 2019 [14], Antrim County, Michigan, in 2020 [28], and DeKalb County, Georgia, in 2022 [23]. In these documented cases the errors were fortunately detected, but only after the results were announced. They likely could have been prevented in the first place by sufficient L&A testing.

L&A testing can also serve a role in election security. Research has long recognized that L&A testing *cannot* reliably defeat an adversary who manages to execute malware on voting machines, because the malware could detect when it was under test and only begin cheating during the election itself (see, e.g., [24]). However, L&A testing can potentially thwart more limited attackers who manage to tamper with election definitions or configuration settings. For example, although there is no evidence that the instances of error described above were caused by fraud, attackers could cause similar election definition problems deliberately in an attempt to alter results. This would likely require far less sophistication than creating vote-stealing malware. Moreover, there is growing concern about threats posed by dishonest election insiders, who routinely have the access necessary to perform such an attack [17].

Beyond providing these protections, L&A testing also frequently serves a role in enhancing public confidence in elections. Most states conduct at least part of their L&A testing during a public ceremony, where interested political party representatives, candidates, news media, and residents can observe the process and sometimes even participate by marking test ballots. Some jurisdictions also provide live or recorded video of their testing ceremonies online. These public tests can help build trust by allowing voters to meet their local officials, observe their level of diligence, and become more familiar with election processes. Additionally, public observers have the potential to make testing stronger, by providing an independent check that the required tests were completed and performed correctly. At least in principle, public observation could also help thwart attempts by dishonest officials to subvert L&A testing by skipping tests or ignoring errors.

#### **2.2 U.S. Elections**

L&A testing fills a role that is best understood with a view towards the broader context of election administration in the jurisdictions where it is practiced. In the U.S., many subjects are put to the voters, frequently all at once, and a single ballot might include contests ranging from the national presidency and congress to the state governor, legislature, and judges to the local mayor, city council, sheriff, and school board [13]. This means elections tend to involve many contests—typically around 20, although some jurisdictions have occasionally had nearly 100 [76]. There may also be several ballot variants within a single polling place to accommodate candidates from different sets of districts. These features make tallying by hand impracticable in many areas. As a result, nearly all jurisdictions rely on electronic tabulation equipment, today most commonly in the form of computerized ballot scanners [70]. Ensuring that these machines are properly configured and functioning on election day is the key motivation for L&A testing.

Election administration in the U.S. is largely the province of state and local governments. Although the Constitution gives Congress the power to override state law regarding the "manner of holding Elections for Senators and Representatives," this authority has been applied only sparingly, for instance to establish accessibility requirements and enforce civil rights [30,73]. Each state legislature establishes its own election laws, and the state executive (typically the secretary of state) promulgates more detailed regulations and procedures. In practice, election administration powers are exercised primarily by local jurisdictions, such

as counties or cities and townships, where local officials (often elected officials called "clerks") are responsible for conducting elections [45].

Because of this structure, there is little standardization of election practices across the states, and L&A testing is no exception. Testing processes (and the ceremonies that accompany them) vary substantially between and within states. As we show, these variations have significant effects, both with respect to errordetection effectiveness and procedural transparency and intelligibility. Pessimistically, one can view this broad local discretion as a way for some jurisdictions to use lax practices with little accountability. We note, however, that it also grants many clerks the power to depart *upwards* from their states' mandatory procedures, achieving stronger protections than the law requires. This provides an opportunity for improved practices to see early and rapid adoption.

# **2.3 Related Work**

Although L&A testing itself has so far received little research attention, there is extensive literature analyzing other aspects of election mechanics across states and countries, with the goal of informing policymaking and spreading best practices. For instance, past work has examined state practices and their impacts regarding post-election audits [68], voter registration list maintenance [10], voter identification requirements [16], online voter registration [79], election observation laws [27], the availability of universal vote-by-mail [67]. A far larger body of research exists comparing state practices in fields other than elections.

Despite the abundance of this work, we are the first (to our knowledge) to examine states' L&A testing practices in detail. A 2018 state-by-state report by the Center for American Progress [58] considered L&A testing among several other aspects of election security preparedness; however, it primarily focused on the narrow question of whether states required all equipment to be tested. To build upon this research, we consider many other policy choices that influence the effectiveness of L&A requirements and procedures.

# **3 Methodology**

#### **3.1 Data Collection**

To gather information on states' practices, we began by collecting official documentation where publicly available, relying primarily on state legal codes, state election websites, and Internet search engines. If we could not locate sufficient information, we attempted to contact the state via email or by phone to supplement our understanding or ask for clarifications. We directed these inquiries to the state elections division's main contact point, as identified on its website.

State responses varied. While some states provided line by line answers to each of our questions, it was common for states to indicate that our criteria were more specific than what state resources dictated, pointing us instead to the same statues and documentation we had already examined, providing us with additional documentation that was still unresponsive to our questions, or replying in paragraphs that partially addressed some questions while completely disregarding others. In cases where we could not find evidence to support that a state satisfied certain criteria and the state did not provide supporting evidence upon request, we did not award the state any points for those criteria.

Upon finalizing our summary of each state's practices, we contacted officials again to provide an opportunity for them to complete or correct our understanding. Over the course of nine months, we communicated with all 50 states and received at least some feedback on our summaries from all but seven states— Iowa, New Jersey, New York, Rhode Island, Tennessee, Vermont, and Wisconsin. Our data and analysis are current as of July 2022.

#### **3.2 Evaluation Criteria**

To uniformly assess and compare states practices, we applied the following criteria and scoring methodology, which reflect attributes we consider important for maximizing the benefits of L&A testing in terms of accuracy and voter confidence. These criteria are non-exhaustive, but we believe they are sufficiently comprehensive to evaluate state procedures relative to one another. (Additional desirable testing properties are discussed in Sect. 5.) Note that our assessments do not necessarily reflect practice in each of a state's subdivisions, since local officials sometimes have authority to exceed state guidelines. To keep the analysis tractable, we instead focus on the *baseline* established by statewide requirements.

We developed two categories of criteria: *procedural criteria*, which encompass the existence of procedures, the scope of testing, and transparency; and *functional criteria*, which reflect whether the testing could reliably detect various kinds of errors and attacks. To facilitate quantitative comparisons, we assigned point values to each criterion, such that each category is worth a total of 10 points and the weights of specific items reflect our assessment of their relative importance.

#### **Procedural Criteria**

*Rules and Transparency* (5 points). To provide the strongest basis for trust, testing should meet or exceed published requirements and be conducted in public.

RT1 (1*.*5 pts): Procedures are specified in a detailed public document.

This captures the threshold matter of whether states have published L&A requirements. Detailed or step-by-step guidelines received full credit, and general laws or policies received half credit.

RT2 (1*.*0 pts): The document is readily available, e.g., via the state's website. Making L&A procedures easily available helps inform the public and enables observers to assess tests they witness.1

1 Even when procedures are public documents, they are not always readily accessible. One state, Delaware, instructed us that we would need to find a resident to file a Freedom of Information Act request before their procedures would be provided.

RT3 (1*.*5 pts): Some testing is open to the public, candidates/parties, journalists.

This tracks the potential for public L&A ceremonies to strengthen confidence. RT4 (1*.*0 pts): Local jurisdictions have latitude to exceed baseline requirements.

*Scope of Testing* (5 points). A comprehensive approach to testing covers every ballot design across all the voting machines or scanners where they can be used.

ST1 (2*.*0 pts): All voting machines/scanners must be tested before each election. ST2 (1*.*0 pts): All devices must be tested *at a public event* before each election. ST3 (2*.*0 pts): All devices must be tested with every applicable ballot design.

Failing to test all machines or all ballot styles risks that localized problems will go undetected, so each was assigned a substantial 2 points. One additional point was provided if all testing is public, to reflect transparency interests.

# **Functional Criteria**

In each of three sets of functional criteria, we assess a simple form of the protection (with a small point value) and a more rigorous form (with a large point value).

*Basic Protections* (4 points). To guard against common errors, tests should cover every voting target and ensure detection of transpositions.

BP1 (1*.*0 pts): All choices receive at least one valid vote during testing.

BP2 (3*.*0 pts): No two choices in a contest receive the same number of votes. The first test minimally detects whether each candidate has some functioning voting target. The second further ensures the detection of transposed targets within a contest, which can result from misconfigured election definitions.

*Overvote Protection* (2 points). Testing should exercise overvote detection and, ideally, confirm that the overvote threshold in each contest is set correctly.

*Nondeterministic Testing* (4 points). For stronger protection against deliberate errors, attackers should be unable to predict how the test deck is marked.

ND1 (1*.*0 pts): Public observers are allowed to arbitrarily mark and cast ballots. ND2 (3*.*0 pts): Some ballots must be marked using a source of randomness.

Attackers who can predict the test deck potentially can tamper with the election definition such that errors will not be visible during testing. If the public can contribute test ballots, this introduces uncertainty for the attacker, while requiring random ballots allows for more rigorous probabilistic detection.

# **4 Analysis**

Our nationwide review of L&A procedures highlights significant variation among the testing practices of the fifty states, as illustrated by the maps in Fig. 2. The tables on page 7 summarize our findings and rank the states with respect to the procedural and functional criteria. We also provide a capsule summary of each state's practices in Appendix A.

**Fig. 1.** We count the number of states that met, partly met, or did not meet each criterion. While states commonly require simple protections (BP1, OP1), most do not achieve more rigorous forms of error detection (e.g., OP2, ND1, and ND2).

### **4.1 Performance by Criterion**

Figure 1 shows the number of states that met, partly met, or did not meet each criterion. All 50 states have laws that require L&A testing, but only 22 have a public, statewide document that details the steps necessary to properly conduct the tests (RT1). Of those that do not, several (such as California) merely instruct local jurisdictions to follow instructions from their voting equipment vendors, limiting the efficacy of logic and accuracy procedures to each vendor's preferences.

States generally performed well with respect to transparency criteria. Every state has some public documentation about its L&A practices, with 40 states making this documentation readily available (RT2). At least 45 states perform some or all testing in public (RT3), although 7 of these impose restrictions on who is allowed to attend. At least 32 states test every machine in public (ST2). Just three states (Kentucky, Maryland, and Hawaii) do not conduct any public L&A testing, which may be a significant lost opportunity to build public trust.