Joseph A. Calandrino [1], J. Alex Halderman [1], and Edward W. Felten [1,2]
1. Center for Information Technology Policy and Dept. of Computer Science, Princeton University
2. Woodrow Wilson School of Public and International Affairs, Princeton University
{jcalandr,jhalderm,felten}@cs.princeton.edu
Election audit procedures usually rely on precinct-based recounts, in which workers manually review all paper ballots from selected polling places, but these recounts can be expensive due to the labor required. This paper proposes an alternative audit strategy that allows machines to perform most of the work. Precincts are recounted using recounting machines, and their output is manually audited using efficient ballot sampling techniques. This strategy can achieve equal or greater confidence than precinct-based auditing at a significantly lower cost while protecting voter privacy better than previous ballot-based auditing methods. We show how to determine which ballots to audit against the recounting machines' records and compare this new approach to precinct-based audits in the context of Virginia's November 2006 election. Far fewer ballots need to be audited by hand using our approach. We also explore extensions to these techniques, such as varying individual ballots' audit probabilities based on the votes they contain, that promise further efficiency gains.
Security analyses of computerized voting systems, including DREs and optical scan machines, have exposed numerous vulnerabilities that could compromise the integrity of elections performed using these devices (see [7,5] and references therein). One proposed defense against such attacks is to produce voter-verified paper records and audit them to ensure that they support the totals claimed by the machines.
The most common auditing method is the precinct-based audit [3,9,10,12,13], in which workers count all paper ballots from selected precincts and compare the results to the reported precinct tallies.1 Unfortunately, performing precinct-based audits can require considerable time, labor, and expense. These costs are multiplied by the complexity of the ballots in many elections, which may include dozens of contests. In a trial recount of a DRE paper trail performed in Cobb County, Georgia, workers took an average of 5 minutes per ballot to audit 976 votes at a total cost of nearly $3,000 [4]. Unless efficiency can be improved, performing a similar recount of 3% of precincts in New Jersey could cost more than $200,000. Slow, expensive manual recounts limit the level of confidence that can be achieved within a fixed election budget, and they may delay the detection of errors until well after election results have been announced and losing candidates have conceded.
In this paper we propose an alternative audit strategy that substantially reduces these costs by using specialized machines to automate most of the work of recounting paper ballots followed by a manual audit of the machine results. The problem with machines, of course, is that the ones used for the recount are not necessarily more trustworthy than the ones used in the initial count. They may be useful for catching inadvertent errors (especially if they use a different technology and independently developed software), but a determined attacker could still target both sets of machines. What we desire is software independence--an assurance that any tampering with the machines will not cause undetected changes to the election outcome [11]. To achieve this, we pair recount machines with efficient statistical auditing techniques that allow humans to confirm that the election outcome is correct.
Statistical ``ballot-based'' audits are an alternative to manually recounting every ballot from selected precincts. Workers sample from all the paper ballots in all precincts and use the sample to assess the accuracy of the original count. Ballot-based audits tend to be more efficient than traditional precinct-based audits [8], since fewer ballots need to be recounted to achieve the same level of confidence in the result. For example, in a state-wide race in New Jersey, fewer than one ballot per precinct (4,599 ballots total) would need to be sampled to achieve 99% confidence that the outcome had not been shifted by more than 0.2%. By contrast, over 150,000 ballots (6.9% of precincts) would need to be recounted using standard precinct-based audits (e.g., [13]) to achieve the same confidence.
Neff [8] and Johnson [6] were among the first to propose combining ballot-based audit techniques with electronic voting. Neff assumes that the voting machines link each paper ballot to its electronic counterpart using, for example, a unique identifier printed on the paper ballot and stored with the electronic ballot. When voting is complete, each precinct commits to its set of electronic ballots, then demonstrates that the paper ballots in a given random sample match the corresponding electronic ballots.
The primary weakness of this method is that it establishes the link between electronic and paper ballots at the time that votes are cast. This raises problematic voter privacy issues. For example, if the ballots are linked using sequentially increasing serial numbers, observers could correlate votes with the order in which they were cast, which can reveal the identity of voters. While a cryptographic link might protect privacy, opaque, random-looking identifiers printed on ballots may provide covert channels for leaking voter identities. Even if used securely, they might aid malicious parties who seek to intimidate voters by undermining their confidence in the secrecy of the ballot. Our audit strategy postpones linking paper and electronic records until the recount phase, which allows it to achieve equivalent confidence without jeopardizing privacy or resorting to cryptography.
Johnson alternatively proposes delaying both vote tallying and serial number printing until after all ballots are submitted, allowing voting machines to be simple, memory-less ballot printers [6]. Voters submit their ballots, which, once polls close, are randomized and scanned/tallied. The tallying machine is therefore able to print serial numbers while scanning without privacy risk. Unlike Johnson, we assume that the voting machines maintain an electronic tally, which helps deter traditional attacks against paper-based voting, such as ballot-box stuffing, and, as we will show, provides opportunities for improving the efficiency of the audit.
Our main contributions are:
We propose replacing manual precinct-based audits with machine-assisted audits. Poll workers, rather than recounting ballots manually, feed them through a specialized recount machine that functions like a combined optical scanner and printer. As it scans the contents of each ballot, it prints a unique serial number that is stored along with the ballot contents. At the end of the scanning process, the machine outputs a list of votes on each ballot together with the ballot's serial number. If the recount tallies differ from the initially reported electronic count, discrepancies clearly exist and a wider investigation should be conducted.2 If both tallies match, the workers perform a secondary audit to check the accuracy of the machine's recount. They first quickly flip through the pile of numbered ballots to ensure that it increases sequentially from one to the reported ballot total without repeats.3 They then take a random sample of the electronic ballot records, retrieve the corresponding paper ballots, and verify that they match.
Since the ballots are serialized and fed out of the machine in order, retrieving a particular ballot for verification requires very little effort. The most significant labor required may be to check for repeats, which given sequential ordering, is a rapid single-pass process.
In practice, separate devices may be used to perform the printing and scanning functions of our proposed recount machine. When voting is complete, a printer device could place serial numbers on the ballots, and then a separate scanner could read the numbers along with the votes. In precincts utilizing optical scan machines, properly designed machines could perform both the initial count and the recount: this option decreases costs but reduces redundancy. If the same machine performs counts, recounts, and printing, officials must have some means of mechanically disabling the printer while polls are open, such as removal of the printer head. Printers also must be physically unable to alter the record of the vote on the ballot. They could be designed so that they cannot reach outside of a predefined empty margin on ballots, or they could utilize a kind of ink that would be immediately apparent when ballots were inspected.
The redundancy of combining electronic and paper-based systems increases the security of the overall system. With high probability, the manual audit process detects any discrepancies between the sets of electronic and paper ballots that are substantial enough to impact the election's outcome. Because the process checks the correspondence between the sets of ballots, measures improving the integrity of either set increase the overall integrity of the election result. Since both the electronic and paper ballot sets must remain similar for a discrepancy to avoid detection, combined systems are more likely to detect malfunctions, and they increase the sophistication necessary to commit fraud.
For an error to go undetected, the voting machine must report an incorrect electronic tally, the recount machine must support the incorrect tally, and the manual audit process must not detect a discrepancy between the paper and electronic ballot records.
A malfunctioning or dishonest voting machine may add, subtract, or switch votes to introduce errors in its electronic tallies. If election officials maintain an accurate sign-in list for the precinct, any significant discrepancy in the total number of reported votes will be detected. Therefore, the voting machine is limited to switching votes from one candidate to another.
For a recount machine to support an incorrect electronic tally, either the set of paper ballots must match the incorrect tally, or the machine must fail to detect a discrepancy. The set of paper ballots can only match the tally if either the voting machine printed an incorrect set of paper ballots or another party modified that set. If voters generally verify their paper ballots, the ballot box will likely contain at an accurate paper ballot for most voters when polls close. While the voting machine may print additional, incorrect ballots, this would cause the number of paper ballots to exceed the electronic vote total, which mirrors the number of voters, so an accurate recount machine would detect this discrepancy. The simple, sequential nature of machine-assisted auditing also reduces opportunities for adversaries to modify paper ballots during the audit. Assuming that no adversary can modify the set of paper ballots after polls close, only recount machine malfunction, whether accidental or malicious, would allow the discrepancy to go undetected.
A malfunctioning recount machine may report incorrect electronic ballots that agree with any incorrect electronic tally regardless of the true paper ballots. The machine may even collude with other parties by omitting or printing incorrect serial numbers on paper ballots to hide errors. For example, a voting machine may print additional paper ballots with desirable votes, and a recounting machine may reuse serial numbers on certain undesirable voter-verified paper ballots to effectively replace them with the additional ballots. The manual check of serial numbers detects duplicate or omitted serial numbers and ensures that the number of paper ballots matches the total reported number of electronic ballots.
If no errors are detected before the sampling phase, we know that we have a set of electronic ballots from the recount machine that support the initial electronic tally and an equal-sized set of paper ballots with corresponding serial numbers. We designed the sampling process specifically to detect discrepancies between these sets significant enough to affect the election's outcome. Unless an error or adversary modified both the initial electronic tally and the paper ballots, the manual audit should catch any remaining errors with a high level of confidence.
Our technique avoids many of the privacy issues inherent in some earlier ballot-based audit methods that involve placing identifiers on ballots during the voting process. In our technique, the ballots do not receive serial numbers until the recount phase, so they are likely to become at least partially reordered before being numbered. Well-designed ballot boxes and cut-and-drop paper trail systems assure that the papers are somewhat shuffled as they are inserted. Since voters widely trust these methods to frustrate correlation with voter check-in times, this provides significant practical privacy benefits. Should alternative ballot shuffling methods offer greater protection, officials may substitute such methods without modifying the audit process. In any case, the recount machine has no more information about the order of votes than would workers performing a manual recount.
Another benefit of this technique is that a voting machine need only maintain tallies rather than electronic copies of individual ballots. Thus, voting machine designers do not need to worry about properly shuffling electronic ballots to protect voter privacy or about maintaining storage for those ballots. However, if the same machines perform counts and recounts, they must have some means of attaching extra memory during the recount for storing the ballot scan results.
Due to the popularity of plurality voting systems in the U.S. we
exclusively consider those systems, though machine-assisted audits may
be useful in many other voting systems. With plurality voting, voters
may choose a number of candidates equal to the number of seats
available.4 If 
seats are available, voters may select up to
candidates, and candidates receiving the top vote totals are the
victors. This definition is an extension of the familiar single-seat
contest.
An audit process need only sample enough ballots to confidently detect the minimum amount of fraud that would have affected the election's outcome. To modify the fewest ballots while changing the outcome, an adversary would swap the positions of the losing candidate with the most votes and the victor with fewest votes. Switching votes directly between these candidates requires the fewest ballot changes, as each switch alters the relative difference by two. To do so, the adversary would take ballots with votes for candidate A but not B and change them to contain votes for B but not A. Therefore, we need only audit enough ballots to discover fraud that alters a number of ballots equal to half the difference (rounded up) in vote totals between the ``just losing'' and ``just winning'' candidates.
We describe two techniques for selecting which ballots and precincts need to be audited. The first technique has the benefit of a constant sample size given the number of ballots, the margin of victory, and the desired level of confidence. Sample size may vary with the second approach, but that approach is more amenable to extensions that we propose later.
The hypergeometric distribution describes the number of bad ballots an
auditor can expect to find when sampling without replacement. Assume
that auditors desire a confidence level 
that no fraud significant
enough to change the election's outcome occurred. By [9],
given 
total ballots and a minimum of 
incorrect ballots, the
probability mass function of the hypergeometric distribution dictates
a minimum sample size, 
, of:
A machine recount of a precinct is only necessary if a ballot will be selected for manual verification in that precinct. For this method, auditors could use the initial electronic tallies to perform a mock ballot selection before the machine recount. Any precinct which would have contained a chosen ballot given the mock selection will undergo a machine recount. Following the machine recount, officials may randomly select a single ballot from each recounted precinct and randomly draw the remaining required ballots from the full pool in all recounted precincts.
Rivest [10] proposes an efficient precinct-based auditing
technique in which, rather than drawing a given-size sample from the
population of precincts, auditors instead randomly select each
precinct with a given probability. The same idea is also useful in
the context of ballot-based auditing. Assume that, to change the
results of an election, the set of ballots must contain a minimum of
bad ballots. To achieve a confidence level of that at least
one bad ballot will be sampled, auditors may select each ballot with
probability 
chosen such that
, or
.
To determine which precincts need to be audited, we may calculate the
probability that one or more of the 
ballots in precinct 
will
be sampled as
. Auditors may select each precinct
based on the probability that it contains a sampled ballot. If so,
officials perform a machine recount in that precinct. Given that at
least one ballot is sampled in a precinct, the probability of sampling
ballots in that precinct is:
 |
