Verifiable, secret shuffles of encrypted data, such as elgamal encrypted data for secure multi-authority elections
First Claim
1. An electronic voting system for use with a computerized network, comprising:
- a plurality of voting computers coupled to the computerized network, wherein each voting computer provides an electronic encrypted ballot, wherein each electronic ballot is encrypted under a discrete log asymmetric encryption process using underlying groups Zp or elliptic curve;
at least first, second and third authority computers coupled to the computerized network, wherein the first authority computer is configured to receive a series of electronic ballots corresponding to an aggregation of each of the electronic ballots received from the plurality of voting computers, and to apply a secret, one-way cryptographic transformation using at least a first secret key to anonymously shuffle the series of electronic ballots and produce a first shuffled series of ballots, wherein only the first authority computer knows a correspondence between the first series of shuffled ballots and the series of electronic ballots, and wherein the first authority computer is further configured to provide a first non-interactive proof of correctness for the first series of shuffled ballots based on a scaled iterated logarithmic multiplication proof;
wherein the second authority computer is configured to receive the first series of shuffled ballots, to apply the cryptographic transformation using at least a second secret key to anonymously shuffle the first series of shuffled ballots and produce a second series of shuffled ballots, wherein only the second authority computer knows a correspondence between the first series of shuffled ballots and the second series of shuffled ballots, and wherein the second authority computer is further configured to provide a second non-interactive proof of correctness for the second series of shuffled ballots based on the scaled iterated logarithmic multiplication proof;
wherein the third authority computer is configured to receive the second series of shuffled ballots, to apply the cryptographic transformation using at least a third secret key to anonymously shuffle the second series of shuffled ballots and produce a third series of shuffled ballots, wherein only the third authority computer knows a correspondence between the third series of shuffled ballots and the second series of shuffled ballots, and wherein the third authority computer is further configured to provide a third non-interactive proof of correctness for the third series of shuffled ballots based on the scaled iterated logarithmic multiplication proof; and
a verification computer coupled to the computerized network, wherein the verification computer is configured to receive the proofs of correctness from the first, second and third authority computers and without interacting with the first, second and third authority computers, to verify a correctness of the shuffled ballots.
5 Assignments
0 Petitions
Accused Products
Abstract
A cryptographic process permits one to verifiably shuffle a series of input data elements. One or more authorities or individuals “shuffle,” or “anonymize” the input data (e.g. public keys in discrete log form or ElGamal encrypted ballot data). The process includes a validity construction that prevents any one or more of the authorities or individuals from making any changes to the original data without being discovered by anyone auditing a resulting proof transcript. The shuffling may be performed at various times. In the election example, the shuffling may be performed, e.g., after ballots are collected or during the registration, or ballot request phase of the election, thereby anonymizing the identities of the voters.
154 Citations
35 Claims
-
1. An electronic voting system for use with a computerized network, comprising:
-
a plurality of voting computers coupled to the computerized network, wherein each voting computer provides an electronic encrypted ballot, wherein each electronic ballot is encrypted under a discrete log asymmetric encryption process using underlying groups Zp or elliptic curve;
at least first, second and third authority computers coupled to the computerized network, wherein the first authority computer is configured to receive a series of electronic ballots corresponding to an aggregation of each of the electronic ballots received from the plurality of voting computers, and to apply a secret, one-way cryptographic transformation using at least a first secret key to anonymously shuffle the series of electronic ballots and produce a first shuffled series of ballots, wherein only the first authority computer knows a correspondence between the first series of shuffled ballots and the series of electronic ballots, and wherein the first authority computer is further configured to provide a first non-interactive proof of correctness for the first series of shuffled ballots based on a scaled iterated logarithmic multiplication proof;
wherein the second authority computer is configured to receive the first series of shuffled ballots, to apply the cryptographic transformation using at least a second secret key to anonymously shuffle the first series of shuffled ballots and produce a second series of shuffled ballots, wherein only the second authority computer knows a correspondence between the first series of shuffled ballots and the second series of shuffled ballots, and wherein the second authority computer is further configured to provide a second non-interactive proof of correctness for the second series of shuffled ballots based on the scaled iterated logarithmic multiplication proof;
wherein the third authority computer is configured to receive the second series of shuffled ballots, to apply the cryptographic transformation using at least a third secret key to anonymously shuffle the second series of shuffled ballots and produce a third series of shuffled ballots, wherein only the third authority computer knows a correspondence between the third series of shuffled ballots and the second series of shuffled ballots, and wherein the third authority computer is further configured to provide a third non-interactive proof of correctness for the third series of shuffled ballots based on the scaled iterated logarithmic multiplication proof; and
a verification computer coupled to the computerized network, wherein the verification computer is configured to receive the proofs of correctness from the first, second and third authority computers and without interacting with the first, second and third authority computers, to verify a correctness of the shuffled ballots. - View Dependent Claims (2, 3, 4, 5)
-
-
6. 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 first secret key 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 a scaled iterated logarithmic multiplication proof. - View Dependent Claims (7, 8, 9)
-
10. A computer-implemented method, comprising:
-
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 proof of correctness for the shuffled public keys based on a scaled iterated logarithmic multiplication proof and a value corresponding to the one private key, wherein the value 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 that corresponds to the one private key;
issuing a certificate to the one individual; and
reducing the plurality of public keys by the one public key. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17)
-
-
18. A computer-implemented cryptographic method between a prover computer and a verifier computer with respect to first and second sequences of data elements, the method comprising:
-
selecting a subgroup generator g selected from a group G;
secretly generating a prover key c, and a commitment value C based on the subgroup generator g;
secretly establishing a cryptographic relationship between first and second sequences of elements, wherein the cryptographic relationship employs scaled iterated logarithmic multiplication;
providing to the verifier computer the commitment C and the first and second sequences of elements, but not the cryptographic relationship;
computing a series of proof values based on the cryptographic relationship; and
providing the series of computed proof values to the verifier computer as a non-interactive proof of knowledge that the prover computer has access to the cryptographic relationship without revealing the cryptographic relationship to the verifier computer. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26, 27)
-
-
28. A computer-readable medium whose contents provide instructions, when implemented by a computer, perform a shuffling of a sequence of electronic data elements, comprising:
-
receive the sequence of electronic data elements;
apply a secret, one-way cryptographic transformation using at least a first secret key to anonymously permute the sequence of electronic data elements and produce a first shuffled sequence of electronic data elements; and
generate a non-interactive proof of correctness for the first shuffled sequence of electronic data elements based on a scaled iterated logarithmic multiplication proof. - View Dependent Claims (29, 30, 31, 32, 33, 34)
-
-
35. In a cryptographic method, a transmitted signal for use by a computer, comprising:
-
a shuffled sequence of electronic data elements representing individual data files, wherein a one-way cryptographic transformation using at least a first secret key anonymously permuted an input sequence of electronic data elements to produce the shuffled sequence of electronic data elements, and a proof of correctness for the shuffled sequence of electronic data elements based on a scaled iterated logarithmic multiplication proof.
-
Specification