Alice, Bob, Carol, and Dave are voting yes or no (0 or 1) on a particular issue. Assume each voter has a public and private key. Also assume that everyone knows everyone else’s public keys.

(1)  Each voter chooses his vote and does the following:

(a)  He attaches a random string to his vote.

(b)  He encrypts the result of step (a) with Dave’s public key.

(c)  He encrypts the result of step (b) with Carol’s public key.

(d)  He encrypts the result of step (c) with Bob’s public key.

(e)  He encrypts the result of step (d) with Alice’s public key.

(f)  He attaches a new random string to the result of step (e) and encrypts it with Dave’s public key. He records the value of the random string.

(g)  He attaches a new random string to the result of step (f) and encrypts it with Carol’s public key. He records the value of the random string.

(h)  He attaches a new random string to the result of step (g) and encrypts it with Bob’s public key. He records the value of the random string.

(i)  He attaches a new random string to the result of step (h) and encrypts it with Alice’s public key. He records the value of the random string.
If E is the encryption function, R _i is a random string, and V is the vote, his message looks like:

E_A(R₅,E_B(R₄,E_C(R₃,E_D(R₂,E_A(E _B(E_C(E_D(V,R₁))))))))

Each voter saves the intermediate results at each point in the calculation. These results will be used later in the protocol to confirm that his vote is among those being counted.

(2)  Each voter sends his message to Alice.

(3)  Alice decrypts all of the votes with her private key and then removes all of the random strings at that level.

(4)  Alice scrambles the order of all the votes and sends the result to Bob.
Each vote now looks like this:

E_B(R₄,E_C(R₃,E_D(R₂,E_A(E_B(E_C(E_D(V,R₁)))))))

(5)  Bob decrypts all of the votes with his private key, checks to see that his vote is among the set of votes, removes all the random strings at that level, scrambles all the votes, and then sends the result to Carol.
Each vote now looks like this:

E_C(R₃,E_D (R₂,E_A(E_B(E_C(E_D(V,R₁))))))

(6)  Carol decrypts all of the votes with her private key, checks to see that her vote is among the set of votes, removes all the random strings at that level, scrambles all the votes, and then sends the result to Dave.
Each vote now looks like this:

E_D(R₂,E_A(E_B(E_C(E_D(V,R₁)))))

(7)  Dave decrypts all of the votes with his private key, checks to see that his vote is among the set of votes, removes all the random strings at that level, scrambles all the votes, and sends them to Alice.
Each vote now looks like this:

E_A(E_B(E_C(E_D(V,R₁))))

(8)  Alice decrypts all the votes with her private key, checks to see that her vote is among the set of votes, signs all the votes, and then sends the result to Bob, Carol, and Dave.
Each vote now looks like this:

S_A(E_B(E_C(E_D(V,R₁))))

(9)  Bob verifies and deletes Alice’s signatures. He decrypts all the votes with his private key, checks to see that his vote is among the set of votes, signs all the votes, and then sends the result to Alice, Carol, and Dave.
Each vote now looks like this:

S_B(E_C(E_D(V,R₁)))

(10)  Carol verifies and deletes Bob’s signatures. She decrypts all the votes with her private key, checks to see that her vote is among the set of votes, signs all the votes, and then sends the result to Alice, Bob, and Dave.
Each vote now looks like this:

S_C(E_D(V,R₁))

(11)  Dave verifies and deletes Carol’s signatures. He decrypts all the votes with his private key, checks to see that his vote is among the set of votes, signs all the votes, and then sends the result to Alice, Bob, and Carol.
Each vote now looks like this:

S_D(V,R₁)

(12)  All verify and delete Dave’s signature. They check to make sure that their vote is among the set of votes (by looking for their random string among the votes).

(13)  Everyone removes the random strings from each vote and tallies the votes.

Not only does this protocol work, it is also self-adjudicating. Alice, Bob, Carol, and Dave will immediately know if someone tries to cheat. No CTF or CLA is required. To see how this works, let’s try to cheat.

If someone tries to stuff the ballot, Alice will detect the attempt in step (3) when she receives more votes than people. If Alice tries to stuff the ballot, Bob will notice in step (4).

More devious is to substitute one vote for another. Since the votes are encrypted with various public keys, anyone can create as many valid votes as needed. The decryption protocol has two rounds: round one consists of steps (3) through (7), and round two consists of steps (8) through (11). Vote substitution is detected differently in the different rounds.

If someone substitutes one vote for another in round two, his actions are discovered immediately. At every step the votes are signed and sent to all the voters. If one (or more) of the voters noticed that his vote is no longer in the set of votes, he immediately stops the protocol. Because the votes are signed at every step, and because everyone can backtrack through the second round of the protocol, it is easy to detect who substituted the votes.

Substituting one vote for another during round one of the protocol is more subtle. Alice can’t do it in step (3), because Bob, Carol, or Dave will detect it in step (5), (6), or (7). Bob could try in step (5). If he replaces Carol’s or Dave’s vote (remember, he doesn’t know which vote corresponds to which voter), Carol or Dave will notice in step (6) or (7). They wouldn’t know who tampered with their vote (although it would have had to be someone who had already handled the votes), but they would know that their vote was tampered with. If Bob is lucky and picks Alice’s vote to replace, she won’t notice until the second round. Then, she will notice her vote missing in step (8). Still, she would not know who tampered with her vote. In the first round, the votes are shuffled from one step to the other and unsigned; it is impossible for anyone to backtrack through the protocol to determine who tampered with the votes.