Secure receipt-free electronic voting

• US 6,092,051 A
• Filed: 05/19/1995
• Issued: 07/18/2000
• Est. Priority Date: 05/19/1995
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation, NEC Research Institute, Inc. (NEC Corporation)
• Inventors: Sako, Kazue, Kilian, Joseph John
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): SAYADIAN, HRAYR
• Application Number:
  US08/444,701
• Time in Patent Office: 1,887 Days
• Field of Search: 380/49, 380/23, 380/25, 380/28, 380/30, 395/212, 705/12, 705/74
• US Class Current: 705/12
• CPC Class Codes: G06Q 20/383 Anonymous user system
• CPC Class Codes: G07C 13/00 Voting apparatus

Abstract

A number-theoretic based algorithm provides for secure receipt-free voting. A vote generating center generates a choice of votes for each voter or vote chooser. The votes are encrypted, shuffled, and conveyed to a vote chooser along with information regarding how the votes were shuffled without being intercepted en route. The information is preferably sent along untappable secure channels. The method can incorporate validation of generation and shuffling of the votes using chameleon commitment and interactive proofs. The invention can be realized by current-generation personal computers with untappable channels and access to an electronic bulletin board.

Claims

1. A computer implemented method of secure receipt-free voting, the method comprising the steps of:

(a) constructing ballots at at least one vote generating center for each vote chooser, each ballot having a value;

(b) posting the ballots on a bulletin board;

(c) proving that the ballots are correctly constructed without generally revealing the values of the ballots;

(d) sending at least one private message from the vote generating center to each of the vote choosers without the at least one private messages being intercepted, the at least one private message revealing and proving to each vote chooser the values of the ballots from which that vote chooser may choose to vote;

(e) permitting each vote chooser to create an alternative message based upon the at least one private message received by that vote chooser, the alternative message not being indicative of the correct values for the ballots revealed and proven to that vote chooser;

(f) each vote chooser choosing a ballot from the revealed and constructed ballots indicative of a chosen vote;

(g) preventing proof of the value of the chosen ballot to a malicious party by rendering computationally infeasible a determination by the malicious party of whether the vote generating center sent the at least one private message actually received by the vote chooser or the alternative message regardless of any information provided by the vote chooser to the malicious party at any time,

(h) the vote chooser specifying the ballot chosen by the vote chooser to a vote counting center through a secure anonymous channel; and

(i) counting, the ballots specified by all vote choosers to the vote counting center.

2. The method of secure receipt-free voting of claim 1, wherein proving that the ballots are correctly constructed is performed by executing algorithm prove 1-0, given encrypted forms of 1-votes and 0-votes as v_i⁰ =(g^r.sbsp.i1 mod p,m₀ ·

y^r.sbsp.i1 mod p) and v_i¹ =(g^r.sbsp.i2 mod p, m₁ ·

y^r.sbsp.i2 mod p), and a string which has been committed using chameleon commitment to th e vote chooser, then a prover uniformly chooses r'"'"', r" and calculates

