Secure electronic voting using partially compatible homomorphisms

• US 5,495,532 A
• Filed: 08/19/1994
• Issued: 02/27/1996
• Est. Priority Date: 08/19/1994
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation, NEC Research Institute, Inc. (NEC Corporation)
• Inventors: Sako, Kazue, Kilian, Joseph J.
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/293,363
• Time in Patent Office: 557 Days
• Field of Search: 380/23, 380/25, 380/28, 380/30, 380/46, 380/49, 380/50, 364/409
• US Class Current: 380/30
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: G07C 13/00 Voting apparatus
• CPC Class Codes: H04L 2209/463 Electronic voting
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• 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 electronic voting. A voter may cast a votes among n centers in a manner which prevents fraud and authenticates the votes. Preprocessing allows for nearly all of the communication and computation to be performed before any voting takes place. Each center can verify that each vote has been properly counted. The algorithm is based on families of homomorphic encryptions which have a partial compatibility property. The invention can be realized by current-generation PCs with access to an electronic bulletin board.

Claims

1. A method of secure electronic voting with a plurality of voting means and a plurality of vote counting means using partially compatible homomorphisms comprising the steps of:

(a) choosing a randomly selected family of partially compatible encryption functions, E_a, E_b {E_i }, for voting means V₁, V₂, . . . , V_n and vote counting means C₁, C₂, . . . , C_n which functions are posted;

(b) each voting means V_k randomly choosing masking votes, v_k,j ε

{1,-1} and then randomly choosing two representations for v_k,j ;

v_k,j =X_k,j.sup.(1) +X_k,j.sup.(2) + . . . +X_k,j.sup.(n) =A_k,j +B_k,j and posting E_i (X_k,j.sup.(i)),E_a (A_k,j) and E_b (B_k,j);

(c) reducing the equations in step (b) to X^--_k.sup.(1) +X^--_k.sup.(2) +. . . +X^--_k.sup.(n) = A_k + B_k,

(d) proving the validity of the equation in step (c) by using prove-sum algorithm;

(e) executing algorithm prove±

1, and

(f) encrypting X_k,j.sup.(i) using C_i '"'"'s public encryption algorithm for all j and i and posting the encryptions.

2. A method of secure electronic voting as set forth in claim 1, further comprising the steps of:

(g) voting means k in order to use vote j, computing s_k,j ε

{-1,1} such that an actual vote is equal to s_k,j v_k,j, and posting s_k,j.

3. A method of secure electronic voting as set forth in claim 2 further comprising the steps of:

(h) each vote counting means C_i decrypting X_k,j.sup.(i) for all k and j, and verifying whether it is consistent with E_i (X_k,j.sup.(i));

(i) each vote counting means C_i calculating subtally t.sup.(i) =Σ

_k s_k ·

X_k,j.sup.(i) and posting t.sup.(i), and

(j) verifying that Π

_k (E_i (X_k.sup.(i)))^s.sbsp.k is equal to E_i (t.sup.(i)).

4. A method of secure electronic voting as set forth in claim 3, further comprising the step of combining said subtallies.

5. A method of secure electronic voting as set forth in claim 2, further comprising the step of posting j.

6. A method of secure electronic voting as set forth in claim 1, where steps (c), (d) and (e) result in generating an authentication certificate.

7. A method of secure electronic voting as set forth in claim 6, where said generating comprises applying the Fiat-Shamir method.

8. A method of secure electronic voting as set forth in claim 6, further comprising the steps of:

(g) voting means k in order to use vote j, computing s_k,j ε

{-1,1} such that an actual vote is equal to s_k,j v_k,j, and posting s_k,j.

9. A method of secure electronic voting as set forth in claim 8, further comprising the steps of:

(h) each vote counting means C_i decrypting X_k,j.sup.(i) for all k and j, and verifying whether it is consistent with E_i (X_k,j.sup.(i));

(i) each vote counting means C_i calculating subtally t.sup.(i) =Σ

_k s_k ·

X_k,j.sup.(i) and posting t.sup.(i), and

(j) verifying that Π

_k (E_i (X_k.sup.(i)))^s.sbsp.k is equal to E_i (t.sup.(i)).

10. A method of secure electronic voting as set forth in claim 9, further comprising the step of combining said subtallies.

11. A method of secure electronic voting as set forth in claim 8, further comprising the step of posting j.

12. A method of secure electronic voting with a plurality of voting means and a plurality of vote counting means using partially compatible homomorphisms comprising the steps of:

(a) choosing a randomly selected family of partially compatible encryption functions, E_a, E_b {E_i } for voting means V₁, V₂, . . . V_n and vote counting means C₁, C₂,. . . C_n, which functions are posted;

(b) each voting means V_k randomly choosing a masking vote, v_k,j ε

{1,-1} and

then randomly choosing two representations for v_k,j ;

v_k,j =X_k,j.sup.(1) +X_k,j.sup.(2) + . . . +X_x,j.sup.(n) =A_k,j +B_k,j ;

(c) voting means k in order to use vote j, computing s_k,j ε

{-1,1} such that an actual vote is equal to s_k,j v_k,j, and posting s_k,j ;

(d) each vote counting means C_i calculating subtally t.sup.(i) =Σ

_k s_k ·

X_k,j.sup.(i) and posting t.sup.(i) ; and

(e) combining said subtallies for determining the outcome of the voting.

