Efficient User-Guided Ballot Image Verification
Back to Program
Optical scan voting systems are ubiquitous. Unfortunately, optical scan technology is vulnerable to failures that can result in miscounted votes and lost confidence. While manual counts may be able to detect these failures, counting all the ballots by hand is in many situations impractical and prohibitively expensive. In this paper, we present a novel approach for examining a large set of ballot images to verify that they were properly interpreted by the opscan system. Our system allows the user to simultaneously inspect and verify many ballot images at once. In this way, our scheme is significantly more efficient than manually recounting or inspecting ballots one at a time, providing the accuracy associated with human inspection at reduced cost. We evaluate our approach on approximately 30,000 ballots cast in the June 2008 Humboldt County Primary Election and demonstrate that our approach improves the efficiency of human verification of ballot images by an order of magnitude.

OpenScan: A Fully Transparent Optical Scan Voting System
Back to Program
Existing optical scan voting systems depend on the integrity of the scanner. If a compromised — or merely faulty — scanner reports incorrect results, there is no ready mechanism for detecting errors. While methods exist for ameliorating these risks, none of them are entirely satisfactory. We propose an alternative: a radically open system in which any observer can simultaneously and independently count the ballots for himself. Our approach, called OpenScan, combines digital video recordings of ballot sheet feeding with computer vision techniques to allow any observer with a video camera to obtain a series of ballot images that he can then process with ordinary optical scan counting software. Preliminary experimental results indicate that OpenScan produces accurate results at a manageable cost of around $1000 in hardware plus $0.0010 per ballot counted.

On the Use of Financial Data as a Random Beacon
Back to Program
In standard voting procedures, random audits are one method for increasing election integrity. In the case of cryptographic (or end-to-end) election verification, random challenges are often used to establish that the tally was computed correctly. In both cases, a source of randomness is required. In two recent binding cryptographic elections, this randomness was drawn from stock market data. This approach allows anyone with access to financial data to verify the challenges were generated correctly and, assuming market fluctuations are unpredictable to some degree, the challenges were generated at the correct time. However the degree to which these fluctuations are unpredictable is not known to be sufficient for generating a fair and unpredictable challenge. In this paper, we use tools from computational finance to provide an estimate of the amount of entropy in the closing price of a stock. We estimate that for each of the 30 stocks in the Dow Jones industrial average, the entropy is between 6 and 9 bits per trading day. We then propose a straightforward protocol for regularly publishing verifiable 128-bit random seeds with entropy harvested over time from stock prices. These "beacons" can be used as challenges directly, or as a seed to a deterministic pseudorandom generator for creating larger challenges.

Queuing and Elections: Long Lines, DREs and Paper Ballots
Back to Program
Computerized touchscreen "Direct Recording Electronic" (DRE) voting systems have been used by over 1/3 of American voters in recent elections. In many places, insufficient DRE numbers, in combination with lengthy ballots and high voter traffic, have caused long lines and disenfranchised voters who left without voting. We have applied computer queuing simulation to the voting process and conclude that far more DREs, at great expense, would be needed to keep waiting times low. Alternatively, paper ballot-optical scan systems can be easily and economically scaled to prevent long lines and meet unexpected contingencies. We have developed a heuristic "Queue Stop Rule" that can be applied to prevent long lines at voting stations. We have also carried out queuing simulations of other parts of the voting process, for example, voter check-in and ballot scanning. Our results can be used to help plan cost-effective election systems that will produce expeditious elections.

Determining the Causes of AccuVote Optical Scan Voting Terminal Memory Card Failures
Back to Program
Optical scan (OS) voting systems play an increasing role in the United States elections, with over 40 states deploying such systems. The AccuVote optical scanners (AV-OS) manufactured by ES&S account for over 20% of all OS systems. OS systems typically use removable media (cards) to provide election-specific programming to the scanners and to convey precinct election results for central tabulation. Several reports document occurrences of AV-OS memory card failures, with up to 15% of all cards failing in some cases. This paper reports on determining the causes of memory card failures that lead to complete loss of data from the card. An initial experimental analysis identified the battery discharge as a significant part of the problem. This finding led to the question of the dependability of the built-in function of the AccuVote OS system that issues a warning when the memory card contains a low-voltage battery. We identified the components used to implement this function in one type of AccuVote memory card. Using the specifications of the commodity batteries that are used in these cards, we determined the time interval from the instant when a battery warning is issued by the AccuVote to the point when the battery does not have enough voltage to retain data on the memory card. We show that such interval is about 2 weeks. Thus timely warnings cannot be provided to protect against battery discharge and loss of data during the election process. The factors contributing to the short warning interval are likely to apply to other battery-backed RAM cards, such as those used in the ES&S Model 100. Recommendations for mitigating the problem are made in light of the expected behavior of the warning system.

