Title of Invention	A METHOD FOR ELECTRONICALLY CASTING VOTES
Abstract	We present a mathematical construct which provides a cryptographic protocol to (venflably 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 per mutation 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 (1 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 zerofcnowl-edge 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

Title of Invention

A METHOD FOR ELECTRONICALLY CASTING VOTES

Abstract

We present a mathematical construct which provides a cryptographic protocol to (venflably 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 per mutation 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 (1 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 zerofcnowl-edge 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

Full Text	Field of the Invention The present invention relates to a method for electronically casting votes. 1 Introduction The notion of a shuffle of a collection,of objects, records, or tokens is simple and intuitive, and useful examples abound in various daily human activities. A gambler in a casino knows that among the cards in his hand, each will be one of 52 unique values, and that no one else at the table will have duplicates of the ones he holds. He does not, however, have any knowledge of how the cards are distributed, even though he may have recorded the exact card order before they were shuffled by the dealer. In the context of electronic data, the problem of achieving the same kind of random, yet verifiable permutation of an input sequence is surprisingly difficult. The problem is that the data itself is either always visible to the auditor, or it isn't. If it is, then the correspondence between input records and output records is trivial to reconstruct by the auditor, or other observer. If it isn't, then input and output records must be different representations of the same underlying data. But if the output is different enough (that is, encrypted well enough) that the auditor cannot reconstruct the correspondence, then how can the auditor be sure that the shuffler did not change the underlying data in the process of shuffling? Most of the paper is devoted to giving an efficient (linear) method for solving this problem in an important context - ElGamal, or Diffie-Hellman encrypted data. In order to make the exposition as clear and concise as possible, the majority of the paper explicitly refers to the specific case where the operations are carried out in a prime subgroup of Zp, the multiplicative group of units modulo a large prime, p. However, the only properties of the underlying (multiplicative) group that we use is that the associated Diffie-Hellman problem is intractable. Thus, the shuffle protocol is also useful when the ElGamal cryptosystem is implemented over other groups such as elliptic curves. The general Boolean proof techniques of [1] and [4] can also be used to construct a proof with the same properties, however, the resulting proof size (complexity) is quadratic, or worse, in the size of the input sequence. The technique of this paper also offers several advantages over the cut-and-choose technique used in [8]. In this approach, the size of proof is dependent on the probability of a cheating prover that is required to satisfy all participants. In the shuffle protocol of this paper, this cheating probability is essentially k/q, where k is the number of elements to be shuffled, and q is the size of the subgroup of Zp in which the elements are encrypted. Although no analysis of the proof size dependence on cheating probability is done in [8], it appears that, in order to obtain similarly low cheating probability, it will need to be orders of magnitude larger than the size of the proof given in this paper. (Moreover, if the [8] protocol is implemented non~ interactively, the cheating probability would need to be chosen exceedingly small, because a malicious participant might use considerable off-line computation to generate a forged proof by exhaustive search. This of course, could be the case with the protocol of this paper as well, but the probability k/q is, for all practical values of k and q, certainly small enough - even for offline attacks.) The results of this paper provide for several ways to implement a universally verifiable election protocol. Some of these are presented in the final sections. In this context, it is worth comparing the elegant homomorphic election protocol of [2]. That protocol works well when ballots have only questions of a simple "choose (at most) m of n" type. This effectively precludes "write-in" responses, as well as "proportional type" questions where the voter is expected to indicate answers in preferential order, and questions are tabulated in accordance with this preference. (Theoretically, proportional type questions can be handled by mapping each valid permutation of selections to a single yes/no response. However, in practice this is infeasible unless the number of choices is quite small.) A couple of somewhat less important disadvantages of the [2] scheme are that it expands vote data size considerably, and that it requires a voter validity proof. This proof further expands the vote data size by about an order of magnitude, and is unattractive from a practical perspective, because it presumes special purpose code to be running on the voter's computer. The shuffle protocols herein are constructed entirely from elementary arithmetic operations. They are thus simple to implement, and are imminently practical for the anonymous credential application described herein. 1.1 Applications to voting The voting application that occurs immediately is that which employs the usual tabulation/mixing center approach to provide anonymity. In this setting, the protocols of this paper offer important advantages. They are much more efficient, and allow the mixing centers to be completely independent of the authorities who hold some share of the key necessary to decrypt ballots. Perhaps, however, a more valuable and exciting application of the new protocol is for creating "anonymous credentials". A member of an authorized group, identified only by a set of DSA, or Diffie-Hellman public keys, can authenticate group membership, and/or sign in a one time way, without revealing his/her individual identity. This leads to a novel solution to the voting problem that is universally verifiable, but does not require any special set of "authorities" in order to tabulate. It also offers a better privacy model to the voter, and speeds tabulation enormously since ballots do not need to be encrypted/decrypted. In effect, instead of mixing encrypted vote cyphertexts after ballots have been received at the vote collection center, voter credentials are mixed before the start of the election. This mixing can naturally be done by the voters themselves to achieve "anonymous authentication". (See section 7.1.) (It should be noted that the mixing could also be done by a set of authorities, this providing a more efficient means to implement a threshold privacy election. One where, again, ballots do not need to be encrypted/decrypted.) 2 Notation In the following, unless explicitly stated otherwise, n will be a positive integer, p and q will be prime integers, publicly known. Arithmetic operations are performed in the modular ring Zp (or occasionally Zn), and g εZp will have (prime) multiplicative order q. (So, trivially, q \| (p — 1).) In each proof protocol, P will be the prover (shuffler) and V the verifier (auditor). We recall the Chaum-Pedersen proof of equality for discrete logarithms. For G, X, H, Y E Zp this is a proof of knowledge for the relation (Equation Removed)(1) It is not known to be zero-knowledge, however it is known to be honest-verifier zeroknowledge. In the next section, we will give a natural multi-variable generalization of this protocol which also has these properties. These are sufficient for our main application where the verifier is implemented via the Fiat-Shamir heuristic. (See [5] and [2].) Definition 1 An instance of this proof, as above, will be denoted by(Equation Removed) Definition 2 For fixed g ε Zp, let g be the binary operator on (g) x (g) defined by (Equation Removed) for all x,y € (g). Alternatively (Equation Removed)for all a,b ε Z,. Following the conventions used for summations and multiplications, we also use the notation(Equation Removed) We refer to this operation as logarithmic multiplication base, g. In each of the notations in the preceding definition, the subscript g may be omitted when its value is clear from context. Remark 1 Notice that (Equation Removed) (2) We note the following collection of well know results, since they will be heavily used in the remainder of the paper. Lemma 1 Let f(x) e Zq[x], be a polynomial of degree d. Then there are at most d values z1,..., zd ε Z, such that f (xi) = 0. Corollary 1 Let f(x), g{x) ε Zq{x) be two monic polynomials of degree at most d, with f ≠ g. Then there are at most d—1 values Zi,...,z^-i e Zq such that f(zi) = gfe). Corollary 2 Let f(x), g{x) e Zq[x] be two monic polynomials of degree at most d, with f ≠ g. If € R Zg (t is selected at random from Zq), then (Equation Removed)Corollary 3 Let f(x), g(x) e Zq[x] be any two polynomials of degree at most d. Then for every constant R ^ 0, there are at most d values, Zi(R),...,Zd(R), such that f(zi(R)) = Rg(zi(R)). Definition 3 Let f(x) be a polynomial in Zq[x]. We denote by Xf the (unordered) set of all roots of f. (Equation Removed) (3) Definition 4 //A C Zq, and R 6 Zq, we write (Equation Removed) (4) Corollary 4 Let f{x), g(x) e Zq[x] be any two polynomials of degree at most d. Fix constants, R ≠ 0,  ≠ 0, and δ ≠ 0. Ift e R Zq, then (Equation Removed)Lemma 2 Let Zq be the standard k-dimensional vector space over Zq, and fix v = (v1,....... vk) € Zkq, v ≠ 0, and, a ε Zq. If r εR Zq is chosen at random, then (Equation Removed) 3 Proofs for iterated logarithmic multiplication For the rest of this section, all logarithmic multiplications will be computed relative to a fixed element g, and hence we will omit the subscript in notation. The following problem is fundamental to the simffle protocols which are to come later. Iterated. Logarithmic Multiplication Problem: Two sequences {Xi}ki=1 and {Yi}ki=1 are publicly known. The prover, P also knows ui = logg Xi and ui, = logg Yi for all i, but these are unknown to the verifier, v. P is required to convince v of the relation (Equation Removed) (5) without revealing any information about the secret logarithms ui and vi. The protocol we give is precisely a higher dimensional generalization of the Chaum-Pedersen protocol discussed at the beginning of section 2. In fact, we will see that in the case k = 2, the protocol is exactly the Chaum-Pedersen protocol. The presentation will be considerably simplified by restricting the problem instance to a case where (Equation Removed) (6) Clearly, if any of these inequalities do not hold, then there is no sense in constructing a proof since equation (5) can be seen to hold or not by inspection. (If Xi = 1 then xi = 0 and so equation (5) holds if and only if Yj = 1 for some j. Similarly with the roles of X and Y reversed.) Iterated Logarithmic Multiplication Proof Protocol (ILMPP) : 1. V secretly generates, randomly and independently from Zq, k — 1 elements, θ1,... θk-i. P then computes (Equation Removed)and reveals to v the sequence A1,..., Ak 2. v generates a random challenge,  ε Zq and reveals it to P. 3. P computes k — 1 elements, r1,..., rk-1, of Zg satisfying (Equation Removed) (8) and reveals the sequence r1,..., rk-1 to v. (We will see in the proof of completeness, below, how these values are computed.) 4. v accepts the proof if and only if all of the equations in (8) hold. Theorem 1 The ILMPP is a three-move, public coin proof of knowledge for the relationship in equation (5) which is special honest-verifier zeroknowledge. The number of exponentiations required to construct the proof is k, and the number of exponentiations required to verify it is 2k. If v generates challenges randomly, the probability of a forged proof is 1/q. Remark 2 Note that in constructing the proof, all exponentiations can be done to the same base, g, so fixed base algorithms can be employed. (See [6], p. 623.) Proof: The protocol is clearly three-move and public coin. The exponentiation count in the construction of the proof looks like it should be 2k — 2, but actually it can be constructed with only k exponentiations. This is because P knows the logarithms Xi and yi, and hence can compute Ai as Ai = gθi-1 +θi-y1 for all 2 Completeness Completeness means that, given arbitrary θ = (θ1,..., θk-i) and , P can always find r = (r1,... ,rk-1) satisfying the system of equations in (8). To see that this is the case, take logg of each side of the equations in (8), and set i = ri — θi for 1 (Equation Removed) (9) The (k — 1) x (k — 1) sub-system (Equation Removed) (10) is non-singular sincets determinant is θ-i=2:ri which is non-zero by assumption (6). Hence, one can always solve it for r1,..., rk+-1 In fact, the solution is (Equation Removed) (11) However, under the hypotheses of the problem, (10) actually implies (9). This is because (Equation Removed) (12) which, combined with the fact that, the sub-matrix on the left of equation (10) is non-singular, means that the first column vector of the k x k matrix in (12) must be a linear combination of the remaining k — 1 column vectors. Soundness If the first column vector of the matrix on the left of equation (12), is not a linear combination of the remaining k — 1 column vectors, then there can be at most one value of  € Zg for which equation (9) holds. Thus, if  is chosen randomly, there is at most a chance of 1 in q that P can prodtice r1,..., rk-1 which convince v. Special Honest-Verifier Zeroknowledge Honest-verifier zero-knowledge holds because, for random 7 and random r = (r1,... ,rk-1), and for (Equation Removed) (13) the triple (Ᾱ,, r) is an accepting conversation. Hence, a simulation is constructed by generating random and independent  and ri and setting Ᾱ as in equation (13). It is easy to see that the distribution so generated for Ᾱ is identical to that generated according to (7), again because the first column vector of the matrix in (12) is a fixed linear combination of the remaining column vectors. So if v is honest, the simulation is perfect. Since the challenge, , can be chosen freely, we also have special honest-verifier zero-knowledge. Remark 3 The solutions for ri in (11) could also be written formally as (Equation Removed) However, this will not work if some of the yi are 0. In the case of equation (11), this problem was avoided by assumption (6). Of course, the main part of the solution could just have well been set up under the assumption that yt ≠ 0 for all 1 Remark 4 We leave it to the reader to check that in the case k = 2, the ILMPP reduces exactly to the well known Chaum-Pedersen protocol. In so doing, it is worth recalling remark 1, equation (2). Remark 5 Special Soundness As is the case with the Chaum-Pedersen protocol, which proves that P knows s = logG X = logH Y, the ILMPP proves that P knows s1,..., sk such that logs Xi = logg Yu and πi=1 si = 1. This is clear because from two accepting conversations, (Ᾱ, , r ) and (Ᾱ, ', r"), with the same first move and  ≠ ', a witness, (Equation Removed) can be extracted satisfying (Equation Removed) (14) Since  =  — ' ≠ 0, it follows that pi ≠ 0 for all 1 4 The Simple k-Shuffle The first shuffle proof protocol we construct requires a restrictive set of conditions. It will be useful for two reasons. First, it is a basic building block of the more general shuffle proof protocol to come later. Fortuitously, it also serves a second important purpose. A single instance of this proof can be constructed to essentially "commit" a particular permutation. This can be important when shuffles need to be performed' on tuples of Zp elements, which is exactly what is required when shuffling ElGamal pairs, as in the voting application. Definition 5 Suppose two sequences of k elements of Zp, X1,... ,Xk, and Y1,..., Yk, along with two additional elements, C and D, are publicly known. Suppose also, that the prover, P, knows xi = logg Xi yi = iogs Yi, c = logg C, and d = logg D,, but that all these values are unknown to the verifier, V. V is required to convince V that there is some permutation, π ε Σk, with bhe property that (Equation Removed) (15) for all 1 Remark 6 For this section, and the remainder of the paper, we will make the simplifying assumptions that in all shuffle constructions 1. X1 ≠ Xj for i ≠ j (and hence, of course, yt ≠ yj, for i ≠ j). 2. Xi ≠ 1 for all 1 There are obvious ways to handle these special cases. Moreover, in practice, they will "essentially never" occur since elements are usually random. The protocol of the previous section, in combination with corollary 2, provide the tools necessary to solve this problem in a fairly straightforward manner. Simple k-Shuffle Proof Protocol: 1. v generates a random t. e Z, and gives it to P as a challenge. 2. P and v publicly compute U = Dl = gdt, W = Ct = gct- and(Equation Removed) 3. P and v execute the ILMPP for the two length 2k vectors (Equation Removed) (16) The protocol succeeds (v accepts the proof) if and only if v accepts this ILMPP. Theorem 2 The Simple k-Shuffle Proof Protocol is a four-move, public coin proof of knowledge for the relationship in equation (15). It satisfies special soundness, and is special honest-verifier zeroknowledge. The number of exponentiations required to construct the proof is 2k, and the number of exponentiations required to verify it is 4k. If V generates challenges randomly, the probability of a forged proof is less than or equal to (Equation Removed) Remark 7 The observations of remark 2 also apply in this case. Proof: All of the required properties follow immediately from the results of the previous section. (Special soundness can be argued from remark 5.) A forged proof can only be generated in two conditions. 1. The challenge t is one of the special values for which (Equation Removed) 2. The challenge t is not one of the special values in 1 above, and the ILMPP is forged. By corollary 2, the probability of 1 is at most (k — l)/q, and the probability of 2 is (q—k + l)/q'z by the results of the previous section. 4.1 A complexity improvement Both the size and complexity of the simple k-shuffle protocol can be improved by a factor of 2. Instead of using corollary 2, we use corollary 4. Intuitively, we would like to replace the k copies of D and k copies of C in equation (16) with single entries gdk and gck respectively. Unfortunately, this would ruin the zeroknowledge property of the protocol. Instead, we modify the protocol ,as follows. Simple k-Shuffle Proof Protocol II: 1. P generates randomly and independently β from Zq and τ from Zq — {0}, computes (Equation Removed) (17) and reveals B and T to v. 2. v generates a random λ from Zq and reveals it to P. 3. P computes s by (Equation Removed) (18) and reveals s to v.v generates a random tεZq, and gives it to V as a challenge. 4. P and v publicly compute U = Dt = gdt, W = Ct = gct, (Equation Removed) and (Equation Removed) 6. P secretly generates, randomly and independently from Zq, k elements, θ1,...θk. P then computes (Equation Removed) (19) and reveals to v the sequence A1,..., Ak+1. 7. v generates a random challenge,  € Zq and reveals it to P. 8. P computes k elements, ri, . .,rk, of Zq satisfying (Equation Removed) (20) and reveals the sequence rt,..., rk to v. 9. v accepts the proof if and only if all of the equations in (20) hold. Theorem 3 Simple k-Shuffle Proof Protocol II is a five-move, public coin proof of knowledge for the relationship in equation (15). It satisfies special soundness, and is special honest-verifier zeroknowledge. The number of exponentiations required to construct the proof is k+4, and the number of exponentiations required to verify it is 2k+ 2. If v generates challenges randomly, the probability of a forged proof remains less than or equal to Proof Sketch: All of the arguments are very similar, property by property, to the arguments constructed in the case of the original protocol. The main difference is that one makes an appeal to corollary 4 rather than corollary 2. Definition 6 We denote an instance of the Simple fc-Shuffle Protocol II by SSk [X, Y, C, D), where X — (X1,..., Xk), Y — (Y1,..., Yk), C, and D are as in definition 5. 5 The General fc-Shuffle An obvious limitation of the simple k-Shuffle protocol is that the shuffler, P, must know all the original exponents x1...,xk and y1,...,yk- In many applications, this will not be the case. The goal of this section is to eliminate that restriction. General k-Shuffle Problem: Two sequences of k elements of Zp, X1,..., Xk, and Y1,..., Yk, are publicly known. In addition, constants c,d € Zg are known only to P, but commitments C = gc and D = gd are made public. P is required to convince v that there is some permutation, π ε Σk , with the property that (Equation Removed) (21) for all 1 General k-Shuffle Proof Protocol: (For the sake of presentation, we consider the case d=l. The general case can be reduced to this case simply by changing the group generator from g to C, and making the substitution c = c/d.) 1. For 1 (Equation Removed) (22) In addition, P generates  from Z, — {0}, and also z0, z1 randomly and independently from Zq, and computes (Equation Removed) (23) and, for 1 (Equation Removed) (24) and finally (Equation Removed) (25) p then reveals the ordered sequences Ai, Bi, Ci Ui, and Wi along with X0, Y0, and Λ to v. 2. For 1 3. P computes (Equation Removed) (26) for 1 4. v generates t ε Z9 — {0} and returns it to P as a challenge. . 5. For 1 (Equation Removed) (27) 6. P and v then execute the simple k-shuffie, SSk (R,S, g, T), where (Equation Removed) (28) (Note that P need not explicitly compute Ri and Si in order to construct the proof, while v can compute Ri and Si as Ri= AiBtei and Si = CiDti Thus, this proof protocol requires P to compute k+4 exponentiations, and v to compute 4k + 2 exponentiations.) 7. P reveals the exponents (Equation Removed) (29) 8. v checks that (Equation Removed) (30) and evaluates (Equation Removed) (31) 9. P computes (Equation Removed) (32) and executes with V the two Chaum-Pedersen proofs, CP (g, F, G, G0) and CP (g, C, Z1G0 G1 (Thus proving to v that equations 32 hold.) 10. v finally checks that(Equation Removed) (33) 11. v accepts the proof if and only if (a) All equations that must be checked (steps 8 and 10) are satisfied (b) v accepts the simple shuffle proof of step 6 (c) v accepts both Chaum-Pedersen proofs in step 9 6 The Multi-Authority Voting Application Much of the setting for the conventional voting application can be found in [2]. Votes are submitted as ElGamal pairs of the form (g0, haim) (or a sequence of these pairs if more data is required), where m is some standard encoding of the voter choices, the αi are generated secretly by the voters, and h is a public parameter constructed via a dealerless secret sharing scheme ([7]). Once the polls are closed (voting finished), an independent collection of authorities sequentially shuffles the ballots. Each shuffle is constructed as (Equation Removed) (34) where the rt are randomly chosen from Zg and (Equation Removed) On output of the final shuffle, the final collection of encrypted ballots is decrypted in accordance with the threshold scheme, and the clear text votes are tabulated in full view by normal election rules. The authorities who participate in the sequential shuffles, may be arbitrary in number, and they may be completely different from those who hold shares of the election private key. The sequence of ballots which axe finally decrypted can only be matched with the original sequence of submitted ballots if all of the shuffling authorities collude, since each of their permutations is completely arbitrary. Although the form of each shuffle is different from the shuffle discussed in section 5, a proof protocol can be constructed with minor modifications. We present the details in the following subsection. 6.1 Shuffles of ElGamal Pairs 1. For 1 (Equation Removed) (35) In addition, P generates  from Zg — {0}, and also xo, y0 and t0 randomly and independently from Zg, and computes (Equation Removed) (36) and, for 1 (Equation Removed) (37) and finally (Equation Removed) (38) V then reveals the ordered sequences Ait Bi, Ci, Uit and Wi along with X0 Y0, and A to ν.. 2. For 1 3. V computes (Equation Removed) (39) for 1 4. V generates c ε Z,- {0} and returns it to P as a challenge. 5. For 1 (Equation Removed) (40) 6. P and v then execute bhe simple k-shuffle, SSk (R, S, g, T), where (Equation Removed) (41) (Note that P need not explicitly compute Ri and S, in order to construct the proof, while v can compute Ri and Si as Ri = Ai Bceii and Si = CiDci. Thus, this proof protocol requires P to compute k+4 exponentiations, and v to compute 4k+2 exponentiations.) 7. P reveals the exponents (Equation Removed) (42) 8. v checks that (Equation Removed) (43) (Equation Removed) (44) 9. P computes (Equation Removed) (45) and executes with V the two Chaum-Pedersen proofs, CP (g, T, G, G0) and CV (g, T, H, H0). (Thus proving to v that equations 45 hold.) 10. P and ν compute (Equation Removed) (46) 11. ρ computes (Equation Removed) (47) and reveals it to ν. 12. ν finally checks that (Equation Removed) (48) 13. ν accepts the proof if and only if (a) All equations that must be checked (steps 8 and 12) are satisfied (b) ν accepts the simple shuffle proof of step 6 (c) ν accepts both Chaum-Pedersen proofs in step 9 6.2 One Pass Tabulation In the standard mix-net implementation, it is assumed that two distinct phases must take place: Shuffling (or mixing) The set of encrypted ballots are mixed. This means that the entire encrypted (and iteratively shuffled) ballot box must be passed sequentially from one authority to another until a sufficient number of mixing stages have been performed. More precisely, let Ai,..., An be the sequence of shuffling, or mixing entities, usually called authorities. Let B be a sequence of encrypted ballots. Sequentially, each Ai performs the following operations. 1. At receives (Equation Removed) from Aj-i, along with all required authentication and validity proofs. (In the case i == 1, Ai receives B directly from the vote collection center.) 2. Ai performs all necessary authentication checks and validity (proof) verifications. 3. If any of the checks in the step 2 fail, tabulation is aborted, or possibly restarted. Qtherwise, Ai computes (Equation Removed) according to equation 34, and also the corresponding validity proof, Pi, of section 6.1. (Typically, this is a non-interactive version of the protocol.) 4. Renaming B as B, Ai sends B to Ai+i along with Pi and any other required au thentication or validity checks. In the case i = n, the mixing is terminated, and tabulation proceeds to the decryption phase. Decryption After shuffling (mixing), the resulting set of ballots are all encrypted to the election public key, usually denoted by h. In order to decrypt these ballots, each authority must now contribute a decryption share. This is accomplished as follows. 1. Let (Equation Removed) be the set of encrypted ballots output by the final mixing authority, An, and let S-p = {D1,...,Vt} be the subset of decryption authorities participating in the decryption. (The value t is determined by the threshold used when the election public key, h, was created. See [7].) 2. For each 1 (a) Dj receives the sequence X1,...tXk along with proper authentication of its validity. (b) If a check of the authentication provided in step 2a fails, Vj should abort the decryption. Otherwise, for each 1 (Equation Removed) (49) where Sj is Dj's decryption share, and z(j,SD) is a publically computable constant multiplier. (See [7].) Vj also produces a Chaum-Pedersen proof of validity, Cij, for equation 49. (c) V returns all Zij and Cij to a tabulation center. 3. Assuming that all Cij received at the tabulation center are valid, the set of clear text ballots are computed as (Equation Removed) (50) 4. The election tally is finally computed by counting the Mi as in any election. If the set, Sv, of decryption authoritias (or even just some subset of it) is included in the set of shuffling authorities (this is almost always the case in practice), a disadvantage of this procedure is that it requires each authority that is in both sets to receive two separate communications, each of which may be quite large. The disadvantage is particularly severe when the authorities are connected by a slow communication link. We observe that it is possible for some or all of the decryption to take place at the same time as mixing. This is accomplished simply by combining, during the shuffling phase, shuffling step 3 with decryption step 2 for each of those shuffling authorities who are members of SD. Those shuffling authorities who are not members of 5© can follow the steps unmodified. So, if Aj is a member of Sj>, in shuffling step 4, rather than jxist send B to Aj+i. Aj sends both and (Equation Removed) where Zij and Cij are as above. Father, instead of using B as the input to its shuffle, Aj+\ should use In this way, if all of the decryption authorities are also shuffle authorities, as is usually the case, then the final output will be a set of decrypted ballots, thus eliminating the need for a seperate decryption phase. If only t0 7 k-Shuffles of DSA Public Keys The general k-shuffle is ideally suited to.verifiably permuting a set of DSA, or Diffie-Hellman public keys. By this we mean that a new set of DSA public keys is produced, which is computationally, unlinkable to the original set, but which verifiably represents the same set of private keys. This can be extremely valuable when one wishes to anonymize a set of authenticated keys while still protecting the integrity of the original group of private keys -the election setting is just one such example. We only sketch the technique here, but the details should then be completely obvious to the reader. It is assumed that initially all the public keys are of the form (g,H), H — gs, where g is some fixed generator and s is the private key. That is, loosely, "all the keys use the same base". The protocol proceeds as follows: 1. Shuffler, or mixer, is presented with g and the list of keys Hi4. 2. Shuffler executes the general k-shuffle with C = g, and Yi — H'i (the new public keys), implementing the verifier's random challenges via the Fiat-Shamir hetiristic. (That is, a non-interactive version of the proof protocol is executed.) 3. Shuffler "returns" the entire proof transcript. 4. Assuming the transcript verifies, set g = C, and Ht = H'v By changing the common base to C, the private keys all remain the same since (Equation Removed) (51) 7.1 Anonymous Voters In the voting application, it is often said that for. election integrity one must know "who voted", but for privacy, one must not know "how.yoted". The technique of this section solves the privacy/integrity dilemma in a new way. Instead of knowing "who voted", one only knows that the person who voted is a member of a set of authorized voters! As a consequence, we are left with a voting solution that 1. Does not require key sharing to implement a distributed trust tabulation scheme. 2. Guarantees computational privacy to the voter, rather than threshold privacy, which is a necessary evil of other voting solutions based on distributed trust tabulation. (If a threshold number of authorities agree to collude, all voters' votes can be decrypted.) 3. Does not require encryption or decryption of voted ballots. Of course, one must look after the problem of "double voting", but the technique of this section is easily modified to take care of that as follows. AV-1. In step 3, the voter (shuffler) - who knows one of the private keys S0 in this case -signs his voted ballot using a DSA signature scheme with group generator (or base), C, and key pair (s0,H'0). (H'0 is the "post shuffle" public key which belongs to the voter. The voter knows its place in the new sequence, since he/she executed the shuffle. And, moreover, the properties of the shuffle guarantee that H'0 = CSn - that is, s0 is the private key corresponding to H'Q.) AV-2. In step 4, assuming that the shuffle transcript checks, and that the ballot signature checks, the vote center simply removes H'0 from the list of authorized keys, and starts the process again waiting for the next ballot request. The new list of public keys is now one smaller, and unless the voter (shuffler) knew more than one private key in the first place, he/she now knows none of the new private keys, and hence can not vote again. The resulting election protocol is Universally Verifiable if all the shuffle transcripts and signatures are maintained. Although this election scheme offers superior privacy characteristics (the secrecy of each voter's ballot is protected by the voter', rather"than by a distributed set of authorities), there is a potential practical drawback. The amount of computation required both of the voter (that is, the voter's computer) and the vote collection server computer for the purpose of authentication is much larger than in standard election protocols, where the voter must only compute a standard public key signature. However, if this additional computation is expected to cause a problem, then the same anonymization can be performed well in advance of the election, before the ballot is available. This is accomplished by issuing standard PKI certificates issued in response to a certificate request which is anonymously signed exactly as the ballot is signed in step AV-1 above. Of course these certificate requests would contain no identifying personal information, but they would otherwise be completely standard, including, most importantly, a standard public key for which the voter has the corresponding private key. At vote time, the ballot can be simply signed with this ordinary private key. With this strategy, it is possible to re-use the anonymous certificates. Thus the computational cost of the anonymous signatures can be amortized over many elections. 8 k-Shuffles of Tuples It should be clear that in section 5, the simple shuffle generated essentially "froze" the permutation that could be proved. This makes it easy to see how to extend the previous section to shuffles of k l-tuples of elements of (g), or k l-tuples of ElGamal pairs. Thinking of a sequence of k l-tuples as a k x / array, a single simple k-shuffle can serve to prove that all columns have been permuted according to the same permutation. Precisely, this means that the same values of Ai, Bi, Ci and Di in both the General k-Shuffle protocol, and the ElGamal Shuflle protocol are used for all columns. (In the General k-Shuffle, the same value of t can be used for all columns, while in the ElGamal Shuffle, the same value of c can be used for all columns, though this is not essential.) 8.1 DSA key shuffles without common base The observation of this section also allows a generalization of the DSA key shuffle protocol of section 7. Rather than maintaining the entire set of public keys to the same base, g ↔ C, the keys are maintained as independent pairs (gu Hi). The shuffler can pick an arbitrary subset of key pairs, (Gi,Hi), shuffle them "as 2-tuples", and return the result. This makes shuffling more manageable if the original set is large, at the cost of increasing the work per key by about 50%. References [1] R. Cramer, I. Damgrd, B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. Advances in Cryptology - CRYPTO '94, Lecture Notes in Computer Science, pp. 174-187, Springer-Verlag, Berlin, 1994. [2] R. Cramer, R. Gennaro, B. Schoenmakers. A secure and optimally efficient multi-authority election scheme. Advances in Cryptology - EUROCRYPT '97, Lecture Notes in-Computer Science, Springer-Verlag, 1997. [3] D. Chaum and T.P. Pedersen. Wallet databases with observers. Advances in Cryptology - CRYPTO '92, volume 740 of Lecture Notes in Compute Science, pages 89-105, Berlin, 1993. Springer-Verlag. [4] A. De Santis, G. Di Crescenzo, G. Persiano and M. Yung. On Monotone Formula Closure of SZK. FOCS 94, pp. 454-465. [5] A. Fiat, A. Shamir. Etow to prove yourself: Practical solutions to identification and signature problems. Advances in Cryptology - CRYPTO '86, Lecture Notes in Computer Science, pp. 186-194, Springer-Verlag, New York, 1987. [6] A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone. Handbook of Applied Cryptography, CRC Press, 1997. [7] T. Pedersen. A threshold cryptosystem without a trusted party, Advances in Cryptology - EUROCRYPT '91, Lecture Notes in Computer Science, pp. 522-526, Springer-Verlag, 1991. [8] K. Sako, J. Kilian. Receipt-free mix-type voting scheme - A practical solution to the implementation of a voting booth, Advances in Cryptology - EUROCRYPT '95, Lecture Notes in Computer Science, Springer-Verlag, 1995. Accordingly, the present invention relates to a method for electronically casting votes comprising the steps of: 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; checking the proof of correctness; and checking that the value is related, in a unique way, to the one public key and the file. The present invention also relates to a method for performing a mixing of electronic data elements, comprising the steps of: 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 cannot be correlated with the original subset of public keys, but wherein the mixed set of public keys corresponds to the set of private keys. Figure 1 and the following discussion provide a brief, general description of a suitable computing environment in which aspects of the invention can be implemented. Although not required, embodiments of the invention may be implemented as computer-executable instructions, such as routines executed by a general-purpose computer, such as a personal computer or web server. Those skilled in the relevant art will appreciate that aspects of the invention (such as small elections) can be practiced with other computer system configurations, including Internet appliances, hand-held devices, wearable computers, personal digital assistants ("PDAs"), multiprocessor systems, microprocessor-based or programmable consumer electronics, network PCs, mini computers, cell or mobile phones, set-top boxes, mainframe computers, and the like. Aspects of the invention can be embodied in a special purpose computer or data processor that is specifically programmed, configured or constructed to perform one or more of the computer-executable instructions explained herein. Indeed, the term "computer," as generally used herein, refers to any of the above devices, as well as any data processor. The invention can also be practiced in distributed computing environments where tasks or modules are performed by remote processing devices, which are linked through a communications network, such as a Local Area Network (LAN), Wide Area Network (WAN), or the Internet. In a distributed computing environment, program modules or sub-routines may be located in both local and remote memory storage devices. The invention described herein may be stored or distributed on computer-readable media, including magnetic and optically readable and removable computer disks, stored as firmware in chips, as well as distributed electronically over the Internet or other networks (including wireless networks). Those skilled in the relevant art will recognize that portions of the protocols described herein may reside on a server computer, while corresponding portions reside on client computers. . Data structures and transmission of data particular to such protocols are also encompassed within the scope of the invention. Unless described otherwise, the construction and operation of the various blocks shown in Figure 1 are of conventional design. As a result, such blocks need not be described in further detail herein, as they will be readily understood by those skilled in the relevant art. Referring to Figure 1, a suitable environment of system 100 includes one or more voter or client computers 102, each of which includes a browser program module 104 that permits the computer to access and exchange data with the Internet, including web sites within the World Wide Web portion 106 of the Internet. The voter computers 102 may include one or more central processing units or other logic processing circuitry, memory, input devices (e.g., keyboards, microphones, touch screens, and pointing devices), output devices (e.g., display devices, audio speakers and printers), and storage devices (e.g., fixed, floppy, and optical disk drives), all well known but not shown in Figure 1. The voter computers 102 may also include other program modules, such as an operating system, one or more application programs (e.g., word processing or spread sheet applications), and the like. As shown in Figure 1, there are N number of voter computers 102, representing voters 1, 2, 3...N. A server computer system 108 or "vote collection center," coupled to the Internet or World Wide Web ("Web") 106, performs much or all of the ballot collection, storing and other processes. A database 110, coupled to the server computer 108, stores much of the web pages and data (including ballots and shuffle validity proofs) exchanged between the voter computers 102, one or more voting poll computers 112 and the server computer 108. The voting poll computer 112 is a personal computer, server computer, mini-computer, or the like, positioned at a public voting location to permit members of the public, or voters who may not have ready access to computers coupled to the Internet 106, to electronically vote under the system described herein. Thus, the voter computers 102 may be positioned at individual voter's homes, where one or more voting poll computers 112 are located publicly or otherwise accessible to voters in a public election. The voting poll computer 112 may include a local area network (LAN) having one server computer and several client computers or voter terminals coupled thereto via the LAN to thereby permit several voters to vote simultaneously or in parallel. Note also that the term "voter" is generally used herein to refer to any individual or organization that employs some or all of the protocols described herein. Under an alternative embodiment, the system 100 may be used in the context of a private election, such as the election of corporate officers or board members. Under this embodiment, the voter computers 102 may be laptops or desktop computers of shareholders, and the voting poll computer 112 can be one or more computers positioned within the company (e.g., in the lobby) performing the election. Thus, shareholders may visit the company to access the voting poll computer 112 to cast their votes. One or more authority or organization computers 114 are also coupled to the server computer system 108 via the Internet 106. If a threshold cryptosystem is employed, then the authority computers 114 each hold a key share necessary to decrypt the electronic ballots stored in the database 110. Threshold cryptographic systems require that a subset t of the total number of authorities n (i.e., t Furthermore, under the depicted embodiment, each of the authority computers may perform one shuffle of the ballots, as described herein. In conjunction with each shuffle, each authority computer generates a shuffle validity proof, which may be encrypted and forwarded to the server computer 108, or stored locally by the authority computer. In an alternative embodiment, an additional set of authority computers are provided, where one set of authority computers shuffle the encrypted ballots and generate shuffle validity proofs, while the second set of authority computers employ keys shares for decrypting the ballots. One or more optional verifier computers 130 may also be provided, similar to the authority computers 114. The verifier computers may receive election transcripts to verify that the election has not been compromised. For example, the verifier computers may receive the shuffle validity proofs from each of the authority computers, as described herein. The verifier computers may perform verifications after the election, and need not be connected to the Internet. Indeed, the verifications may be performed by other computers shown or described herein. The server, verifier or authority computers may perform voter registration protocols, or separate registration computers may be provided (not shown). The registration computers may include biometric readers for reading biometric data of registrants, such as fingerprint data, voice fingerprint data, digital picture comparison, and other techniques known by those skilled in the relevant art. Voter registration and issuing anonymous certificates for use with verifiable shuffles is described below. The server computer 108 includes a server engine 120, a web page management component 122, a database management component 124, as well as other components not shown. The server engine 120 performs, in addition to standard functionality, portions of an electronic voting protocol. The encryption protocol may be stored on the server computer, and portions of such protocol also stored on the client computers, together with appropriate constants. Indeed, the above protocol may be stored and distributed on computer readable media, including magnetic and optically readable and removable computer disks, microcode stored on semiconductor chips (e.g., EEPROM), as well as distributed electronically over the Internet or other networks. Those skilled in the relevant art will recognize that portions of the protocol reside on the server computer, while corresponding portions reside on the client computer. Data structures and transmission of data particular to the above protocol are also encompassed within the present invention. Thus, the server engine 120 may perform all necessary ballot transmission to authorized voters, ballot collection, verifying ballots (e.g., checking digital signatures and passing verification of included proofs of validity in ballots), vote aggregation, ballot decryption and/or vote tabulation. Under an alternative embodiment, the server engine 120 simply collects all electronic ballots as a data collection center. The electronic ballots are then stored and provided to a third party organization conducting the election, such as a municipality, together with 1ools to shuffle ballots, decrypt the tally and produce election results. Likewise, election audit information, such as shuffle validity proofs and the like may be stored locally or provided to a municipality or other organization. The web page component 122 handles creation and display or routing of web pages such as an electronic ballot box web page, as described below. Voters and users may access the server computer 108 by means of a URL associated therewith, such as http:Wwww.votehere.net, or a URL associated with the election, such as a URL for a municipality. The municipality may host or operate the server computer system 108 directly, or automatically forward such received electronic ballots to a third party vote authorizer who, may operate the server computer system. The URL, or any link or address noted herein, can be any resource locator. The web page management process 122 and server computer 108 may have secure sections or pages that may only be accessed by authorized people, such as authorized voters or system adrninistrators. The server computer 108 may employ, e.g., a secure socket layer ("SSL") and tokens or cookies to authenticate such users. Indeed, for small elections, or those where the probability of fraud is low (or results of fraud are relatively inconsequential), the system 100 may employ such simple network security measures for gathering and storing votes as explained below, rather than employing complex electronic encrypted ballots, as described in the above-noted patent application. Methods of authenticating users (such as through the use of passwords), establishing secure transmission connections, and providing secure servers and web pages are known to those skilled in the relevant art. The election scheme and system may use a "bulletin board" where each posting is digitally signed and nothing can be erased. The bulletin board is implemented as a web server. The "ballot box" resides on the bulletin board and holds all of the encrypted ballots. Erasing can be prevented by writing the web server data to a write-once, read-many (WORM) permanent storage medium or similar device. Note that while one embodiment of the invention is described herein as employing the Internet to connect computers, other alternative embodiments are possible. For example, aspects of the invention may be employed by stand alone computers. Aspects of the invention may also be employed by any interconnected data processing machines. Rather than employing a browser, such machines may employ client software for implementing aspects of the methods or protocols described herein. Referring to Figure 2, a schematic diagram illustrates a basic application of the shuffle protocol to an election, shown as a method 200. In block 202, three encrypted ballots are submitted, one each for voters Joe Smith, Sally Jones, and Ian Kelleigh. ha block 204, the list or roll of voters is separated from the encrypted ballots, which are shown in block 206. Thereafter, a one-way reencryption of the ballots is performed to produce a shuffled set of ballots, shown in block 208. A shuffle validity proof is generated based on this first shuffle, shown in block 210. The shuffle validity proof allows a third party to ensure that all. input data (the ballots) had the same operation applied to them, and that no altering of the ballots had been performed. A second shuffle of the (previously shuffled) ballots is performed, to generate a second shuffled set of ballots, shown as block 212. Again, a shuffle validity proof is generated, shown in block 214. The shuffled ballots of block 212 are shuffled a third time, to produce a final shuffled set of ballots under block 216. A third validity proof 218 is likewise generated based on the third shuffle. In sum, a three-by-three shuffle array is provided under this example. Following, the shuffling, the ballots are decrypted to produce a tally, shown as block 220; A third party may verify that the election by analyzing, among other things, each shuffle validity proof to ensure that each shuffler has preserved election integrity. The shuffle protocol is presented above as effectively separate subroutines that may be employed for various applications, such as in a electronic voting scheme. A first subroutine provides the functionality of scaled, iterated, logarithmic multiplication proofs between a prover and a verifier. A second subroutine provides the functionality of a simple shuffle protocol and employs the scaled, iterated, logarithmic multiplication proofs. Thereafter, a third subroutine implements general shuffle functionality, where the shuffler does not know the exponents, building upon the second subroutine of the simple shuffle. A fourth subroutine extends the third subroutine to shuffling k tuples of elements. Other routines are of course also provided. One skilled in the art will appreciate that the concepts of the invention can be used in various environments other than the Internet. For example, the concepts can be used in an electronic mail environment in which electronic mail ballots, transactions, or forms are processed and stored. In general, a web page or display description (e.g., the bulletin board) may be in HTML, XML or WAP format, email format, or any other format suitable for displaying information (including character/code based formats, bitmapped formats and vector based formats). Also, various communication channels, such as local area networks, wide area networks, or point-to-point dial-up connections, may be used instead of the Internet. The various transactions may also be conducted within a single computer environment, rather than in a client/server environment. Each voter or client computer may comprise any combination of hardware or software that interacts with the server computer or system. These client systems may include television-based systems, Internet appliances, mobile phones/PDA's and various other consumer products through which transactions can be performed. In general, as used herein, a "link" refers to any resource locator identifying a resource on the network, such as a display description of a voting authority having a site or node on the network. In general, while hardware platforms, such as voter computers, terminals and servers, are described herein, aspects of the invention are equally applicable to nodes on the network having corresponding resource locators to identify such nodes. Unless the context clearly requires otherwise, throughout the description and the claims, the words 'comprise,1 'comprising,' and the like are to be construed in an inclusive sense as opposed to an exclusive or exhaustive sense; that is to say, in the sense of "including, but not limited to." Words using the singular or plural number also include the plural or singular number, respectively. Additionally, the words "herein," "above," "below" and words of similar import, when used in this application, shall refer to this application as a whole and not to any particular portions of this application. The above description of illustrated embodiments of the invention is not intended to be exhaustive or to limit the invention to the precise form disclosed. While specific embodiments of, and examples for, the invention are described herein for illustrative purposes, various equivalent modifications are possible within the scope of the invention, as those skilled in the relevant art will recognize. The teachings of the invention provided herein can be applied to other encryption applications, not only the electronic voting system described above. For example, the protocol has applications in electronic commerce where both anonymity and auditability are requirements. Examples of this are electronic payment schemes ("e-cash"). These and other changes can be made to the invention in light of the above detailed description. In general, in the following claims, the terms used should not be construed to limit the invention to the specific embodiments disclosed in the specification and the claims, but should be construed to include all encryption systems and methods that operate under the claims to provide data security. Accordingly, the invention is not limited by the disclosure, but instead the scope of the invention is to be determined entirely by the claims. While certain aspects of the invention are presented below in certain claim forms, the inventor contemplates the various aspects of the invention in any number of claim forms. For example, while only one aspect of the invention is recited as embodied in a computer-readable medium, other aspects may likewise be embodied in computer-readable medium. Accordingly, the inventor reserves the right to add additional claims after filing the application to pursue such additional claim forms for other aspects of the invention. WE CLAIM: 1. A system for electronically casting votes comprising: receiving means for 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; a means for providing at least a shuffled subset of the plurality of public keys to the requesting computer; receiving means for receiving a file from the requesting computer; receiving means for 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; checking means for checking the proof of correctness and checking that the value is related, in a unique way, to the one public key and the file; issuing means for issuing a certificate; receiving means for receiving the issued certificate from one of a plurality of individuals; and a means for providing an electronic ballot to the one individual for casting of votes. 2. The system as claimed in claim 1, having receiving means for receiving at least an indication of the one public key in the new shuffled subset of public keys. 3. The system as claimed in claim 1, having removing means for removing the one public key from the new shuffled subset of public keys. 4. The system as claimed in claim 1, having receiving means for 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 means for 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. 5. The system as claimed in claim 1, having setting means for 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. 6. The as claimed in claim 1, having a signing means for digitally signing a received request to produce a public key infrastructure ("PKI") certificate. 7. The as claimed in claim 1, having receiving means for receiving issued certificates from at least some of a plurality of user computers and a means for providing initial electronic ballots in response thereto; and receiving means for receiving unencrypted voted ballots from the at least some of the plurality of user computers. 8. A system for electronically casting votes substantially as herein described with reference to the accompanying drawings.

Full Text

Field of the Invention
The present invention relates to a method for electronically casting votes.
1 Introduction
The notion of a shuffle of a collection,of objects, records, or tokens is simple and intuitive, and
useful examples abound in various daily human activities. A gambler in a casino knows that
among the cards in his hand, each will be one of 52 unique values, and that no one else at the
table will have duplicates of the ones he holds. He does not, however, have any knowledge of
how the cards are distributed, even though he may have recorded the exact card order before
they were shuffled by the dealer.
In the context of electronic data, the problem of achieving the same kind of random, yet
verifiable permutation of an input sequence is surprisingly difficult. The problem is that the
data itself is either always visible to the auditor, or it isn't. If it is, then the correspondence
between input records and output records is trivial to reconstruct by the auditor, or other
observer. If it isn't, then input and output records must be different representations of the
same underlying data. But if the output is different enough (that is, encrypted well enough) that the auditor cannot reconstruct the correspondence, then how can the auditor be sure that the shuffler did not change the underlying data in the process of shuffling?
Most of the paper is devoted to giving an efficient (linear) method for solving this problem in an important context - ElGamal, or Diffie-Hellman encrypted data. In order to make the exposition as clear and concise as possible, the majority of the paper explicitly refers to the specific case where the operations are carried out in a prime subgroup of Z*p, the multiplicative group of units modulo a large prime, p. However, the only properties of the underlying (multiplicative) group that we use is that the associated Diffie-Hellman problem
is intractable. Thus, the shuffle protocol is also useful when the ElGamal cryptosystem is implemented over other groups such as elliptic curves.
The general Boolean proof techniques of [1] and [4] can also be used to construct a proof with the same properties, however, the resulting proof size (complexity) is quadratic, or worse, in the size of the input sequence.
The technique of this paper also offers several advantages over the cut-and-choose technique used in [8]. In this approach, the size of proof is dependent on the probability of a cheating prover that is required to satisfy all participants. In the shuffle protocol of this paper, this cheating probability is essentially k/q, where k is the number of elements to be shuffled, and q is the size of the subgroup of Z*p in which the elements are encrypted. Although no analysis of the proof size dependence on cheating probability is done in [8], it appears that, in order to obtain similarly low cheating probability, it will need to be orders of magnitude larger than the size of the proof given in this paper. (Moreover, if the [8] protocol is implemented non~ interactively, the cheating probability would need to be chosen exceedingly small, because a malicious participant might use considerable off-line computation to generate a forged proof by exhaustive search. This of course, could be the case with the protocol of this paper as well, but the probability k/q is, for all practical values of k and q, certainly small enough - even for offline attacks.)
The results of this paper provide for several ways to implement a universally verifiable election protocol. Some of these are presented in the final sections. In this context, it is worth comparing the elegant homomorphic election protocol of [2]. That protocol works well when ballots have only questions of a simple "choose (at most) m of n" type. This effectively precludes "write-in" responses, as well as "proportional type" questions where the voter is expected to indicate answers in preferential order, and questions are tabulated in accordance with this preference. (Theoretically, proportional type questions can be handled by mapping each valid permutation of selections to a single yes/no response. However, in practice this is infeasible unless the number of choices is quite small.) A couple of somewhat less important disadvantages of the [2] scheme are that it expands vote data size considerably, and that it requires a voter validity proof. This proof further expands the vote data size by about an order
of magnitude, and is unattractive from a practical perspective, because it presumes special purpose code to be running on the voter's computer.
The shuffle protocols herein are constructed entirely from elementary arithmetic operations. They are thus simple to implement, and are imminently practical for the anonymous credential application described herein.
1.1 Applications to voting
The voting application that occurs immediately is that which employs the usual tabulation/mixing center approach to provide anonymity. In this setting, the protocols of this paper offer important advantages. They are much more efficient, and allow the mixing centers to be completely independent of the authorities who hold some share of the key necessary to decrypt ballots.
Perhaps, however, a more valuable and exciting application of the new protocol is for creating "anonymous credentials". A member of an authorized group, identified only by a set of DSA, or Diffie-Hellman public keys, can authenticate group membership, and/or sign in a one time way, without revealing his/her individual identity. This leads to a novel solution to the voting problem that is universally verifiable, but does not require any special set of "authorities" in order to tabulate. It also offers a better privacy model to the voter, and speeds tabulation enormously since ballots do not need to be encrypted/decrypted. In effect, instead of mixing encrypted vote cyphertexts after ballots have been received at the vote collection center, voter credentials are mixed before the start of the election. This mixing can naturally be done by the voters themselves to achieve "anonymous authentication". (See section 7.1.) (It should be noted that the mixing could also be done by a set of authorities, this providing a more efficient means to implement a threshold privacy election. One where, again, ballots do not need to be encrypted/decrypted.)
2 Notation
In the following, unless explicitly stated otherwise, n will be a positive integer, p and q will be prime integers, publicly known. Arithmetic operations are performed in the modular ring
Zp (or occasionally Zn), and g εZp will have (prime) multiplicative order q. (So, trivially, q | (p — 1).) In each proof protocol, P will be the prover (shuffler) and V the verifier (auditor). We recall the Chaum-Pedersen proof of equality for discrete logarithms. For G, X, H, Y E Zp this is a proof of knowledge for the relation
(Equation Removed)(1)
It is not known to be zero-knowledge, however it is known to be honest-verifier zeroknowledge. In the next section, we will give a natural multi-variable generalization of this protocol which also has these properties. These are sufficient for our main application where the verifier is implemented via the Fiat-Shamir heuristic. (See [5] and [2].)
Definition 1 An instance of this proof, as above, will be denoted by(Equation Removed)
Definition 2 For fixed g ε Z*p, let g be the binary operator on (g) x (g) defined by (Equation Removed) for all x,y € (g). Alternatively
(Equation Removed)for all a,b ε Z,. Following the conventions used for summations and multiplications, we also use the notation(Equation Removed)
We refer to this operation as logarithmic multiplication base, g.
In each of the notations in the preceding definition, the subscript g may be omitted when its value is clear from context.
Remark 1 Notice that (Equation Removed) (2)
We note the following collection of well know results, since they will be heavily used in the remainder of the paper.
Lemma 1 Let f(x) e Zq[x], be a polynomial of degree d. Then there are at most d values z1,..., zd ε Z, such that f (xi) = 0.
Corollary 1 Let f(x), g{x) ε Zq{x) be two monic polynomials of degree at most d, with f ≠ g. Then there are at most d—1 values Zi,...,z^-i e Zq such that f(zi) = gfe).
Corollary 2 Let f(x), g{x) e Zq[x] be two monic polynomials of degree at most d, with f ≠ g. If € R Zg (t is selected at random from Zq), then
(Equation Removed)Corollary 3 Let f(x), g(x) e Zq[x] be any two polynomials of degree at most d. Then for every constant R ^ 0, there are at most d values, Zi(R),...,Zd(R), such that f(zi(R)) = Rg(zi(R)).
Definition 3 Let f(x) be a polynomial in Zq[x]. We denote by Xf the (unordered) set of all roots of f.
(Equation Removed) (3)
Definition 4 //A C Zq, and R 6 Zq, we write
(Equation Removed) (4)
Corollary 4 Let f{x), g(x) e Zq[x] be any two polynomials of degree at most d. Fix constants, R ≠ 0,  ≠ 0, and δ ≠ 0. Ift e R Zq, then
(Equation Removed)Lemma 2 Let Zq be the standard k-dimensional vector space over Zq, and fix v = (v1,....... vk) €
Zkq, v ≠ 0, and, a ε Zq. If r εR Zq is chosen at random, then
(Equation Removed)
3 Proofs for iterated logarithmic multiplication
For the rest of this section, all logarithmic multiplications will be computed relative to a fixed element g, and hence we will omit the subscript in notation. The following problem is fundamental to the simffle protocols which are to come later.
Iterated. Logarithmic Multiplication Problem: Two sequences {Xi}ki=1 and {Yi}ki=1 are publicly known. The prover, P also knows ui = logg Xi and ui, = logg Yi for all i, but these are unknown to the verifier, v. P is required to convince v of the relation
(Equation Removed) (5)
without revealing any information about the secret logarithms ui and vi.
The protocol we give is precisely a higher dimensional generalization of the Chaum-Pedersen protocol discussed at the beginning of section 2. In fact, we will see that in the case k = 2, the protocol is exactly the Chaum-Pedersen protocol. The presentation will be considerably simplified by restricting the problem instance to a case where
(Equation Removed) (6)
Clearly, if any of these inequalities do not hold, then there is no sense in constructing a proof since equation (5) can be seen to hold or not by inspection. (If Xi = 1 then xi = 0 and so equation (5) holds if and only if Yj = 1 for some j. Similarly with the roles of X and Y reversed.)
Iterated Logarithmic Multiplication Proof Protocol (ILMPP) :
1. V secretly generates, randomly and independently from Zq, k — 1 elements, θ1,... θk-i. P then computes
(Equation Removed)and reveals to v the sequence A1,..., Ak
2. v generates a random challenge,  ε Zq and reveals it to P.
3. P computes k — 1 elements, r1,..., rk-1, of Zg satisfying
(Equation Removed) (8)
and reveals the sequence r1,..., rk-1 to v. (We will see in the proof of completeness, below, how these values are computed.)
4. v accepts the proof if and only if all of the equations in (8) hold.
Theorem 1 The ILMPP is a three-move, public coin proof of knowledge for the relationship in equation (5) which is special honest-verifier zeroknowledge. The number of exponentiations required to construct the proof is k, and the number of exponentiations required to verify it is 2k. If v generates challenges randomly, the probability of a forged proof is 1/q.
Remark 2 Note that in constructing the proof, all exponentiations can be done to the same base, g, so fixed base algorithms can be employed. (See [6], p. 623.)
Proof: The protocol is clearly three-move and public coin. The exponentiation count in the construction of the proof looks like it should be 2k — 2, but actually it can be constructed
with only k exponentiations. This is because P knows the logarithms Xi and yi, and hence can compute Ai as Ai = gθi-1 +θi-y1 for all 2 Completeness
Completeness means that, given arbitrary θ = (θ1,..., θk-i) and , P can always find r = (r1,... ,rk-1) satisfying the system of equations in (8). To see that this is the case, take logg of each side of the equations in (8), and set i = ri — θi for 1 (Equation Removed) (9)
The (k — 1) x (k — 1) sub-system
(Equation Removed) (10)
is non-singular sincets determinant is θ-i=2:ri which is non-zero by assumption (6). Hence, one can always solve it for r1,..., rk+-1 In fact, the solution is
(Equation Removed) (11)
However, under the hypotheses of the problem, (10) actually implies (9). This is because
(Equation Removed) (12)

which, combined with the fact that, the sub-matrix on the left of equation (10) is non-singular, means that the first column vector of the k x k matrix in (12) must be a linear combination of the remaining k — 1 column vectors.
Soundness
If the first column vector of the matrix on the left of equation (12), is not a linear combination of the remaining k — 1 column vectors, then there can be at most one value of  € Zg for which equation (9) holds. Thus, if  is chosen randomly, there is at most a chance of 1 in q that P can prodtice r1,..., rk-1 which convince v.
Special Honest-Verifier Zeroknowledge
Honest-verifier zero-knowledge holds because, for random 7 and random r = (r1,... ,rk-1), and for
(Equation Removed) (13)
the triple (Ᾱ,, r) is an accepting conversation. Hence, a simulation is constructed by generating random and independent  and ri and setting Ᾱ as in equation (13).
It is easy to see that the distribution so generated for Ᾱ is identical to that generated according to (7), again because the first column vector of the matrix in (12) is a fixed linear combination of the remaining column vectors. So if v is honest, the simulation is perfect. Since the challenge, , can be chosen freely, we also have special honest-verifier zero-knowledge.
Remark 3 The solutions for ri in (11) could also be written formally as
(Equation Removed)
However, this will not work if some of the yi are 0. In the case of equation (11), this problem was avoided by assumption (6). Of course, the main part of the solution could just have well been set up under the assumption that yt ≠ 0 for all 1 Remark 4 We leave it to the reader to check that in the case k = 2, the ILMPP reduces exactly to the well known Chaum-Pedersen protocol. In so doing, it is worth recalling remark 1, equation (2).
Remark 5 Special Soundness
As is the case with the Chaum-Pedersen protocol, which proves that P knows s = logG X = logH Y, the ILMPP proves that P knows s1,..., sk such that logs Xi = logg Yu and πi=1 si = 1. This is clear because from two accepting conversations, (Ᾱ, , r ) and (Ᾱ, ', r"), with the same first move and  ≠ ', a witness,
(Equation Removed) can be extracted satisfying
(Equation Removed) (14)
Since  =  — ' ≠ 0, it follows that pi ≠ 0 for all 1 4 The Simple k-Shuffle
The first shuffle proof protocol we construct requires a restrictive set of conditions. It will be useful for two reasons. First, it is a basic building block of the more general shuffle proof
protocol to come later. Fortuitously, it also serves a second important purpose. A single instance of this proof can be constructed to essentially "commit" a particular permutation. This can be important when shuffles need to be performed' on tuples of Zp elements, which is exactly what is required when shuffling ElGamal pairs, as in the voting application.
Definition 5 Suppose two sequences of k elements of Zp, X1,... ,Xk, and Y1,..., Yk, along with two additional elements, C and D, are publicly known. Suppose also, that the prover, P, knows xi = logg Xi yi = iogs Yi, c = logg C, and d = logg D,, but that all these values are unknown to the verifier, V. V is required to convince V that there is some permutation, π ε Σk, with bhe property that
(Equation Removed) (15)
for all 1 Remark 6 For this section, and the remainder of the paper, we will make the simplifying assumptions that in all shuffle constructions
1. X1 ≠ Xj for i ≠ j (and hence, of course, yt ≠ yj, for i ≠ j).
2. Xi ≠ 1 for all 1 There are obvious ways to handle these special cases. Moreover, in practice, they will "essentially never" occur since elements are usually random.
The protocol of the previous section, in combination with corollary 2, provide the tools necessary to solve this problem in a fairly straightforward manner.
Simple k-Shuffle Proof Protocol:
1. v generates a random t. e Z, and gives it to P as a challenge.
2. P and v publicly compute U = Dl = gdt, W = Ct = gct-
and(Equation Removed)
3. P and v execute the ILMPP for the two length 2k vectors
(Equation Removed) (16)
The protocol succeeds (v accepts the proof) if and only if v accepts this ILMPP.
Theorem 2 The Simple k-Shuffle Proof Protocol is a four-move, public coin proof of knowledge for the relationship in equation (15). It satisfies special soundness, and is special honest-verifier zeroknowledge. The number of exponentiations required to construct the proof is 2k, and the number of exponentiations required to verify it is 4k.
If V generates challenges randomly, the probability of a forged proof is less than or equal to
(Equation Removed) Remark 7 The observations of remark 2 also apply in this case.
Proof: All of the required properties follow immediately from the results of the previous section. (Special soundness can be argued from remark 5.) A forged proof can only be generated in two conditions.
1. The challenge t is one of the special values for which
(Equation Removed) 2. The challenge t is not one of the special values in 1 above, and the ILMPP is forged.
By corollary 2, the probability of 1 is at most (k — l)/q, and the probability of 2 is (q—k + l)/q'z by the results of the previous section.
4.1 A complexity improvement
Both the size and complexity of the simple k-shuffle protocol can be improved by a factor of 2. Instead of using corollary 2, we use corollary 4. Intuitively, we would like to replace the k copies of D and k copies of C in equation (16) with single entries gdk and gck respectively. Unfortunately, this would ruin the zeroknowledge property of the protocol. Instead, we modify the protocol ,as follows.
Simple k-Shuffle Proof Protocol II:
1. P generates randomly and independently β from Zq and τ from
Zq — {0}, computes
(Equation Removed) (17)
and reveals B and T to v.
2. v generates a random λ from Zq and reveals it to P.
3. P computes s by
(Equation Removed) (18) and reveals s to v.v generates a random tεZq, and gives it to V as a challenge.
4. P and v publicly compute U = Dt = gdt, W = Ct = gct,
(Equation Removed) and
(Equation Removed)
6. P secretly generates, randomly and independently from Zq, k elements, θ1,...θk. P
then computes
(Equation Removed) (19)
and reveals to v the sequence A1,..., Ak+1.
7. v generates a random challenge,  € Zq and reveals it to P.
8. P computes k elements, ri, . .,rk, of Zq satisfying
(Equation Removed) (20)
and reveals the sequence rt,..., rk to v.
9. v accepts the proof if and only if all of the equations in (20) hold.
Theorem 3 Simple k-Shuffle Proof Protocol II is a five-move, public coin proof of knowledge for the relationship in equation (15). It satisfies special soundness, and is special honest-verifier zeroknowledge. The number of exponentiations required to construct the proof is k+4, and the number of exponentiations required to verify it is 2k+ 2.
If v generates challenges randomly, the probability of a forged proof remains less than or equal to
Proof Sketch: All of the arguments are very similar, property by property, to the arguments constructed in the case of the original protocol. The main difference is that one makes an appeal to corollary 4 rather than corollary 2.
Definition 6 We denote an instance of the Simple fc-Shuffle Protocol II by SSk [X, Y, C, D), where X — (X1,..., Xk), Y — (Y1,..., Yk), C, and D are as in definition 5.
5 The General fc-Shuffle
An obvious limitation of the simple k-Shuffle protocol is that the shuffler, P, must know all the original exponents x1...,xk and y1,...,yk- In many applications, this will not be the case. The goal of this section is to eliminate that restriction.
General k-Shuffle Problem: Two sequences of k elements of Zp, X1,..., Xk, and Y1,..., Yk, are publicly known. In addition, constants c,d € Zg are known only to P, but commitments C = gc and D = gd are made public. P is required to convince v that there is some permutation, π ε Σk , with the property that
(Equation Removed) (21)
for all 1 General k-Shuffle Proof Protocol:
(For the sake of presentation, we consider the case d=l. The general case can be reduced to this case simply by changing the group generator from g to C, and making the substitution c = c/d.)

1. For 1 (Equation Removed) (22)
In addition, P generates  from Z, — {0}, and also z0, z1 randomly and independently from Zq, and computes
(Equation Removed) (23)
and, for 1 (Equation Removed) (24)
and finally
(Equation Removed) (25)
p then reveals the ordered sequences Ai, Bi, Ci Ui, and Wi along with X0, Y0, and Λ to v.
2. For 1 3. P computes
(Equation Removed) (26)
for 1 4. v generates t ε Z9 — {0} and returns it to P as a challenge. .
5. For 1 (Equation Removed) (27)
6. P and v then execute the simple k-shuffie, SSk (R,S, g, T), where
(Equation Removed) (28)
(Note that P need not explicitly compute Ri and Si in order to construct the proof, while v can compute Ri and Si as Ri= AiBtei and Si = CiDti Thus, this proof protocol requires P to compute k+4 exponentiations, and v to compute 4k + 2 exponentiations.)
7. P reveals the exponents
(Equation Removed) (29)
8. v checks that
(Equation Removed) (30)
and evaluates
(Equation Removed) (31)
9. P computes
(Equation Removed) (32)
and executes with V the two Chaum-Pedersen proofs, CP (g, F, G, G0) and CP (g, C, Z1G0 G1 (Thus proving to v that equations 32 hold.)
10. v finally checks that(Equation Removed)
(33)
11. v accepts the proof if and only if
(a) All equations that must be checked (steps 8 and 10) are satisfied
(b) v accepts the simple shuffle proof of step 6
(c) v accepts both Chaum-Pedersen proofs in step 9
6 The Multi-Authority Voting Application
Much of the setting for the conventional voting application can be found in [2]. Votes are submitted as ElGamal pairs of the form (g0*, haim) (or a sequence of these pairs if more data is required), where m is some standard encoding of the voter choices, the αi are generated secretly by the voters, and h is a public parameter constructed via a dealerless secret sharing scheme ([7]). Once the polls are closed (voting finished), an independent collection of authorities sequentially shuffles the ballots. Each shuffle is constructed as
(Equation Removed) (34) where the rt are randomly chosen from Zg and
(Equation Removed) On output of the final shuffle, the final collection of encrypted ballots is decrypted in accordance with the threshold scheme, and the clear text votes are tabulated in full view by normal election rules.
The authorities who participate in the sequential shuffles, may be arbitrary in number, and they may be completely different from those who hold shares of the election private key. The
sequence of ballots which axe finally decrypted can only be matched with the original sequence of submitted ballots if all of the shuffling authorities collude, since each of their permutations is completely arbitrary.
Although the form of each shuffle is different from the shuffle discussed in section 5, a proof protocol can be constructed with minor modifications. We present the details in the following subsection.
6.1 Shuffles of ElGamal Pairs
1. For 1 (Equation Removed) (35)
In addition, P generates  from Zg — {0}, and also xo, y0 and t0 randomly and independently from Zg, and computes
(Equation Removed) (36)
and, for 1 (Equation Removed) (37)
and finally
(Equation Removed) (38)
V then reveals the ordered sequences Ait Bi, Ci, Uit and Wi along with X0 Y0, and A
to ν..
2. For 1 3. V computes
(Equation Removed) (39)
for 1 4. V generates c ε Z,- {0} and returns it to P as a challenge.
5. For 1 (Equation Removed) (40)
6. P and v then execute bhe simple k-shuffle, SSk (R, S, g, T), where
(Equation Removed) (41)
(Note that P need not explicitly compute Ri and S, in order to construct the proof, while
v can compute Ri and Si as Ri = Ai Bceii and Si = CiDci. Thus, this proof protocol
requires P to compute k+4 exponentiations, and v to compute 4k+2 exponentiations.)
7. P reveals the exponents
(Equation Removed) (42)
8. v checks that
(Equation Removed) (43)
(Equation Removed) (44)
9. P computes
(Equation Removed) (45)
and executes with V the two Chaum-Pedersen proofs, CP (g, T, G, G0) and CV (g, T, H, H0). (Thus proving to v that equations 45 hold.)
10. P and ν compute
(Equation Removed) (46)
11. ρ computes
(Equation Removed) (47) and reveals it to ν.
12. ν finally checks that
(Equation Removed) (48)
13. ν accepts the proof if and only if
(a) All equations that must be checked (steps 8 and 12) are satisfied
(b) ν accepts the simple shuffle proof of step 6
(c) ν accepts both Chaum-Pedersen proofs in step 9
6.2 One Pass Tabulation
In the standard mix-net implementation, it is assumed that two distinct phases must take place:
Shuffling (or mixing) The set of encrypted ballots are mixed. This means that the entire encrypted (and iteratively shuffled) ballot box must be passed sequentially from one authority to another until a sufficient number of mixing stages have been performed.
More precisely, let Ai,..., An be the sequence of shuffling, or mixing entities, usually called authorities. Let B be a sequence of encrypted ballots. Sequentially, each Ai performs the following operations.
1. At receives
(Equation Removed) from Aj-i, along with all required authentication and validity proofs. (In the case i == 1, Ai receives B directly from the vote collection center.)
2. Ai performs all necessary authentication checks and validity (proof) verifications.
3. If any of the checks in the step 2 fail, tabulation is aborted, or possibly restarted. Qtherwise, Ai computes
(Equation Removed) according to equation 34, and also the corresponding validity proof, Pi, of section 6.1. (Typically, this is a non-interactive version of the protocol.)
4. Renaming B as B, Ai sends B to Ai+i along with Pi and any other required au
thentication or validity checks. In the case i = n, the mixing is terminated, and
tabulation proceeds to the decryption phase.
Decryption After shuffling (mixing), the resulting set of ballots are all encrypted to the election public key, usually denoted by h. In order to decrypt these ballots, each authority must now contribute a decryption share. This is accomplished as follows.
1. Let
(Equation Removed) be the set of encrypted ballots output by the final mixing authority, An, and let S-p = {D1,...,Vt} be the subset of decryption authorities participating in the decryption. (The value t is determined by the threshold used when the election public key, h, was created. See [7].)
2. For each 1 (a) Dj receives the sequence X1,...tXk along with proper authentication of its validity.
(b) If a check of the authentication provided in step 2a fails, Vj should abort the decryption. Otherwise, for each 1 (Equation Removed) (49)
where Sj is Dj's decryption share, and z(j,SD) is a publically computable constant multiplier. (See [7].) Vj also produces a Chaum-Pedersen proof of validity, Cij, for equation 49.
(c) V returns all Zij and Cij to a tabulation center.
3. Assuming that all Cij received at the tabulation center are valid, the set of clear
text ballots are computed as
(Equation Removed) (50)
4. The election tally is finally computed by counting the Mi as in any election.
If the set, Sv, of decryption authoritias (or even just some subset of it) is included in the set of shuffling authorities (this is almost always the case in practice), a disadvantage of this procedure is that it requires each authority that is in both sets to receive two separate communications, each of which may be quite large. The disadvantage is particularly severe when the authorities are connected by a slow communication link.
We observe that it is possible for some or all of the decryption to take place at the same time as mixing. This is accomplished simply by combining, during the shuffling phase, shuffling step 3 with decryption step 2 for each of those shuffling authorities who are members of SD. Those shuffling authorities who are not members of 5© can follow the steps unmodified.
So, if Aj is a member of Sj>, in shuffling step 4, rather than jxist send B to Aj+i. Aj sends both
and
(Equation Removed) where Zij and Cij are as above. Father, instead of using B as the input to its shuffle, Aj+\ should use
In this way, if all of the decryption authorities are also shuffle authorities, as is usually the case, then the final output will be a set of decrypted ballots, thus eliminating the need for a seperate decryption phase. If only t0 7 k-Shuffles of DSA Public Keys
The general k-shuffle is ideally suited to.verifiably permuting a set of DSA, or Diffie-Hellman public keys. By this we mean that a new set of DSA public keys is produced, which is computationally, unlinkable to the original set, but which verifiably represents the same set of private keys. This can be extremely valuable when one wishes to anonymize a set of authenticated keys while still protecting the integrity of the original group of private keys -the election setting is just one such example.
We only sketch the technique here, but the details should then be completely obvious to the reader. It is assumed that initially all the public keys are of the form (g,H), H — gs,
where g is some fixed generator and s is the private key. That is, loosely, "all the keys use the same base". The protocol proceeds as follows:
1. Shuffler, or mixer, is presented with g and the list of keys Hi4.
2. Shuffler executes the general k-shuffle with C = g, and Yi — H'i (the new public keys), implementing the verifier's random challenges via the Fiat-Shamir hetiristic. (That is, a non-interactive version of the proof protocol is executed.)
3. Shuffler "returns" the entire proof transcript.
4. Assuming the transcript verifies, set g = C, and Ht = H'v By changing the common base to C, the private keys all remain the same since
(Equation Removed) (51)
7.1 Anonymous Voters
In the voting application, it is often said that for. election integrity one must know "who voted", but for privacy, one must not know "how.yoted". The technique of this section solves the privacy/integrity dilemma in a new way. Instead of knowing "who voted", one only knows that the person who voted is a member of a set of authorized voters! As a consequence, we are left with a voting solution that
1. Does not require key sharing to implement a distributed trust tabulation scheme.
2. Guarantees computational privacy to the voter, rather than threshold privacy, which is a necessary evil of other voting solutions based on distributed trust tabulation. (If a threshold number of authorities agree to collude, all voters' votes can be decrypted.)
3. Does not require encryption or decryption of voted ballots.
Of course, one must look after the problem of "double voting", but the technique of this section is easily modified to take care of that as follows.

AV-1. In step 3, the voter (shuffler) - who knows one of the private keys S0 in this case -signs his voted ballot using a DSA signature scheme with group generator (or base), C, and key pair (s0,H'0). (H'0 is the "post shuffle" public key which belongs to the voter. The voter knows its place in the new sequence, since he/she executed the shuffle. And, moreover, the properties of the shuffle guarantee that H'0 = CSn - that is, s0 is the private key corresponding to H'Q.)
AV-2. In step 4, assuming that the shuffle transcript checks, and that the ballot signature checks, the vote center simply removes H'0 from the list of authorized keys, and starts the process again waiting for the next ballot request. The new list of public keys is now one smaller, and unless the voter (shuffler) knew more than one private key in the first place, he/she now knows none of the new private keys, and hence can not vote again.
The resulting election protocol is Universally Verifiable if all the shuffle transcripts and signatures are maintained.
Although this election scheme offers superior privacy characteristics (the secrecy of each voter's ballot is protected by the voter', rather"than by a distributed set of authorities), there is a potential practical drawback. The amount of computation required both of the voter (that is, the voter's computer) and the vote collection server computer for the purpose of authentication is much larger than in standard election protocols, where the voter must only compute a standard public key signature. However, if this additional computation is expected to cause a problem, then the same anonymization can be performed well in advance of the election, before the ballot is available.
This is accomplished by issuing standard PKI certificates issued in response to a certificate request which is anonymously signed exactly as the ballot is signed in step AV-1 above. Of course these certificate requests would contain no identifying personal information, but they would otherwise be completely standard, including, most importantly, a standard public key for which the voter has the corresponding private key. At vote time, the ballot can be simply signed with this ordinary private key. With this strategy, it is possible to re-use the anonymous certificates. Thus the computational cost of the anonymous signatures can be amortized over many elections.
8 k-Shuffles of Tuples
It should be clear that in section 5, the simple shuffle generated essentially "froze" the permutation that could be proved. This makes it easy to see how to extend the previous section to shuffles of k l-tuples of elements of (g), or k l-tuples of ElGamal pairs. Thinking of a sequence of k l-tuples as a k x / array, a single simple k-shuffle can serve to prove that all columns have been permuted according to the same permutation. Precisely, this means that the same values of Ai, Bi, Ci and Di in both the General k-Shuffle protocol, and the ElGamal Shuflle protocol are used for all columns. (In the General k-Shuffle, the same value of t can be used for all columns, while in the ElGamal Shuffle, the same value of c can be used for all columns, though this is not essential.)
8.1 DSA key shuffles without common base
The observation of this section also allows a generalization of the DSA key shuffle protocol of section 7. Rather than maintaining the entire set of public keys to the same base, g ↔ C, the keys are maintained as independent pairs (gu Hi). The shuffler can pick an arbitrary subset of key pairs, (Gi,Hi), shuffle them "as 2-tuples", and return the result. This makes shuffling more manageable if the original set is large, at the cost of increasing the work per key by about 50%.
References
[1] R. Cramer, I. Damgrd, B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. Advances in Cryptology - CRYPTO '94, Lecture Notes in Computer Science, pp. 174-187, Springer-Verlag, Berlin, 1994.
[2] R. Cramer, R. Gennaro, B. Schoenmakers. A secure and optimally efficient multi-authority election scheme. Advances in Cryptology - EUROCRYPT '97, Lecture Notes in-Computer Science, Springer-Verlag, 1997.
[3] D. Chaum and T.P. Pedersen. Wallet databases with observers. Advances in Cryptology
- CRYPTO '92, volume 740 of Lecture Notes in Compute Science, pages 89-105, Berlin,
1993. Springer-Verlag.
[4] A. De Santis, G. Di Crescenzo, G. Persiano and M. Yung. On Monotone Formula Closure of SZK. FOCS 94, pp. 454-465.
[5] A. Fiat, A. Shamir. Etow to prove yourself: Practical solutions to identification and signature problems. Advances in Cryptology - CRYPTO '86, Lecture Notes in Computer Science, pp. 186-194, Springer-Verlag, New York, 1987.
[6] A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone. Handbook of Applied Cryptography, CRC Press, 1997.
[7] T. Pedersen. A threshold cryptosystem without a trusted party, Advances in Cryptology
- EUROCRYPT '91, Lecture Notes in Computer Science, pp. 522-526, Springer-Verlag,
1991.
[8] K. Sako, J. Kilian. Receipt-free mix-type voting scheme - A practical solution to the implementation of a voting booth, Advances in Cryptology - EUROCRYPT '95, Lecture Notes in Computer Science, Springer-Verlag, 1995.
Accordingly, the present invention relates to a method for electronically casting votes comprising the steps of:
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;
checking the proof of correctness; and
checking that the value is related, in a unique way, to the one public key and the file.
The present invention also relates to a method for performing a mixing of electronic data elements, comprising the steps of:
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 cannot be correlated with the original subset of public keys, but wherein the mixed set of public keys corresponds to the set of private keys.
Figure 1 and the following discussion provide a brief, general description of a suitable computing environment in which aspects of the invention can be implemented. Although not required, embodiments of the invention may be implemented as computer-executable instructions, such as routines executed by a general-purpose computer, such as a personal computer or web server. Those skilled in the relevant art will appreciate that aspects of the invention (such as small elections) can be practiced with other computer system configurations, including Internet appliances, hand-held devices, wearable computers, personal digital assistants ("PDAs"), multiprocessor systems, microprocessor-based or programmable consumer electronics, network PCs, mini computers, cell or mobile phones, set-top boxes, mainframe computers, and the like. Aspects of the invention can be embodied in a special purpose computer or data processor that is specifically programmed, configured or constructed to perform one or more of the computer-executable instructions explained herein. Indeed, the term "computer," as generally used herein, refers to any of the above devices, as well as any data processor.
The invention can also be practiced in distributed computing environments where tasks or modules are performed by remote processing devices, which are linked through a communications network, such as a Local Area Network (LAN), Wide Area Network (WAN), or the Internet. In a distributed computing environment, program modules or sub-routines may be located in both local and remote memory storage devices. The invention described herein may be stored or distributed on computer-readable media, including magnetic and optically readable and removable computer disks, stored as firmware in chips, as well as distributed electronically over the Internet or other networks (including wireless networks). Those skilled in the relevant art will recognize that portions of the protocols described herein may reside on a server computer, while corresponding portions reside on client computers. . Data structures and transmission of data particular to such protocols are also encompassed within the scope of the invention.
Unless described otherwise, the construction and operation of the various blocks shown in Figure 1 are of conventional design. As a result, such blocks need not be described in further detail herein, as they will be readily understood by those skilled in the relevant art.
Referring to Figure 1, a suitable environment of system 100 includes one or more voter or client computers 102, each of which includes a browser program module 104 that permits the computer to access and exchange data with the Internet, including web sites within the World Wide Web portion 106 of the Internet. The voter computers 102 may include one or more central processing units or other logic processing circuitry, memory, input devices (e.g., keyboards, microphones, touch screens, and pointing devices), output devices (e.g., display devices, audio speakers and printers), and storage devices (e.g., fixed, floppy, and optical disk drives), all well known but not shown in Figure 1. The voter computers 102 may also include other program modules, such as an operating system, one or more application programs (e.g., word processing or spread sheet applications), and the like. As shown in Figure 1, there are N number of voter computers 102, representing voters 1, 2, 3...N.
A server computer system 108 or "vote collection center," coupled to the Internet or World Wide Web ("Web") 106, performs much or all of the ballot collection, storing and other processes. A database 110, coupled to the server computer 108, stores much of the web pages and data (including ballots and shuffle validity proofs) exchanged between the voter computers 102, one or more voting poll computers 112 and the server computer 108. The voting poll computer 112 is a personal computer, server computer, mini-computer, or the like, positioned at a public voting location to permit members of the public, or voters who may not have ready access to computers coupled to the Internet 106, to electronically vote under the system described herein. Thus, the voter computers 102 may be positioned at individual voter's homes, where one or more voting poll computers 112 are located publicly or otherwise accessible to voters in a public election. The voting poll computer 112 may include a local area network (LAN) having one server computer and several client computers or voter terminals coupled thereto via the LAN to thereby permit several voters to vote simultaneously or in parallel. Note also that the term "voter" is generally used herein to refer to any individual or organization that employs some or all of the protocols described herein.
Under an alternative embodiment, the system 100 may be used in the context of a private election, such as the election of corporate officers or board members. Under this embodiment, the voter computers 102 may be laptops or desktop computers of shareholders, and the voting poll
computer 112 can be one or more computers positioned within the company (e.g., in the lobby) performing the election. Thus, shareholders may visit the company to access the voting poll computer 112 to cast their votes.
One or more authority or organization computers 114 are also coupled to the server computer system 108 via the Internet 106. If a threshold cryptosystem is employed, then the authority computers 114 each hold a key share necessary to decrypt the electronic ballots stored in the database 110. Threshold cryptographic systems require that a subset t of the total number of authorities n (i.e., t Furthermore, under the depicted embodiment, each of the authority computers may perform one shuffle of the ballots, as described herein. In conjunction with each shuffle, each authority computer generates a shuffle validity proof, which may be encrypted and forwarded to the server computer 108, or stored locally by the authority computer. In an alternative embodiment, an additional set of authority computers are provided, where one set of authority computers shuffle the encrypted ballots and generate shuffle validity proofs, while the second set of authority computers employ keys shares for decrypting the ballots.
One or more optional verifier computers 130 may also be provided, similar to the authority computers 114. The verifier computers may receive election transcripts to verify that the election has not been compromised. For example, the verifier computers may receive the shuffle validity proofs from each of the authority computers, as described herein. The verifier computers may perform verifications after the election, and need not be connected to the Internet. Indeed, the verifications may be performed by other computers shown or described herein.
The server, verifier or authority computers may perform voter registration protocols, or separate registration computers may be provided (not shown). The registration computers may include biometric readers for reading biometric data of registrants, such as fingerprint data, voice fingerprint data, digital picture comparison, and other techniques known by those skilled in the relevant art. Voter registration and issuing anonymous certificates for use with verifiable shuffles is described below.
The server computer 108 includes a server engine 120, a web page management component 122, a database management component 124, as well as other components not shown. The server engine 120 performs, in addition to standard functionality, portions of an electronic voting protocol. The encryption protocol may be stored on the server computer, and portions of such protocol also stored on the client computers, together with appropriate constants. Indeed, the above protocol may be stored and distributed on computer readable media, including magnetic and optically readable and removable computer disks, microcode stored on semiconductor chips (e.g., EEPROM), as well as distributed electronically over the Internet or other networks. Those skilled in the relevant art will recognize that portions of the protocol reside on the server computer, while corresponding portions reside on the client computer. Data structures and transmission of data particular to the above protocol are also encompassed within the present invention. Thus, the server engine 120 may perform all necessary ballot transmission to authorized voters, ballot collection, verifying ballots (e.g., checking digital signatures and passing verification of included proofs of validity in ballots), vote aggregation, ballot decryption and/or vote tabulation. Under an alternative embodiment, the server engine 120 simply collects all electronic ballots as a data collection center. The electronic ballots are then stored and provided to a third party organization conducting the election, such as a municipality, together with 1ools to shuffle ballots, decrypt the tally and produce election results. Likewise, election audit information, such as shuffle validity proofs and the like may be stored locally or provided to a municipality or other organization.
The web page component 122 handles creation and display or routing of web pages such as an electronic ballot box web page, as described below. Voters and users may access the server computer 108 by means of a URL associated therewith, such as http:Wwww.votehere.net, or a URL
associated with the election, such as a URL for a municipality. The municipality may host or operate the server computer system 108 directly, or automatically forward such received electronic ballots to a third party vote authorizer who, may operate the server computer system. The URL, or any link or address noted herein, can be any resource locator.
The web page management process 122 and server computer 108 may have secure sections or pages that may only be accessed by authorized people, such as authorized voters or system adrninistrators. The server computer 108 may employ, e.g., a secure socket layer ("SSL") and tokens or cookies to authenticate such users. Indeed, for small elections, or those where the probability of fraud is low (or results of fraud are relatively inconsequential), the system 100 may employ such simple network security measures for gathering and storing votes as explained below, rather than employing complex electronic encrypted ballots, as described in the above-noted patent application. Methods of authenticating users (such as through the use of passwords), establishing secure transmission connections, and providing secure servers and web pages are known to those skilled in the relevant art.
The election scheme and system may use a "bulletin board" where each posting is digitally signed and nothing can be erased. The bulletin board is implemented as a web server. The "ballot box" resides on the bulletin board and holds all of the encrypted ballots. Erasing can be prevented by writing the web server data to a write-once, read-many (WORM) permanent storage medium or similar device.
Note that while one embodiment of the invention is described herein as employing the Internet to connect computers, other alternative embodiments are possible. For example, aspects of the invention may be employed by stand alone computers. Aspects of the invention may also be employed by any interconnected data processing machines. Rather than employing a browser, such machines may employ client software for implementing aspects of the methods or protocols described herein.
Referring to Figure 2, a schematic diagram illustrates a basic application of the shuffle protocol to an election, shown as a method 200. In block 202, three encrypted ballots are submitted, one each for voters Joe Smith, Sally Jones, and Ian Kelleigh. ha block 204, the list or roll of voters is
separated from the encrypted ballots, which are shown in block 206. Thereafter, a one-way reencryption of the ballots is performed to produce a shuffled set of ballots, shown in block 208. A shuffle validity proof is generated based on this first shuffle, shown in block 210. The shuffle validity proof allows a third party to ensure that all. input data (the ballots) had the same operation applied to them, and that no altering of the ballots had been performed.
A second shuffle of the (previously shuffled) ballots is performed, to generate a second shuffled set of ballots, shown as block 212. Again, a shuffle validity proof is generated, shown in block 214. The shuffled ballots of block 212 are shuffled a third time, to produce a final shuffled set of ballots under block 216. A third validity proof 218 is likewise generated based on the third shuffle. In sum, a three-by-three shuffle array is provided under this example. Following, the shuffling, the ballots are decrypted to produce a tally, shown as block 220; A third party may verify that the election by analyzing, among other things, each shuffle validity proof to ensure that each shuffler has preserved election integrity.
The shuffle protocol is presented above as effectively separate subroutines that may be employed for various applications, such as in a electronic voting scheme. A first subroutine provides the functionality of scaled, iterated, logarithmic multiplication proofs between a prover and a verifier. A second subroutine provides the functionality of a simple shuffle protocol and employs the scaled, iterated, logarithmic multiplication proofs. Thereafter, a third subroutine implements general shuffle functionality, where the shuffler does not know the exponents, building upon the second subroutine of the simple shuffle. A fourth subroutine extends the third subroutine to shuffling k tuples of elements. Other routines are of course also provided.
One skilled in the art will appreciate that the concepts of the invention can be used in various environments other than the Internet. For example, the concepts can be used in an electronic mail environment in which electronic mail ballots, transactions, or forms are processed and stored. In general, a web page or display description (e.g., the bulletin board) may be in HTML, XML or WAP format, email format, or any other format suitable for displaying information (including character/code based formats, bitmapped formats and vector based formats). Also, various communication channels, such as local area networks, wide area networks, or point-to-point dial-up
connections, may be used instead of the Internet. The various transactions may also be conducted within a single computer environment, rather than in a client/server environment. Each voter or client computer may comprise any combination of hardware or software that interacts with the server computer or system. These client systems may include television-based systems, Internet appliances, mobile phones/PDA's and various other consumer products through which transactions can be performed.
In general, as used herein, a "link" refers to any resource locator identifying a resource on the network, such as a display description of a voting authority having a site or node on the network. In general, while hardware platforms, such as voter computers, terminals and servers, are described herein, aspects of the invention are equally applicable to nodes on the network having corresponding resource locators to identify such nodes.
Unless the context clearly requires otherwise, throughout the description and the claims, the words 'comprise,1 'comprising,' and the like are to be construed in an inclusive sense as opposed to an exclusive or exhaustive sense; that is to say, in the sense of "including, but not limited to." Words using the singular or plural number also include the plural or singular number, respectively. Additionally, the words "herein," "above," "below" and words of similar import, when used in this application, shall refer to this application as a whole and not to any particular portions of this application.
The above description of illustrated embodiments of the invention is not intended to be exhaustive or to limit the invention to the precise form disclosed. While specific embodiments of, and examples for, the invention are described herein for illustrative purposes, various equivalent modifications are possible within the scope of the invention, as those skilled in the relevant art will recognize. The teachings of the invention provided herein can be applied to other encryption applications, not only the electronic voting system described above. For example, the protocol has applications in electronic commerce where both anonymity and auditability are requirements. Examples of this are electronic payment schemes ("e-cash").
These and other changes can be made to the invention in light of the above detailed description. In general, in the following claims, the terms used should not be construed to limit the invention to
the specific embodiments disclosed in the specification and the claims, but should be construed to include all encryption systems and methods that operate under the claims to provide data security. Accordingly, the invention is not limited by the disclosure, but instead the scope of the invention is to be determined entirely by the claims.
While certain aspects of the invention are presented below in certain claim forms, the inventor contemplates the various aspects of the invention in any number of claim forms. For example, while only one aspect of the invention is recited as embodied in a computer-readable medium, other aspects may likewise be embodied in computer-readable medium. Accordingly, the inventor reserves the right to add additional claims after filing the application to pursue such additional claim forms for other aspects of the invention.

WE CLAIM:
1. A system for electronically casting votes comprising:
receiving means for 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;
a means for providing at least a shuffled subset of the plurality of public keys to the requesting computer;
receiving means for receiving a file from the requesting computer;
receiving means for 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;
checking means for checking the proof of correctness and checking that the value is related, in a unique way, to the one public key and the file;
issuing means for issuing a certificate;
receiving means for receiving the issued certificate from one of a plurality of individuals; and
a means for providing an electronic ballot to the one individual for casting of votes.
2. The system as claimed in claim 1, having receiving means for receiving at least an indication of the one public key in the new shuffled subset of public keys.
3. The system as claimed in claim 1, having removing means for removing the one public key from the new shuffled subset of public keys.
4. The system as claimed in claim 1, having receiving means for 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 means for 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.
5. The system as claimed in claim 1, having setting means for 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.
6. The as claimed in claim 1, having a signing means for digitally signing a received request to produce a public key infrastructure ("PKI") certificate.
7. The as claimed in claim 1, having receiving means for receiving issued certificates from at least some of a plurality of user computers and a means for providing initial electronic ballots in response thereto; and receiving means for receiving unencrypted voted ballots from the at least some of the plurality of user computers.
8. A system for electronically casting votes substantially as herein described with reference to the accompanying drawings.

Documents:

1479-delnp-2003-abstract.pdf

1479-delnp-2003-claims.pdf

1479-delnp-2003-complete specification (granted).pdf

1479-delnp-2003-correspondence-others.pdf

1479-delnp-2003-correspondence-po.pdf

1479-delnp-2003-description (complete).pdf

1479-delnp-2003-drawings.pdf

1479-delnp-2003-form-1.pdf

1479-delnp-2003-form-13.pdf

1479-delnp-2003-form-19.pdf

1479-delnp-2003-form-2.pdf

1479-DELNP-2003-Form-3.pdf

1479-delnp-2003-form-5.pdf

1479-delnp-2003-pa.pdf

1479-delnp-2003-pct-101.pdf

1479-delnp-2003-pct-210.pdf

1479-delnp-2003-pct-304.pdf

1479-delnp-2003-pct-401.pdf

1479-delnp-2003-pct-408.pdf

1479-delnp-2003-petition-137.pdf

« Previous Patent

Next Patent »

Patent Number

218070

Indian Patent Application Number

01479/DELNP/2003

PG Journal Number

37/2008

Publication Date

12-Sep-2008

Grant Date

31-Mar-2008

Date of Filing

16-Sep-2003

Name of Patentee

VOTEHERE, INC.

Applicant Address

155-108TH AVENUE N.E., SUITE 425, BELLEVUE, WESHINGTON 98004, UNITED STATES OF AMERICA.

Inventors:

#	Inventor's Name	Inventor's Address
1	ANDREW CHARLES NEFF,	250, 3010 NORTHUP WAY BELLEVUE WA 98004, USA

PCT International Classification Number

G07C 13/00

PCT International Application Number

PCT/US02/09264

PCT International Filing date

2002-03-25

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1	60/311,680	2001-08-09	U.S.A.
2	60/312,671	2001-08-15	U.S.A.
3	09/816,869	2001-03-24	U.S.A.
4	60/313,003	2001-08-16	U.S.A.