Secure anonymous message transfer and voting scheme

• US 5,682,430 A
• Filed: 01/23/1995
• Issued: 10/28/1997
• Est. Priority Date: 01/23/1995
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Research Institute, Inc. (NEC Corporation)
• Inventors: Sako, Kazue, Kilian, Joseph John
• Primary Examiner(s): Barron, Jr., Gilberto
• Application Number:
  US08/376,568
• Time in Patent Office: 1,009 Days
• Field of Search: 380/28, 380/30, 380/42, 364/409, 395/933
• US Class Current: 380/30
• CPC Class Codes: G07C 13/00 Voting apparatus
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 2209/463 Electronic voting
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs

Abstract

A number-theoretic based algorithm provides for secure anonymous message transfer and electronic voting. A voter or sender may cast an encrypted vote or message that is processed through n centers in a manner which prevents fraud and authenticates the votes. Any interested party can verify that each vote has been properly counted. The invention can be realized by current-generation personal computers with access to an electronic bulletin board.

Claims

1. A method of secure anonymous message transfer from a plurality of senders by use of a plurality of mixing centers comprising the steps of:

(a) choosing constants which are posted for senders S₁, S₂, . . . S_l and mixing centers, C₁, C₂, . . . C_n ;

(b) each sender S_k constructing an encrypted message which is posted;

(c) a first mixing center C₁ processing the posted messages from each sender S_k which processed messages are then posted for use by the next center;

(d) each mixing center C₂ through C_n-1 sequentially processing the processed messages from the previous center, which sequentially processed messages are then posted for use by the next center;

(e) the last mixing center C_n processing messages from the previous center C_n-1 and posting the result;

(f) each mixing center proving the validity of its processing, which proof is posted; and

(g) channel checker verifying correctness of the execution from posted messages when necessary.

2. A method of secure anonymous message transfer as set forth in claim 1, where steps (c), (d) and (e) further comprises:

(h) providing each mixing center with a secret key; and

(i) said processing including using the secret key of a respective mixing center.

3. A method of secure anonymous message transfer as set forth in claim 2, where said proving comprises executing algorithm prove-DECRYPT.

4. A method of secure anonymous message transfer as set forth in claim 3, where said proving further comprises executing algorithm prove-SHUFFLE.

5. A method of secure anonymous message transfer as set forth in claim 3, where said executing algorithm prove-DECRYPT is executed for multiple messages together.

6. A method of secure anonymous message transfer as set forth in claim 2, where said proving comprises applying the Fiat-Shamir method.

7. A method of secure anonymous message transfer as set forth in claim 2, further comprising (j) shuffling the messages.

8. A method of secure anonymous message transfer as set forth in claim 1, where steps (c), (d), and (e) further comprises shuffling the messages.

9. A method of secure anonymous message transfer as set forth in claim 8, where after the last mixing center C_n posts the result, each mixing center executes algorithm prove-DECRYPT using the result.

10. A method of secure anonymous message transfer as set forth in claim 8, further comprising providing each mixing center with a secret key and where after the last mixing center C_n posts the result, each mixing center performs said processing using its respective secret key and the result.

11. A method of secure anonymous message transfer as set forth in claim 8, where said proving comprises executing algorithm prove-SHUFFLE.

12. A method of secure anonymous message transfer as set forth in claim 11, where said proving comprises applying the Fiat-Shamir method.

13. A method of secure anonymous message transfer as set forth in claim 8, where said proving comprises applying the Fiat-Shamir method.

14. A method of secure anonymous message transfer as set forth in claim 1, where said proving comprises applying the Fiat-Shamir method.

15. A method of secure anonymous message transfer as set forth in claim 1, where in step (b) each sender S_k posts its encrypted message substantially simultaneously.

16. A method of secure anonymous message transfer as set forth in claim 1, where in step (b) each sender S_k constructs its encrypted message using a key of said first mixing center C₁ and said encrypted message includes a signature of a respective sender S_k.

17. A method of secure anonymous message transfer as set forth in claim 1, where in step (b) each sender S_k constructs an encrypted message which is publicly revealed after said first mixing center C₁ receives a respective encrypted message.

18. A method of secure anonymous message transfer as set forth in claim 1, said first mixing center C₁ processing only legitimate messages and processing only one message from each sender.

19. A method of secure anonymous message transfer as set forth in claim 18, where said senders are voters and said messages are votes.

20. A method of secure anonymous message transfer as set forth in claim 19, where said processing of said last mixing center C_n comprises computing a tally.

21. An apparatus for secure anonymous message transfer comprising:

a bulletin board having constants;

a plurality of senders, S₁, S₂, . . . , S_l, each sender S_k constructing an encrypted message using the constants and posting said encrypted message to said bulletin board;

a plurality of mixing centers, C₁, C₂, . . . , C_n, a first mixing center C₁ processing the posted messages from each sender using the constants and posting a processed message to said bulletin board for use by the next mixing center, each mixing center C₂ through C_n-1 sequentially processing the processed message from the previous mixing center using the constants and posting a further processed message to said bulletin board for use by the next mixing center, the last mixing center C_n processing messages from the previous center C_n-1 using the constants and posting the result on said bulletin board;

means associated with each respective mixing center for proving the validity of the processing of the respective mixing center, which proof is posted on said bulletin board; and

channel checking means for verifying the correctness of execution from posted messages.

22. An apparatus for anonymous message transfer as set forth in claim 21, further comprising secret key means associated with each respective mixing center for providing a secret key to said respective mixing center for processing messages.

23. An apparatus for anonymous message transfer as set forth in claim 22, where said mixing center processes messages by executing algorithm prove-DECRYPT.

24. An apparatus for anonymous message transfer as set forth in claim 23, where each said means associated with each respective mixing center executes algorithm prove-DECRYPT.

25. An apparatus for anonymous message transfer as set forth in claim 24, where each means associated with each respective mixing center executes algorithm prove-DECRYPT for multiple messages.

26. An apparatus for anonymous message transfer as set forth in claim 21, where said mixing center processes messages by shuffling messages.

27. An apparatus for anonymous message transfer as set forth in claim 26, where said mixing centers process messages by executing algorithm prove-SHUFFLE.

28. An apparatus for anonymous message transfer as set forth in claim 26, where each said means associated with each respective mixing center executes algorithm prove-SHUFFLE.

29. An apparatus for anonymous message transfer as set forth in claim 21, where each sender S_k posts its encrypted message to said bulletin board substantially simultaneously.

30. An apparatus for anonymous message transfer as set forth in claim 22, where each sender S_k constructs its encrypted message using said secret key of said first mixing center C₁ and including a signature of the respective sender S_k.

31. An apparatus for anonymous message transfer as set forth in claim 21, where each sender constructs an encrypted message which is publicly revealed after said first mixing center C₁ receives a respective encrypted message.

32. An apparatus for anonymous message transfer as set forth in claim 21, said first mixing center C₁ processing only legitimate messages and processing only one message from each sender.

33. An apparatus for anonymous message transfer as set forth in claim 32, where said senders are voters and said messages are votes.

34. An apparatus for anonymous message transfer as set forth in claim 33, where said result comprises a tally.