13. An apparatus for secure electronic voting using partially compatible homomorphisms comprising:

a plurality of voting means and a plurality of vote counting means, each having a randomly selected family of partially compatible encryption functions, E_a, E_b {E_i } which are posted on a publicly accessible media;

each voting means randomly choosing masking votes, v_k,j ε

{1,-1} and randomly choosing two representations for v_k,j ;

v_k,j =X_k,j.sup.(1) +X_k,j.sup.(2) +. . . +X_k,j.sup.(n) =A_k,j +B_k,j and posting E_i (X_k,j.sup.(i)), E_a (A_k,j) and E_b (B_k,j) on said publicly accessible media;

means for reducing the equations for v_k,j to the form X^--_k.sup.(1) +X^--_k.sup.(2) +. . . +X^--_k.sup.(n) = A_k + B_k,;

means for proving the validity of v_k,j using prove-sum algorithm;

means for executing algorithm±

1;

means for encrypting X_k,j.sup.(i) using said partial encryption function for all j and i and posting the encryptions on said publicly accessible media.

14. An apparatus for secure electronic voting as set forth in claim 13, further comprising:

means for computing s_k,j ε

{1,-1} such that an actual vote is equal to s_k,j v_k,j and posting s_k,j on said publicly accessible media where k is one of said plurality of voting means and j is a vote.

15. An apparatus for secure electronic voting as set forth in claim 14, further comprising:

means associated with each of said vote counting means for decrypting X_k,j.sup.(i) for all k and j, and verifying whether it is consistent with E_i (X_k,j.sup.(i));

means associated with each of said vote counting means for calculating a subtally t.sup.(i) =Σ

_k s_k ·

X_k,j.sup.(i) and posting t.sup.(i) on said publicly accessible media; and

means for verifying that Π

_k (E_i (X_k.sup.(i)))^s.sbsp.k is equal to E_i (t.sup.(i))

16. An apparatus for secure electronic voting as set forth in claim 14, further comprising means for posting j on said publicly accessible media.

17. An apparatus for secure electronic voting as set forth in claim 13, where said vote counting means and said voting means comprise a personal computer and said publicly accessible media comprises an electronic bulletin board.

18. An apparatus for secure electronic voting as set forth in claim 13, further comprising means for generating an authentication certificate.

19. An apparatus for secure electronic voting as set forth in claim 18, where said means for generating includes means for applying the Fiat-Shamir method.

20. An apparatus for secure electronic voting as set forth in claim 18, further comprising:

means for computing s_k,j ε

{1,-1} such that an actual vote is equal to s_k,j v_k,j and posting s_k,j on said publicly accessible media where k is one of said plurality of voters and j is a vote.

21. An apparatus for secure electronic voting as set forth in claim 20, further comprising:

means associated with each of said vote counting means for decrypting X_k,j.sup.(i) for all k and j, and verifying whether it is consistent with E_i (X_k,j.sup.(i));

means associated with each of said vote counting means for calculating a subtally t.sup.(i) =Σ

_k s_k ·

X_k,j.sup.(i) and posting t.sup.(i) on said publicly accessible media; and

means for verifying that Π

_k (E_i (X_k.sup.(i)))^s.sbsp.k is equal to E_i (t.sup.(i)).

22. An apparatus for secure electronic voting as set forth in claim 20, further comprising means for posting j on said publicly accessible media.

23. An apparatus for secure electronic voting as set forth in claim 18, where said vote counting means and said voting means comprise a personal computer and said publicly accessible media comprises an electronic bulletin board.

24. An apparatus for secure electronic voting using partially compatible homomorphisms comprising:

a plurality of voting means and a plurality of vote counting means, each having a randomly selected family of partially compatible encryption functions E_a, E_b {E_i } which are posted on a publicly accessible media;

each voting means randomly choosing a masking vote, v_k,j ε

{1,-1} and randomly choosing two representations for v_k,j ;

v_k,j =X_k,j.sup.(1) +X_k,j.sup.(2) + . . . +X_k,j.sup.(n) =A_k,j +B_k,j and posting E_i (X_k,j.sup.(i)), E_a (A_k,j) and E_b (B_k,j) on said publicly accessible media;

means for computing s_k,j ε

{-1,1} such that an actual vote is equal to s_k,j v_k,j, and posting s_k,j on said publicly accessible media, where k is one of said plurality of voters and j is a vote;

means associated with each of said vote counting means for decrypting X_k,j.sup.(i) for all k and j, and verifying whether it is consistent with E_i (X_k,j.sup.(i));

means associated with each of said vote counting means for calculating a subtally t.sup.(i) =Σ

_k s_k ·

X_k,j.sup.(i) and posting t.sup.(i) on said publicly accessible media; and

means for combining said subtallies for determining the outcome of said voting.

25. An apparatus for secure electronic voting as set forth in claim 24, where said vote counting means and said voting means comprise a personal computer and said publicly accessible media comprises an electronic bulletin board.

26. An apparatus for secure electronic voting as set forth in claim 24, further comprising means for generating an authentication certificate.

27. An apparatus for secure electronic voting as set forth in claim 26, where said means for generating includes means for applying the Fiat-Shamir method.

28. An apparatus for secure electronic voting as set forth in claim 26, where said vote counting means and said voting means comprise a personal computer and said publicly accessible media comprises an electronic bulletin.