DIMACS Workshop on Electronic Voting -- Theory and Practice

May 26 - 27, 2004
DIMACS Center, CoRE Building, Rutgers University, Piscataway, NJ

Markus Jakobsson, RSA Laboratories, mjakobsson@rsasecurity.com
Ari Juels, RSA Laboratories, ajuels@rsasecurity.com
Presented under the auspices of the Special Focus on Communication Security and Information Privacy and
Special Focus on Computation and the Socio-Economic Sciences.


Andre Dos Santos, Georgia Institute of Technology

Title: Providing Trusted Paths Using Untrusted Components

A problem that is always highlighted when discussing electronic voting is the security of the device used for input, and sometimes computing, the votes. In current solutions the device used for voting is considered secure. However, experience has shown that many times the devices used for voting is left unattended for a long period of time. The time the device is left alone represents an opportunity for malicious parties to modify the software inside the device so that votes will be miscomputed favoring one, or many, candidates. In addition, insiders could program some, or all, voting machine to do the same miscomputation. In my research I advocate that tamper resistant devices should be used as trusted computing bases (TCB) in order to decrease the likelihood of insider attacks and completely stop attacks against unattended devices. My research takes into consideration the small memory size of most tamper resistant devices to compare it to a TCB, enabling complete verification of the code. In addition, the well defined steps for manufacturing a tamper resistant device, from the floppy that contains the code to the actual burn of the ROM, can be better monitored than generic voting machines. A well monitored code and process verification will decrease the likelihood of an insider attack. Economics will stop attacks against unattended devices. Tamper resistant devices have consistently shown weakness in relation to its resistance to tampering. However, there is a price to be paid in order to overcome the resistance of a device. In my research I am designing a system that ideally will enable the selling of only one vote per device broken. In addition, a device is considered broken only if it's attacked by complex, and expensive, methods (e.g., layer peeling and analysis using electronic microscope). Therefore, due to cost factors, the attack against the devices will not be feasible. Although many aspects of electronic voting are addressed by my research I propose a talk about my ongoing research that addresses one very important topic related to the use of tamper resistant devices for electronic voting, namely how to provide a trusted path between the user and the device. As already known, the tamper resistant devices that are the best candidates for use on electronic voting systems, like smart cards and USB tokens, do not have direct I/O capability. Therefore, these devices need to use additional, potentially malicious computing devices to interact with a user. I propose the use of hard AI problems in order to enable trusted output from a tamper resistant device to a user. A user receiving data (or not receiving) using this trusted output path can disable the tamper resistant device, for example disconnecting it from the reader, creating then a one bit trusted input path. The idea of using AI hard problems for creating a trusted output path is for the tamper resistant device to generate data that the untrusted device have to present to the user without modification; or solve a hard AI problem. For example, considering speech synthesizing and recognition a hard AI problem, the tamper resistant device can generate a speech file saying "yes" or "no" with the user's mother voice to represent a "yes" or "no" vote received by it. Since the untrusted device cannot synthesize the user's mother voice it cannot maliciously change the user's choice that goes to the tamper resistant device. The just described approach is a simplified view of the approach I propose. A more detailed description of this solution is given on the attached paper. I am currently working on implementing the approach using different AI domains to check which one is the most appropriate.

Edith Elkind, Princeton University and Helger Lipmaa, Helsinki University of Technology

Title: How Hard Is It to Manipulate Voting?

We demonstrate how to make voting protocols resistant against manipulations by computationally bounded malicious voters. It extends the recent results of Conitzer and Sandholm in two important directions: we demonstrate how to make voting manipulation as hard as inverting one-way functions (rather than just worst-case hard), and we show that our hardness results hold against a large fraction of manipulating voters (rather than a single voter). Both improvements address important concerns in the field of secure voting systems. We also discuss the limitations of the current approach, showing that it cannot be used to achieve certain very desirable hardness criteria.

Kwangjo Kim, Information and Communications University, Korea

Title: Lessions from Internet voting during 2002 FIFA WorldCup Korea/Japan(TM)"

We discuss all the lessones of Internet voting system called as "Votopia" which was jointly developed by Korea and Japan IT experts to celebrate 2002 FIFA Korea/Japan Worldcup. This project is believed to be one of first and best practices using cryptography, information security, DB management, computer network and web programming etc. in the world and further directions will be discussed to promote our efforts.

Andy Neff, VoteHere, Inc.

Title: Trustworthy Elections Without Paper Ballots: Why Vote Receipts Deserve Consideration

Would people play the lottery if they were not issued a ticket as proof of purchase? Probably not. In this talk we consider the fundamental information requirements for secret ballot elections and argue that modern cryptographic techniques provide new tools that can facilitate the election equivalent of the lottery ticket -- a vote receipt -- while still meeting the critical requirement for ballot secrecy. Further, we observe that such "secret" vote receipts enable the safe use of complex computing devices in the vote collection and vote counting process. In fact, they can bring to large scale elections a level of transparency previously achieved only by small, "board room" sized paper ballot elections.

