Workshop Program

All sessions will be held in Grand C unless otherwise noted.

August 6, 2012

8:30 a.m.–9:00 a.m. Monday
9:00 a.m.–10:00 a.m. Monday

Opening Remarks/Keynote Address

Opening Remarks

Program Co-Chairs: J. Alex Halderman, University of Michigan; Olivier Pereira, Université catholique de Louvain

Keynote Address

Speaker: Dean C. Logan, Registrar-Recorder/County Clerk, Los Angeles County

Available Media
10:00 a.m.–10:20 a.m. Monday


Grand Ballroom Foyer

10:20 a.m.–11:10 a.m. Monday

Experience from Practice

Session Chair: Jeremy Epstein, SRI International

Using Prêt à Voter in Victoria State Elections

Craig Burton, Victorian Electoral Commission; Chris Culnane and James Heather, University of Surrey; Thea Peacock and Peter Y A Ryan, University of Luxembourg; Steve Schneider, University of Surrey; Vanessa Teague, University of Melbourne; Roland Wen, University of New South Wales; Zhe (Joson) Xia and Sriramkrishnan Srinivasan, University of Surrey

The Prêt à Voter cryptographic voting system was designed to be flexible and to offer voters a familiar and easy voting experience. In this paper we present a case study of our efforts to adapt Prêt à Voter to the idiosyncrasies of elections in the Australian state of Victoria. The general background and desired user experience have previously been described; here we concentrate on the cryptographic protocols for dealing with some unusual aspects of Victorian voting. We explain the problems, present solutions, then analyse their security properties and explain how they tie in to other design decisions. We hope this will be an interesting case study on the application of end-to-end verifiable voting protocols to real elections.

Available Media

Probing the Front Lines: Pollworker Perceptions of Security & Privacy

Joseph Lorenzo Hall, New York University; Emily Barabas, Gregory Shapiro, Deirdre Mulligan, and Coye Cheshire, University of California, Berkeley

Voting technologies have undergone intense scrutiny in recent years. In contrast, the human components of these socio-technical systems, including the policies and procedures that guide and bind behavior have received less attention. To begin to understand pollworker behavior, we conducted a two stage qualitative investigation in a single jurisdiction to explore the challenges pollworkers face on election day, their recollection of relevant policies and procedures, and their high-level ability to perceive and remedy threats to security and privacy whether they relate directly to policies and procedures or not. We first observed 4 polling places in one California county during the general election in November 2010, recording security and privacy related events. Based on our observations we developed 10 "vignettes", each focusing on a privacy or security risk that we witnessed. In August 2011, we used this instrument to interview twenty pollworkers — recruited from the four polling places we observed the previous year and four additional demographically-similar polling places — in order to understand how they would respond to the vignettes. We report 1) qualitative findings from our observations; and, 2) qualitative findings from our vignette-based interviews of pollworkers. We find that awareness of security-related policies and procedures and comprehension of security risks is low compared with privacy policies, procedures and risks. We find divergent polling place management styles, which we tentatively suggest relate to different perspectives on risk management and trust. We propose that training materials be oriented around the risks they are designed to address, to promote pollworkers' general knowledge of risks to election integrity as well as the specific policies their roles support in order to mitigate risks on election day.

Available Media
11:10 a.m.–11:30 a.m. Monday


Grand Ballroom Foyer

11:30 a.m.–12:20 p.m. Monday

Coercion-Resistant Elections

Session Chair: Peter Y. A. Ryan, University of Luxembourg

Cobra: Toward Concurrent Ballot Authorization for Internet Voting

Aleksander Essex, CHEO Research Institute; Jeremy Clark, Carleton University; Urs Hengartner, University of Waterloo 

