🚀 go-pugleaf

A recent newswire article about suggestions to allow telephone voting
got me thinking about the possibility of running a cryptographically
secure presidential election via email.  I claim that the problem is
very similar to the problem of untraceable electronic cash, and that
with a little work, we could concoct a secure protocol for running
national elections by email, using known technology.

I made this claim on a local newsgroup, and a colleague, Doug Tygar, 
disagreed strongly.  I thought I'd run this by you and see if I can
get a reaction.  Do you think that secure elections are within the
grasp of modern cryptography?  If so, how would you do it?  If not, 
what do you see as the major obstacles?

----

Here's a straw man proposal which looks good to me.  It requires
  (1) Public key cryptography, say, RSA.
  (2) The equivalent of untraceable electronic cash.  I like the work
      of David Chaum.  In this proposal, I use an RSA-based scheme from 
      his overview article in CACM, October '85, but he also presents
      a similar scheme using collision-free functions in the Crypto '88
      Proceedings.
  (3) Anonymous secure email.  Again, I like Chaum's suggestions for
      defeating traffic analysis (CACM, February '81):  route your message 
      through any number of "laundering" machines which cryptographically 
      unwrap your message and send it along to its next destination.  
      Organizations such as the ACLU could operate vote-laundering services.

Aside:  Recall that RSA works like this:  the key owner chooses modulus
N and powers e and d which have the property (M^e)^d = M, modulo N.  
e is public and d is secret; anyone can encrypt a message by computing
M^e, but only the key owner can decrypt it, computing (M^e)^d, or sign
a message M by computing M^d.

----

In my scheme, voter registration is a public process much like it is today,
with the addition that a public key is associated with each registered voter.
Voters and the government communicate via encrypted, signed email.

An election has the following steps:

   1. The government announces the election and the candidates, and
      the public half of a new public/private key pair which will be 
      used to sign votes.

   2. The voter appends a bit string corresponding to the desired vote
      (say, "Clinton " or "Bush    ") to a string of random bits chosen
      by the voter.  This is a unique "vote" V which is to be signed by
      the government.  We're running a secret ballot, though, so we must 
      "wrap" the vote so the government can't see it, but nevertheless 
      can sign it:

        2a. The voter generates a secret random number R and computes 
            W = V * R^e.

        2b. The voter sends W to the government via signed, secure email.

        2c. The government signs W, records that it has signed a vote for
            the given voter, and securely returns X=W^d.  

        2d. The voter divides X by R to get  (V^d * R^e^d)/R = V^d, the 
            signed vote.

   3. The voter anonymously sends the (untraceable) vote to the government.

   4. The government posts a list of all signed votes it has received.  
      People can make sure that their vote is on the list, and everybody
      can count the votes (removing duplicates) to determine the winner.


The most critical step of this process is the signing of votes:  the
vote-signing machine must be monitored by all interested parties to
make sure that it is only used to sign one vote per registered voter.
Actually, it would be much better to require several signatures per
vote, with independent agencies operating each signature machine.

In a similar vein, voters could also anonymously send their votes to other
watchdog agencies to ensure that their vote is published.


----

It might be worth discussing the cryptographic guarantees at each 
step of the process, and whether we feel that RSA is up to the job.


What do you think?


[ Marc Ringuette | Cranberry Melon University, Cucumber Science Department  ]
[ mnr@cs.cmu.edu | 412-268-3728 |      ".surivorter erutangis a ma I"       ]