Secure electronic voting using partially compatible homomorphisms
AssigneesNEC Research Institute, Inc., NEC Corporation
InventorsJoseph J. Kilian, Kazue Sako
Life of this patent
Estimating the term…
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.
Claims28
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.sub.a, E.sub.b {E.sub.i }, for voting means V.sub.1, V.sub.2, . . . , V.sub.n and vote counting means C.sub.1, C.sub.2, . . . , C.sub.n which functions are posted;
- (b) each voting means V.sub.k randomly choosing masking votes, v.sub.k,j .epsilon. {1,-1} and then randomly choosing two representations for v.sub.k,j :
- v.sub.k,j =X.sub.k,j.sup.(1) +X.sub.k,j.sup.(2) + . . . +X.sub.k,j.sup.(n) =A.sub.k,j +B.sub.k,j and posting E.sub.i (X.sub.k,j.sup.(i)),E.sub.a (A.sub.k,j) and E.sub.b (B.sub.k,j);
- (c) reducing the equations in step (b) to X.sup.--.sub.k.sup.(1) +X.sup.--.sub.k.sup.(2) +. . . +X.sup.--.sub.k.sup.(n) = A.sub.k + B.sub.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.sub.k,j.sup.(i) using C.sub.i 's public encryption algorithm for all j and i and posting the encryptions.
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.sub.a, E.sub.b {E.sub.i } for voting means V.sub.1, V.sub.2, . . . V.sub.n and vote counting means C.sub.1, C.sub.2,. . . C.sub.n, which functions are posted;
- (b) each voting means V.sub.k randomly choosing a masking vote, v.sub.k,j .epsilon. {1,-1} and
- then randomly choosing two representations for v.sub.k,j :
- v.sub.k,j =X.sub.k,j.sup.(1) +X.sub.k,j.sup.(2) + . . . +X.sub.x,j.sup.(n) =A.sub.k,j +B.sub.k,j ;
- (c) voting means k in order to use vote j, computing s.sub.k,j .epsilon. {-1,1} such that an actual vote is equal to s.sub.k,j v.sub.k,j, and posting s.sub.k,j ;
- (d) each vote counting means C.sub.i calculating subtally t.sup.(i) =.SIGMA..sub.k s.sub.k .multidot.X.sub.k,j.sup.(i) and posting t.sup.(i) ;
- and
- (e) combining said subtallies for determining the outcome of the voting.
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.sub.a, E.sub.b {E.sub.i } which are posted on a publicly accessible media;
- each voting means randomly choosing masking votes, v.sub.k,j .epsilon. {1,-1} and randomly choosing two representations for v.sub.k,j ;
- v.sub.k,j =X.sub.k,j.sup.(1) +X.sub.k,j.sup.(2) +. . . +X.sub.k,j.sup.(n) =A.sub.k,j +B.sub.k,j and posting E.sub.i (X.sub.k,j.sup.(i)), E.sub.a (A.sub.k,j) and E.sub.b (B.sub.k,j) on said publicly accessible media;
- means for reducing the equations for v.sub.k,j to the form X.sup.--.sub.k.sup.(1) +X.sup.--.sub.k.sup.(2) +. . . +X.sup.--.sub.k.sup.(n) = A.sub.k + B.sub.k,;
- means for proving the validity of v.sub.k,j using prove-sum algorithm;
- means for executing algorithm.+-.1;
- means for encrypting X.sub.k,j.sup.(i) using said partial encryption function for all j and i and posting the encryptions on said publicly accessible media.
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.sub.a, E.sub.b {E.sub.i } which are posted on a publicly accessible media;
- each voting means randomly choosing a masking vote, v.sub.k,j .epsilon. {1,-1} and randomly choosing two representations for v.sub.k,j :
- v.sub.k,j =X.sub.k,j.sup.(1) +X.sub.k,j.sup.(2) + . . . +X.sub.k,j.sup.(n) =A.sub.k,j +B.sub.k,j and posting E.sub.i (X.sub.k,j.sup.(i)), E.sub.a (A.sub.k,j) and E.sub.b (B.sub.k,j) on said publicly accessible media;
- means for computing s.sub.k,j .epsilon. {-1,1} such that an actual vote is equal to s.sub.k,j v.sub.k,j, and posting s.sub.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.sub.k,j.sup.(i) for all k and j, and verifying whether it is consistent with E.sub.i (X.sub.k,j.sup.(i));
- means associated with each of said vote counting means for calculating a subtally t.sup.(i) =.SIGMA..sub.k s.sub.k .multidot.X.sub.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.
Dependencies are inferred from the claim text.