CDR: A secure voting protocol

[Ray Dillinger]

Okay, this information is old hat to most folk here - but 
it seems relevant just now, and if the infrastructure had 
been in place for this election, it could have saved us a 
heck of a lot of trouble.

			Bear




An Election Protocol: Or, a way for people in voting societies to 
exercise their franchise without stirring themselves to get down to 
the polls or, for that matter, leaving their computer. 

1) Alice the voter creates twenty sets of ballots.  Each set of 
   ballots contains one ballot each for all the different things 
   Alice could vote for. ie, if it's a presidential election,  
   each set would contain:
   a ballot voting for the American Reform Party candidate,
   a ballot voting for the Constitutional Party candidate
   a ballot voting for the Democratic Party candidate,
   a ballot voting for the Green Party candidate, 
   a ballot voting for the Libertarian Party candidate, 
   a ballot voting for the Nazi Party candidate, 
   a ballot voting for the Republican Party candidate, 
   a ballot voting for the Socialist Party candidate, 
   a ballot voting for the Whig Party candidate,
   et cetera.

   Each set of ballots also has an identification number, chosen 
   at random from a number field big enough to make collisions 
   unlikely.  The identification number is on each ballot, and 
   is common to all ballots in that set.  For 3 * 10^8 voters, 
   a 25-digit decimal number should make collisions acceptably 
   unlikely. 

2) Alice now blinds all the ballot sets with different blinding 
   factors and transmits them to Bob the vote tabulator.  She Also 
   sends Bob a digitally signed message that says "I'm voting -- 
   Alice". 

3) Bob checks the digital signature, checks to make sure he hasn't 
   already signed a ballot for Alice, picks one of the twenty sets, 
   and communicates his choice to Alice. 

4) Alice responds by sending Bob the blinding factors for the 
   other nineteen sets of ballots. 

5) Bob unblinds the nineteen sets of ballots, making sure that 
   they all have exactly one ballot per candidate and that each 
   set uses its own identification number. Satisfied that Alice 
   is not trying to "pull a fast one", Bob then signs each 
   ballot in the chosen set of ballots and returns them all to 
   Alice.  

6) Alice unblinds the ballot set while preserving Bob's signature. 
   She now has a set of ballots signed by Bob. She encrypts the ballot 
   reflecting her choice with Bob's public key and sends it to Bob
   anonymously. 

7) Bob decrypts the ballot, checks his own signature to make sure 
   it's valid, checks the identification number to make sure no 
   other ballots from this set have been submitted already, writes 
   down the identification number to check future ballots against, 
   and increments his tally for the candidate Alice selected.

8) When the election is over, Bob publishes the ballots and the 
   signed "I'm voting" messages.  Alice can scan the published 
   information to make sure that her vote is present and that 
   the numbers all add up correctly.  Alice can also check to 
   make sure that there are NOT more ballots than there were 
   "I'm voting" messages, preventing Bob from stuffing the ballot 
   box.



The protocol enforces the one vote per voter rule. If Alice tries 
to obtain more than one set of ballots, Bob will detect it in step 3.
If Alice tries to submit more than one ballot from the same set, Bob 
will detect it in step 7.

No one other than the voter can tell whom a particular voter voted 
for. Bob signs the ballots from the selected set under a blinding 
factor in step 5.  When he later gets the unblinded ballot in step 
6, he can check his signature, but cannot correlate it to any 
particular ballot he's signed. 

The only person who can prove who Alice voted for is Alice.  She 
can communicate her  submitted ballot to a third party before Bob 
publishes the results, and when Bob publishes the ballots the third 
party can make sure there's a ballot that matches.  

Bob is able to generate fake ballots, but he cannot generate signed 
"I'm voting" messages from eligible voters.  Therefore if he uses 
fake ballots to try to stuff the ballot box, he will be detected 
in step 8. One exception to this is if people obtain ballots (giving 
him "I voted" messages) but do not then complete the protocol by 
submitting a vote. Bob can then enter a fake ballot without being 
detected. 

One fact about this protocol is that even though you cannot prove 
who anyone voted *for*, you can prove that they did or did not 
*vote*.  This may or may not be a problem depending on the application. 

A vulnerability about this protocol is that Alice can transfer her vote 
if she wants to.  To do this, Alice would unblind her ballots in step 
6, and send the whole set to Carol.  Carol could pretend to be Alice 
in step 7, and check in step 8 to make sure Alice didn't submit one 
of her own votes (invalidating Carol's purchased vote).  

So California Democratic supporters could swap ballots with Nevada 
Green supporters, enabling the Nevadans to vote Green in California 
(where it's "safe" to vote for a third party because there isn't a 
close race between the major parties one of whom they regard as 
EVIL) while the Californians voted Democratic in Nevada, where they'd 
stand a better chance of having their vote make a difference in the 
determination of electoral votes and keeping the EVIL guy out of 
office. 

Again, this may or may not be a problem depending on the application - 
in most voting situations, where there is no electoral college, there 
would be no motive to exchange ballots.  But selling of ballots is also 
usually bad for the process, and the US seems to dislike transfer of 
ballots in general as regards its own elections - so I'm listing this 
as a vulnerability.