Detecting compromised ballots

Abstract

A facility for discerning corruption of an electronic ballot is described. The facility sends from a first computer system to a second computer system an encrypted ballot that reflects a ballot choice selected by a voter. The facility then sends a confirmation from the second computer system to the first computer system, which serves to convey the decrypted contents of the encrypted ballot as received at the second computer system, and which is generated without decrypting the encrypted ballot. In the first computer system, the facility uses the confirmation to determine whether the decrypted contents of the encrypted ballot as received at the second computer system match the ballot choice selected by the voter.

1 . A method in a data processing system for discerning corruption of an electronic ballot, 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. 
   
   
   
       2 . The method of  claim 1  wherein the encoding comprises selecting a value having a predetermined correspondence to the selected ballot choice. 
   
   
       3 . The method of  claim 1  wherein the encrypting is performed using an election public key. 
   
   
       4 . The method of  claim 1  wherein encrypting the ballot comprises generating an ElGamal pair representing the ballot. 
   
   
       5 . The method of  claim 1 , further comprising signing the encrypted ballot with a private key of the voter before sending the encrypted ballot to the vote collection center computer system. 
   
   
       6 . The method of  claim 1  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. 
   
   
       7 . The method of  claim 6  wherein the confirmation dictionary is sent in response to a request from the voter. 
   
   
       8 . The method of  claim 7  wherein the request includes one or more identifiers associated with the voter. 
   
   
       9 . The method of  claim 6  wherein the confirmation dictionary is sent without being requested by the voter. 
   
   
       10 . The method of  claim 6  wherein individual confirmation dictionaries are sent to each of a plurality of voters including the voter. 
   
   
       11 . The method of  claim 1 , further 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. 
   
   
       12 . A computer-readable medium whose content cause a data processing system to discern corruption of an electronic ballot b y :
 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; 
 displaying the decrypted vote confirmation; and 
 if a confirmation dictionary in the user's possession does not translate the displayed decrypted vote confirmation to the ballot choice selected by the voter, determining that the ballot has been corrupted. 
   
   
   
       13 . A method in a data processing system for discerning corruption of an electronic ballot, comprising, in a voting node:
 using a secret maintained in the voting node to encrypt a ballot value selected by a voter;   sending the encrypted ballot value to a vote collection point;   receiving, in response to sending the encrypted ballot, an encrypted vote confirmation;   using the secret maintained in the voting node 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. 
   
   
       14 . The method of  claim 13 , further comprising:
 before displaying the decrypted vote confirmation, using a hash function to transform the decrypted vote confirmation into a smaller hash output value.   
   
   
       15 . The method of  claim 13  wherein encrypting the ballot value comprises generating an ElGamal pair representing the ballot value. 
   
   
       16 . The method of  claim 15  wherein the ElGamal pair is generated by evaluating the expressions g α  and h α m, where p is prime; gεZ p , which has prime multiplicative order q, with the property that q is a multiplicity 1 divisor of p−1; hε g ; αεZ q  is chosen randomly at the voting node; and m is the ballot value. 
   
   
       17 . The method of  claim 15  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, ε, of prime order q and αεZ q  is chosen randomly at the voting node, and m is the ballot value. 
   
   
       18 . The method of  claim 13  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 W i /U i   α     i   , where α i  is the secret maintained in the voting node, and W i  and U i  together comprise the encrypted vote confirmation; and   comparing the determined ballot value to the ballot value selected by the voter.   
   
   
       19 . The method of  claim 13 , further comprising sending to the vote collection point a validity proof proving that the encrypted ballot value corresponds to a valid ballot value. 
   
   
       20 . The method of  claim 19  wherein the validity proof is a non-interactive proof of validity. 
   
   
       21 - 50 . (canceled)