Verifiable secret shuffles and their application to electronic voting

• US 20050028009A1
• Filed: 03/25/2002
• Published: 02/03/2005
• Est. Priority Date: 03/24/2001
• Status: Active Grant

• Current Assignee: FederatedIdentity.com Inc.
• Original Assignee: FederatedIdentity.com Inc.
• Inventors: Neff, C Andrew
• Granted Patent: US 7,360,094 B2
• Time in Patent Office: Days
• US Class Current: 726/4
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 2209/463 Electronic voting
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/0825 using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/321 involving a third party or a trusted authority
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes

Abstract

We present a mathematical construct which provides a cryptographic protocol to (verifiably shuffle) a sequence of (k) modular integers, and discuss its application to secure, universally verifiable, multi-authority election schemes. The output of the shuffle operation is another sequence of (k) modular integers, each of which is the same secret power of a corresponding input element, but the order of elements in the output is kept secret. Though it is a trivial matter for the “shuffler” (who chooses the permutation of the elements to be applied) to compute the output from the input, the construction is important because it provides a linear size proof of correctness for the output sequence (i.e. a proof that it is of the form claimed) that can be checked by one or more arbitrary verifiers. The protocol is shown to be honest-verifier zeroknowledge in a special case, and is computational zeroknowledge in general. On the way to the final result, we also construct a generalization of the well known Chaum-Pedersen protocol for knowledge of discrete logarithm equality ([3], [2]). In fact, the generalization specializes (exactly) to the Chaum-Pedersen protocol in the case (k)=2. This result may be of interest on its own. An application to electronic voting is given that matches the features of the best current protocols with significant efficiency improvements. An alternative application to electronic voting is also given that introduces an entirely new paradigm for achieving (Universally Verifiable) elections.

Claims

1. An electronic voting system for use with a computerized network, comprising:

at least one server computer coupled to receive requests from at least first, second and third voter computers coupled to the computerized network;

wherein the first voter computer is configured to receive, from the server computer, a series of electronic credentials corresponding to an aggregation of electronic credentials received from a plurality of voter computers, wherein each electronic credential is a Digital Signature Algorithm (DSA) or ElGamal pair, and wherein the first voter computer is configured to apply a secret, one-way cryptographic transformation using at least a first secret key to anonymously shuffle the series of electronic credentials, and produce a first shuffled series of credentials for the server computer, wherein only the first voter computer knows a correspondence between the first series of shuffled credentials and the series of electronic credentials, and wherein the first voter computer is further configured to provide a first linear size proof of correctness for the first series of shuffled credentials based on an iterated logarithmic multiplication proof, and to provide a first ballot with a first associated credential;

wherein the second voter computer is configured to receive, from the server computer, the first series of shuffled credentials, to apply the cryptographic transformation using at least a second secret key to anonymously shuffle the first series of shuffled credentials, and produce a second series of shuffled credentials for the server computer, wherein only the second voter computer knows a correspondence between the first series of shuffled credentials and the second series of shuffled credentials, and wherein the second voter computer is further configured to provide to the server computer a second linear size proof of correctness for the second series of shuffled credentials based on the iterated logarithmic multiplication proof with a second ballot having a second associated credential;

wherein the third voter computer is configured to receive the second series of shuffled credentials, to apply the cryptographic transformation using at least a third secret key to anonymously shuffle the second series of shuffled credentials, and produce a third series of shuffled credentials for the server computer, wherein only the third voter computer knows a correspondence between the second series of shuffled credentials and the third series of shuffled credentials, and wherein the third voter computer is further configured to provide a third linear size proof of correctness for the third series of shuffled credentials based on the iterated logarithmic multiplication proof with a third ballot having a third associated credential; and

wherein the server computer is configured to receive the proofs of correctness from the first, second and third voter computers and to verify a correctness of the shuffled credentials, and to receive, verify and tally the first, second and third ballots having the respective first, second and third associated credentials.

2. The system of claim 1, further comprising:

a plurality of authority computers coupled to the computerized network, wherein the first, second and third ballots are encrypted under a threshold, discrete log asymmetric encryption process using underlying groups Z_p or elliptic curve;

and wherein each of the plurality of authority computers, in turn;

receives at least the first, second and third encrypted ballots,

secretly shuffles the ballots;

applies a decryption key share to the secretly shuffled ballots to partially decrypt the secretly shuffled ballots; and

passes the partially decrypted and secretly shuffled ballots to a next authority computer.

3. The system of claim 1 wherein the first, second and third voter computers are configured to provide to the server computer at least an identification of first, second and third public keys in the aggregation of electronic credentials associated with the first, second and third voter computers, all respectively, and

wherein the server computer is further configured to remove the first, second and third public keys in response thereto.

4. The system of claim 1 wherein the computerized network includes the World Wide Web, wherein each of the first, second and third voter computers include a web browser program.

5. The system of claim 1 wherein at least one of the first, second and third voter computers is a palm-sized computer, cell phone, wearable computer, interactive television terminal or Internet appliance.

6. A computer system for receiving a sequence of elements, comprising:

a computer coupled to a computer network and configured to;

