CSAIL Publications and Digital Archive header
bullet Technical Reports bullet Work Products bullet Research Abstracts bullet Historical Collections bullet

link to publications.csail.mit.edu link to www.csail.mit.edu horizontal line

 

Research Abstracts - 2006
horizontal line

horizontal line

vertical line
vertical line

Secure Voting

Ben Adida & Ronald L. Rivest

Overview

Voting presents a number of hard cryptographic problems. Two central requirements of elections give rise to these problems:

  • the voter would like strong assurance that her vote was recorded and tallied correctly, yet
  • she cannot be allowed to prove how she voted, as that would allow vote selling and coercion.

The Secure Voting project combines careful system security and innovative cryptographic methods to achieve these election goals.

Voting Process

Though there is much interesting in online voting techniques, there is no known method by which online voting can be securely achieved, as coercion presents a significant complication of elections without private, monitored isolation booths. It would be unfortunate to simply discard this entire area of research on the sole basis that coercion cannot be prevented. Pre-Voting [1] attempts to sidestep this limitation so as to enable continued research in online voting techniques.

In a Pre-Voting scenario, Alice the voter can prepare her ballot online. She may even prepare multiple ballots, if she is uncertain, or if she wants to claim that she is voting one way while actually voting differently. On election day, Alice enters the isolation booth, and may simply cast her saved ballot using its ID number. She may also, at her discretion, change her ballot, even replacing it entirely.

Pre-Voting allows the research community to continue exploring new methods of online voter user interfaces, even online secure transmissions. If Alice is coerced in any way, she may change her vote in the booth. Even if she wants to sell her vote of her own volition, she has no way to prove that she didn't change her vote inside the booth.

Anonymous Channels in Voting

In the more classic voting setting, cryptography can provide a significant level of verifiability called universal verifiability, where any observer can verify that the election was not corrupted, even if all administrators conspire. Such systems generally depend on an anonymous channel whose role it is to dissociate the identity of Alice, the voter, from her ballot.

We have introduced Public Mixing [2], a technique which allows for the anonymization of inputs using only public computation on election day. All proofs of correctness can be performed beforehand, leaving little to chance in the critical hours after the polls close. Public Mixing is effectively an obfuscation of a mixnet program. Our solution is currently a proof of concept, with estimated performance acceptable only for small elections. However, as the process of public mixing is superior in operational quality to that of mixnets, the dominant alternative, further research in this area is warranted and promising.

Encrypted Voter Receipts

In a cryptographic voting setting, Alice uses a voting machine to create an encrypted ballot. How can she be sure that the machine correctly encoded her vote? Some solutions have been proposed informally in the literature, whereby Alice, the voter, receives an encrypted receipt of her interaction. This receipt, in combination with private information the voter sees in the isolation booth, proves to Alice how she voted. In and of itself, the receipt cannot be used to prove or even glean Alice's vote.

We have prepared the first formal definition of this encrypted voter receipt, and proven a particularly efficient protocol secure against this definition. Our definition effectively considers a Zero-Knowledge model where the verifier is human and needs assistance to complete the verification of the proof. Thus, our model is called Assisted Zero-Knowledge [3]. Two main issues arise in this new setting:

  • Alice, the voter, is strongly computationally limited. In fact, she may not be able to do more than simple string comparisons.
  • The receipt provided by the voting machine is not simulatable, as it is printed on paper in a way the voter cannot replicate, and it may often be digitally signed by the voting machine.

Research Support

This project is part of the Caltech/MIT Voting Technology Project, which is funded by the Knight Foundation and the Carnegie Foundation.

References:

[1] Ronald L. Rivest. Preliminary Voting -- PreVoting. Available at http://theory.csail.mit.edu/~rivest/Rivest-PreliminaryVotingPrevoting.pdf

[2] Ben Adida and Douglas Wikstrom. Obfuscated Ciphertext Mixing. Availalbe as IACR ePrint 2005/394.

[3] Ben Adida and C. Andrew Neff. Assisted Zero-Knowledge: a Formal Treatment of Encrypted Voter Receipts. In submission.

vertical line
vertical line
 
horizontal line

MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
The Stata Center, Building 32 - 32 Vassar Street - Cambridge, MA 02139 - USA
tel:+1-617-253-0073 - publications@csail.mit.edu