Title of Invention	Data Processing System for Discerning Corruption of an Electronic Ballot
Abstract	A method in a data processing system for discerning corruption of an electronic ballot, comprising sending an encrypted ballot from a first computer system to a second computer system, the encrypted ballot reflecting a ballot choice selected by a voter; sending a confirmation from the second computer system to the first computer system, the confirmation serving to convey the decrypted contents of the encrypted ballot as received at the second computer system, the confirmation being generated without decrypting the encrypted ballot; and in the first computer system, displaying the confirmation, so that the voter can determine whether the decrypted contents of the encrypted ballot as received at the second computer system match the ballot choice selected by the voter.

Title of Invention

Data Processing System for Discerning Corruption of an Electronic Ballot

Abstract

A method in a data processing system for discerning corruption of an electronic ballot, comprising sending an encrypted ballot from a first computer system to a second computer system, the encrypted ballot reflecting a ballot choice selected by a voter; sending a confirmation from the second computer system to the first computer system, the confirmation serving to convey the decrypted contents of the encrypted ballot as received at the second computer system, the confirmation being generated without decrypting the encrypted ballot; and in the first computer system, displaying the confirmation, so that the voter can determine whether the decrypted contents of the encrypted ballot as received at the second computer system match the ballot choice selected by the voter.