We propose and study the notion of concurrent ballot authorization for coercion-resistant, end-to-end verifiable (E2E) internet voting. A central part of providing coercion resistance is the ability for an election authority to filter out fake ballots from legitimate ones in a way that is both private and universally verifiable. This ballot authorization process, however, can potentially come at a heavy computational cost. In previous proposals, the bulk of this computation cannot be performed until the last ballot has been cast. By contrast, concurrent ballot authorization allows ballots to be authorized as they are submitted, allowing the tally to be declared immediately after polls close. An efficient tally is especially important in the coercion-resistant internet voting setting, as it is particularly vulnerable to denial of service attacks caused by floods of fake ballots. We present a proof-of-concept voting system, Cobra, the first coercion-resistant system to offer concurrent ballot authorization. Although Cobra  offers the fastest tallying relative to the related work, it has a registration process that we consider to be too slow to be viable; one that is quadratic in the number of eligible voters. We present Cobra  as a first-step toward what we hope will become a standard feature of coercion-resistant internet voting schemes: concurrent ballot authorization.

Available Media

Coercion-Resistant Electronic Elections with Write-In Candidates

Carmen Kempka, Karlsruhe Institute of Technology

It is often argued in the e-voting community that in the presence of write-in candidates, forced abstention attacks are always possible. Therefore, write-in candidates are often excluded in existing definitions of coercion-resistance arguing that those definitions cannot be achieved by write-in supporting schemes. This is only true if the tally is made public directly. Coercion-resistance may well be achieved if only a fuzzy version of the tally is published. This paper provides a formalization of fuzzy tally representations which enables definitions for coercion-resistance to take into account write-in candidates without being weakened. We also show how the cryptographic voting scheme Bingo Voting can be applied to write-in candidates with respect to this formalization, providing what we believe to be the first evoting scheme that prevents forced abstention while allowing for write-in candidates. We then give a general construction of coercion-resistant schemes that provide a verifiable fuzzy tally representation from mix-based and homomorphic election schemes with trusted authority.

Available Media
12:20 p.m.–1:50 p.m. Monday

Workshop Luncheon

Grand EFGH

1:50 p.m.–2:50 p.m. Monday
2:50 p.m.–3:10 p.m. Monday


Grand Ballroom Foyer

3:10 p.m.–4:10 p.m. Monday


What Would It Take?

Moderators: J. Alex Halderman, University of Michigan; Olivier Pereira, Université catholique de Louvain 

Panelists: Peter Neumann, SRI International, Harri Hursti, SafelyLocked LLC, Josh Benaloh, Microsoft Research, Pamela Smith, Verified Voting, Michael Byrne, Rice University, Dean Logan, Los Angeles County

5:30 p.m.–7:30 p.m. Monday

Rump Session

Session Chair: Stephen Checkoway, Johns Hopkins University

August 7, 2012

8:30 a.m.–9:00 a.m. Tuesday
9:00 a.m.–10:00 a.m. Tuesday
10:00 a.m.–10:20 a.m. Tuesday


Grand Ballroom Foyer

10:20 a.m.–11:10 a.m. Tuesday

New Interfaces

Session Chair: Philip B. Stark, University of California, Berkeley

Operator-Assisted Tabulation of Optical Scan Ballots

Kai Wang, University of California, San Diego; Nicholas Carlini, Eric Kim, Ivan Motyashov, Daniel Nguyen, and David Wagner, University of California, Berkeley

We present OpenCount: a system that tabulates scanned ballots from an election by combining computer vision algorithms with focused operator assistance. OpenCount is designed to support risk-limiting audits and to be scalable to large elections, robust to conditions encountered using typical scanner hardware, and general to a wide class of ballot types—all without the need for integration with any vendor systems. To achieve these goals, we introduce a novel operator-in-the-loop computer vision pipeline for automatically processing scanned ballots while allowing the operator to intervene in a simple, intuitive manner. We evaluate our system on data collected from five risk-limiting audit pilots conducted in California in 2011.

Available Media

A Hybrid Touch Interface for Prêt à Voter

Chris Culnane, University of Surrey

In this paper we propose a novel front-end for Prêt à Voter that aims to maintain the privacy and integrity guarantees found in the paper based version, whilst simultaneously improving the accessibility of Prêt à Voter. Namely, we maintain the Prêt à Voter property that no machine learns your vote, whilst providing improved accessibility. We term this new front-end Hybrid Touch and have implemented it on both a Microsoft Surface and a multi-touch screen. Hybrid Touch combines the privacy benefits of paper with the accessibility benefits of a touch screen. It is this combination that provides more accessibility opportunities as well as allowing Prêt à Voter to handle larger and more complicated elections. Our goal is to develop a single unified front-end, which can be easily augmented with additional accessibility technology, to provide the same core interface for both able-bodied and disabled voters.