(2) |
Assume use of the audit method in Section 3.2, and
let
. The probability that precinct
requires a machine recount is therefore
. If
an adversary can steal any number of votes in a precinct, Rivest [10]
proposes a logistic precinct-based approach that yields the same
precinct audit probability. For machine-assisted auditing, however,
auditors need only manually review a subset of the recounted ballots.
Rivest presents his logistic approach as a non-optimal heuristic [10], so the usefulness of this link seems limited. Furthermore, the percentage of votes in a precinct that one may steal without generating suspicion is more likely 10-20% than the 100% assumed here. In light of this, a performance comparison between Rivest's optimal precinct-based techniques and our methods under realistic circumstances would be informative.
To evaluate the efficiency of machine-assisted auditing (and ballot-based auditing in general) versus precinct-based auditing,5 we consider both techniques in the context of available data from Virginia's November 2006 elections, both for local and statewide races.6 In all cases, we seek a 99% confidence level.
Virginia contains 2,599 precincts and approximately 4.6 million registered voters, nearly 53% of whom cast ballots during the November 2006 election. The general election decided nineteen issues: four statewide issues, including a U.S. Senate race and several statewide initiatives, and fifteen smaller races, such as U.S. House races. In addition, voters considered numerous local ballot issues, ranging from city council elections to school constructions projects [14]. Because auditing is typically both more important and more labor-intensive in closer races, we focus on such races, excluding consideration of races for which modification of 10% or more of the ballots would have been necessary to change the outcome. This choice rules out many of the races but leaves a set of 49 remaining. Seven of those remaining were general election issues and forty-two were local issues.
The remaining general election issues include a U.S. Senate race with a margin of victory of 0.39%, four U.S. House races, a race for the Virginia House of Delegates, and a state constitutional amendment. For those races, machine-assisted auditing would require a manual review of approximately 437 ballots on average--0.06% of the 796,469 average total ballots. Only the smaller House of Delegates race would require review of greater than 1% of the ballots (1.05%), and five of seven races require audit rates under 0.1%. Precinct-based auditing would review approximately 177,849 ballots on average--22.33% of the average total ballots. In each case, precinct-based auditing requires an expected hand count of more than 42 times as many ballots. The closely contested U.S. Senate race would require review of 2,337 of 2,370,445 ballots with machine-assisted auditing and 1,141,900 ballots on average with precinct-based auditing.
While less overwhelming, the results for local ballot issues are highly favorable as well. In this case, machine-assisted audits would review approximately 224 ballots on average--2.28% of the 9,842 average total ballots. Precinct-based audits would require manual review of approximately 3,928 ballots on average--39.91% of the average total ballots. Only five of the forty-two races would require a manual review of more than 50% of the ballots with machine-assisted audits. In contrast, only six of the forty-two races would require a review of less than 50% of the ballots on average with precinct-based audits. Precinct-based audits would require a complete recount in more than half of the cases.
The races that are particularly difficult for machine-assisted auditing are town council, city council, and school board races with 7/492, 5/849, 12/769, 7/246, and 3/2409 margins of victory--requiring manual review of 68.3%, 78.4%, 53.4%, 68.3%, and 90.0% of ballots respectively. In each of these cases, precinct-based auditing would require a full recount.
If comparing machine-assisted audits and precinct-based audits purely on the number of manual ballot reviews, these results indicate a conclusive advantage for machine-assisted audits.
One way to further reduce the number of ballots that need to be verified by hand is to take into account the ballot contents when sampling. Consider a two-candidate mayoral race in which electronic results indicate that Alice beat Bob 10,001 to 10,000. Traditional audit techniques would require that officials consider ballots containing votes for either candidate even though the primary objective is to discover whether any votes for Alice should have been for Bob. Examining only ballots reported to contain votes for Alice could cut auditor work nearly in half, as auditors seek to discover an equivalent amount of fraud in a far smaller pool of ballots. In any two-candidate single-seat race, auditors may restrict their consideration to the subset of ballots claimed to contain votes for the the winning candidate. By considering the contents of ballots, officials may reduce the number of manual verifications required in nearly any race. In the full version of this paper, we generalize these ideas to races with arbitrary numbers of candidates competing for any number of seats.7
The full version of this paper also presents a number of additional methods for increasing the efficiency, practicality, and utility of machine-assisted audits:
A well-designed audit process assures the public that an election's outcome is the product of voters' intentions, not fraud or voting machine flaws. By adding a novel machine-assisted recount procedure to ballot-based audits, we can enjoy the efficiency benefits of those audits while avoiding privacy concerns and retaining the security benefits of combined paper/electronic solutions. Our tests using data from Virginia's November 2006 elections confirm the efficiency advantages of machine-assisted audits, and the extended techniques that we propose promise to reduce even further the number of ballots that need to be inspected by humans.
Though future work is needed to better estimate the costs of machine-assisted audits and to assess other practical challenges that election officials face, we believe that the techniques in this paper offer a promising alternative to traditional precinct-based auditing and warrant further study.
We thank Andrew Appel, Ari Feldman, Shirley Gaw, David Wagner, Harlan Yu, and Bill Zeller for helpful discussions. We also thank Ronald Rivest and Joe Hall for pointing us towards useful papers and resources and the anonymous reviewers for helpful comments.
Calandrino performed this research while under appointment to the Department of Homeland Security (DHS) Scholarship and Fellowship Program under DOE contract number DE-AC05-06OR23100. All opinions expressed in this paper are the authors' and do not necessarily reflect the policies and views of DHS or DOE.
This material is based upon work supported under a National Science Foundation Graduate Research Fellowship. Any opinions, findings, conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the National Science Foundation.