Modeling and Analyzing Faults to Improve Election Process Robustness
Back to Program
This paper presents an approach for continuous process improvement and illustrates its application to improving the robustness of election processes. In this approach, the Little-JIL process definition language is used to create a precise and detailed model of an election process. Given this process model and a potential undesirable event, or hazard, a fault tree is automatically derived. Fault tree analysis is then used to automatically identify combinations of failures that might allow the selected potential hazard to occur. Once these combinations have been identified, we iteratively improve the process model to increase the robustness of the election process against those combinations that seem the most likely to occur. We demonstrate this approach for the Yolo County election process. We focus our analysis on the ballot counting process and what happens when a discrepancy is found during the count. We identify two single points of failure (SPFs) in this process and propose process modifications that we then show remove these SPFs.

Exploiting the Client Vulnerabilities in Internet E-voting Systems: Hacking Helios 2.0 as an Example
Back to Program
Helios is a web-based open-audit voting system designed using state of the art web technologies and advanced cryptographic techniques to provide integrity of ballots and voter secrecy in an insecure Internet environment. In this paper, we demonstrate a simple attack against Helios 2.0 that takes advantage of the fact that every candidate in Helios can provide a URL referring to his/her candidacy statement. A malicious candidate, who wishes to win a Helios-managed election, uploads a specially crafted PDF file containing a candidacy statement to his/her website. The attack is then triggered against each voter who is using a vulnerable machine. The security of the machine is undermined, e.g., when the voter visits the attacker's webpage. In essence, we exploit Adobe Acrobat/Reader's vulnerabilities to install a malicious browser extension on the voters' machines. Such an extension provides an opportunity for an attacker which may fool the voter (using Social Engineering) into accepting a hacked ballot. Due to our attack Helios 2.0 was upgraded to Helios 3.0. We discuss generalizations and the impact of the latest upgrade of Helios on security. We also discuss defences against this attack, generalizations and the impact of the latest upgrade of Helios on security.

Computational Complexity and Information Asymmetry in Election Audits with Low-Entropy Randomness
Back to Program
We investigate the security of an election audit using a table of random numbers prepared in advance. We show how this scenario can be modeled using tools from combinatorial graph theory and computational complexity theory, and obtain the following results: (1) A randomly generated table can be used to produce a statistically good election audit that requires less randomness to be generated in real time by the auditors. (2) It is likely to be computationally infeasible for an adversary to compute, given a pre-prepared table of random numbers, how to minimize their chances of detection in an audit. (3) It is computationally infeasible to distinguish a truly random table from a malicious table that has been modified to decrease the probability of detecting cheating in certain precincts.

Super-Simple Simultaneous Single-Ballot Risk-Limiting Audits
Back to Program
Simultaneous risk-limiting audits of a collection of contests have a known minimum chance of leading to a full hand count if the outcome of any of those contests is wrong. Risk-limiting audits are generally performed in stages. Each stage involves drawing a sample of ballots, comparing a hand count of the votes on those ballots with the original count, and assessing the evidence that the original outcomes agree with the outcomes that a full hand count would show. If the evidence is sufficiently strong, the audit can stop; if not, more ballots are counted by hand and the new evidence is assessed. This paper derives simple rules to determine how many ballots must be audited to allow a simultaneous risk-limiting audit to stop at the first stage if the error rate in the sample is sufficiently low. The rules are of the form "audit at least ρ/μ ballots selected at random." The value of ρ depends on the simultaneous risk limit and the amount of error to be tolerated in the first stage without expanding the audit. It can be calculated once and for all without knowing anything about the contests. The number μ is the "diluted margin": the smallest margin of victory in votes among the contests, divided by the total number of ballots cast across all the contests. The initial sample size does not depend on any details of the contests, just the diluted margin. This is far simpler than previous methods. For instance, suppose we are auditing a collection of contests at simultaneous risk limit 10%. In all, N ballots were cast in those contests. The smallest margin is V votes: The diluted margin is μ = V /N . We want the audit to stop at the first stage provided the fraction of ballots in the sample that overstated the margin of some winner over some loser by one vote is no more than μ/2 and no ballot overstates any margin by two votes. Then an initial sample of 15.2/μ ballots suffices. If the sample shows any two-vote overstatements or more than 7 ballots with one-vote overstatements, more sampling might be required, depending on which margins have errors. If so, simple rules that involving only addition, subtraction, multiplication, and division can be used to determine when to stop.