Available Media
11:10 a.m.–11:30 a.m. Tuesday


Grand Ballroom Foyer

11:30 a.m.–12:20 p.m. Tuesday

Vote Privacy

Session Chair: Josh Benaloh, Microsoft Research

Cryptanalysis of a Universally Verifiable Efficient Re-encryption Mixnet

Shahram Khazaei, Sharif University; Björn Terelius and Douglas Wikström, Royal Institute of Technology

We study the heuristically secure mix-net proposed by Puiggalí and Guasch (EVOTE 2010). We present practical attacks on both correctness and privacy for some sets of parameters of the scheme. Although our attacks only allow us to replace a few inputs, or to break the privacy of a few voters, this shows that the scheme can not be proven secure.

Available Media

Improving Helios with Everlasting Privacy Towards the Public

Denise Demirel, Technische Universität Darmstadt, Germany; Jeroen van de Graaf, Universidade Federal de Minas Gerais, Brazil; Roberto Samarone dos Santos Araújo, Federal University of Pará, Brazil

In this paper we propose improvements on the Helios voting protocol such that the audit data published by the authority provides everlasting privacy, as opposed to the computational privacy provided currently. We achieve this with minor adjustments to the current implementation. For the homomorphic Helios variant we use Pedersen commitments to encode the vote, together with homomorphic encryption over a separate, private channel between the user and Helios server to send the decommitment values. For the mix-net variant we apply a recent result which shows that mixing with everlasting privacy is possible. 

Observe that we do not claim everlasting privacy towards the server, which, if dishonest, could try to break the homomorphic encryption scheme used in the private channel. Thus towards the authority the voter’s level of privacy is identical to what Helios currently offers. However, our protocol is much harder to attack by an outsider: apart from having to break the computational assumption, an adversary must intercept the communication between the voter and the server to violate ballot privacy of that voter. The feasibility of such an attack depends on the way both parties choose to implement this channel. Both contributions are generic in the sense that they can be applied to other voting protocols that use homomorphic tallying or mixnets.

Available Media
12:20 p.m.–1:50 p.m. Tuesday

Workshop Luncheon

Grand EFGH

1:50 p.m.–2:40 p.m. Tuesday

What Could Go Wrong?

Session Chair: Joseph Lorenzo Hall, New York University

Automated Analysis of Election Audit Logs

Patrick Baxter, Clemson University; Anne Edmundson, Cornell University; Keishla Ortiz, University of Puerto Rico—Arecibo; Ana Maria Quevedo, Miami Dade College; Samuel Rodríguez, University of Puerto Rico—Mayagüez; Cynthia Sturton and David Wagner, University of California, Berkeley

The voting audit logs produced by electronic voting systems contain data that could be useful for uncovering procedural errors and election anomalies, but they are currently unwieldy and difficult for election officials to use in post-election audits. In this work, we develop new methods to analyze these audit logs for the detection of both procedural errors and system deficiencies. Our methods can be used to detect votes that were not included in the final tally, machines that may have experienced hardware problems during the election, and polling locations that exhibited long lines. We tested our analyses on data from the South Carolina 2010 elections and were able to uncover, solely through the analysis of audit logs, a variety of problems, including vote miscounts. We created a public web application that applies these methods to uploaded audit logs and generates useful feedback on any detected issues.

Available Media

A Systematic Process-Model-based Approach for Synthesizing Attacks and Evaluating Them

Huong Phan and George S. Avrunin, University of Masschusetts Amherst; Matt Bishop, University of California, Davis; Lori A. Clarke and Leon J. Osterweil, University of Masschusetts Amherst

