Practical mix-based election scheme

• US 6,317,833 B1
• Filed: 11/23/1998
• Issued: 11/13/2001
• Est. Priority Date: 11/23/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Jakobsson, Bjorn Markus
• Primary Examiner(s): Peeso, Thomas R.
• Assistant Examiner(s): DARROW, JUSTIN T
• Application Number:
  US09/197,799
• Time in Patent Office: 1,086 Days
• Field of Search: 380/28, 380/30, 380/47, 380/279, 713/170, 713/176, 713/181, 705/12, 235/51, 235/56, 235/57
• US Class Current: 713/181
• CPC Class Codes: G07C 13/00 Voting apparatus
• CPC Class Codes: H04L 2209/463 Electronic voting
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems

Abstract

In an improved election process, a voter constructs his or her vote message (potentially padded with a random string) and encrypts it. The voter then signs the encrypted vote and posts the signed, encrypted, vote on a bulletin board. After the voting booths have closed, a set of talliers decrypt the encrypted votes with the aid of the mix network, to obtain the final tally, but without revealing or being able to notice the relationship between votes cast and votes in the tally.

Claims

1. A method for generating a vote message comprising the steps of:

a voter encrypting a vote with a public key of an authority, using a temporary secret selected at random, forming an encrypted vote;

generating a signature on the encrypted vote using a secret key of said voter; and

sending said encrypted vote and said signature for tallying.

2. The method of claim 1 where said authority performs mixing, decryption, and tallying of votes.

3. The method of claim 2 where said authority is distributed among independent entities.

4. The method of claim 2 where said authority employs a plurality of processors, each under control of an independent party.

5. A method for generating a vote message comprising the steps of:

a voter encrypting a vote with a public key of an authority, using a temporary secret selected at random;

generating a signature on the encrypted vote using a secret key of said voter; and

sending the signed encrypted vote for tallying, where said step of generating a signature includes the steps of

generating a first signature on the encrypted vote using a secret key of said voter;

generating a second signature that employs said temporary secret as a second secret key.

6. A method for generating a vote message comprising the steps of:

a voter encrypting a vote with a public key of an authority, using a temporary secret selected at random;

generating a signature on the encrypted vote using a secret key of said voter; and

sending the signed encrypted vote for tallying, where said authority performs mixing of encrypted votes.

7. The method of claim 6 where said authority performs decryption of mixed encrypted votes.

8. A method for voting comprising the steps of:

a voter encrypting a vote with a public key of an authority, using a temporary secret selected at random;

generating a signature on the encrypted vote using a secret key of said voter;

sending the encrypted vote and the signature for tallying;

collecting the sent encrypted vote with encrypted votes sent by other voters;

verifying signatures associated with said collected encrypted votes;

removing encrypted votes that violate prescribed rules, to form a weeded-out set of encrypted votes;

mixing said weeded-out set of encrypted votes to form a mixed set; and

decrypting said mixed set of encrypted votes to yield a set of decrypted votes.

9. The method of claim 8 where said step of generating a signature comprises the steps of:

generating a first signature on the encrypted vote using a secret key of said voter; and

generating a second signature that employs said temporary secret as a second secret key.

10. The method of claim 8 where said step of decrypting is performed by said authority.

11. The method of claim 8 where said step of decrypting is performed by said authority and said step of mixing is performed by other than said authority.

12. The method of claim 8 where said authority comprises a plurality of entities that are independent of each other.

13. The method of claim 8 where said authority is distributed among independent parties.

14. The method of claim 8 where said rules include the rule that signatures of encrypted votes must verify.

15. The method of claim 8 where said rules include the rule that not more than one vote may be admitted for each allowed public key that is associated with a voter'"'"'s private key.

16. The method of claim 8 where said step of removing, when faced with a violation where more than one vote calls for use of a given public key that is associated with a secret key of a voter, removes all of the encrypted votes that call for use of said public key.

17. The method of claim 8 where said step of removing, when faced with a violation where more than one vote calls for use of a given public key that is associated with a secret key of a voter, removes all but the first of the encrypted votes that call for use of said public key.

18. The method of claim 8 where said step of removing, when faced with a violation where more than one vote calls for use of a given public key that is associated with a secret key of a voter, removes all but the last of the encrypted votes that call for use of said public key.

19. The method of claim 8 further comprising a step of certifying said set of decrypted votes.

20. The method of claim 8 further comprising a step, interposed between said step of mixing and said step of decrypting, a step of generating a certification of said weeded-out set of encrypted votes, and sending said certification and said weeded-out set of encrypted votes to said authority.

21. The method of claim 8 further comprising a step, interposed between said step of removing and said step of mixing and decrypting, a step of generating a certification of said weeded-out set of encrypted votes, and sending said certification and said weeded-out set of encrypted votes to said authority.

22. A method for tallying votes comprising the steps of:

collecting encrypted votes;

verifying signatures associated with said collected encrypted votes;

removing encrypted votes that violate prescribed rules, to form a weeded-out set of encrypted votes;

mixing said weeded-out set of encrypted votes to form a mixed set; and

decrypting said mixed set to yield a set of decrypted votes.

23. The method of claim 22 where said steps of mixing and decrypting are performed by two different entities.

24. The method of claim 22 where said step of decrypting is performed by a decryption authority.

25. The method of claim 24 where said authority is distributed among a plurality of independent entities.

26. The method of claim 22 wherein said step of verifying includes a step of removing encrypted votes whose signatures do not verify.

27. The of claim 22 further comprising a step, interposed between said step of mixing and said step of decrypting, a step of generating a certification of said weeded-out set of encrypted votes, and sending said certification and said weeded-out set of encrypted votes to said authority.

28. The method of claim 22 further comprising a step, interposed between said step of removing and said step of mixing, a step of generating a certification of said weeded-out set of encrypted votes, and sending said certification and said weeded-out set of encrypted votes to said authority.

29. The method of claim 22 further comprising a step of certifying said set of decrypted votes.

30. The method of claim 22 where said rules include the rule that not more than one vote may be admitted for each allowed public key that is associated with a voter'"'"'s private key.

31. The method of claim 22 where said step of removing, when faced with a violation where more than one vote calls for use of a given public key that is associated with a secret key of a voter, removes all of the encrypted votes that call for use of said public key.

32. The method of claim 22 where said step of removing, when faced with a violation where more than one vote calls for use of a given public key that is associated with a secret key of a voter, removes all but the first of the encrypted votes that call for use of said public key.

33. The method of claim 22 where said step of removing, when faced with a violation where more than one vote calls for use of a given public key that is associated with a secret key of a voter, removes all but the last of the encrypted votes that call for use of said public key.