Figure 1.
Polls are popping up all over the World Wide Web. With a few clicks of your mouse, you can cast an unofficial vote for a US Presidential hopeful or a member of the Japanese Parliament, express your opinion on a variety of important and not-so-important issues, vote for your favorite Web sites, and add your ratings to the running average for any of several thousand movies. These polls are fun, and many are even useful, but few are designed to maintain the levels of security and privacy that we come to expect from governmental elections in many democratic countries. While some of these Internet polls take precautions to prevent people from stuffing the ballot box, they generally do so at the expense of voter privacy.
Simultaneously achieving security and privacy in electronic polls is a problem that must be solved if the Internet is to be used for serious large-scale surveys and elections. As more people gain access to the Internet, electronic voting is likely to become increasingly appealing to geographically distributed organizations that currently hold vote-by-mail elections. Electronic elections have the potential of being cheaper and less time consuming to administer than vote-by-mail elections. Eventually electronic voting may be a viable solution to increasing voter participation in governmental elections. However, if not carefully designed, electronic voting systems can be easily compromised, thus corrupting results or violating voters' privacy.
In this article we will discuss the characteristics of a good electronic voting system and explore cryptographic techniques that can be used to build actual implementations with these characteristics.
Prior to an election, organizers determine who is eligible to vote. This may involve a formal registration period or an announcement that anyone who is a member of a certain group as of a certain time may vote. Once the election begins, administrators may validate the credentials of those attempting to vote. This may involve asking voters for identification cards or passwords. Generally, this procedure also involves keeping track of who has already voted so that eligible voters may vote only once. After validating each voter, the administrators collect the voted ballots. Finally, the voted ballots are tallied to determine the election result. Thus, a typical election involves registration, validation, collection, and tallying. Because the registration task often takes place prior to the actual election and may employ techniques currently used for traditional elections, this article will focus on the other three tasks.
To have confidence in the election results, people must believe that the election tasks are performed properly. However, there are numerous opportunities for corruption during the performance of each of these tasks. For example, election authorities may cheat by knowingly allowing ineligible voters to register, allowing registered voters to cast more than one vote, or systematically miscounting or destroying ballots. In addition, ineligible voters may register (often under the name of someone who is deceased) or eligible voters may register under multiple names. Registered voters (eligible and otherwise) may also be impersonated at the polls, and ballot boxes, ballots, and vote counting machines may be compromised.
Traditionally, election fraud has been prevented through the use of physical security measures, audit trails, and observers representing of all parties involved. But the prevention of election fraud is made more difficult by the frequent requirement that votes remain private. Observers may not observe a ballot until after it has been placed in a ballot box, and audit trails must not provide the ability to link a ballot back to the voter who cast it. Even so, these security measures generally work well enough that the possibility of widespread fraud is small and people have confidence that election results are accurate.
When designing an electronic polling system, it is essential to consider ways in which the polling tasks can be performed electronically without sacrificing voter privacy or introducing opportunities for fraud. In order to determine whether a system performs these tasks well, it is useful to develop a set of criteria for evaluating system performance. The following is one set of desirable characteristics for electronic polling systems which incorporates the characteristics of most systems described in the electronic voting literature [3]:
Accuracy. A system is accurate if (1) it is not possible for a vote to be altered, (2) it is not possible for a validated vote to be eliminated from the final tally, and (3) it is not possible for an invalid vote to be counted in the final tally.
In the most accurate systems the final vote tally must be perfect, either because no inaccuracies can be introduced or because all inaccuracies introduced can be detected and corrected. Partially accurate systems can detect but not necessarily correct inaccuracies.
Democracy. A system is democratic if (1) it permits only eligible voters to vote and (2) it ensures that each eligible voter can vote only once.
Privacy. A system is private if (1) neither election authorities nor anyone else can link any ballot to the voter who cast it and (2) no voter can prove that he or she voted in a particular way.
The second privacy factor is important for the prevention of vote buying and extortion. Voters can only sell their votes if they are able to prove to the buyer that they actually voted according to the buyer's wishes. While some may argue that in a democratic and capitalistic society there is nothing wrong with voluntarily selling one's vote, most people would probably agree that people should never be forced to sell their votes. Benaloh and Tuinstra [1] report that the use of extortion to force people to vote in a particular way is common in some small Italian villages, where the voting systems employed lend themselves particularly well to this purpose.
Verifiability. A system is verifiable if anyone can independently verify that all votes have been counted correctly.
A weaker definition of verifiability used by some authors allows that a system is verifiable if it allows voters to verify their own votes and correct any mistakes they might find without sacrificing privacy. Less verifiable systems might allow mistakes to be pointed out -- but not corrected -- or might allow verification of the process by party representatives but not by individual voters. Traditional voting systems generally only allow for minimal verification by party representatives.
Convenience. A system is convenient if it allows voters to cast their votes quickly, in one session, and with minimal equipment or special skills.
Flexibility. A system is flexible if it allows a variety of ballot question formats, including open ended questions. Flexibility is important for write-in candidates and some survey questions. Some cryptographic voting protocols are inflexible because they only allow for single-bit (yes/no) votes.
Mobility. A system is mobile if there are no restrictions (other than logistical ones) on the location from which a voter can cast a vote.
One of the reasons people are interested in electronic voting systems is that they can be mobile. Voter participation might increase if people could easily cast votes from computers in their homes, offices, schools, and libraries. Of course, for governmental elections it would be essential to retain centralized polling places for people who would not otherwise have access to computers.
The mobility property itself is a major contributor to some of the problems associated with designing a secure and private electronic voting system. By allowing voters to cast their votes from virtually anywhere, we dramatically expand the universe of ineligible people who may attempt to vote. We also limit our abilities to prevent voters from proving how they voted, as there are no longer private voting booths that can prevent vote buyers from observing vote sellers as they cast their votes.
Figure 1.
Although this simple protocol is flexible, mobile, and convenient, it has several major problems. First, voters could stuff the ballot box by using other voters' identification numbers. Second, although the validator program is not supposed to read or record the contents of the ballot, voters cannot really be sure that the validator program does not violate their privacy in this way. Third, there is no way to ensure that the validator does not alter ballots before sending them to the tallier or manufacture ballots that were never actually submitted by voters. Fourth, there is no way to ensure that the tallier accurately records the votes.
We can solve the problem of voters stuffing the ballot box by requiring voters to sign their ballots with digital signatures -- perhaps using a program such as PGP. Thus, unless a voter's secret key has been compromised, we can be assured that voters are not using others' identification numbers. Furthermore, we can prevent the validator from violating voters' privacy by having voters encrypt their ballots with the tallier's public key. Thus the validator will not be able to read or alter the ballots. However, if the validator and tallier team up and the validator obtains the tallier's secret key, privacy can be compromised. Thus we need a more sophisticated approach to incorporating cryptography into our electronic voting system.
The one and two agency protocols. Nurmi, Salomaa, and Santean [6] proposed an approach that solves many of the problems mentioned above. In this "Two Agency Protocol," shown in Figure 2, the electronic validator distributes a secret identification tag to each voter just prior to the election. The validator then sends the tallier a list of all identification tags, with no record of the corresponding voters. Each voter sends the tallier his or her identification tag and an encrypted file containing a copy of the tag and the voted ballot. At this point the tallier can make sure the identification tag is valid, but the program has no way of examining the contents of the ballot. The tallier publishes the encrypted file (so that the voter has proof that the file was submitted on time), and the voter responds by sending the tallier the key necessary to decrypt it. When the election is over, the tallier publishes a list of all voted ballots and the corresponding encrypted files. At this point the voters can confirm that their votes were counted properly. Any voter who finds an error can protest by submitting the encrypted file and decryption key again. Because the encrypted file was published earlier, the tallier cannot deny having received it.
Figure 2.
The Two Agency Protocol is verifiable by individual voters (unlike the simple protocol discussed earlier), however, it still has several problems. Most importantly, it does not protect voters' privacy if the tallier and validator collude. Thus, the authors state that if the two agencies are going to work together, there might as well be just one agency.
The One Agency Protocol [7] is identical to the Two Agency Protocol, except for the tag distribution procedure. In the One Agency Protocol, tags are distributed by the tallier (there is no validator) using an ANDOS (all-or-nothing disclosure of secrets) protocol for secret selling of secrets. This solves the collusion problem; however, the ANDOS protocol is quite computationally complex and does not scale well.
Both of the Nurmi, Salomaa, and Santean protocols fail to satisfy the second part of the privacy property and part of the accuracy property. The mechanism that allows voters to verify that their votes were counted correctly also allows them to prove that they voted in a particular way. (Of course, even if they could not prove this after the election, they could still prove they voted in a particular way by having someone watch them vote. The protocols that attempt to solve the privacy problem completely [1] also require voters to vote inside a voting booth. In addition, these protocols limit each ballot to a single bit.) The accuracy property is not completely satisfied because the tallier may cast votes for all the voters who have been assigned tags but do not exercise their right to vote. These voters may discover this violation and report it, but they cannot prove that they did not actually vote.
Blind signature protocols. When David Chaum first introduced the concept of blind signatures [2] in 1982, he suggested that blind signatures could be used for secret ballot elections. Ten years later, Fujioka, Okamoto, and Ohta developed a practical voting scheme that uses blind signatures to solve the collusion problem inherent in protocols like the Two Agency Protocol without significantly increasing the overall complexity of the protocol [5]. (A number of other, less satisfactory, blind signature protocols have also been proposed.)
Blind signatures are a class of digital signatures that allow a document to be signed without revealing its contents. The effect is similar to placing a document and a sheet of carbon paper inside an envelope. If somebody signs the outside of the envelope, they also sign the document on the inside of the envelope. The signature remains attached to the document, even when it is removed from the envelope.
In the Fujioka, Okamoto, and Ohta protocol, shown in Figure 3, the voter prepares a voted ballot, encrypts it with a secret key, and blinds 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 that is published after all voters vote. After the list has been published, voters verify that their ballots are on the list and send the tallier the decryption keys necessary to open their ballots. The tallier uses these keys to decrypt the ballots and add the votes to the election tally. After the election the tallier publishes the decryption keys along with the encrypted ballots so that voters may independently verify the election results.
Figure 3.
Cranor and Cytron's Sensus system [3] is based closely on the Fujioka, Okamoto, and Ohta scheme. The main difference between these schemes emerges after the voter has submitted the encrypted ballot to the tallier. In the Sensus protocol, the tallier responds by sending a receipt to the voter. The voter may submit the decryption key immediately after receiving this receipt, completing the entire voting process in one session. The Sensus system employs a pollster program that performs all cryptographic functions and transactions with the election programs on the voter's behalf. Tests conducted with a prototype implementation of Sensus indicate that the entire voting process can be completed within a few minutes.
The Sensus protocol is one of the few electronic voting protocols that has actually been implemented. Another variation of the Fujioka, Okamoto, and Ohta protocol was implemented by Davenport, Newberger, and Woodard [4] and used to conduct a student government election.
The Sensus protocol possesses most of the desirable characteristics; however, it fails to correct some of the problems inherent in the One and Two Agency protocols. Perhaps the most important problem is that the election administrator (in this case the validator) can cast votes for abstaining voters. These invalid votes can be detected by the abstaining voters themselves or by an auditor who checks the signatures on all the validation requests submitted. However, there is no way to identify the invalid ballots and remove them from the tally -- if significant numbers of invalid votes are detected, the election will have to be repeated. If voters who wish to abstain submit blank ballots, this problem can be avoided.
None of the protocols discussed in this article satisfy the verifiability property completely because none can be verified by any interested party. Those that allow voters to verify that their own votes were counted correctly satisfy the property to a large degree. However, a verification system that relies on voters taking action after the election is over is not likely to be thoroughly exercised. One way to encourage voters to verify their votes would be to program the pollster agent to automatically verify the vote after the election and report back to the voter if any problems are detected.
When properly designed, electronic voting systems should be suitable for a variety of polling applications, including large-scale elections. Although electronic governmental elections may be a long way off, professional and social organizations have already started to conduct surveys and elections electronically. While most of these elections currently ignore privacy concerns, advances in email and Web browser software that can easily interface with cryptography software should pave the way for secure and private electronic elections in the near future.
Copyright 1996 by Lorrie Faith Cranor
Want more Crossroads articles about Social Issues? Go to the index or to the next one or the previous one.
Last Modified:
Location: www.acm.org/crossroads/xrds2-4/voting.html