Extended Abstract
Lorrie Faith Cranor
Washington University
Department of Computer Science
One Brookings Drive Box 1045
St. Louis, MO 63130
lorracks@cs.wustl.edu
Due to the rapid growth of computer networks and advances in cryptographic techniques, electronic polling is now a viable alternative for many elections and surveys. Electronic polling over the Internet can be convenient for voters with access to networked computers, even if voters are geographically distributed. In addition, electronic polls can be inexpensive to administer. However, if not carefully designed, electronic polling systems can be easily compromised, corrupting results or violating voters' privacy. Many designs exist for electronic polling systems that are secure and private, but impractical for large-scale elections.
Problem: Design and implement a practical, secure system for conducting Internet surveys and elections that protects voters' privacy.
We reviewed several sets of ``ideal'' election system characteristics found in the literature [1,9,10,11,12] and developed a set of properties that are likely to be desirable in an electronic polling system:
Several cryptographic schemes have been published which possess these properties to varying degrees [2,3,5,7,6,8]. However the more private of these schemes are inconvenient or impractical for large-scale elections.
In the Two Agency Protocol developed by Nurmi, Salomaa, and Santean [10], one agency --- the validator --- distributes secret identification tags to voters prior to the election. The other agency --- the tallier --- is given a list of these tags with no record of the corresponding voters. Voters use the tags as tokens that permit their votes to be counted. This scheme is verifiable. However, if the validator and tallier collude they can determine the mapping between tag and voter, violating voter privacy.
The One Agency Protocol is identical to the Two Agency Protocol, except that tags are distributed by the tallier using an ANDOS protocol. This solves the collusion problem, but it requires the use of a very complex protocol for distributing tags. Another problem with both the One and Two Agency Protocols is that the tallier may cast votes for all voters who have been assigned a tag but do not exercise their right to vote [11,10].
Fujioka, Okamoto, and Ohta developed a practical voting scheme that uses blind signatures [4] to solve the collusion problem without significantly increasing the overall complexity of the protocol [9]. Our solution is based closely on this scheme. The main difference is our scheme allows votes to be cast in a single session, while [9] requires two sessions.
Following the work of Fujioka, Okamoto, and Ohta [9], we have designed and implemented an electronic polling system called Sensus. Sensus has been designed as an easily adaptable modular system. The polling protocol requires the existence of validator, tallier, and pollster modules. Additional modules, such as registrar or ballot-authoring modules, may augment the Sensus system. The pollster acts as a voter's agent, performing all cryptographic and data transfer functions on a voter's behalf.
The Sensus protocol requires the voter (with the assistance of the pollster) to prepare a voted ballot, encrypt it with a secret key, and blind it. The voter then signs the ballot and sends it to the validator. The validator verifies that the signature belongs to a registered voter who has not yet voted. If the ballot is valid, the validator signs the ballot and returns it to the voter. The voter removes the blinding encryption layer, revealing an encrypted ballot signed by the validator. The voter then sends the resultant signed encrypted ballot to the tallier. The tallier checks the signature on the encrypted ballot. If the ballot is valid, the tallier places it on a list of valid ballots to be published after all voters vote. The tallier then signs the encrypted ballot and returns it to the voter as a receipt. Upon receiving the receipt, the voter sends the tallier the ballot decryption key. The tallier uses the key to decrypt the ballot and add the vote to the tally.
We have implemented basic registrar, pollster, validator, and tallier modules in C and Perl on a Unix system.
We have presented desirable properties of electronic polling systems, as well as the design and implementation of a practical system that satisfies these properties well.
Sensus is accurate and democratic. It will not accept ballots from those not registered to vote, nor will it accept more than one ballot from each registered voter. Invalid ballots can only be introduced into the final tally by the validating authority if some voters do not submit ballots. Sensus is private, protecting voter privacy even when election authorities collude (however it does not prevent voters from proving how they voted). It is also verifiable, allowing voters to verify that their votes have been counted correctly, and anonymously challenge the results should their votes be miscounted.
Mock elections conducted with Sensus indicate that the system is convenient. Voters can generally mark a short ballot and complete all transactions within a few minutes. Sensus is also mobile and flexible.
We have demonstrated that Sensus is a practical system for conducting small-scale Internet polls. With further testing and improvements, we believe Sensus will be suitable for large-scale Internet surveys and elections.