This paper describes a systematic approach for incrementally improving the security of election processes by using a model of the process to develop attack plans and then incorporating each plan into the process model to determine if it can complete successfully. More specifically, our approach first applies fault tree analysis to a detailed election process model to find process vulnerabilities that an adversary might be able to exploit, thus identifying potential attacks. Based on such a vulnerability, we then model an attack plan and formally evaluate the process's robustness against such a plan. If appropriate, we also propose modifications to the process and then reapply the approach to ensure that the attack will not succeed. Although the approach is described in the context of the election domain, it would also seem to be effective in analyzing process vulnerability in other domains.

Available Media
2:40 p.m.–3:00 p.m. Tuesday


Grand Ballroom Foyer

3:00 p.m.–3:50 p.m. Tuesday

Election Auditing

Session Chair: Stephen Checkoway, Johns Hopkins University

A Bayesian Method for Auditing Elections

Ronald L. Rivest and Emily Shen, Massachusetts Institute of Technology

We propose an approach to post-election auditing based on Bayesian principles, and give experimental evidence for its efficiency and effectiveness. We call such an audit a “Bayes audit”. It aims to control the probability of miscertification (certifying a wrong election outcome). The miscertification probability is computed using a Bayesian model based on information gathered by the audit so far.

A Bayes audit is a single-ballot audit method applicable to any voting system (e.g. plurality, approval, IRV, Borda, Schulze, etc.) as long as the number of ballot types is not too large. The method requires only the ability to randomly sample single ballots and the ability to compute the election outcome for a profile of ballots. A Bayes audit does not require the computation of a “margin of victory” in order to get started.

Bayes audits are applicable both to ballot-polling audits, which work just from the paper ballots, and to comparison audits, which work by comparing the paper ballots to their electronic representations. The procedure is quite simple and can be described on a single page. The Bayes audit uses an efficient method (which may be based on the use of gamma variates or on Pólya's Urn) for simulating a Bayesian posterior distribution on the tally of a profile of ballots.

A Bayes audit is very similar to single-ballot risk-limiting audits. However, since Bayes audits are based on different principles, the precise relationship between risk-limiting audits and Bayes audits remains open. We provide some initial experimental results indicating that Bayes audits are quite efficient, requiring few ballots to be examined, and that the miscertification rate is indeed kept small, even for very close elections.

We provide some initial experimental results indicating that Bayes audits are quite efficient, requiring few ballots to be examined, and that the miscertification rate is indeed kept small, even for very close elections.

Available Media

BRAVO: Ballot-polling Risk-limiting Audits to Verify Outcomes

Mark Lindeman, Philip B. Stark, and Vincent S. Yates, University of California, Berkeley

Risk-limiting post-election audits guarantee a high probability of correcting incorrect electoral outcomes, regardless of why the outcomes are incorrect. Two types of risk-limiting post-election vote tabulation audits are comparison audits and ballot-polling audits. Comparison audits check some of the subtotals reported by the vote tabulation system, by hand-counting votes on the corresponding ballots. Ballot-polling audits select ballots at random and interpret those ballots by hand until there is strong evidence that the outcome is right, or until all the votes have been counted by hand: They directly assess whether the outcome is correct, rather than assessing whether the tabulation was accurate. Comparison audits have advantages, but make large demands on the vote tabulation system. Ballot-polling audits make no such demands. For small margins, they can require large samples, but the total burden may still be modest for large contests, such as county-wide or state-wide races. This paper describes BRAVO, a flexible protocol for risk-limiting ballot-polling audits. Among 255 state presidential contests between 1992 and 2008, the median expected sample size to confirm the plurality winner in each state using BRAVO was 307 ballots (per state). Ballot-polling audits can improve election integrity immediately at nominal incremental cost to election administration.

Available Media
3:50 p.m.–4:10 p.m. Tuesday


Grand Ballroom Foyer

4:10 p.m.–5:10 p.m. Tuesday


Lightning Debates

Moderator: David Wagner, University of California, Berkeley

Panelists: Ron Rivest, MIT; Philip Stark, University of California, Berkeley; Barbara Simons, IBM Research; Brian Hancock, Election Assistance Commission

Available Media
5:10 p.m.–5:30 p.m. Tuesday
5:30 p.m.–6:30 p.m. Tuesday