receive a sequence of electronic data elements representing individual data files,

apply a cryptographic transformation using at least a first secret value to anonymously permute the sequence of electronic data elements and produce a first shuffled sequence of electronic data elements, wherein the server computer knows a correspondence between the first shuffled sequence of electronic data elements and the sequence of electronic data elements, and

generate a first linear size proof of correctness for the first shuffled sequence of electronic data elements based on an iterated logarithmic multiplication proof employing a binary operator, wherein each of the data elements in the sequence of data elements is associated with a common base value, and wherein verifying the proof of correctness employs a three-move, public coin proof of knowledge wherein in response to a verifying request, the computer computes a series of exponents by solving an associated series of linear equations.

7. The system of claim 6 wherein the received sequence of electronic data elements are encrypted using Z_p or elliptic curve groups using a key unknown to the computer, and wherein the computer is further configured to:

receive a series of randomly generated values e_i from a verifier computer;

secretly generate a series of values D_i based on a secret, one-way cryptographic transformation that employs the received series of values e_i and secretly generated values;

permute the sequence of electronic data elements to produce the first shuffled sequence of elements based on the series of values D_i and a secret value γ

; and

provide the values D_i and a series of proof values based on the cryptographic transformation as a proof of knowledge that the server computer has access to how the cryptographic transformation permuted the sequence of electronic data elements to produce the first shuffled sequence of elements without revealing the cryptographic transformation to the verifier computer.

8. The system of claim 6 wherein the server computer is further configured for:

receiving a plurality of public keys from a corresponding plurality of individuals, wherein each of the plurality of individuals have a private key corresponding to one of the plurality of public keys;

receiving a request from one of the plurality of individuals having a one private key;

providing at least a subset of the plurality of public keys to the requesting individual;

receiving a file and a shuffle of the plurality of public keys and a linear size proof of correctness for the shuffled public keys based on a iterated logarithmic multiplication proof and a value corresponding to the one private key, wherein the value is associated with the file and provides proof that the one individual has knowledge of the one private key without revealing the one private key;

checking the proof of correctness;

checking that the value is mathematically related to a one of the public keys and the file; and

reducing the plurality of public keys by the one public key.

9. The system of claim 6 wherein the sequence of electronic elements are public keys, and wherein the server if further configured to check, in response to a request from an individual, that the individual has a value uniquely and mathematically related to a one of the public keys;

and

if so, issue a certificate to the one individual.

10. A computer-implemented method, comprising:

receiving a request from one of a plurality of individuals having a private key corresponding to one of a plurality of public keys;

providing at least a shuffled subset of the plurality of public keys to the requesting individual;

receiving a file F, and an authentication consisting of;

(1) a new shuffled set of public keys S,

(2) a shuffle proof of correctness for the new shuffled set of public keys, and

(3) a signature value x from the requesting individual; and

accepting the authentication if;

(a) verification of the shuffle proof of correctness succeeds, and

(b) V(F, x, s₀) is true, wherein V is a signature verification function and s₀ is one public key from the new shuffled set of public keys S.

11. A computer-implemented method, comprising:

receiving a request from a computer associated with one private key corresponding to one public key in a plurality of public keys, wherein each of the plurality of public keys corresponds to one of a plurality of private keys;

providing at least a shuffled subset of the plurality of public keys to the requesting computer;

receiving a file from the requesting computer;

receiving a new shuffled subset of the plurality of public keys and a linear size proof of correctness for the new shuffled subset of public keys based on an iterated logarithmic multiplication proof and a value corresponding to the one private key, wherein the value is associated with the file and provides proof that the requesting computer has knowledge of the one private key without revealing the one private key;

checking the proof of correctness; and

checking that the value is mathematically related, in a substantially unique way, to the one public key and the file.

12. The method of claim 11, further comprising receiving from the requesting computer at least an indication of the one public key in the new shuffled subset of public keys.

13. The method of claim 11, further comprising removing the one public key from the new shuffled subset of public keys.

14. The method of claim 11, further comprising:

receiving from each of a plurality of authorities, in sequence, a shuffled set of the plurality of public keys H′

based on a secret cryptographic shuffle operation performed on at least a subset of the plurality of public keys H to produce the shuffled set of the plurality of public keys H′

;

receiving from each of a plurality of authorities, in sequence, a verification transcript of the cryptographic shuffle operation; and

verifying a correctness of the cryptographic shuffle operation based on the verification transcript; and

if verified, then setting the shuffled set of the plurality of public keys from H′

to H.

15. The method of claim 11, further comprising:

at a time after receiving at least some of the plurality of public keys, setting at least a subset of the then received plurality of public keys to a received shuffled set of the plurality of public keys, wherein the shuffled set of the plurality of public keys have been received from a third party.

16. The method of claim 11, further comprising:

following the checking steps, issuing a certificate;

thereafter, receiving the issued certificate from one of a plurality of individuals; and

providing an electronic ballot to the one individual.

17. The method of claim 11, further comprising digitally signing a received request to produce a public key infrastructure (“

PKI”

) certificate.