Single-Ballot Risk-Limiting Audits Using Convex Optimization
Back to Program
We take an information-theoretic approach to sequential election auditing. By comparing how far an empirical distribution of audited votes diverges from any distribution in which the reported outcome is incorrect, we gain a high degree of confidence in the outcome when our procedure confirms the reported results.

Performance Requirements for End-to-End Verifiable Elections
Back to Program
The term "end-to-end verifiability" has been used over the past several years to describe multiple voting system proposals. The term has, however, never been formally defined. As a result, its meaning tends to change from voting system to voting system. We propose a definition for end-to-end verifiability of public elections based on performance requirements, as opposed to design requirements. We suggest a set of properties that collectively define the term. The properties help detect some of the possible problems that may influence the integrity of the election outcome.

Parallel Shuffling and Its Application to Prêt à Voter
Back to Program
We consider the problem of verifiable parallel shuffling in which the same shuffle is simultaneously performed on two or more lists of input ciphertexts, each list encrypted under a different key. We present three parallelisations of shuffle proofs from different paradigms. The properties of each protocol are analyzed and contrasted, and their suitability for electronic voting discussed. We show how parallel shuffling solves the problem of verifiable distributed ballot construction in the Prêt à Voter electronic voting scheme. In conjunction with the use of a new cryptographic primitive for partially-homomorphic addition, the incorporation of parallel shuffling is shown to produce schemes with superior privacy properties to existing protocols. We additionally present several original attacks on Prêt à Voter and demonstrate that our modified schemes are immune.

Eperio: Mitigating Technical Complexity in Cryptographic Election Verification
Back to Program
Cryptographic (or end-to-end) election verification is a promising approach to providing transparent elections in an age of electronic voting technology. In terms of execution time and software complexity however, the technical requirements for conducting a cryptographic election audit can be prohibitive. In an effort to reduce these requirements we present Eperio: a new, provably secure construction for providing a tally that can be efficiently verified using only a small set of primitives. We show how common-place utilities, like the use of file encryption, can further simplify the verification process for election auditors. Using Python, verification code can be expressed in 50 lines of code. Compared to other proposed proof-verification methods for end-to-end election audits, Eperio lowers the technical requirements in terms of execution time, data download times, and code size. As an interesting alternative, we explain how verification can be implemented using TrueCrypt and the built-in functions of a spreadsheet, making Eperio the first end-to-end system to not require special-purpose verification software.

Towards Publishable Event Logs That Reveal Touchscreen Faults
Back to Program
Federal standards require that electronic voting machines log information about the voting system behavior to support post-election audits and investigations. Our study examines interface issues commonly reported in touchscreen voting systems (miscalibration, insensitivity, etc.) and the voter interaction data that can be collected to allow investigation of these issues while at the same time preserving the right to a secret ballot. We also provide empirically derived metrics that can detect these issues by analyzing these data.

Baseline Usability Data for a Non-Electronic Approach to Accessible Voting
Back to Program
The Help America Vote Act mandated that all polling places have an accessible method of voting that provides privacy and independence. Direct Recording Electronic voting machines (DREs) have been assumed to be the solution to providing accessible voting, but there is reason to believe extant systems do not adequately serve this goal (Runyan, 2007). This study is a first step in addressing the lack of existing data on the usability of nonelectronic accessible voting methods and examined the usability of Vote-PAD, a tactile paper ballot. In comparison with sighted users voting on an identical paper ballot, blind users took five times longer to vote. Both blind and sighted voters showed similar error rates and types, and reported similarly high satisfaction with the usability of paper ballots. Blindfolded subjects, representative of newly blind individuals, had reliably lower satisfaction using this interface, and took significantly longer than either blind or sighted subjects. This provides a baseline comparison point for future studies of accessibility solutions, including though not limited to DREs.