Full Text	RELATED APPLICATIONS [ooo1] This application claims the benefit of U.S. Provisional Application No. 60/270,182 filed February 20, 2001, claims the benefit of U.S. Provisional Application No. ___________(patent counsel's docket number 32462-8006US02) filed February 11, 2002, and is a continuation-in-part of each of U.S. Patent Application No. 09/534,836, filed March 24, 2000; U.S. Patent Application No. 09/535,927, filed March 24, 2000; and U.S. Patent Application No. 09/816,869 filed March 24, 2001. Each of these five applications is incorporated by reference in its entirety. TECHNICAL FIELD [0002] The present invention is directed to the fields of election automation and cryptographic techniques therefor. BACKGROUND [0003] The problems of inaccuracy and inefficiency have long attended conventional, manually-conducted elections. While it has been widely suggested that computers could be used to make elections more accurate and efficient, computers bring with them their own pitfalls. Since electronic data is so easily altered, many electronic voting systems are prone to several types of failures that are far less likely to occur with conventional voting systems. [0004] One class of such failures relates to the uncertain integrity of the voter's computer, or other computing device. In today's networked computing environment, it is extremely difficult to keep any machine safe from malicious software. Such software is often able to remain hidden on a computer for long periods of time before actually performing a malicious action. In the meantime, it may replicate itself to other computers on the network, or computers that have some minimal interaction with the network. It may even be transferred to computers that are not networked by way of permanent media carried by users. [0005] In the context of electronic secret ballot elections, this kind of malicious software is especially dangerous, since even when its malicious action is triggered, it may go undetected, and hence left to disrupt more elections in the future. Controlled logic and accuracy tests ("L&A tests") monitor the processing of test ballots to determine whether a voting system is operating properly, and may be used in an attempt to detect malicious software present in a voter's computer. L&A tests are extremely difficult to conduct effectively, however, since it is possible that the malicious software may be able to differentiate between "real" and "test" ballots, and leave all "test" ballots unaffected. Since the requirement for ballot secrecy makes it impossible to inspect "real" ballots for compromise, even exhaustive L&A testing may prove futile. The problem of combating this threat is known as the "Client Trust Problem." [0006] Most existing methods for solving the Client Trust Problem have focused on methods to secure the voting platform, and thus provide certainty that the voter's computer is "clean," or "uninfected." Unfortunately, the expertise and ongoing diligent labor that is required to achieve an acceptable level of such certainty typically forces electronic voting systems into the controlled environment of the poll site, where the client computer systems can be maintained and monitored by computer and network experts. These poll site systems can still offer some advantages by way of ease of configuration, ease of use, efficiency of tabulation, and cost. However, this approach fails to deliver on the great potential for distributed communication that has been exploited in the world of e-commerce. [0007] Accordingly, a solution to the Client Trust Problem that does not require the voting platform to be secured against malicious software, which enables practically any computer system anywhere to be used as the voting platform, would have significant utility. BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS [0008] Figure 1 is a high-level block diagram showing a typical environment in which the facility operates. [0009] Figure 2 is a block diagram showing some of the components typically incorporated in at least some of the computer systems and other devices on which the facility executes. [0010] Figure 3 is a flow diagram showing steps typically performed by the facility in order to detect a compromised ballot. DETAILED DESCRIPTION . s A' ij [0011] A P.S for detecting ballots compromised by malicious programs ("the facility") is provided. The approach employed by the facility typically makes no attempt to eliminate, or prevent the existence of malicious software on the voting computer. Instead, it offers a cryptographically secure method for the voter to verify the contents of the voter's ballot as it is received at the vote collection center, without revealing information about the contents (ballot choices) to the collection center itself. That is, the vote collection center can confirm to the voter exactly what choices were received, without knowing what those choices are. Thus, the voter can detect any differences between the voter's intended choices, and the actual choices received at the vote collection center (as represented in the transmitted voted ballot digital data). Further, each election can choose from a flexible set of policy decisions allowing a voter to re-cast the voter's ballot in the case that the received choices differ from the intended choices. [0012] The facility is described in the context of a fairly standard election setting. For ease of presentation, initial discussion of the facility assumes that there is only one question on the ballot, and that there are a set of K allowable answers, al,...,aK (one of which may be "abstain"). It will be appreciated by those of ordinary skill in the art that it is a straightforward matter to generalize the solution given in this situation to handle the vast majority of real world ballot configurations. [0013] Several typical cryptographic features of the election setting are: 1. Ballot Construction: A set of cryptographic election parameters are agreed upon by election officials in advance, and made publicly known by wide publication or other such means. Significant parameters are the encryption group, generator, election public key and decision encoding scheme. More specifically, these are: (a) The encryption group, G may be Z with p a large prime, or an elliptic curve group. (b) The generator, gsG. In the case G=Zp, g should generate a (multiplicative) subgroup, , of G* which has large prime order q. In the elliptic curve case we assume ~G and q=p. (c) The election public key, he. (d) The decision encoding scheme: A partition of into "answer representatives." That is, =S0US1U...SK where the Sk are pair wise disjoint subsets of . For each l [0014] While the following discussion uses multiplicative group notation for the sake of consistency, it should be clear that all constructions can be implemented equally well using elliptic curves. 2. Vote Submission: Each voter, v,-, encrypts her vote, or decision, as an ElGamal pair, (Xi,Yl) = (gα1,,hα',m1, where αiZq is chosen randomly by the voter, and mt Sk if vi wishes to choose answer αk. This encrypted value is what is transmitted to the vote collection center (cast), usually with an attached digital signature created by vi,-. [0015] If the voter, vi were computing these values herself - say with pencil and paper - this protocol would essentially suffice to implement a secret ballot, universally verifiable election system. (Depending on the tabulation method to be used, some additional information, such as a voter proof of validity would be necessary.) However, since in practice, vi only makes choices through some user interface, it is not realistic to expect her to observe the actual value of the bits sent and check them for consistency with her intended choice. In short, the vote client can ignore voter intent and submit a "µj vote" when the voter actually wished to submit a "µk vote." [0016] The voter typically needs some way to verify that the encrypted vote which was received at the vote collection center is consistent with her choice. Simply making the ballot box data public does not a reasonable solution, since the vote client, not the voter, chooses at. For reasons of vote secrecy, and coercion, this value should be "lost." So v{'s encrypted vote is as opaque to her as it is to anyone else. A generic confirmation from the vote collection center is obviously not sufficient either. The general properties of what is needed are properties: 1. The confirmation string, C, returned by the vote collection center, needs to be a function of the data (encrypted vote) received. 2. The voter and vote client should be able to execute a specific set of steps that allow the voter to tie C exclusively to the choice (or vote),µk, that was received. 3. It should be impossible for the vote client to behave in such a way that the voter "is fooled." That is, the client can not convince the voter that µk was received, when actually, µ=µk was received. [0017] In this section, we present such a scheme, which we shall refer to as SVC, in its basic form. In following sections, we offer some improvements and enhancements. [0018] The following steps are typically performed as part of the voting process. CC-1. The vote client, Mi"operated by" vi, creates an encrypted ballot on behalf of v{ as before. Let us denote this by (Xi ,Yi) = (gα',hα'mi), for some value mi ) and αtZq CC-2. Mi is also required to construct a validity proof, Pt, which is a zeroknowledge proof that mi{µ1...,µk}. (Such a proof is easily constructed from the basic Chaum-Pederson proof for equality of discrete logarithms using the techniques of [CDS94]. See [CGS97] for a specific example.) CC-3. Mi then submits both Pi and the (signed) encrypted vote, (Xt,Yi) to the vote collection center. CC-4. Before accepting the encrypted ballot, the vote collection center first checks the proof, Pi. If verification of Pi fails, corruption has already been detected, and the vote collection center can either issue no confirmation string, or some default random one. CC-5. Assuming then that verification of Pi succeeds, the vote collection center computes the values, Wi and Ui as, Wi = KiYißi=Kihα1ß1mißi (1) Ui = hßi (2) where KiG and ßiZq are generated randomly and independently (on a voter-by-voter basis). CC-6. The vote collection center then returns (Ui,Wi) to Mi. CC-7. The client, Mi, computes C, = Vi/Uiαi = Kimißi (3) and display this string (or, more likely, a hash of it, H(Ci)) to the voter, vi-. [0019] The voter needs to know which confirmation string to look for. This can be accomplished in two different ways. The most straightforward is to have the voter, vi$, obtain Ki and ßi from the vote collection center. This is workable, requires very little data to be transferred, and may be well suited to some implementations. However, in other situations, it may be an unattractive approach because Ci (or H(Ci) must then be computed. Since asking Mi to perform this computation would destroy the security of the scheme, vi$ must have access to an additional computing device, as well as access to the independent communication channel. [0020] An alternative is to have the vote collection center compute all possible confirmation strings for vi$, and send what amounts to a confirmation dictionary to vi$ via the independent channel. In general, the confirmation dictionary for voter vi$ would consist of the following table laid out in any reasonable format: ( Table Removed) where H is the election's public (published) hash function (possibly the identity function), and Cij=Kiµjßi. [0021] Of course care must be used in engineering the independent channel to be sure that it really is independent. Ideally, it should be inaccessible to devices connected to the voting network. Solutions are available, however. Since the Ki and ßican be generated in advance of the election, even slow methods of delivery, such as surface mail, can be employed to transmit the dictionary. [0022] In order to more completely describe the facility, an example illustrating the operation of some of its embodiments is described. The following is a detailed example of a Secret Value Confirmation exchange. [0023] In order to maximize the clarity of the example, several of the basic parameters used - for example, the number of questions on the ballot, and the size of the cryptographic parameters - are much smaller than those that would be typically used in practice. Also, while aspects of the example exchange are discussed below in a particular order, those skilled in the art will recognize that they may be performed in a variety of other orders. [0024] Some electronic election protocols include additional features, such as: • voter and authority certificate (public key) information for authentication and audit • ballot page style parameters • data encoding standards tabulation protocol and parameters [0025] As these features are independent of the Secret Value Confirmation implementation, a detailed description of them is not included in this example. [0026] This example assumes an election protocol that encodes voter responses (answers) as a single ElGamal pair. However, from the description found here, it is a trivial matter to also construct a Secret Value Confirmation exchange for other election protocols using ElGamal encryption for the voted ballot. For example, some embodiments of the facility incorporate the homomorphic election protocol described in U.S. Patent Application No. 09/535,927. In that protocol, a voter response, is represented by multiple ElGamal pairs. The confirmation dictionary used in this example is easily modified to either display a concatenation of the respective confirmation strings, or to display a hash of the sequence of them. [0027] The jurisdiction must first agree on the election initialization data. This at least includes: the basic cryptographic numerical parameters, a ballot (i.e., a set of questions and allowable answers, etc.) and a decision encoding scheme. (It may also include additional data relevant to the particular election protocol being used.) Cryptographic Parameters • Group Arithmetic: Integer multiplicative modular arithmetic • Prime Modulus: p = 47 • Subgroup Modulus: q = 23 • Generator: g = 2 • Public Key: h = gs where s is secret. For the sake of this example, let us say that h = g12 =7. Ballot • One Question • tabulation protocol and parameters [0025] As these features are independent of the Secret Value Confirmation implementation, a detailed description of them is not included in this example. [0026] This example assumes an election protocol that encodes voter responses (answers) as a single ElGamal pair. However, from the description found here, it is a trivial matter to also construct a Secret Value Confirmation exchange for other election protocols using ElGamal encryption for the voted ballot. For example, some embodiments of the facility incorporate the homomorphic election protocol described in U.S. Patent Application No. 09/535,927. In that protocol, a voter response, is represented by multiple ElGamal pairs. The confirmation dictionary used in this example is easily modified to either display a concatenation of the respective confirmation strings, or to display a hash of the sequence of them. [0027] The jurisdiction must first agree on the election initialization data. This at least includes: the basic cryptographic numerical parameters, a ballot (i.e., a set of questions and allowable answers, etc.) and a decision encoding scheme. (It may also include additional data relevant to the particular election protocol being used.) Cryptographic Parameters • Group Arithmetic: Integer multiplicative modular arithmetic • Prime Modulus: p = 47 • Subgroup Modulus: q = 23 • Generator: g = 2 • Public Key: h = gs where s is secret. For the sake of this example, let us say that h = g12 =7. Ballot • One Question • tabulation protocol and parameters [0025] As these features are independent of the Secret Value Confirmation implementation, a detailed description of them is not included in this example. [0026] This example assumes an election protocol that encodes voter responses (answers) as a single ElGamal pair. However, from the description found here, it is a trivial matter to also construct a Secret Value Confirmation exchange for other election protocols using ElGamal encryption for the voted ballot. For example, some embodiments of the facility incorporate the homomorphic election protocol described in U.S. Patent Application No. 09/535,927. In that protocol, a voter response, is represented by multiple ElGamal pairs. The confirmation dictionary used in this example is easily modified to either display a concatenation of the respective confirmation strings, or to display a hash of the sequence of them. [0027] The jurisdiction must first agree on the election initialization data. This at least includes: the basic cryptographic numerical parameters, a ballot (i.e., a set of questions and allowable answers, etc.) and a decision encoding scheme. (It may also include additional data relevant to the particular election protocol being used.) Cryptographic Parameters • Group Arithmetic: Integer multiplicative modular arithmetic • Prime Modulus: p = 47 • Subgroup Modulus: q = 23 • Generator: g = 2 • Public Key: h = gs where s is secret. For the sake of this example, let us say that h = g12 =7. Ballot • One Question 3. (X, Y) = (2α,7α x36) i.e. choice (vote cast) is "Red" 4. (X, Y) = (2α,7αxl7) i.e. choice (vote cast) is "I abstain" for some unspecified value of α without revealing which of them actually does hold. [0035] There are a variety of standard methods that can be used to accomplish this. See, for example, R Cramer, I. Damgard, 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. The Secret Value Confirmation technique used by the facility works equally well with any method that satisfies the abstract criteria of the previous paragraph. While details of one such validity proof method are provided below, embodiments of the facility may use validity proofs of types other than this one. Validity Proof Construction: [0036] (In what follows, each action or computation which V is required to perform is actually carried out by V 's computer.) 1. V sets α2= α = 5. 2. V generates Z23, r1,r2,r3,r4 Z23, sl,s3, s4 R Z23 all randomly and independently. For this example we take 2 = 4 (5) r1=16, r3=17, r4 = 21 s1, =12, s3=4, s4=15 3. V computes corresponding values ai=griXsi = 216x3211=4 (6) a2=g = 24=16 a3=gr3X-s3 = 217x3219=6 a4=gr4X-4 = 221x328=9 b1 = hr1 (Y/9)-s1 = 716 x (24/9)11 = 18 b2 = h = 74=4 b3 = hr3 (Y/36)-s3 = 717 x (24/36)19 = 1 b4=hr'(Y/17)-S5 = 721x(24/17)8=7 (7) 4. V uses a publicly specified hash function H to compute c  Z23 as c=H({X,Y,ai,bi}) l Since many choices of the hash function are possible, for this example we can just pick a random value, say c = 19. (9) (In practice, SHA1, or MD5, or other such standard secure hash function may be used to compute H.) 5. V computes the interpolating polynomial P(x) of degree 4 — 1 = 3. The defining properties of P are P(0) = c=19 (10) P(l) = s1=12 p(3) = S3=4 P(4) = S4=15 P(X.) =J=0Z jxicomputed using standard polynomial interpolation theory, to yield: P(X) = X3+20X2+18X+19 (11) or z0=19 z,=18 z2 = 20 z3 = 1 (12) 6. V computes the values s2=P(2) = 5 (13) r2 =2 +α2 s2=4+5x5 = 6 V's validity proof consists of the 12 numbers {αk ,bk ,rk}6 k= 1 (14) and the three numbers {Zk}3k=1 (15) in precise sequence. (z0 need not be submitted since it is computable from the other data elements submitted using the public hash function H.) [0037] Having computed the required choice encryption, (X, Y) and the corresponding proof of validity, V encodes these elements, in sequence, as defined by the standard encoding format. The resulting sequences form V's voted ballot. (In order to make the ballot unalterable, and indisputable, V may also digitally sign this voted ballot with his private signing key. The resulting combination of V 's voted ballot, and his digital signature (more precisely, the standard encoding of these two elements) forms his signed voted ballot.) Finally, each voter transmits his (optionally signed) voted ballot back to the data center collecting the votes. [0038] As described above, the voter specific random parameters for V (/? and Kj are available at the vote collection center. In this example, these are ß=18 K=37 (16) [0039] When the voter's (optionally signed) voted ballot is received at the vote collection center, the following steps are executed 1. The digital signature is checked to determine the authenticity of the ballot, as well as the eligibility of the voter. 2. If the signature in step 1 verifies correctly, the vote collection center then verifies the proof of validity. For the particular type of validity proof we have chosen to use in this example, this consists of (a) The public hash function H is used to compute the value of z0=P(0) = H({X,Y,ai,bi}4i=1) = 19 (17) (Recall that the remaining coefficients of P, z1 ,z2 , z3 , are part of V 's (optionally signed) voted ballot submission.) (b) For each 1 are evaluated. (Here, as described above, the µj are taken from the Decision Encoding Scheme.) If equality fails in any of these, verification fails. This ballot is not accepted, and some arbitrary rejection string (indication) is sent back to V. 3. Assuming that the previous steps have passed successfully, the reply string {W, U) is computed as W = KYß =37x2418 =9 (19) This sequenced pair is encoded as specified by the public encoding format, and returned to V. A. V 's computer calculates C = W/Uα = 9/(42)5 = 18 (20) and displays this string to V. (Alternatively, the protocol may specify that a public hash function is computed on C and the resulting hash value displayed. In this example, C itself is displayed.) If V's computer attempted to submit a choice other than "Green," the value of C computed above would be different. Moreover, the correct value of C cannot be computed from an incorrect one without solving the Diffie-Hellman problem. (For the small values of p and q we have used here, this is possible. However, for "real" cryptographic parameters, V's computer would be unable to do this.) Thus, if V's computer has submitted an encrypted ballot which does not correspond to V's choice, there are only two things it can do at the point it is expected to display a confirmation. It can display something, or it can display nothing. In the case that nothing is displayed, V may take this as an indication that the ballot was corrupted. In the case that something is displayed, what is displayed will almost certainly be wrong, and again, V may take this as an indication that the ballot was corrupted. 5. V now compares the value of C displayed to the value found in V's confirmation dictionary corresponding to the choice, "Green" (V's intended choice). At this point, V may have already received his confirmation dictionary in advance, or may obtain a copy through any independent channel. An example of such a channel would be to use a fax machine. If the displayed value does not match the corresponding confirmation string in the confirmation dictionary, corruption is detected, and the ballot can be "recast" in accordance with election-specific policy. [0040] Each voter confirmation dictionary is computed by the vote collection center, since, as described above, it is the entity which has knowledge of the voter specific values of a and K. For the case of the voter, V, we have been considering, the dictionary is computed as ( Table Removed) [0041] The level of security provided by the facility when using the SVC scheme is described hereafter: Let A be the vote client adversary, and let 0 be an upper bound on the probability that A is able to forge a validity proof for any given µ1,...,µK. (We know that e0 is negligible.) [0042] Theorem 1 Suppose the SVC scheme is executed with H = Id Fix 1 0, A can, with probability e, submit bt = (ga',ha' ukt), and display Cik2 = Kiµß1k2 , where the probability is taken uniformly over all combinations of values for µ1,...,µK, g, h, ßiand Ki. Then A can solve a random instance of the Diffie-Hellman problem with probability e, and with 0(K) additional work. [0043] Proof: Supposed is givenX,Y,ZeR. A can simulate an election and SVC exchange by picking Cikg> and µkg> independently at random for all k=k2, setting h-X,h^ =Y and µk2 =µk1Z. The resulting distribution on the election parameters and Ciki is obviously identical to the distribution that arises from real elections. With probability , A can display Ciki, so can compute C = Cik2/Cik1 = (µk2/µk1)ß1 = Zß1 (20) So logxC= ßilogliZ=logXYlogXZ, and C is the solution to the Diffie-Hellman problem instance posed by the triple (X,Y,Z). [0044] Corollary 1 Suppose again that the SVC scheme is executed with H - Id Fixl>k2>K. Suppose that for some > 0, A can, with probability ex, choose k1=k2, submit bs = (ga1, ha1µk1 ), and displays Cik2 = Ki µß1k2 where the probability is taken uniformly over all combinations of values for µ1,...,µK, g, h,ßi and K i . Then A cart solve a random instance of the Diffie-Hellman problem with probability /(K-l), and with 0(K) additional work. [0045] Proof: Follow the arguments of theorem 1, but compare to the problem of finding the solution to at least one of K-\ independent Diffie-Hellman problems. [0046] Corollary 2 Let DH be an upper bound on the probability that A can solve a random Diffie-Hellman instance. Then, in the case that H = Id, an upper bound on the probability that A can submit a vote that differs from the voter's choice, and yet display the correct confirmation string is 0 +(K — 1)DH. [0047] If the hash function H is non-trivial, we can not hope to make comparisons to the computational Diffie-Hellman problem without considerable specific knowledge of the properties of H. Rather than consider the security of the scheme with specific choices of H, we assume only that H has negligible collision probability, and instead compare security with the Decision Diffie-Hellman Problem. The variant of this problem we consider is as follows. A is given a sequence of tuples, (Xn,Yn,Zn,Cn), where Xn,Yn,Zn are generated independently at random. With probability 1/2, C„ is the solution to the Diffie-Hellman instance, (Xn,Yn,Zn, and with probability 1-1/2=1/2, Cn is generated randomly and independently. A is said to have an e-DDH advantage if A can, with probability 1/2+ e, 7 answer the question logXnCn = logxn Yn logxn Zn. [0048] Theorem 1, and corollaries 1 and 2 have obvious analogs in the case H &Id (assuming only that H has negligible collision probability). Both the statements and proofs are constructed with minor variation, so we only summarize with: Corollary 3 Let DDH. be an upper bound on A's DDH advantage. Then, ifH is any hash function with negligible collision probability, an upper bound on the probability that A can submit a vote that differs from the voter's choice, and yet display the correct confirmation string is 0+(K-l)DDH. [0049] SVC may not offer any protection if the adversary, A, also controls the vote collection center. If this were the case, A has access to Ki and ßi, and thus can easily display any valid confirmation string of its choosing. It seems unlikely that this would happen, since the vote collection center would be undeniably implicated in the event that such activity is discovered. Nevertheless, in case it is unacceptable to trust the vote collection center in this regard, the "confirmation responsibility" can be distributed among arbitrarily many authorities. [0050] To distribute the confirmation responsibility, each authority, Aj, l^j (for voter vi) independent random Kij and ßij. The authorities can combine these by two general methods. 1. Concatenation. The voter's confirmation string is computed as a concatenation, in pre-specified order, of the individual confirmation strings (computed separately as in the revious section) corresponding to each of the J authorities. In this case, confirmation is successful only if all of the substrings verify correctly. 2. Trusted Server or Printer. If it is acceptable to trust a single central server, or printer, the multiple confirmation strings can be combined into one of the same size by simply computing (21) (22) This has the advantage of reducing the amount of confirmation data that must be transmitted to the voter, but at the cost of creating a central point of attack for the system. [0051] It is always desirable to reduce the size of the data that must be sent to the voter via the independent channel. As described in section 3, the confirmation dictionary is already small by the standards of modem communications technology, but it may be cost advantageous if even less data can be transmitted. As mentioned above, one approach might be to send the secrets Ki and ßi directly to the voter, but this has the disadvantage of putting a computational burden on the voter that is too large to be executed "in the voter's head," or "on paper." The following variation on the SVC scheme achieves both goals -less data through the independent communication channel, and "mental computation" by the voter. It comes at a cost, namely that the probability that a client adversary may be able to fool the voter is increased, however, this may be quite acceptable from the overall election perspective. Even if the probability of the adversary going undetected is, say 1/2, in order for it to change a substantial fraction of votes, the probability that it will be detected by a statistically significant fraction of voters will be very high. As discussed in the introduction, remedial measures are possible. [0052] The idea is to deliver the entire set of confirmation strings to the voter via the suspect client, but in randomly permuted order. The only additional piece of information that the voter needs then is the permutation that was used. This isn't quite enough, in this scenario, since all the confirmation strings are available, the adversary can gain some advantage simply by process of elimination. (The case K=2 is particularly useful to consider.) In order to increase the security, we include with the dictionary, several random confirmation strings, that are also permuted. [0053] The steps in subsection 3.1 are executed as before. In addition, the vote collection sends to the client, Mi, a "randomized dictionary," Di. This is created by the vote collection center, C, as follows: RD-1. The K (voter specific) confirmation strings (Sa,...,Sik) = (H(Cn),...,H(CiK)) (23) are computed as before. RD-2. Additionally, L extra strings are generated as (Si(K+1),...,Si(K+L) = (H(gej),...,H(gel)) (24) where the el,...,eL are generated independently at random in Zq. RD-3. A random permutation,ΣI K+L is generated. RD-4. C sets Qij=Sioi(j), for l (2,1, -Qi(K+L))-[0054] If C sends some "human readable" representation of Σi to vi, through an independent channel, vi can now verify her vote by simply finding the confirmation string with the proper index. We denote this scheme by SVCO. [0055] With respect to the level of security of SVCO, consider the following form of the Diffie-Hellman Decision Problem: A is given a sequence of tuples, (Xn,Yn,Zn,Cn,Dn), where Xn,Yn,Zn are generated independently at random. Let Rn be generated independently at random, and let On be the solution to logXnOn=logXnYnlogXnZn. With probability 1/2, (Cn,Dn)=(0n,Rn), and with probability 1-1/2=1/2, (Cn,DtJ)=(Rn,0„). A is said to have an e- DDHP advantage if A can, with probability 1/2+e, answer the question logXnCn, = logXn Yn logXn Zn. That is, A must answer the same question as in the original version of the problem, but the problem may be easier because more information is available. [0056] Theorem 2 Let DDHP be an tipper bound on A's DDHP advantage, and H any hash function with negligible collision probability. An upper bound on the probability, under the SVCO scheme, that A can submit a vote that differs from the voter's choice, and yet display the correct confirmation string is [0057] Proof: As in the proof of theorem 1, A can simulate an election and SVCO exchange. In this case, however, A must also simulate the list of confirmation strings that were not available in the SVC scheme. For k1, k2 fixed, A can pick Ciki  at random, and for all k=k2, pick  k q independently at random. A then sets µK = X0k. For k=k1,k2, A sets Cjk = CikY . A setsµk2 =µxk1Z, and generatesL additional random µ1 and l-1 additional Cil at random. Finally, A sets Cik = CikCn, and the last remaining Cn = Cik1Dn. As before, finding the right confirmation string is equivalent to deciding which of the values, Cn, Dn is the correct Diffie-Hellman solution. Averaging over all permutations with uniform probability gives the result. [0058] Below is described one possible alternative to the secret vote confirmation scheme described above. The level of security between those two schemes is essentially equivalent. 1. In addition to the election public key, h, the vote collection publishes another public key of the form h-hd, where dZq is a secret known only to the vote collection center. 2. The client, Mi, submits a an encrypted ballot on behalf of vi- as before, but redundantly encrypted with both h and h. We denote the second encryption by (Xi Yi)=(gα1,hα1,m) (26) Where αi is selected independently of a.. 3. Mi also constructs a simple proof of validity (essentially a single Chaum-Pedersen proof) that the two are encryptions of the same value. 4. If the proof of validity does not pass at the vote collection center, corruption is detected as before. 5. The vote collection center selects random Ki;ßi Zq, and computes ( Equation Removed) 6. The vote collection center returns /zp' and vi$ toM{. 7. Micomputes Si=Kim(d+1)ßi by the equation ( Equation Removed) and displays this value (or, H(Si)) to the voter, Vi. 8. The voter requests a confirmation dictionary as before, and checks against the displayed value. [0059] In the case of detected corruption, corrective action is taken as before. [0060] The description of the facility)above describes using a single d (and therefore a single h=hd) for all voters and publishing this value in advance of the election. [0061] Alternatively, the vote collection center (or distributed set of "confirmation authorities") issues an independent, random dt (and therefore hi=hdi) for each voter, vi. The value dt is always kept secret, but the value hi is communicated to vi. [0062] In one embodiment, the facility communicates hi to vi as follows: A-l Vi contacts the vote collection center and authenticates himself/herself A-2 Assuming authentication is successful, the vote collection center: 1. Generates di randomly 2. Computes hi=hd1 3. Sends hi to vi. A-3 The voter, vf then proceeds as described above with hi in place of h [0063] In another embodiment, the facility communicates ht to vi$ as follows: B-l Vi contacts vote collection center (and optionally authenticates himself/herself) B-2 vi makes ballot choice mi , and returns the encrypted ballot (gα1,hα1mi) B-3 The vote collection center at this point: 1. Generates d{ randomly 2. Computes hi=hdi 3. Sends hi to vi. B-4 Voter, v; then 1. Generates second encryption of mt as (gα1,hα1mi) 2. Generates same proof of validity showing that first and second encryptions are encryptions of the same ballot choice, mt 3. Sends both the second encryption, and the proof of validity to the ballot collection agency B-5 The rest of the confirmation process proceeds as described above [0064] Figures 1-3 illustrate certain aspects of the facility. Figure 1 is a high-level block diagram showing a typical environment in which the facility operates. The block diagram shows several voter computer systems 110, each of which may be used by a voter to[Submit. P.S ballot and verify its uncorrupted receipt. Each of the voter computer systems are connected via the Internet 120 to a vote collection center computer system 150. Those skilled in the art will recognize that voter computer systems could be connected to the vote collection center computer system by networks other than the Internet, however. The facility transmits ballots from the voter computer systems to the vote collection center computer system, which returns an encrypted vote confirmation. In each voter computer system, the facility uses this encrypted vote confirmation to determine whether the submitted ballot has been corrupted. While preferred embodiments are described in terms in the environment described above, those skilled in the art will appreciate that the facility may be implemented in a variety of other environments including a single, monolithic computer system, as well as various other combinations of computer systems or similar devices connected in various ways. [0065] Figure 2 is a block diagram showing some of the components typically incorporated in at least some of the computer systems and other devices on which the facility executes, such as computer systems 110 and 130. These computer systems and devices 200 may include one or more central processing units ("CPUs") 201 for executing computer programs; a computer memory 202 for storing programs and data while they are being used; a persistent storage device 203, such as a hard drive for persistently storing programs and data; a computer-readable media drive 204, such as a CD-ROM drive, for reading programs and data stored on a computer-readable medium; and a network connection 205 for connecting the computer system to other computer systems, such as via the Internet. While computer systems configured as described above are preferably used to support the operation of the facility, those skilled in the art will appreciate that the facility may be implemented using devices of various types and configurations, and having various components. [0066] Figure 3 is a flow diagram showing steps typically performed define the facilities in order to detect a compromised ballot. Those skilled in the art will appreciate that the facility may perform a set of steps that diverges from those shown, including proper supersets and subsets of these steps, reorderings of these steps, and steps of sets in which performance of , certain steps by other computing devices. [0067] In step 301, on the voter computer system, the facility encodes a ballot choice selected by the voter in order to form a ballot. In step 302, tha facility encrypts this ballot. In some embodiments, the encrypted ballot is an ElGamal pair, generated using an election public key and a secret maintained on the voter computer system. In step 303, the, facility optionally signs the ballot with a private key belonging to the voter. In step 304, the facility constructs a validity proof that demonstrates that the encrypted ballot is the encryption of a ballot in which a valid ballot choice is selected. In step 305, the facility transmits the encrypted, signed ballot and the validity proof to a vote collection center computer system. [0068] In step 321, the facility receives this transmission in the vote collection center computer system. In step 322, the facility verifies the received validity proof. In step 323, if the validity proof is successfully verified, then the facility continues with 324, else the facility does not continue in step 324. In step 324, the facility generates an encrypted confirmation of the encrypted ballot. The facility does so without decrypting the ballot, which is typically not possible in the vote collection center computer system, where the secret used to encrypt the ballot is not available. In step 325, the facility transmits the encrypted confirmation 331 to the voter computer system. [0069] In step 341, the facility receives the encrypted vote confirmation in the voter computer system. In step 342, the facility uses the secret maintained on the voter computer system to decrypt the encrypted vote confirmation. In step 343, the facility displays the decrypted vote confirmation for viewing by the user. In step 344, if the displayed vote confirmation is translated to the ballot choice selected by the voter by a confirmation dictionary in the voter's possession, then the facility continues in step 345, else the facility continues in step 346. In step 345, the facility determines that the voter's ballot is not corrupted, whereas, in step 346, the facility determines that the voter's ballot is corrupted. In this event, embodiments of the facility assist the user in revoking and resubmitting the voter's ballot. [0070] It will be appreciated by those skilled in the art that the above-described facility may be straightforwardly adapted or extended in various ways. While the foregoing description makes reference to preferred embodiments, the scope of the invention is defined solely by the claims that follow and the elements recited therein. We claim: 1. A method in a data processing system for discerning corruption of an electronic ballot, comprising: - sending an encrypted ballot from a first computer system to a second computer system, the encrypted ballot reflecting a ballot choice selected by a voter; - sending a confirmation from the second computer system to the first computer system, the confirmation serving to convey the decrypted contents of the encrypted ballot as received at the second computer system, the confirmation being generated without decrypting the encrypted ballot; and - in the first computer system, displaying the confirmation, so that the voter can determine whether the decrypted contents of the encrypted ballot as received at the second computer system match the ballot choice selected by the voter. 2. The method as claimed in claim 1, further comprising sending from the first computer system to the second computer system a validity proof proving that the encrypted ballot sent from the first computer system to the second computer system reflects a valid ballot choice without identifying the reflected ballot choice. 3. The method as claimed in claim 2 wherein the confirmation is sent from the second computer system to the first computer system only if the validity proof sent from the first computer system to the second computer is verified to prove that the encrypted ballot sent from the first computer system to the second computer system reflects a valid ballot choice. 4. The method as claimed in claim 1, comprising the steps of: - receiving the electronic ballot, the electronic ballot containing an encrypted ballot choice; - determining that the received encrypted ballot choice is not accompanied by a valid validity proof that proves that the encrypted ballot choice constitutes the encryption of one of a plurality of permissible ballot choices; and - in response to so determining, determining that the generated first ballot has been compromised. 5. The method as claimed in claim 4 wherein no validity proof is received for the encrypted ballot choice. 6. The method as claimed in claim 4 wherein a validity proof is received along with the encrypted ballot choice, and the combination of validity proof and encrypted ballot fail a verification operation performed by the vote collection computer system, where the verification operation is constructed explicitly to determine whether the encrypted ballot is an encryption of at least one of the valid ballot responses. 7. A ballot collection computer system for detecting the compromise of an electronic ballot for use in the connection with the method as claimed in claim 1, the ballot collection computer system comprising: - means for receiving the electronic ballot, the electronic ballot containing an encrypted ballot choice; - means for determining that the received encrypted ballot choice is not accompanied by a valid validity proof that proves that the encrypted ballot choice constitutes the encryption of one of a plurality of permissible ballot choices; and - means for, in response to so determining, determining that the generated first ballot has been compromised. 8. The method as claimed in claim 1, further for confirming receipt of a ballot choice selected by a voter, the method further comprising: - receiving a first confirmation message from a first party, the content of the first confirmation message confirming the unencrypted value of an encrypted ballot choice received for the voter by a vote collection authority; and - receiving a second confirmation message from a second party that is independent of the first party, the content of the second confirmation message independently confirming the unencrypted value of the encrypted ballot choice received for the voter by the vote collection authority, wherein the encrypted ballot choice is not decryptable by the first party, the second party, or the vote collection authority. 9. The method as claimed in claim 8, comprising displaying the content of the first and second confirmation messages, such that both the displayed first confirmation message and the displayed second confirmation message may be compared by the voter to expected vote confirmation messages for the ballot choice selected by the voter to determine whether an encrypted version of a ballot choice other than the b allot c hoice s elected b y t he v oter h as been received for the voter by the vote collection authority. 10. The method as claimed in claim 8, further comprising: - combining the content of the first and second confirmation messages to obtain a combined confirmation message; and - displaying the combined confirmation message, such that the displayed combined confirmation message may be compared by the voter to an expected combined vote confirmation message for the ballot choice selected by the voter to determine whether an encrypted version of a ballot choice other than the ballot choice selected by the voter has been received for the voter by the vote collection authority. 1 1. The method as claimed in claim 10 wherein the combined confirmation message i s o btained u sing c oncatenating c ontent from each of the first and second confirmation messages. 12. The method as claimed in claim 10 wherein the combined confirmation message is obtained using a threshold secret reconstruction technique. The method as claimed in claim 8 wherein each of the first and second confirmation messages contains a first value and a second value, wherein the combined confirmation message is obtained by: - determining the product of the first values contained in the first and second confirmation messages; and - determining the product of the second values contained in the first and second confirmation messages. A computer memory device under the control of a voter containing a data structure for confirming receipt of a ballot choice selected by a voter for use in connection with the method as claimed in claim 1, the data structure comprising: - a first confirmation message received from a first party, the content of the first confirmation message confirming the unencrypted value of an encrypted ballot choice received for the voter by a vote collection authority; and - a s econd c onfirmation m essage r eceived from a s econd p arty that is independent of the first party, the content of the second confirmation message independently confirming the unencrypted value of the encrypted ballot choice received for the voter by the vote collection authority, wherein the encrypted ballot choice is not decryptable by the first party, the second party, or the vote collection authority. The method as claimed in claim 1, further for confirming receipt of a ballot choice selected by a voter, the method further comprising: - sending to a first recipient via a first communications channel a confirmation dictionary for a first voter containing a list of ballot choice confirmation messages ordered in a first order; and - sending to the first recipient via a second communications channel that is distinct from the first communications channel a confirmation dictionary guide for the first voter indicating, for each of a plurality of valid ballot choices, a position in the first order containing a ballot choice confirmation message corresponding to the valid ballot choice, such that the first recipient may use the identity of the ballot choice selected by the first voter together with the confirmation dictionary guide to identify in the confirmation dictionary the ballot choice confirmation message corresponding to the ballot choice selected by the voter. The method as claimed in claim 15, further comprising sending to a second recipient via the first communications channel a second confirmation dictionary for a second voter containing a list of ballot choice confirmation messages ordered in a second order, the second voter being distinct from the first voter, the second recipient being distinct from the first recipient, the second order being distinct from the first order. A computing system for confirming receipt of a ballot choice selected by a voter for use in the connection with the method as claimed in claim 1, the computing system comprising: - a first transmission system coupled to a first communications channel that sends to a recipient a confirmation dictionary containing a list of ballot choice confirmation messages ordered in a first order; and - a second transmission system coupled to a second communications channel that is distinct from the first communications channel that sends to the recipient a confirmation dictionary guide indicating, for each of a plurality of valid ballot choices, a position in the first order containing a ballot choice confirmation message corresponding to the valid ballot choice, such that the recipient may use the identity of the ballot choice selected by the voter together with the confirmation dictionary guide to identify in the confirmation dictionary the ballot choice confirmation message corresponding to the ballot choice selected by the voter. The computing system as claimed in claim 17 wherein the second transmission system sends the confirmation dictionary guide via a voice message. The computing system as claimed in claim 17 wherein the second transmission system sends the confirmation dictionary guide via a postal mail message. One or more generated data signals that collectively convey a randomized confirmation dictionary data structure for use in the connection with the method as claimed i n c laim 1, the randomized confirmation dictionary data structure comprising a sequence of ballot confirmation strings, a subset of the ballot confirmation strings each corresponding to a different valid ballot choice, the order in which the ballot strings occur in the sequence being randomly selected, such that it cannot be determined without a separate confirmation dictionary guide which of the ballot confirmation strings in the sequence correspond to which valid ballot choices. The method as claimed in claim 1, further comprising: - in the first computer system: - encrypting the ballot choice with a first secret known only to the first computer system to generate a first encrypted ballot component; - encrypting the ballot choice with a second secret known only to the first computer system, the second secret chosen independently of the first secret, to generate a second encrypted ballot component; - generating a proof demonstrating that the first and second encrypted ballot components are encrypted from the same ballot choice; and - sending the first and second ballot components and the proof to the second computer system; - in the second computer system: - determining whether the proof demonstrates that the first and second encrypted ballot components are encrypted from the same ballot choice; and - only if the proof demonstrates that the first and second encrypted ballot components are encrypted from the same ballot choice, accepting the ballot choice. 22.The method as claimed in claim 21 wherein the first encrypted ballot component i s g enerated by evaluating gα and hαm, where p is prime; gEZ, which has prime multiplicative order q, with the property that q is a multiplicity 1 divisor of P-1; hE (g); α E Zq is chosen randomly at the first computer system; and m is the ballot choice and wherein the second encrvpted ballot component is generated by evaluating the expressions gα and hαm, where hε(g); αεZq is chosen randomly and independently at the second computer system; and m is the ballot choice. 23.The method as claimed in claim 22, wherein a ballot confirmation is generated by evaluating the expression of the kind as herein described. 24. The method as claimed in claim 23 wherein the ballot confirmation is decrypted by evaluating the expression of the kind as herein described 25. One or more generated data signals together conveying an encrypted ballot data structure for use in connection with the method as claimed in claim 1, the data structure comprising: - a first encrypted ballot choice encrypted with a first secret known only to a client computer system to generate a first encrypted ballot component, - a second encrypted ballot choice encrypted with a second secret known only to the client computer system, the second secret chosen independently of the first secret, and a proof; and - such that the ballot represented by the encrypted ballot data structure may be counted only where the proof demonstrates that the first and second encrypted ballot choices are encryptions of the same ballot choice. The method as claimed in claim 1, comprising: - receiving from the first computer system: - a first encrypted ballot choice encrypted with a first secret known only to the first computer system to generate a first encrypted ballot component, - a second encrypted ballot choice encrypted with a second secret known only to the first computer system, the second secret chosen independently of the first secret, and - a proof; and - only where the proof demonstrates that the first and second encrypted ballot choices are encryptions of the same ballot choice, accepting the ballot choice. he method as claimed in claim 1, comprising: - in a voter computer system: - receiving a ballot choice selected by a voter from among a set of valid ballot choices; - encoding the received ballot choice in a ballot; - encrypting the ballot; - constructing a validity proof proving that the encrypted ballot corresponds to a valid ballot choice; - sending the encrypted ballot and the validity proof to a vote collection center computer system; - in the vote collection center computer system: - receiving the encrypted ballot and validity proof; - verifying the validity proof; - only if the validity proof is successfully verified: - without decrypting the encrypted ballot, generating an encrypted vote confirmation of the encrypted ballot; - sending the encrypted vote confirmation to the voter computer system; - in the voter computer system: - receiving the encrypted vote confirmation; - decrypting the encrypted vote confirmation to obtain a vote confirmation; - displaying the obtained vote confirmation; and - if a confirmation dictionary in the user's possession does not translate the displayed vote confirmation to the ballot choice selected by the voter, determining that the ballot has been corrupted. 28. The method as claimed in claim 27 wherein encrypting the ballot comprises generating an ElGamal pair representing the ballot. 29. The method as claimed in claim 27 wherein the vote collection center computer system sends the encrypted vote confirmation to the voter computer system via a first communication channel, further comprising, in the vote collection center computer system, sending the confirmation dictionary to the voter via a second communications channel distinct from the first communications channel. 30. The method as claimed in claim 29 wherein individual confirmation dictionaries are sent to each of a plurality of voters including the voter. 3 1. The method as claimed in claim 27, comprising applying a hash function to the decrypted vote confirmation before it is displayed, and wherein it is determined that the ballot has been corrupted if the confirmation dictionary in the user's possession does not translate the displayed hashed decrypted vote confirmation to the ballot choice selected by the voter. 32. The method as claimed in claim 1, comprising, in the first computer system: - using a secret maintained in the voting node to encrypt a ballot value selected by a voter; - sending the encrypted ballot value to the second computer system; - receiving, in response to sending the encrypted ballot, an encrypted vote confirmation; - using the secret maintained in the first computer system to decrypt the encrypted vote confirmation; and - displaying the decrypted vote confirmation, such that the displayed vote confirmation may be compared to an expected vote confirmation for the ballot value selected by the voter to determine whether the electronic ballot has been corrupted. The method as claimed in claim 32, comprising: before displaying the decrypted vote confirmation, using a hash function to transform the decrypted vote confirmation into a smaller hash output value. The method as claimed in claim 32 wherein encrypting the ballot value comprises generating an ElGamal pair representing the ballot value. The method as claimed in claim 34 wherein the ElGamal pair is generated by evaluating the expressions g" and hαm, where p is prime; gεZp, which has prime multiplicative order q, with the property that q is a multiplicity 1 divisor of/? - 1; hε(g); αεZq is chosen randomly at the voting node; and m is the ballot value. The method as claimed in claim 35 wherein the ElGamal pair is generated by evaluating the expressions αg and αh + m, where g and h are both elements of an elliptic curve group, e, of prime order q and αεZp is chosen randomly at the voting node, and m is the ballot value. 37. The method as claimed in claim 32 wherein applying the secret maintained in the voting node to determine whether the encrypted vote confirmation reflects receipt of the ballot value selected by the voter at the vote collection point comprises: - determining the ballot value corresponding to the encrypted ballot value received at the vote collection point by evaluating the expression W1/U1α1, where α1, is the secret maintained in the voting node, and i W1 and U1, together comprise the encrypted vote confirmation; and - comparing the determined ballot value to the ballot value selected by the voter. 3 8. The m ethod a s c laimed i n c laim 2 7 w herein t he v alidity p roof i s a non-interactive proof of validity. 39. One or more computer memories collectively containing a voter security data structure for use in the connection with the method as claimed in claim 1, the data structure containing one or more secrets usable both (a) to encrypt an encoded ballot for transmission to a ballot collection point, and (b) to decrypt an encrypted ballot confirmation received from the ballot collection point, which indicates the contents of the ballot as received at the ballot collection point. 40.One or more computer memories collectively containing a ballot data structure for use in the connection with the method as claimed in claim 1, the ballot data structure comprising: - an encrypted ballot choice formed by encrypting one of a plurality of valid ballot choices selected by a voter in a voter computer system; - a proof of validity that demonstrates that the encrypted ballot choice constitutes an encryption of one of the plurality of valid ballot choices without indicating which of the plurality of valid ballot choices the encrypted ballot choice constitutes an encryption of; and - an encrypted ballot confirmation generated in response to the receipt in a ballot collection center computer system of the encrypted ballot choice and proof of validity. 41. The computer memories as claimed in claim 40 wherein the encrypted ballot is an ElGamal pair. 42. The method as claimed in claim 1, comprising in the second computer system: - receiving an encrypted ballot value from the first computer system, the encrypted ballot value being encrypted from a ballot value based on a voter selection using a secret not available in the second computer system; - generating from the encrypted ballot value an encrypted secret value confirmation that indicates to those in possession of the secret used to encrypt the encrypted ballot value the ballot value to which the received encrypted ballot value corresponds; and - sending the encrypted secret value confirmation to the first computer system, such that the encrypted secret value confirmation may be used in the first computer system to determine if the encrypted ballot value received at the second computer s ystem c orresponds t o t he b allot s election made by the voter. 43. The method as claimed in claim 42 wherein the secret value confirmation is generated without decrypting the encrypted ballot value. 44. The method as claimed in claim 42 wherein the enci'ypted secret value confirmation is encrypted in such a manner that, in the first computer system, given the encrypted secret value confirmation corresponding to a selection other than the voter selection, it is intractable to generate a decrypted secret value confirmation corresponding to the voter selection. 45. One or more generated data signals collectively conveying a ballot response data structure for use in connection with the method as claimed in claim 1, the ballot response data structure containing an encrypted ballot confirmation generated in response to the receipt at a ballot collection point of a ballot cast by a voter, the encrypted ballot confirmation, when decrypted on behalf of the voter, indicating a voting selection made by the voter in the cast ballot as received at the ballot collection point. 46. The data signals as claimed in claim 45 wherein the ballot received at the ballot collection point is encrypted, and wherein the encrypted ballot confirmation is generated without decrypting the encrypted ballot. 47. The data signals as claimed in claim 45 wherein the encrypted ballot confirmation, when decrypted, yields a value that, if the ballot received at the ballot collection point is uncorrupted, matches a value listed in a confirmation dictionary for the voting selection made by the voter.

Full Text

RELATED APPLICATIONS
[ooo1] This application claims the benefit of U.S. Provisional Application No. 60/270,182
filed February 20, 2001, claims the benefit of U.S. Provisional Application No.
___________(patent counsel's docket number 32462-8006US02) filed February 11, 2002,
and is a continuation-in-part of each of U.S. Patent Application No. 09/534,836, filed March 24, 2000; U.S. Patent Application No. 09/535,927, filed March 24, 2000; and U.S. Patent Application No. 09/816,869 filed March 24, 2001. Each of these five applications is incorporated by reference in its entirety.
TECHNICAL FIELD
[0002] The present invention is directed to the fields of election automation and
cryptographic techniques therefor.
BACKGROUND
[0003] The problems of inaccuracy and inefficiency have long attended conventional,
manually-conducted elections. While it has been widely suggested that computers could be used to make elections more accurate and efficient, computers bring with them their own pitfalls. Since electronic data is so easily altered, many electronic voting systems are prone to several types of failures that are far less likely to occur with conventional voting systems.
[0004] One class of such failures relates to the uncertain integrity of the voter's computer,
or other computing device. In today's networked computing environment, it is extremely difficult to keep any machine safe from malicious software. Such software is often able to remain hidden on a computer for long periods of time before actually performing a malicious action. In the meantime, it may replicate itself to other computers on the network, or computers that have some minimal interaction with the network. It may even
be transferred to computers that are not networked by way of permanent media carried by users.
[0005] In the context of electronic secret ballot elections, this kind of malicious software is
especially dangerous, since even when its malicious action is triggered, it may go undetected, and hence left to disrupt more elections in the future. Controlled logic and accuracy tests ("L&A tests") monitor the processing of test ballots to determine whether a voting system is operating properly, and may be used in an attempt to detect malicious software present in a voter's computer. L&A tests are extremely difficult to conduct effectively, however, since it is possible that the malicious software may be able to differentiate between "real" and "test" ballots, and leave all "test" ballots unaffected. Since the requirement for ballot secrecy makes it impossible to inspect "real" ballots for compromise, even exhaustive L&A testing may prove futile. The problem of combating this threat is known as the "Client Trust Problem."
[0006] Most existing methods for solving the Client Trust Problem have focused on
methods to secure the voting platform, and thus provide certainty that the voter's computer is "clean," or "uninfected." Unfortunately, the expertise and ongoing diligent labor that is required to achieve an acceptable level of such certainty typically forces electronic voting systems into the controlled environment of the poll site, where the client computer systems can be maintained and monitored by computer and network experts. These poll site systems can still offer some advantages by way of ease of configuration, ease of use, efficiency of tabulation, and cost. However, this approach fails to deliver on the great potential for distributed communication that has been exploited in the world of e-commerce.
[0007] Accordingly, a solution to the Client Trust Problem that does not require the voting
platform to be secured against malicious software, which enables practically any computer system anywhere to be used as the voting platform, would have significant utility.
BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS
[0008] Figure 1 is a high-level block diagram showing a typical environment in which the
facility operates.

[0009] Figure 2 is a block diagram showing some of the components typically incorporated
in at least some of the computer systems and other devices on which the facility executes.
[0010] Figure 3 is a flow diagram showing steps typically performed by the facility in order
to detect a compromised ballot.
DETAILED DESCRIPTION . s A' ij
[0011] A P.S for detecting ballots compromised by malicious programs ("the
facility") is provided. The approach employed by the facility typically makes no attempt to eliminate, or prevent the existence of malicious software on the voting computer. Instead, it offers a cryptographically secure method for the voter to verify the contents of the voter's ballot as it is received at the vote collection center, without revealing information about the contents (ballot choices) to the collection center itself. That is, the vote collection center can confirm to the voter exactly what choices were received, without knowing what those choices are. Thus, the voter can detect any differences between the voter's intended choices, and the actual choices received at the vote collection center (as represented in the transmitted voted ballot digital data). Further, each election can choose from a flexible set of policy decisions allowing a voter to re-cast the voter's ballot in the case that the received choices differ from the intended choices.
[0012] The facility is described in the context of a fairly standard election setting. For ease
of presentation, initial discussion of the facility assumes that there is only one question on the ballot, and that there are a set of K allowable answers, al,...,aK (one of which may be "abstain"). It will be appreciated by those of ordinary skill in the art that it is a straightforward matter to generalize the solution given in this situation to handle the vast majority of real world ballot configurations.
[0013] Several typical cryptographic features of the election setting are:
1. Ballot Construction: A set of cryptographic election parameters are agreed upon by election officials in advance, and made publicly known by wide
publication or other such means. Significant parameters are the encryption

group, generator, election public key and decision encoding scheme. More specifically, these are:
(a) The encryption group, G may be Z with p a large prime, or an elliptic curve group.
(b) The generator, gsG. In the case G=Zp, g should generate a (multiplicative) subgroup, , of G* which has large prime order q. In the elliptic curve case we assume ~G and q=p.
(c) The election public key, he.
(d) The decision encoding scheme: A partition of into "answer representatives." That is, =S0US1U...SK where the Sk are pair wise disjoint subsets of . For each l [0014] While the following discussion uses multiplicative group notation for the sake of
consistency, it should be clear that all constructions can be implemented equally well using elliptic curves.
2. Vote Submission: Each voter, v,-, encrypts her vote, or decision, as an
ElGamal pair, (Xi,Yl) = (gα1,,hα',m1, where αiZq is chosen randomly by
the voter, and mt Sk if vi wishes to choose answer αk. This encrypted value is what is transmitted to the vote collection center (cast), usually with an attached digital signature created by vi,-. [0015] If the voter, vi were computing these values herself - say with pencil and paper -
this protocol would essentially suffice to implement a secret ballot, universally verifiable election system. (Depending on the tabulation method to be used, some additional information, such as a voter proof of validity would be necessary.) However, since in practice, vi only makes choices through some user interface, it is not realistic to expect her

to observe the actual value of the bits sent and check them for consistency with her intended choice. In short, the vote client can ignore voter intent and submit a "µj vote" when the voter actually wished to submit a "µk vote." [0016] The voter typically needs some way to verify that the encrypted vote which was
received at the vote collection center is consistent with her choice. Simply making the ballot box data public does not a reasonable solution, since the vote client, not the voter, chooses at. For reasons of vote secrecy, and coercion, this value should be "lost." So v{'s encrypted vote is as opaque to her as it is to anyone else. A generic confirmation from the vote collection center is obviously not sufficient either. The general properties of what is needed are properties:
1. The confirmation string, C, returned by the vote collection center, needs to be a function of the data (encrypted vote) received.
2. The voter and vote client should be able to execute a specific set of steps that allow the voter to tie C exclusively to the choice (or vote),µk, that was received.
3. It should be impossible for the vote client to behave in such a way that the voter "is fooled." That is, the client can not convince the voter that µk was received, when actually, µ=µk was received.
[0017] In this section, we present such a scheme, which we shall refer to as SVC, in its basic
form. In following sections, we offer some improvements and enhancements. [0018] The following steps are typically performed as part of the voting process.
CC-1. The vote client, Mi"operated by" vi, creates an encrypted ballot on behalf of v{ as before. Let us denote this by (Xi ,Yi) = (gα',hα'mi), for some value mi ) and
αtZq
CC-2. Mi is also required to construct a validity proof, Pt, which is a zeroknowledge proof that mi{µ1...,µk}. (Such a proof is easily constructed from the basic Chaum-Pederson proof for equality of discrete logarithms using the techniques of [CDS94]. See [CGS97] for a specific example.)
CC-3. Mi then submits both Pi and the (signed) encrypted vote, (Xt,Yi) to the vote
collection center.
CC-4. Before accepting the encrypted ballot, the vote collection center first checks the proof, Pi. If verification of Pi fails, corruption has already been detected, and the vote collection center can either issue no confirmation string, or some default random one.
CC-5. Assuming then that verification of Pi succeeds, the vote collection center computes the values, Wi and Ui as,
Wi = KiYißi=Kihα1ß1mißi (1)
Ui = hßi (2)
where KiG and ßiZq are generated randomly and independently (on a voter-by-voter basis).
CC-6. The vote collection center then returns (Ui,Wi) to Mi.
CC-7. The client, Mi, computes
C, = Vi/Uiαi = Kimißi (3)
and display this string (or, more likely, a hash of it, H(Ci)) to the voter, vi-.
[0019] The voter needs to know which confirmation string to look for. This can be
accomplished in two different ways. The most straightforward is to have the voter, vi$, obtain Ki and ßi from the vote collection center. This is workable, requires very little data to be transferred, and may be well suited to some implementations. However, in other situations, it may be an unattractive approach because Ci (or H(Ci) must then be computed. Since asking Mi to perform this computation would destroy the security of the scheme, vi$ must have access to an additional computing device, as well as access to the independent communication channel.
[0020] An alternative is to have the vote collection center compute all possible confirmation
strings for vi$, and send what amounts to a confirmation dictionary to vi$ via the independent channel. In general, the confirmation dictionary for voter vi$ would consist of the following table laid out in any reasonable format:

( Table Removed)
where H is the election's public (published) hash function (possibly the identity function), and Cij=Kiµjßi.
[0021] Of course care must be used in engineering the independent channel to be sure that
it really is independent. Ideally, it should be inaccessible to devices connected to the voting network. Solutions are available, however. Since the Ki and ßican be generated in advance of the election, even slow methods of delivery, such as surface mail, can be employed to transmit the dictionary.
[0022] In order to more completely describe the facility, an example illustrating the
operation of some of its embodiments is described. The following is a detailed example of a Secret Value Confirmation exchange.
[0023] In order to maximize the clarity of the example, several of the basic parameters used
- for example, the number of questions on the ballot, and the size of the cryptographic parameters - are much smaller than those that would be typically used in practice. Also, while aspects of the example exchange are discussed below in a particular order, those skilled in the art will recognize that they may be performed in a variety of other orders.
[0024] Some electronic election protocols include additional features, such as:
• voter and authority certificate (public key) information for authentication and audit
• ballot page style parameters
• data encoding standards

tabulation protocol and parameters
[0025] As these features are independent of the Secret Value Confirmation implementation,
a detailed description of them is not included in this example.
[0026] This example assumes an election protocol that encodes voter responses (answers)
as a single ElGamal pair. However, from the description found here, it is a trivial matter to also construct a Secret Value Confirmation exchange for other election protocols using ElGamal encryption for the voted ballot. For example, some embodiments of the facility incorporate the homomorphic election protocol described in U.S. Patent Application No. 09/535,927. In that protocol, a voter response, is represented by multiple ElGamal pairs. The confirmation dictionary used in this example is easily modified to either display a concatenation of the respective confirmation strings, or to display a hash of the sequence of them.
[0027] The jurisdiction must first agree on the election initialization data. This at least
includes: the basic cryptographic numerical parameters, a ballot (i.e., a set of questions and allowable answers, etc.) and a decision encoding scheme. (It may also include additional data relevant to the particular election protocol being used.)
Cryptographic Parameters
• Group Arithmetic: Integer multiplicative modular arithmetic
• Prime Modulus: p = 47
• Subgroup Modulus: q = 23
• Generator: g = 2
• Public Key: h = gs where s is secret. For the sake of this example, let us say that h = g12 =7.
Ballot
• One Question

• tabulation protocol and parameters
[0025] As these features are independent of the Secret Value Confirmation implementation,
a detailed description of them is not included in this example.
[0026] This example assumes an election protocol that encodes voter responses (answers)
as a single ElGamal pair. However, from the description found here, it is a trivial matter to also construct a Secret Value Confirmation exchange for other election protocols using ElGamal encryption for the voted ballot. For example, some embodiments of the facility incorporate the homomorphic election protocol described in U.S. Patent Application No. 09/535,927. In that protocol, a voter response, is represented by multiple ElGamal pairs. The confirmation dictionary used in this example is easily modified to either display a concatenation of the respective confirmation strings, or to display a hash of the sequence of them.
[0027] The jurisdiction must first agree on the election initialization data. This at least
includes: the basic cryptographic numerical parameters, a ballot (i.e., a set of questions and allowable answers, etc.) and a decision encoding scheme. (It may also include additional data relevant to the particular election protocol being used.)
Cryptographic Parameters
• Group Arithmetic: Integer multiplicative modular arithmetic
• Prime Modulus: p = 47
• Subgroup Modulus: q = 23
• Generator: g = 2
• Public Key: h = gs where s is secret. For the sake of this example, let us say that h = g12 =7.
Ballot
• One Question

• tabulation protocol and parameters
[0025] As these features are independent of the Secret Value Confirmation implementation,
a detailed description of them is not included in this example.
[0026] This example assumes an election protocol that encodes voter responses (answers)
as a single ElGamal pair. However, from the description found here, it is a trivial matter to also construct a Secret Value Confirmation exchange for other election protocols using ElGamal encryption for the voted ballot. For example, some embodiments of the facility incorporate the homomorphic election protocol described in U.S. Patent Application No. 09/535,927. In that protocol, a voter response, is represented by multiple ElGamal pairs. The confirmation dictionary used in this example is easily modified to either display a concatenation of the respective confirmation strings, or to display a hash of the sequence of them.
[0027] The jurisdiction must first agree on the election initialization data. This at least
includes: the basic cryptographic numerical parameters, a ballot (i.e., a set of questions and allowable answers, etc.) and a decision encoding scheme. (It may also include additional data relevant to the particular election protocol being used.)
Cryptographic Parameters
• Group Arithmetic: Integer multiplicative modular arithmetic
• Prime Modulus: p = 47
• Subgroup Modulus: q = 23
• Generator: g = 2
• Public Key: h = gs where s is secret. For the sake of this example, let us say that h = g12 =7.
Ballot
• One Question
3. (X, Y) = (2α,7α x36) i.e. choice (vote cast) is "Red"
4. (X, Y) = (2α,7αxl7) i.e. choice (vote cast) is "I abstain"
for some unspecified value of α without revealing which of them actually does hold. [0035] There are a variety of standard methods that can be used to accomplish this. See,
for example, R Cramer, I. Damgard, 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. The Secret Value Confirmation technique used by the facility works equally well with any method that satisfies the abstract criteria of the previous paragraph. While details of one such validity proof method are provided below, embodiments of the facility may use validity proofs of types other than this one.
Validity Proof Construction:
[0036] (In what follows, each action or computation which V is required to perform is
actually carried out by V 's computer.)
1. V sets α2= α = 5.
2. V generates Z23, r1,r2,r3,r4 Z23, sl,s3, s4 R Z23 all randomly and independently. For this example we take
2 = 4 (5)
r1=16, r3=17, r4 = 21
s1, =12, s3=4, s4=15
3. V computes corresponding values
ai=griXsi = 216x3211=4 (6)
a2=g = 24=16

a3=gr3X-s3 = 217x3219=6
a4=gr4X-4 = 221x328=9
b1 = hr1 (Y/9)-s1 = 716 x (24/9)11 = 18
b2 = h = 74=4
b3 = hr3 (Y/36)-s3 = 717 x (24/36)19 = 1
b4=hr'(Y/17)-S5 = 721x(24/17)8=7
(7)
4. V uses a publicly specified hash function H to compute c  Z23 as
c=H({X,Y,ai,bi}) l Since many choices of the hash function are possible, for this example we can just pick a random value, say
c = 19. (9)
(In practice, SHA1, or MD5, or other such standard secure hash function may be used to compute H.)
5. V computes the interpolating polynomial P(x) of degree 4 — 1 = 3. The defining properties of P are
P(0) = c=19 (10)
P(l) = s1=12
p(3) = S3=4 P(4) = S4=15
P(X.) =J=0Z jxicomputed using standard polynomial interpolation theory, to yield:
P(X) = X3+20X2+18X+19 (11)
or
z0=19 z,=18
z2 = 20 z3 = 1
(12)
6. V computes the values
s2=P(2) = 5 (13)
r2 =2 +α2 s2=4+5x5 = 6
V's validity proof consists of the 12 numbers
{αk ,bk ,rk}6 k= 1 (14)
and the three numbers
{Zk}3k=1 (15)
in precise sequence. (z0 need not be submitted since it is computable from the other data elements submitted using the public hash function H.)
[0037] Having computed the required choice encryption, (X, Y) and the corresponding
proof of validity, V encodes these elements, in sequence, as defined by the standard encoding format. The resulting sequences form V's voted ballot. (In order to make the ballot unalterable, and indisputable, V may also digitally sign this voted ballot with his private signing key. The resulting combination of V 's voted ballot, and his digital signature (more precisely, the standard encoding of these two elements) forms his signed voted ballot.) Finally, each voter transmits his (optionally signed) voted ballot back to the data center collecting the votes.
[0038] As described above, the voter specific random parameters for V (/? and Kj are
available at the vote collection center. In this example, these are
ß=18 K=37 (16)
[0039] When the voter's (optionally signed) voted ballot is received at the vote collection
center, the following steps are executed
1. The digital signature is checked to determine the authenticity of the ballot, as well as the eligibility of the voter.
2. If the signature in step 1 verifies correctly, the vote collection center then verifies the proof of validity. For the particular type of validity proof we have chosen to use in this example, this consists of
(a) The public hash function H is used to compute the value of
z0=P(0) = H({X,Y,ai,bi}4i=1) = 19 (17)
(Recall that the remaining coefficients of P, z1 ,z2 , z3 , are part of V 's (optionally signed) voted ballot submission.)
(b) For each 1 are evaluated. (Here, as described above, the µj are taken from the
Decision Encoding Scheme.) If equality fails in any of these, verification fails. This ballot is not accepted, and some arbitrary rejection string (indication) is sent back to V.
3. Assuming that the previous steps have passed successfully, the reply string
{W, U) is computed as
W = KYß =37x2418 =9 (19)
This sequenced pair is encoded as specified by the public encoding format, and returned to V.
A. V 's computer calculates
C = W/Uα = 9/(42)5 = 18 (20)
and displays this string to V. (Alternatively, the protocol may specify that a public hash function is computed on C and the resulting hash value displayed. In this example, C itself is displayed.) If V's computer attempted to submit a choice other than "Green," the value of C computed above would be different. Moreover, the correct value of C cannot be
computed from an incorrect one without solving the Diffie-Hellman problem. (For the small values of p and q we have used here, this is possible.
However, for "real" cryptographic parameters, V's computer would be unable to do this.) Thus, if V's computer has submitted an encrypted ballot which does not correspond to V's choice, there are only two things it can do at the point it is expected to display a confirmation. It can display something, or it can display nothing. In the case that nothing is displayed, V may take this as an indication that the ballot was corrupted. In the case that something is displayed, what is displayed will almost certainly be wrong, and again, V may take this as an indication that the ballot was corrupted.
5. V now compares the value of C displayed to the value found in V's
confirmation dictionary corresponding to the choice, "Green" (V's intended choice). At this point, V may have already received his confirmation dictionary in advance, or may obtain a copy through any independent channel. An example of such a channel would be to use a fax machine. If the displayed value does not match the corresponding confirmation string in

the confirmation dictionary, corruption is detected, and the ballot can be
"recast" in accordance with election-specific policy. [0040] Each voter confirmation dictionary is computed by the vote collection center, since,
as described above, it is the entity which has knowledge of the voter specific values of a and K. For the case of the voter, V, we have been considering, the dictionary is computed as

( Table Removed)

[0041] The level of security provided by the facility when using the SVC scheme is
described hereafter: Let A be the vote client adversary, and let 0 be an upper bound on the
probability that A is able to forge a validity proof for any given µ1,...,µK. (We know that e0
is negligible.)
[0042] Theorem 1 Suppose the SVC scheme is executed with H = Id Fix 1 0, A can, with probability e, submit bt = (ga',ha' ukt), and
display Cik2 = Kiµß1k2 , where the probability is taken uniformly over all combinations of
values for µ1,...,µK, g, h, ßiand Ki. Then A can solve a random instance of the Diffie-Hellman problem with probability e, and with 0(K) additional work. [0043] Proof: Supposed is givenX,Y,ZeR. A can simulate an election and SVC exchange by picking Cikg> and µkg> independently at random for all k=k2, setting h-X,h^ =Y and µk2 =µk1Z. The resulting distribution on the election parameters and Ciki is obviously
identical to the distribution that arises from real elections. With probability , A can display Ciki, so can compute
C = Cik2/Cik1 = (µk2/µk1)ß1 = Zß1 (20)
So logxC= ßilogliZ=logXYlogXZ, and C is the solution to the Diffie-Hellman problem instance posed by the triple (X,Y,Z). [0044] Corollary 1 Suppose again that the SVC scheme is executed with H - Id Fixl>k2>K. Suppose that for some > 0, A can, with probability ex, choose k1=k2, submit bs = (ga1, ha1µk1 ), and displays Cik2 = Ki µß1k2 where the probability is taken uniformly over all
combinations of values for µ1,...,µK, g, h,ßi and K i . Then A cart solve a random instance of the Diffie-Hellman problem with probability /(K-l), and with 0(K) additional work.
[0045] Proof: Follow the arguments of theorem 1, but compare to the problem of finding the
solution to at least one of K-\ independent Diffie-Hellman problems. [0046] Corollary 2 Let DH be an upper bound on the probability that A can solve a random
Diffie-Hellman instance. Then, in the case that H = Id, an upper bound on the probability
that A can submit a vote that differs from the voter's choice, and yet display the correct confirmation string is 0 +(K — 1)DH.
[0047] If the hash function H is non-trivial, we can not hope to make comparisons to the
computational Diffie-Hellman problem without considerable specific knowledge of the properties of H. Rather than consider the security of the scheme with specific choices of H, we assume only that H has negligible collision probability, and instead compare security with the Decision Diffie-Hellman Problem. The variant of this problem we consider is as follows. A is given a sequence of tuples, (Xn,Yn,Zn,Cn), where Xn,Yn,Zn are generated independently at random. With probability 1/2, C„ is the solution to the Diffie-Hellman instance, (Xn,Yn,Zn, and with probability 1-1/2=1/2, Cn is generated randomly and independently. A is said to have an e-DDH advantage if A can, with probability 1/2+ e,
7
answer the question logXnCn = logxn Yn logxn Zn. [0048] Theorem 1, and corollaries 1 and 2 have obvious analogs in the case H &Id
(assuming only that H has negligible collision probability). Both the statements and proofs are constructed with minor variation, so we only summarize with:
Corollary 3 Let DDH. be an upper bound on A's DDH advantage. Then, ifH is any hash
function with negligible collision probability, an upper bound on the probability that A can submit a vote that differs from the voter's choice, and yet display the correct confirmation
string is 0+(K-l)DDH.
[0049] SVC may not offer any protection if the adversary, A, also controls the vote
collection center. If this were the case, A has access to Ki and ßi, and thus can easily display any valid confirmation string of its choosing. It seems unlikely that this would happen, since the vote collection center would be undeniably implicated in the event that such activity is discovered. Nevertheless, in case it is unacceptable to trust the vote collection center in this regard, the "confirmation responsibility" can be distributed among arbitrarily many authorities.
[0050] To distribute the confirmation responsibility, each authority, Aj, l^j (for voter vi) independent random Kij and ßij. The authorities can combine these by two general methods.
1. Concatenation. The voter's confirmation string is computed as a concatenation, in pre-specified order, of the individual confirmation strings (computed separately as in the revious section) corresponding to each of the J authorities. In this case, confirmation is successful only if all of the substrings verify correctly.
2. Trusted Server or Printer. If it is acceptable to trust a single central server, or printer, the multiple confirmation strings can be combined into one of the same size by simply computing
(21)
(22)
This has the advantage of reducing the amount of confirmation data that must be
transmitted to the voter, but at the cost of creating a central point of attack for the
system.
[0051] It is always desirable to reduce the size of the data that must be sent to the voter via
the independent channel. As described in section 3, the confirmation dictionary is already
small by the standards of modem communications technology, but it may be cost

advantageous if even less data can be transmitted. As mentioned above, one approach might be to send the secrets Ki and ßi directly to the voter, but this has the disadvantage of putting a computational burden on the voter that is too large to be executed "in the voter's head," or "on paper." The following variation on the SVC scheme achieves both goals -less data through the independent communication channel, and "mental computation" by the voter. It comes at a cost, namely that the probability that a client adversary may be able to fool the voter is increased, however, this may be quite acceptable from the overall election perspective. Even if the probability of the adversary going undetected is, say 1/2, in order for it to change a substantial fraction of votes, the probability that it will be detected by a statistically significant fraction of voters will be very high. As discussed in the introduction, remedial measures are possible.
[0052] The idea is to deliver the entire set of confirmation strings to the voter via the
suspect client, but in randomly permuted order. The only additional piece of information that the voter needs then is the permutation that was used. This isn't quite enough, in this scenario, since all the confirmation strings are available, the adversary can gain some advantage simply by process of elimination. (The case K=2 is particularly useful to consider.) In order to increase the security, we include with the dictionary, several random confirmation strings, that are also permuted.
[0053] The steps in subsection 3.1 are executed as before. In addition, the vote collection
sends to the client, Mi, a "randomized dictionary," Di. This is created by the vote collection center, C, as follows:
RD-1. The K (voter specific) confirmation strings
(Sa,...,Sik) = (H(Cn),...,H(CiK)) (23)
are computed as before. RD-2. Additionally, L extra strings are generated as
(Si(K+1),...,Si(K+L) = (H(gej),...,H(gel)) (24)
where the el,...,eL are generated independently at random in Zq.

RD-3. A random permutation,ΣI K+L is generated.
RD-4. C sets Qij=Sioi(j), for l (2,1, -Qi(K+L))-[0054] If C sends some "human readable" representation of Σi to vi, through an independent
channel, vi can now verify her vote by simply finding the confirmation string with the proper
index. We denote this scheme by SVCO.
[0055] With respect to the level of security of SVCO, consider the following form of the
Diffie-Hellman Decision Problem: A is given a sequence of tuples, (Xn,Yn,Zn,Cn,Dn), where
Xn,Yn,Zn are generated independently at random. Let Rn be generated independently at
random, and let On be the solution to logXnOn=logXnYnlogXnZn. With probability 1/2,
(Cn,Dn)=(0n,Rn), and with probability 1-1/2=1/2, (Cn,DtJ)=(Rn,0„). A is said to have an e-
DDHP advantage if A can, with probability 1/2+e, answer the question logXnCn, = logXn Yn
logXn Zn. That is, A must answer the same question as in the original version of the
problem, but the problem may be easier because more information is available. [0056] Theorem 2 Let DDHP be an tipper bound on A's DDHP advantage, and H any hash
function with negligible collision probability. An upper bound on the probability, under the SVCO scheme, that A can submit a vote that differs from the voter's choice, and yet display the correct confirmation string is
[0057] Proof: As in the proof of theorem 1, A can simulate an election and SVCO exchange. In
this case, however, A must also simulate the list of confirmation strings that were not available in the SVC scheme. For k1, k2 fixed, A can pick Ciki  at random, and for all
k=k2, pick  k q independently at random. A then sets µK = X0k. For k=k1,k2, A sets
Cjk = CikY . A setsµk2 =µxk1Z, and generatesL additional random µ1 and l-1 additional Cil at random. Finally, A sets Cik = CikCn, and the last remaining Cn = Cik1Dn. As before,
finding the right confirmation string is equivalent to deciding which of the values, Cn, Dn is the correct Diffie-Hellman solution. Averaging over all permutations with uniform probability gives the result.

[0058] Below is described one possible alternative to the secret vote confirmation scheme
described above. The level of security between those two schemes is essentially equivalent.
1. In addition to the election public key, h, the vote collection publishes another public key of the form h-hd, where dZq is a secret known only to the vote collection center.
2. The client, Mi, submits a an encrypted ballot on behalf of vi- as before, but
redundantly encrypted with both h and h. We denote the second
encryption by
(Xi Yi)=(gα1,hα1,m) (26)
Where αi is selected independently of a..
3. Mi also constructs a simple proof of validity (essentially a single Chaum-Pedersen proof) that the two are encryptions of the same value.
4. If the proof of validity does not pass at the vote collection center, corruption is detected as before.
5. The vote collection center selects random Ki;ßi Zq, and computes
( Equation Removed)
6. The vote collection center returns /zp' and vi$ toM{.
7. Micomputes Si=Kim(d+1)ßi by the equation
( Equation Removed)

and displays this value (or, H(Si)) to the voter, Vi.

8. The voter requests a confirmation dictionary as before, and checks against
the displayed value. [0059] In the case of detected corruption, corrective action is taken as before.
[0060] The description of the facility)above describes using a single d (and therefore a
single h=hd) for all voters and publishing this value in advance of the election. [0061] Alternatively, the vote collection center (or distributed set of "confirmation
authorities") issues an independent, random dt (and therefore hi=hdi) for each voter, vi. The value dt is always kept secret, but the value hi is communicated to vi. [0062] In one embodiment, the facility communicates hi to vi as follows:
A-l Vi contacts the vote collection center and authenticates himself/herself A-2 Assuming authentication is successful, the vote collection center:
1. Generates di randomly
2. Computes hi=hd1
3. Sends hi to vi.
A-3 The voter, vf then proceeds as described above with hi in place of h [0063] In another embodiment, the facility communicates ht to vi$ as follows:
B-l Vi contacts vote collection center (and optionally authenticates
himself/herself) B-2 vi makes ballot choice mi , and returns the encrypted ballot (gα1,hα1mi) B-3 The vote collection center at this point:
1. Generates d{ randomly
2. Computes hi=hdi
3. Sends hi to vi. B-4 Voter, v; then
1. Generates second encryption of mt as (gα1,hα1mi)
2. Generates same proof of validity showing that first and second encryptions are encryptions of the same ballot choice, mt
3. Sends both the second encryption, and the proof of validity to the ballot collection agency
B-5 The rest of the confirmation process proceeds as described above
[0064] Figures 1-3 illustrate certain aspects of the facility. Figure 1 is a high-level block
diagram showing a typical environment in which the facility operates. The block diagram
shows several voter computer systems 110, each of which may be used by a voter to[Submit.
P.S ballot and verify its uncorrupted receipt. Each of the voter computer systems are
connected via the Internet 120 to a vote collection center computer system 150. Those
skilled in the art will recognize that voter computer systems could be connected to the vote
collection center computer system by networks other than the Internet, however. The
facility transmits ballots from the voter computer systems to the vote collection center
computer system, which returns an encrypted vote confirmation. In each voter computer
system, the facility uses this encrypted vote confirmation to determine whether the
submitted ballot has been corrupted. While preferred embodiments are described in terms in
the environment described above, those skilled in the art will appreciate that the facility may
be implemented in a variety of other environments including a single, monolithic computer
system, as well as various other combinations of computer systems or similar devices
connected in various ways. [0065] Figure 2 is a block diagram showing some of the components typically incorporated
in at least some of the computer systems and other devices on which the facility executes, such as computer systems 110 and 130. These computer systems and devices 200 may include one or more central processing units ("CPUs") 201 for executing computer programs; a computer memory 202 for storing programs and data while they are being used; a persistent storage device 203, such as a hard drive for persistently storing programs and data; a computer-readable media drive 204, such as a CD-ROM drive, for reading programs and data stored on a computer-readable medium; and a network connection 205 for connecting the computer system to other computer systems, such as via the Internet. While computer systems configured as described above are preferably used to support the operation of the facility, those skilled in the art will appreciate that the facility may be implemented using devices of various types and configurations, and having various components.
[0066] Figure 3 is a flow diagram showing steps typically performed define the facilities in order
to detect a compromised ballot. Those skilled in the art will appreciate that the facility may

perform a set of steps that diverges from those shown, including proper supersets and subsets of these steps, reorderings of these steps, and steps of sets in which performance of , certain steps by other computing devices.
[0067] In step 301, on the voter computer system, the facility encodes a ballot choice
selected by the voter in order to form a ballot. In step 302, tha facility encrypts this ballot. In some embodiments, the encrypted ballot is an ElGamal pair, generated using an election public key and a secret maintained on the voter computer system. In step 303, the, facility optionally signs the ballot with a private key belonging to the voter. In step 304, the facility constructs a validity proof that demonstrates that the encrypted ballot is the encryption of a ballot in which a valid ballot choice is selected. In step 305, the facility transmits the encrypted, signed ballot and the validity proof to a vote collection center computer system. [0068] In step 321, the facility receives this transmission in the vote collection center
computer system. In step 322, the facility verifies the received validity proof. In step 323, if the validity proof is successfully verified, then the facility continues with 324, else the facility does not continue in step 324. In step 324, the facility generates an encrypted confirmation of the encrypted ballot. The facility does so without decrypting the ballot, which is typically not possible in the vote collection center computer system, where the secret used to encrypt the ballot is not available. In step 325, the facility transmits the encrypted confirmation 331 to the voter computer system. [0069] In step 341, the facility receives the encrypted vote confirmation in the voter
computer system. In step 342, the facility uses the secret maintained on the voter computer system to decrypt the encrypted vote confirmation. In step 343, the facility displays the decrypted vote confirmation for viewing by the user. In step 344, if the displayed vote confirmation is translated to the ballot choice selected by the voter by a confirmation dictionary in the voter's possession, then the facility continues in step 345, else the facility continues in step 346. In step 345, the facility determines that the voter's ballot is not corrupted, whereas, in step 346, the facility determines that the voter's ballot is corrupted. In this event, embodiments of the facility assist the user in revoking and resubmitting the voter's ballot.

[0070] It will be appreciated by those skilled in the art that the above-described facility may
be straightforwardly adapted or extended in various ways. While the foregoing description makes reference to preferred embodiments, the scope of the invention is defined solely by the claims that follow and the elements recited therein.

We claim:
1. A method in a data processing system for discerning corruption of an
electronic ballot, comprising:
- sending an encrypted ballot from a first computer system to a second computer system, the encrypted ballot reflecting a ballot choice selected by a voter;
- sending a confirmation from the second computer system to the first computer system, the confirmation serving to convey the decrypted contents of the encrypted ballot as received at the second computer system, the confirmation being generated without decrypting the encrypted ballot; and
- in the first computer system, displaying the confirmation, so that the voter can determine whether the decrypted contents of the encrypted ballot as received at the second computer system match the ballot choice selected by the voter.

2. The method as claimed in claim 1, further comprising sending from the first computer system to the second computer system a validity proof proving that the encrypted ballot sent from the first computer system to the second computer system reflects a valid ballot choice without identifying the reflected ballot choice.
3. The method as claimed in claim 2 wherein the confirmation is sent from the second computer system to the first computer system only if the validity proof sent from the first computer system to the second computer is verified to prove that the encrypted ballot sent from the

first computer system to the second computer system reflects a valid ballot choice.
4. The method as claimed in claim 1, comprising the steps of:
- receiving the electronic ballot, the electronic ballot containing an encrypted ballot choice;
- determining that the received encrypted ballot choice is not accompanied by a valid validity proof that proves that the encrypted ballot choice constitutes the encryption of one of a plurality of permissible ballot choices; and
- in response to so determining, determining that the generated first ballot has been compromised.
5. The method as claimed in claim 4 wherein no validity proof is
received for the encrypted ballot choice.
6. The method as claimed in claim 4 wherein a validity proof is received along with the encrypted ballot choice, and the combination of validity proof and encrypted ballot fail a verification operation performed by the vote collection computer system, where the verification operation is constructed explicitly to determine whether the encrypted ballot is an encryption of at least one of the valid ballot responses.
7. A ballot collection computer system for detecting the compromise of
an electronic ballot for use in the connection with the method as
claimed in claim 1, the ballot collection computer system comprising:
- means for receiving the electronic ballot, the electronic ballot containing an encrypted ballot choice;
- means for determining that the received encrypted ballot choice is not accompanied by a valid validity proof that proves that the encrypted ballot choice constitutes the encryption of one of a plurality of permissible ballot choices; and
- means for, in response to so determining, determining that the generated first ballot has been compromised.
8. The method as claimed in claim 1, further for confirming receipt of a
ballot choice selected by a voter, the method further comprising:
- receiving a first confirmation message from a first party, the
content of the first confirmation message confirming the
unencrypted value of an encrypted ballot choice received for
the voter by a vote collection authority; and
- receiving a second confirmation message from a second party
that is independent of the first party, the content of the second
confirmation message independently confirming the
unencrypted value of the encrypted ballot choice received for
the voter by the vote collection authority, wherein the encrypted
ballot choice is not decryptable by the first party, the second
party, or the vote collection authority.
9. The method as claimed in claim 8, comprising displaying the content of the first and second confirmation messages,
such that both the displayed first confirmation message and the displayed second confirmation message may be compared by the voter to expected vote confirmation messages for the ballot choice selected by the voter to determine whether an encrypted version of a ballot choice other than the b allot c hoice s elected b y t he v oter h as been received for the voter by the vote collection authority.
10. The method as claimed in claim 8, further comprising:
- combining the content of the first and second confirmation messages to obtain a combined confirmation message; and
- displaying the combined confirmation message,
such that the displayed combined confirmation message may be compared by the voter to an expected combined vote confirmation message for the ballot choice selected by the voter to determine whether an encrypted version of a ballot choice other than the ballot choice selected by the voter has been received for the voter by the vote collection authority.
1 1. The method as claimed in claim 10 wherein the combined confirmation message i s o btained u sing c oncatenating c ontent from each of the first and second confirmation messages.
12. The method as claimed in claim 10 wherein the combined confirmation message is obtained using a threshold secret reconstruction technique.
The method as claimed in claim 8 wherein each of the first and second confirmation messages contains a first value and a second value, wherein the combined confirmation message is obtained by:
- determining the product of the first values contained in the first and second confirmation messages; and
- determining the product of the second values contained in the first and second confirmation messages.
A computer memory device under the control of a voter containing a data structure for confirming receipt of a ballot choice selected by a voter for use in connection with the method as claimed in claim 1, the data structure comprising:
- a first confirmation message received from a first party, the content of the first confirmation message confirming the unencrypted value of an encrypted ballot choice received for the voter by a vote collection authority; and
- a s econd c onfirmation m essage r eceived from a s econd p arty that is independent of the first party, the content of the second confirmation message independently confirming the unencrypted value of the encrypted ballot choice received for the voter by the vote collection authority, wherein the encrypted ballot choice is not decryptable by the first party, the second party, or the vote collection authority.

The method as claimed in claim 1, further for confirming receipt of a ballot choice selected by a voter, the method further comprising:
- sending to a first recipient via a first communications channel a confirmation dictionary for a first voter containing a list of ballot choice confirmation messages ordered in a first order; and
- sending to the first recipient via a second communications channel that is distinct from the first communications channel a confirmation dictionary guide for the first voter indicating, for each of a plurality of valid ballot choices, a position in the first order containing a ballot choice confirmation message corresponding to the valid ballot choice,
such that the first recipient may use the identity of the ballot choice selected by the first voter together with the confirmation dictionary guide to identify in the confirmation dictionary the ballot choice confirmation message corresponding to the ballot choice selected by the voter.
The method as claimed in claim 15, further comprising sending to a second recipient via the first communications channel a second confirmation dictionary for a second voter containing a list of ballot choice confirmation messages ordered in a second order, the second voter being distinct from the first voter, the second recipient being distinct from the first recipient, the second order being distinct from the first order.
A computing system for confirming receipt of a ballot choice selected by a voter for use in the connection with the method as claimed in claim 1, the computing system comprising:
- a first transmission system coupled to a first communications channel that sends to a recipient a confirmation dictionary containing a list of ballot choice confirmation messages ordered in a first order; and
- a second transmission system coupled to a second communications channel that is distinct from the first communications channel that sends to the recipient a confirmation dictionary guide indicating, for each of a plurality of valid ballot choices, a position in the first order containing a ballot choice confirmation message corresponding to the valid ballot choice,
such that the recipient may use the identity of the ballot choice selected by the voter together with the confirmation dictionary guide to identify in the confirmation dictionary the ballot choice confirmation message corresponding to the ballot choice selected by the voter.
The computing system as claimed in claim 17 wherein the second transmission system sends the confirmation dictionary guide via a voice message.
The computing system as claimed in claim 17 wherein the second transmission system sends the confirmation dictionary guide via a postal mail message.
One or more generated data signals that collectively convey a randomized confirmation dictionary data structure for use in the connection with the method as claimed i n c laim 1, the randomized confirmation dictionary data structure comprising a sequence of ballot confirmation strings, a subset of the ballot confirmation strings each corresponding to a different valid ballot choice, the order in which the ballot strings occur in the sequence being randomly selected, such that it cannot be determined without a separate confirmation dictionary guide which of the ballot confirmation strings in the sequence correspond to which valid ballot choices.
The method as claimed in claim 1, further comprising:
- in the first computer system:
- encrypting the ballot choice with a first secret known only to the first computer system to generate a first encrypted ballot component;
- encrypting the ballot choice with a second secret known only to the first computer system, the second secret chosen independently of the first secret, to generate a second encrypted ballot component;
- generating a proof demonstrating that the first and second encrypted ballot components are encrypted from the same ballot choice; and
- sending the first and second ballot components and the proof to the second computer system;
- in the second computer system:
- determining whether the proof demonstrates that the first and second encrypted ballot components are encrypted from the same ballot choice; and
- only if the proof demonstrates that the first and second encrypted ballot components are encrypted from the same ballot choice, accepting the ballot choice.
22.The method as claimed in claim 21 wherein the first encrypted ballot component i s g enerated by evaluating gα and hαm, where p is prime; gEZ, which has prime multiplicative order q, with the property that q is a multiplicity 1 divisor of P-1; hE (g); α E Zq is chosen randomly at the
first computer system; and m is the ballot choice and wherein the second encrvpted ballot component is generated by evaluating the expressions gα and hαm, where hε(g); αεZq is chosen randomly and
independently at the second computer system; and m is the ballot choice.
23.The method as claimed in claim 22, wherein a ballot confirmation is generated by evaluating the expression of the kind as herein described.
24. The method as claimed in claim 23 wherein the ballot confirmation is decrypted by evaluating the expression of the kind as herein described
25. One or more generated data signals together conveying an encrypted ballot data structure for use in connection with the method as claimed in claim 1, the data structure comprising:
- a first encrypted ballot choice encrypted with a first secret known only to a client computer system to generate a first encrypted ballot component,
- a second encrypted ballot choice encrypted with a second secret known only to the client computer system, the second secret chosen independently of the first secret, and
a proof; and
- such that the ballot represented by the encrypted ballot data
structure may be counted only where the proof demonstrates
that the first and second encrypted ballot choices are
encryptions of the same ballot choice.
The method as claimed in claim 1, comprising:
- receiving from the first computer system:
- a first encrypted ballot choice encrypted with a first secret known only to the first computer system to generate a first encrypted ballot component,

- a second encrypted ballot choice encrypted with a second secret known only to the first computer system, the second secret chosen independently of the first secret, and
- a proof; and
- only where the proof demonstrates that the first and second encrypted ballot choices are encryptions of the same ballot choice, accepting the ballot choice.
he method as claimed in claim 1, comprising:
- in a voter computer system:
- receiving a ballot choice selected by a voter from among a set of valid ballot choices;
- encoding the received ballot choice in a ballot;
- encrypting the ballot;
- constructing a validity proof proving that the encrypted ballot corresponds to a valid ballot choice;
- sending the encrypted ballot and the validity proof to a vote collection center computer system;
- in the vote collection center computer system:
- receiving the encrypted ballot and validity proof;
- verifying the validity proof;
- only if the validity proof is successfully verified:
- without decrypting the encrypted ballot, generating an encrypted vote confirmation of the encrypted ballot;
- sending the encrypted vote confirmation to the voter computer system;

- in the voter computer system:
- receiving the encrypted vote confirmation;
- decrypting the encrypted vote confirmation to obtain a vote confirmation;
- displaying the obtained vote confirmation; and
- if a confirmation dictionary in the user's possession does not translate the displayed vote confirmation to the ballot choice selected by the voter, determining that the ballot has been corrupted.
28. The method as claimed in claim 27 wherein encrypting the ballot comprises generating an ElGamal pair representing the ballot.
29. The method as claimed in claim 27 wherein the vote collection center computer system sends the encrypted vote confirmation to the voter computer system via a first communication channel, further comprising, in the vote collection center computer system, sending the confirmation dictionary to the voter via a second communications channel distinct from the first communications channel.
30. The method as claimed in claim 29 wherein individual confirmation dictionaries are sent to each of a plurality of voters including the voter.
3 1. The method as claimed in claim 27, comprising applying a hash function to the decrypted vote confirmation before it is displayed, and wherein it is determined that the ballot has been corrupted if the confirmation dictionary in the user's possession does not translate the displayed hashed decrypted vote confirmation to the ballot choice selected by the voter.
32. The method as claimed in claim 1, comprising, in the first computer system:
- using a secret maintained in the voting node to encrypt a ballot value selected by a voter;
- sending the encrypted ballot value to the second computer system;
- receiving, in response to sending the encrypted ballot, an encrypted vote confirmation;
- using the secret maintained in the first computer system to decrypt the encrypted vote confirmation; and
- displaying the decrypted vote confirmation,
such that the displayed vote confirmation may be compared to an expected vote confirmation for the ballot value selected by the voter to determine whether the electronic ballot has been corrupted.
The method as claimed in claim 32, comprising: before displaying the decrypted vote confirmation, using a hash function to transform the decrypted vote confirmation into a smaller hash output value.
The method as claimed in claim 32 wherein encrypting the ballot value comprises generating an ElGamal pair representing the ballot value.
The method as claimed in claim 34 wherein the ElGamal pair is generated by evaluating the expressions g" and hαm, where p is prime; gεZp, which has prime multiplicative order q, with the property that q is a multiplicity 1 divisor of/? - 1; hε(g); αεZq is chosen randomly at the voting node; and m is the ballot value.
The method as claimed in claim 35 wherein the ElGamal pair is generated by evaluating the expressions αg and αh + m, where g and h
are both elements of an elliptic curve group, e, of prime order q and αεZp is chosen randomly at the voting node, and m is the ballot value.
37. The method as claimed in claim 32 wherein applying the secret maintained in the voting node to determine whether the encrypted vote confirmation reflects receipt of the ballot value selected by the voter at the vote collection point comprises:
- determining the ballot value corresponding to the encrypted ballot value received at the vote collection point by evaluating the expression W1/U1α1, where α1, is the secret maintained in the voting node, and i W1 and U1, together comprise the encrypted vote confirmation; and
- comparing the determined ballot value to the ballot value selected by the voter.
3 8. The m ethod a s c laimed i n c laim 2 7 w herein t he v alidity p roof i s a non-interactive proof of validity.
39. One or more computer memories collectively containing a voter security data structure for use in the connection with the method as claimed in claim 1, the data structure containing one or more secrets usable both (a) to encrypt an encoded ballot for transmission to a ballot collection point, and (b) to decrypt an encrypted ballot confirmation received from the ballot collection point, which indicates the contents of the ballot as received at the ballot collection point.
40.One or more computer memories collectively containing a ballot data structure for use in the connection with the method as claimed in claim 1, the ballot data structure comprising:
- an encrypted ballot choice formed by encrypting one of a plurality of valid ballot choices selected by a voter in a voter computer system;
- a proof of validity that demonstrates that the encrypted ballot choice constitutes an encryption of one of the plurality of valid ballot choices without indicating which of the plurality of valid ballot choices the encrypted ballot choice constitutes an encryption of; and
- an encrypted ballot confirmation generated in response to the receipt in a ballot collection center computer system of the encrypted ballot choice and proof of validity.

41. The computer memories as claimed in claim 40 wherein the encrypted ballot is an ElGamal pair.
42. The method as claimed in claim 1, comprising in the second computer system:

- receiving an encrypted ballot value from the first computer system, the encrypted ballot value being encrypted from a ballot value based on a voter selection using a secret not available in the second computer system;
- generating from the encrypted ballot value an encrypted secret value confirmation that indicates to those in possession of the
secret used to encrypt the encrypted ballot value the ballot value to which the received encrypted ballot value corresponds; and - sending the encrypted secret value confirmation to the first computer system, such that the encrypted secret value confirmation may be used in the first computer system to determine if the encrypted ballot value received at the second computer s ystem c orresponds t o t he b allot s election made by the voter.
43. The method as claimed in claim 42 wherein the secret value confirmation is generated without decrypting the encrypted ballot value.
44. The method as claimed in claim 42 wherein the enci'ypted secret value confirmation is encrypted in such a manner that, in the first computer system, given the encrypted secret value confirmation corresponding to a selection other than the voter selection, it is intractable to generate a decrypted secret value confirmation corresponding to the voter selection.
45. One or more generated data signals collectively conveying a ballot
response data structure for use in connection with the method as
claimed in claim 1, the ballot response data structure containing an
encrypted ballot confirmation generated in response to the receipt at a
ballot collection point of a ballot cast by a voter, the encrypted ballot
confirmation, when decrypted on behalf of the voter, indicating a
voting selection made by the voter in the cast ballot as received at the ballot collection point.
46. The data signals as claimed in claim 45 wherein the ballot received at
the ballot collection point is encrypted, and wherein the encrypted ballot
confirmation is generated without decrypting the encrypted ballot.
47. The data signals as claimed in claim 45 wherein the encrypted ballot
confirmation, when decrypted, yields a value that, if the ballot
received at the ballot collection point is uncorrupted, matches a value
listed in a confirmation dictionary for the voting selection made by the
voter.

Documents:

01361-delnp-2003-abstract.pdf

01361-delnp-2003-assignment.pdf

01361-delnp-2003-claims.pdf

01361-delnp-2003-complete specification granted.pdf

01361-delnp-2003-correspondence-others.pdf

01361-delnp-2003-correspondence-po.pdf

01361-delnp-2003-decsription (complete).pdf

01361-delnp-2003-drawings.pdf

01361-delnp-2003-form-1.pdf

01361-delnp-2003-form-13.pdf

01361-delnp-2003-form-19.pdf

01361-delnp-2003-form-2.pdf

01361-DELNP-2003-Form-3.pdf

01361-delnp-2003-form-5.pdf

01361-delnp-2003-gpa.pdf

01361-delnp-2003-pct-210.pdf

01361-delnp-2003-pct-304.pdf

01361-delnp-2003-petition-137.pdf

01361-delnp-2003-petition-138.pdf

« Previous Patent

Next Patent »

Patent Number

199740

Indian Patent Application Number

01361/DELNP/2003

PG Journal Number

36/2008

Publication Date

05-Sep-2008

Grant Date

22-Dec-2006

Date of Filing

26-Aug-2003

Name of Patentee

Dategrity Corporation

Applicant Address

155 108TH AVENUE NORTHEAST, SUITE 425, BELLEVEUE, WASHINGTON, 98004, USA

Inventors:

#	Inventor's Name	Inventor's Address
1	Andrew Charles Neff	3048-164th Place N.E., Bellevue, WA 98008

PCT International Classification Number

H041, 9/00

PCT International Application Number

PCT/US02/0569

PCT International Filing date

2002-02-20

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1	60/270,182	2001-02-20	U.S.A.
2	09/816, 869	2001-03-24	U.S.A.
3	60/355,857	2002-02-11	U.S.A.