18. The method of claim 11, further comprising:

receiving issued certificates from at least some of a plurality of user computers and providing initial electronic ballots in response thereto; and

receiving unencrypted voted ballots from the at least some of the plurality of user computers.

19. A computer-implemented cryptographic method between a prover computer and a verifier computer, the method comprising:

secretly shuffling a first series of electronic data elements with respect to a second series of electronic data elements to produce a shuffled set;

generating a linear size proof of correctness for the shuffled set based on proving that a first set of roots for a first polynomial equation is equal to a fixed constant multiple of a second set of roots for a second polynomial equation; and

wherein the linear size proof of correctness that the first set of roots is equal to a fixed multiple of the second sets of roots is obtained by;

specifying a second fixed constant, evaluating the first polynomial equation at a first random point to obtain a first value, evaluating the second polynomial equation at the first random point to obtain a second value, and determining that the second value is equal to a product of the first value and the second fixed constant.

20. The method of claim 19 wherein at least some of the elements in the first sequence of elements are electronic ballots.

21. The method of claim 19 wherein at least some of the elements in the shuffled set are ElGamal pairs.

22. The method of claim 19, further comprising repeating the secretly shuffling, generating and providing for l-tuple of elements in an input sequence of elements.

23. The method of claim 19 wherein secretly shuffling the first series of elements includes receiving a subset of a set of identifying elements, wherein each identifying element in the set corresponds to an individual, and wherein the method further comprises:

receiving an anonymous certificate if the verifying computer verifies the proof of correctness.

24. An electronic voting system for use with a computerized network, comprising:

a plurality of authority computers coupled to the computerized network to receive a plurality of ballots encrypted under a threshold, discrete log asymmetric encryption process;

wherein each of the plurality of authority computers is configured to, in turn;

receive at least the plurality of encrypted ballots,

secretly shuffle the ballots;

apply a decryption key share to the secretly shuffled ballots to partially decrypt the secretly shuffled ballots;

generate a proof of validity for the shuffled and partially decrypted ballots; and

pass the partially decrypted and secretly shuffled ballots to a next authority computer; and

wherein a last of the authority computers applies a last decryption key share to the secretly shuffled ballots to fully decrypt the secretly shuffled ballots.

25. The system of claim 24 wherein each of the plurality of authority computers is configured to substantially simultaneously:

(1) secretly shuffle the ballots,

(2) apply the decryption key share to the secretly shuffled ballots to partially decrypt the secretly shuffled ballots, and

(3) generate the proof of validity for the partially decrypted ballots.

26. A computer-readable medium whose contents provide instructions, when implemented by a computer, perform a shuffling of a sequence of electronic data elements, comprising:

providing a request from a computer associated with one private key corresponding to one public key in a plurality of public keys, wherein each of the plurality of public keys corresponds to one of a plurality of private keys;

receiving at least a shuffled subset of the plurality of public keys;

providing a file;

producing a new shuffled subset of the plurality of public keys and a proof of correctness for the new shuffled subset of public keys based on an iterated logarithmic multiplication proof and a value corresponding to the one private key, wherein the value is associated with the file and provides proof of knowledge of the one private key without revealing the one private key.

27. The computer-readable medium of claim 26 wherein the computer-readable medium is a logical node in a computer network receiving the sequence of electronic data elements and the contents.

28. The computer-readable medium of claim 26 wherein the computer-readable medium is a computer-readable disk.

29. The computer-readable medium of claim 26 wherein the computer-readable medium is a data transmission medium transmitting a generated data signal containing the contents.

30. The computer-readable medium of claim 26 wherein the computer-readable medium is a memory of a computer system.

31. The computer-readable medium of claim 26 wherein the computer-readable medium is an Internet connection link to a voting authority server computer.

32. The computer-readable medium of claim 26 wherein the proof of correctness is a linear size proof of correctness that includes computing first and second polynomial equations, and wherein an evaluation of the first and second polynomials at a randomly chosen point results in a same computed value.

33. A computer-implemented method for performing a mixing of electronic data elements, comprising:

receiving at least an original subset of multiple public keys, wherein each of public keys in the original subset of public keys corresponds to one private key in a set of private keys; and

mixing the original subset of public keys to produce a mixed set of public keys,

wherein the mixed set of public keys can not be correlated with the original subset of public keys, but wherein the mixed set of public keys corresponds to the set of private keys.

34. The method of claim 33, further comprising:

providing a file; and

producing a proof of correctness for the new mixed subset of public keys based on an iterated logarithmic multiplication proof and a value corresponding to the one private key, wherein the value is associated with the file and provides proof of knowledge of the one private key without revealing the one private key.

35. The method of claim 33, further comprising generating a proof of correctness for the mixed set of public keys, wherein the proof of correctness proves that the mixed set of public keys corresponds to the set of private keys.

36. The method of claim 33 wherein the mixed subset of public keys correspond to a sequence of ballots.

37. The method of claim 33, further comprising generating a proof of correctness for the mixed set of public keys that includes computing first and second polynomial equations, wherein an evaluation of the first and second polynomials at a randomly chosen point results in a same computed value.