Chapter 6
Esoteric Protocols

6.1 Secure Elections

Computerized voting will never be used for general elections unless there is a protocol that both maintains individual privacy and prevents cheating. The ideal protocol has, at the very least, these six requirements:

1.  Only authorized voters can vote.

2.  No one can vote more than once.

3.  No one can determine for whom anyone else voted.

4.  No one can duplicate anyone else’s vote. (This turns out to be the hardest requirement.)

5.  No one can change anyone else’s vote without being discovered.

6.  Every voter can make sure that his vote has been taken into account in the final tabulation.

Additionally, some voting schemes may have the following requirement:

7.  Everyone knows who voted and who didn’t.

Before describing the complicated voting protocols with these characteristics, let’s look at some simpler protocols.

Simplistic Voting Protocol #1

(1)  Each voter encrypts his vote with the public key of a Central Tabulating Facility (CTF).

(2)  Each voter sends his vote in to the CTF.

(3)  The CTF decrypts the votes, tabulates them, and makes the results public.

This protocol is rife with problems. The CTF has no idea where the votes are from, so it doesn’t even know if the votes are coming from eligible voters. It has no idea if eligible voters are voting more than once. On the plus side, no one can change anyone else’s vote; but no one would bother trying to modify someone else’s vote when it is far easier to vote repeatedly for the result of your choice.

Simplistic Voting Protocol #2

(1)  Each voter signs his vote with his private key.

(2)  Each voter encrypts his signed vote with the CTF’s public key.

(3)  Each voter sends his vote to a CTF.

(4)  The CTF decrypts the votes, checks the signatures, tabulates the votes, and makes the results public.

This protocol satisfies properties one and two: Only authorized voters can vote and no one can vote more than once—the CTF would record votes received in step (3). Each vote is signed with the voter’s private key, so the CTF knows who voted, who didn’t, and how often each voter voted. If a vote comes in that isn’t signed by an eligible voter, or if a second vote comes in signed by a voter who has already voted, the facility ignores it. No one can change anyone else’s vote either, even if they intercept it in step (3), because of the digital signature.

The problem with this protocol is that the signature is attached to the vote; the CTF knows who voted for whom. Encrypting the votes with the CTF’s public key prevents anyone from eavesdropping on the protocol and figuring out who voted for whom, but you have to trust the CTF completely. It’s analogous to having an election judge staring over your shoulder in the voting booth.

These two examples show how difficult it is to achieve the first three requirements of a secure voting protocol, let alone the others.

Voting with Blind Signatures

We need to somehow dissociate the vote from the voter, while still maintaining authentication. The blind signature protocol does just that.

(1)  Each voter generates 10 sets of messages, each set containing a valid vote for each possible outcome (e.g., if the vote is a yes or no question, each set contains two votes, one for “yes” and the other for “no”). Each message also contains a randomly generated identification number, large enough to avoid duplicates with other voters.

(2)  Each voter individually blinds all of the messages (see Section 5.3) and sends them, with their blinding factors, to the CTF.

(3)  The CTF checks its database to make sure the voter has not submitted his blinded votes for signature previously. It opens nine of the sets to check that they are properly formed. Then it individually signs each message in the set. It sends them back to the voter, storing the name of the voter in its database.

(4)  The voter unblinds the messages and is left with a set of votes signed by the CTF. (These votes are signed but unencrypted, so the voter can easily see which vote is “yes” and which is “no.”)

(5)  The voter chooses one of the votes (ah, democracy) and encrypts it with the CTF’s public key.

(6)  The voter sends his vote in.

(7)  The CTF decrypts the votes, checks the signatures, checks its database for a duplicate identification number, saves the serial number, and tabulates the votes. It publishes the results of the election, along with every serial number and its associated vote.

A malicious voter, call him Mallory, cannot cheat this system. The blind signature protocol ensures that his votes are unique. If he tries to send in the same vote twice, the CTF will notice the duplicate serial number in step (7) and throw out the second vote. If he tries to get multiple votes signed in step (2), the CTF will discover this in step (3). Mallory cannot generate his own votes because he doesn’t know the facility’s private key. He can’t intercept and change other people’s votes for the same reason.

The cut-and-choose protocol in step (3) is to ensure that the votes are unique. Without that step, Mallory could create a set of votes that are the same except for the identification number, and have them all validated.

A malicious CTF cannot figure out how individuals voted. Because the blind signature protocol prevents the facility from seeing the serial numbers on the votes before they are cast, the CTF cannot link the blinded vote it signed with the vote eventually cast. Publishing a list of serial numbers and their associated votes allows voters to confirm that their vote was tabulated correctly.

There are still problems. If step (6) is not anonymous and the CTF can record who sent in which vote, then it can figure out who voted for whom. However, if it receives votes in a locked ballot box and then tabulates them later, it cannot. Also, while the CTF may not be able to link votes to individuals, it can generate a large number of signed, valid votes and cheat by submitting those itself. And if Alice discovers that the CTF changed her vote, she has no way to prove it. A similar protocol, which tries to correct these problems, is [1195, 1370].

Voting with Two Central Facilities

One solution is to divide the CTF in two. Neither party would have the power to cheat on its own.

The following protocol uses a Central Legitimization Agency (CLA) to certify voters and a separate CTF to count votes [1373].

(1)  Each voter sends a message to the CLA asking for a validation number.

(2)  The CLA sends the voter back a random validation number. The CLA maintains a list of validation numbers. The CLA also keeps a list of the validation numbers’ recipients, in case someone tries to vote twice.

(3)  The CLA sends the list of validation numbers to the CTF.

(4)  Each voter chooses a random identification number. He creates a message with that number, the validation number he received from the CLA, and his vote. He sends this message to the CTF.

(5)  The CTF checks the validation number against the list it received from the CLA in step (3). If the validation number is there, the CTF crosses it off (to prevent someone from voting twice). The CTF adds the identification number to the list of people who voted for a particular candidate and adds one to the tally.

(6)  After all votes have been received, the CTF publishes the outcome, as well as the lists of identification numbers and for whom their owners voted.