Verifiable secret shuffles and their application to electronic voting

• US 7,360,094 B2
• Filed: 03/25/2002
• Issued: 04/15/2008
• Est. Priority Date: 03/24/2001
• Status: Expired due to Fees

• Current Assignee: FederatedIdentity.com Inc.
• Original Assignee: FederatedIdentity.com Inc.
• Inventors: Neff, C. Andrew
• Primary Examiner(s): TRAN, ELLEN C
• Application Number:
  US10/484,931
• Publication Number:
  US 20050028009A1
• Time in Patent Office: 2,213 Days
• Field of Search: 713/179, 713/151, 713/150, 713/180, 713/189, 380/28, 380/30, 705/12, 705/50
• US Class Current: 713/179
• 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. 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 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.

2. The system of claim 1 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.

3. The system of claim 1 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 proof of correctness for the shuffled 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 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.

4. The system of claim 1 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.

5. 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 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 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.

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

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

8. The method of claim 5, further comprising repeating the secretly shuffling, generating and providing for I-tuple of elements in an input sequence of elements.

9. The method of claim 5 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.

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

a server 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 secret key to anonymously permute the sequence of electronic data elements and produce a shuffled sequence of electronic data elements, wherein the server computer knows a correspondence between the shuffled sequence of electronic data elements and the sequence of electronic data elements,

wherein the server computer is further configured to;

generate a proof of correctness for the permutation based on a proof that the product of unencrypted values of elements of a first sequence of encrypted data elements is equal to the product of unencrypted values of elements of a second sequence of encrypted data elements.

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

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

generate the proof of correctness as an non-interactive proof based at least in part on at least some of the randomly generated values e_i.

12. The system of claim 10 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 for a certificate 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 shuffle of the plurality of public keys and a non-interactive proof of correctness for the permutation based on a proof that the product of unencrypted values of elements of a first sequence of encrypted data elements is equal to the product of unencrypted values of elements of a second sequence of encrypted data elements;

checking the proof of correctness;

issuing a certificate to the one individual; and

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

13. The system of claim 10 wherein the sequence of electronic elements are public keys, and wherein the server is further configured to check, in response to a request from an individual, that the individual has a secret key uniquely and mathematically related to a one of the public keys;

and

if so, issue a certificate to the one individual.

14. The system of claim 10 wherein the sequence of electronic data elements is a sequence of ballot choices under an electronic election.

15. The system of claim 10 wherein the proof of correctness proves that given the sequence of electronic data elements and the produced shuffled sequence of electronic data elements, there exists a permutation such that for every decrypted element in the sequence of electronic data elements there exists a corresponding permuted decrypted element in the produced shuffled sequence of electronic data elements.

16. The system of claim 10 wherein the proof of correctness for the permutation is based on a proof that one polynomial defined by a first sequence of encrypted linear factors is equal to a constant multiple of a second polynomial defined by a second sequence of encrypted linear factors.

17. A computer-readable medium whose contents store a sequence of electronic data elements and associated data, wherein the sequence of electronic data elements are processed by a computer-implemented method for a shuffling of the sequence of electronic data elements, the method comprising:

receiving the sequence of electronic data elements;

applying a secret, one-way cryptographic transformation using at least a first secret key to anonymously permute the sequence of electronic data elements and producing a first shuffled sequence of electronic data elements; and

generating a proof of correctness for the permutation based on a proof that the product of unencrypted values of elements of a first sequence of encrypted data elements is equal to the product of unencrypted values of elements of a second sequence of encrypted data elements.

18. The computer-readable medium of claim 17 wherein the received sequence of electronic data elements are encrypted with an underlying mathematical group being a ring of integers having a modulus integer value p(Zp).

19. The computer-readable medium of claim 17 wherein the computer-readable medium is logical node in a computer network receiving the sequence of electronic data elements and the proof of correctness.

20. The computer-readable medium of claim 17 wherein the computer-readable medium is computer-readable disk.

21. The computer-readable medium of claim 17 wherein the computer-readable medium is a memory of a computer system.

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

23. The computer-readable medium of claim 17 wherein the electronic data elements include at least public keys or digital certificates associated with public keys.

24. The computer-readable medium of claim 17 wherein the sequence of electronic data elements are electronic ballots or electronic ballot choices.

25. The computer-readable medium of claim 17 wherein the received sequence of electronic data elements are encrypted with an underlying elliptic curve group.

26. The computer-readable medium of claim 17 wherein the proof of correctness is a non-interactive proof of correctness.