Akira Otsuka, Tokyo University, Japan

Title: An Unconditionally Secure Electronic Voting Scheme

We investigate an electronic voting scheme which does not depend upon any computational assumptions. We follow the scenario of PVSS(Publicly Verifiable Secret Sharing)-based voting schemes introduced by Stadler, where we have a number of voters and some talliers, every votes are divided into encrypted shares so that the correctness of the tallying process can be verified by every player. The main result of this study is to achieve an efficient electronic voting scheme with unconditional security, that is, the privacy of votes and its security are protected in information theoretic sense. The approach taken here is threshold approach with pre-distributed private keys, the main parameters are $V$, $T$ and $p$, where $V$ is the maximum number of tolerable colluding voters, $T$ is the maximum number of tolerable colluding talliers, and $p$ is the success probability of adversary against some security goal. Two new efficient primitives are introduced: unconditionally secure verifiable secret sharing (US-VSS) and unconditionally secure oblivious polynomial evaluation (US-OPE). These primitives are efficient in communication complexity and storage size required to store pre-distributed private keys. Our voting scheme, based on these primitives, is practical. For one vote, each voter must send in total $VT^2\log(1/p)$ bits of data non-interactively to talliers, which corresponds to $900$KBytes when parameters are chosen as $V=10,000$, $T=3$ and $p=2^{-80}$. The size of private key for each voter is $(n+1)VT\log(p)$ bits, where $n$ is the number of votes issuable by each voter. For one-time scheme ($n=1$), the size of private key is only $600$KBytes.

Rob Richie, Center for Voting and Democracy

Title: The Politics of Good Voting Systems

Election administration in the United States is a uniquely decentralized system that creates barriers for better voting processes. What is being done and could be done to make the system more coherent and effective? In addition, what are sensible public interest criteria that voting machines should meet? How can those interested in fair and secure voting equipment effectively achieve their goals?

Michael Shamos, Carnegie Mellon University

Title: Theory v. Practice in Electronic Voting

During the past 20 years, much theoretical work has been done to develop protocols to ensure that electronic voting schemes will possess a variety of desirable properties, such as receipt-freeness or universal verifiability. Often these protocols address only a small portion of the actual voting process, leaving the remainder open to "out-of-band" attacks of various kinds. We will review the overall problem of registration, voting, tabulation and reporting requirements, discuss the value of paper records and list a large number of potential trouble spots that require attention. A conclusion is that absentee voting, which is becoming ever more common, is the elephant in the room whose impact must be addressed.

Barbara Simons, SERVE

Title: Why Internet voting is Insecure: a Case Study

The U.S. Department of Defense had been planning to run an Internet-based voting "experiment" called SERVE (Secure Electronic Registration and Voting Experiment) for the 2004 presidential primaries and general election. In order to evaluate the security of SERVE, a group of computer scientists were asked to review the program. On Jan. 21, 2004 four members of the review panel, including the speaker, produced a report, available at www.servesecurityreport.org, that analyzed the security risks of SERVE and called for SERVE to be shut down. On Feb. 3, 2004, the Department of Defense cancelled SERVE.

In this talk I shall discuss the security problems with Internet voting in general and SERVE in particular. If time permits, I'll also discuss some vulnerabilities of other forms of voting such a paperless touch screen machines.

Poorvi Vora, George Washington University

Title: Citizen Verified Voting: An implementation of Chaum's voter verifiable scheme

Citizen Verified Voting: An implementation of Chaum's voter verifiable Scheme Dept. of Computer Science, George Washington University

We will describe and demo our Java implementation of Chaum's voter-verifiable scheme using encrypted paper receipts (as appeared in IEEE Security and Privacy, vol. 2, No. 1, Jan-Feb. 2004). An exposition of the scheme is at chaum.pdf.

Dan Wallach, Rice University

Title: Hack-a-Vote: Demonstrating Security Issues with Electronic Voting Systems

A representative democracy depends on a universally trusted voting system for the election of representatives; voters need to believe that their votes count, and all parties need to be convinced that the winner and loser of the election were declared legitimately. Direct recording electronic (DRE) voting systems are increasingly being deployed to fill this role. Unfortunately, doubts have been raised as to the trustworthiness of these systems. This work presents a research voting system and associated class project which was used to demonstrate several classes of bugs that might occur in such a voting system unbeknownst to voters, with the difficulty of detecting these bugs through auditing. The intent of this project is to justify the mistrust sometimes placed in DRE voting systems that lack a voter-verifiable audit trail.

Previous: Participation
Next: Registration
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on May 26, 2004.