space="preserve" listing-type="equation">E.sub.0 (v.sup.0)=(g.sup.r'"'"' mod p,m.sub.0 ·

y.sup.r'"'"' mod p)

space="preserve" listing-type="equation">E.sub.1 (v.sup.1)=(g.sup.r'"'"' mod p,m.sub.1 ·

y.sup.r'"'"' mod p)

and posts E₀ (v⁰), E₁ (v¹) in the order according to the committed string, then with probability 1/2, the prover is asked to reveal r'"'"' and r" and the vote chooser checks if E₀ (v⁰), E₁ (v¹) are made consistently and with probability 1/2, the prover is asked to reveal s1=r_i1 -r'"'"' and s2=r_i2 -r" and the vote chooser checks that v₁⁰ can be generated from E₀ (v⁰) E₁ (v¹) using s1, s2, g and y.

3. The method of secure receipt-free voting of claim 1, further comprising the steps of:

(i) committing a random string using chameleon commitments, wherein for each bit, 0 or 1, the respective vote choosers know the value a satisfying α

=g^a for public integer α

, and a 0-bit is committed by g^r and a 1-bit is committed by α

·

g^r ;

(k) proving the correctness of the constructed ballots by using the committed bits; and

(l) decommiting through transmission without interception wherein decommiting is performed by revealing the value r and the vote chooser calculating both g^r and α

·

g^r and determining what was the committed bit.

4. The method of secure receipt-free voting of claim 3, wherein proving that the ballots are correctly constructed is performed by executing the algorithm prove 1-0 given encrypted forms of 1-votes and 0-votes as v_i⁰ (g^r.sbsp.i1 mod p,m₀ ·

y^r.sbsp.i1 mod p) and v_i¹ =(g^r.sbsp.i2 mod p,m₁ mod p), and a random string which has been committed using chameleon commitment to the vote chooser, then a prover uniformly chooses r'"'"', r" and calculates

space="preserve" listing-type="equation">E.sub.0 (v.sup.0)=(g.sup.r'"'"' mod p,m.sub.0 ·

y.sup.r'"'"' mod p)

space="preserve" listing-type="equation">E.sub.1 (v.sup.1)=(g.sup.r'"'"' mod p,m.sub.1 ·

y.sup.r'"'"' mod p)

and posts E₀ (v⁰), E₁ (v¹) in the order according to the committed string, then with probability 1/2, the prover is asked to reveal r'"'"' and r" and the vote chooser checks if E₀ (v⁰), E₁ (v¹)are made consistently and with probability 1/2, the prover is asked to reveal s1=r_i1 -r'"'"' and s2=r_i2 -r" and the vote chooser checks that v_i⁰ and v_i¹ can be generated from E₀ (v⁰), E₁ (v¹) using s1, s2, g and y.

5. The method of secure receipt-free voting of claim 3, wherein step (a) further comprises:

(i) shuffling the constructed votes; and

(ii) sending a private message about a respective shuffling to the vote chooser without being intercepted.

6. The method of secure receipt-free voting of claim 1, where in step (a) further comprises:

(i) shuffling the constructed votes; and

(ii) sending a private message about a respective shuffling to the vote chooser without being intercepted.

7. The method of secure receipt-free voting of claim 6, wherein sending the private message about the respective shuffling comprises sending without interception.

8. The method of secure receipt-free voting of claim 6, further comprising the step of proving the correctness of the shuffling of the constructed ballots.

9. The method of secure receipt-free voting of claim 8, further comprising the steps of:

(i) committing a random string using chameleon commitments wherein for each bit 0 or 1 the respective vote choosers know the value a satisfying α

=g^a for public integer α

, and a 0-bit is committed by g^r and a 1 bit is committed by α

·

g^r ;

(k) proving the correctness of shuffling of the constructed ballots using the committed bits; and

(h) decommiting without being intercepted wherein decommiting is performed by revealing the value r and the vote chooser calculating both g^r and α

=g^r and determining what was the committed bit.

10. The method of secure receipt-free voting of claim 9, wherein said proving the correctness of the shuffling is performed by executing the algorithm prove shuffle wherein the algorithm is performed by uniformly choosing c'"'"', c" and calculating E(X₁)=(A₁ ·

g^c'"'"' mod p, A₂ y^c'"'"' mod p) and E(X₂)=(B₁ ·

g^c" mod p, B₂ ·

Y^c" mod p) and posting E(X₁) and E(X₂) in order according to a committed string, then with probability 1/2 revealing c'"'"' and c" and checking if E(X₁), E(X₂) is consistent, then with probability 1/2, revealing t₁ =c₁ -c'"'"' and t₂ =C₂ -C" and checking that E(X₁) and E(X₂) can be generated from S(X₁), S(X₂) using t₁, t₂, g and y, wherein S(X₁)=(A_i ·

g^c1 mod p, A₂ ·

y^c1 mod p) and S(X₂)=B₁ ·

g^c2 mod p, B₂ ·

y^c2 mod p), wherein encrypted shuffle votes X₁ =(A₁, A₂) and (X₂ =(B₁, B₂).

11. The method of secure receipt-free voting of claim 9, further comprising invalidating the chameleon commitments.

12. The method of secure receipt-free voting of claim 11, wherein invalidating the chameleon commitments includes providing a secret message for said shuffling to the bulletin board.

13. The method of secure receipt-free voting of claim 8, wherein said proving the correctness of the shuffling is performed by executing the algorithm prove shuffle wherein the algorithm is performed by uniformly choosing c'"'"', c" and calculating E(X₁)=(A₁ ·

g^c'"'"' mod p, A₂ ·

y^c'"'"' mod p) and E(X₂)=(B₁ ·

g^c'"'"' mod p, B₂ ·

y^c" mod p) and posting E(X₁) and E(X₂) in order according to a committed string, then with probably 1/2 revealing c'"'"' and c" and checking if E(X₁), E(X₂) is consistent, then with probability 1/2, revealing t₁ =c₁ -c'"'"' and t₂ =c₂ -c" and checking that E(X₁) and E(X₂) can be generated from S(X₁), S(X₂) using t₁, t₂, g and y, wherein S(X₁)=(A₁ g^c1 mod p, A₂ ·

y^c1 mod p) and S(X₂)=B₁ ·

g^c2 mod p, B₂ ·

y^c2 mod p), wherein encrypted shuffle votes X₁ =(A₁, A₂) and X₂ =(B₁, B₂).

14. An apparatus for secure receipt-free voting, the apparatus comprising:

a plurality of vote choosers;

at least one vote generating center, the at least one vote generating center constructing ballots for each vote chooser, each ballot having a value;

a bulletin board, the ballots being posted on the bulletin board, wherein the at least one vote generating center proves that the ballots are correctly constructed without generally revealing the values of the ballots and sends at least one private message to each of the vote choosers without the at least one private message being intercepted, the at least one private message revealing and proving to each vote chooser the values of the ballots from which that vote chooser may choose to vote, and wherein each vote chooser is permitted to create an alternative message based upon the at least one private message received by that vote chooser, the alternative message not being indicative of the correct values for the ballots revealed and proven to that vote chooser, wherein each vote chooser chooses a ballot from the revealed and constructed ballots indicative of a chosen vote, wherein proof of the value of the chosen ballot to a malicious party is prevented by rendering computationally infeasible a determination by the malicious party of whether the vote generating center sent the at least one private message actually received by the vote chooser or the alternative message, regardless of any information provided by the vote chooser to the malicious party at any time; and

a vote counting center, wherein the vote chooser specifies the ballot chosen by the vote chooser to the vote counting center through a secure anonymous channel, and the vote counting center counts the ballots specified by all vote choosers to the vote counting center.

15. The apparatus for secure receipt-free voting of claim 14, further comprising:

said vote generating center committing a random string using chameleon commitment wherein for each bit, 0 or 1, the respective vote choosers know the value a satisfying α

=g^a for public integer α and

a 0-bit is committed by g^r and a 1-bit is committed by α

=g^r ;

proving the correctness of the vote construction using the committed bits; and

decommiting through transmission without interception wherein decommiting is performed by revealing the value r and the vote chooser calculating both g^r and α

·

g^r and determining what was the committed bit.

16. The apparatus for secure receipt-free voting of claim 15, further comprising;

a shuffle net of shuffling centers for receiving said constructed ballots; and

each shuffling center in the shuffle net shuffling the ballots and sending a private message to a vote chooser without being intercepted.

17. The apparatus for secure receipt-free voting of claim 14, further comprising:

a shuffle net of shuffling centers for receiving said constructed ballots; and

each shuffling center in the shuffle net shuffling the ballots and sending a private message to a vote chooser without being intercepted.

18. The apparatus for secure receipt-free voting of claim 14, further comprising each shuffling center proving the correctness of its ballot construction.

19. The apparatus for secure receipt-free voting of claim 18, further comprising:

each shuffling center committing a random string using chameleon commitment wherein for each bit, 0 or 1, the respective vote choosers know the value a satisfying α

=g^a for public integer α and

a 0-bit is committed by g^r and a 1-bit is committed by α

·

g^r and proving the correctness of its ballot construction using the committed bits, and decommiting without being intercepted, wherein decommiting is performed by revealing the value r and the vote chooser calculating both g^r and α

·

g^r and determining what was the committed bit.

20. The apparatus for secure receipt-free voting of claim 19, further comprising each vote chooser invalidating the chameleon commitment.

21. The apparatus for secure receipt-free voting of claim 20, wherein each vote chooser invalidates the chameleon commitment by providing its secret key to said shuffling centers or to said bulletin board.