home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / crypt / 2919 < prev    next >
Encoding:
Text File  |  1992-08-16  |  4.4 KB  |  103 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!cis.ohio-state.edu!daisy.learning.cs.cmu.edu!Marc.Ringuette
  3. From: Marc.Ringuette@daisy.learning.cs.cmu.edu
  4. Subject: Cryptographic voting
  5. Message-ID: <9208162214.AA21945@news.cis.ohio-state.edu>
  6. Sender: daemon@cis.ohio-state.edu
  7. Organization: The Ohio State University Department of Computer and Information Science
  8. Date: Sun, 16 Aug 1992 21:49:00 GMT
  9. Lines: 92
  10.  
  11. A recent newswire article about suggestions to allow telephone voting
  12. got me thinking about the possibility of running a cryptographically
  13. secure presidential election via email.  I claim that the problem is
  14. very similar to the problem of untraceable electronic cash, and that
  15. with a little work, we could concoct a secure protocol for running
  16. national elections by email, using known technology.
  17.  
  18. I made this claim on a local newsgroup, and a colleague, Doug Tygar, 
  19. disagreed strongly.  I thought I'd run this by you and see if I can
  20. get a reaction.  Do you think that secure elections are within the
  21. grasp of modern cryptography?  If so, how would you do it?  If not, 
  22. what do you see as the major obstacles?
  23.  
  24. ----
  25.  
  26. Here's a straw man proposal which looks good to me.  It requires
  27.   (1) Public key cryptography, say, RSA.
  28.   (2) The equivalent of untraceable electronic cash.  I like the work
  29.       of David Chaum.  In this proposal, I use an RSA-based scheme from 
  30.       his overview article in CACM, October '85, but he also presents
  31.       a similar scheme using collision-free functions in the Crypto '88
  32.       Proceedings.
  33.   (3) Anonymous secure email.  Again, I like Chaum's suggestions for
  34.       defeating traffic analysis (CACM, February '81):  route your message 
  35.       through any number of "laundering" machines which cryptographically 
  36.       unwrap your message and send it along to its next destination.  
  37.       Organizations such as the ACLU could operate vote-laundering services.
  38.  
  39. Aside:  Recall that RSA works like this:  the key owner chooses modulus
  40. N and powers e and d which have the property (M^e)^d = M, modulo N.  
  41. e is public and d is secret; anyone can encrypt a message by computing
  42. M^e, but only the key owner can decrypt it, computing (M^e)^d, or sign
  43. a message M by computing M^d.
  44.  
  45. ----
  46.  
  47. In my scheme, voter registration is a public process much like it is today,
  48. with the addition that a public key is associated with each registered voter.
  49. Voters and the government communicate via encrypted, signed email.
  50.  
  51. An election has the following steps:
  52.  
  53.    1. The government announces the election and the candidates, and
  54.       the public half of a new public/private key pair which will be 
  55.       used to sign votes.
  56.  
  57.    2. The voter appends a bit string corresponding to the desired vote
  58.       (say, "Clinton " or "Bush    ") to a string of random bits chosen
  59.       by the voter.  This is a unique "vote" V which is to be signed by
  60.       the government.  We're running a secret ballot, though, so we must 
  61.       "wrap" the vote so the government can't see it, but nevertheless 
  62.       can sign it:
  63.  
  64.         2a. The voter generates a secret random number R and computes 
  65.             W = V * R^e.
  66.  
  67.         2b. The voter sends W to the government via signed, secure email.
  68.  
  69.         2c. The government signs W, records that it has signed a vote for
  70.             the given voter, and securely returns X=W^d.  
  71.  
  72.         2d. The voter divides X by R to get  (V^d * R^e^d)/R = V^d, the 
  73.             signed vote.
  74.  
  75.    3. The voter anonymously sends the (untraceable) vote to the government.
  76.  
  77.    4. The government posts a list of all signed votes it has received.  
  78.       People can make sure that their vote is on the list, and everybody
  79.       can count the votes (removing duplicates) to determine the winner.
  80.  
  81.  
  82. The most critical step of this process is the signing of votes:  the
  83. vote-signing machine must be monitored by all interested parties to
  84. make sure that it is only used to sign one vote per registered voter.
  85. Actually, it would be much better to require several signatures per
  86. vote, with independent agencies operating each signature machine.
  87.  
  88. In a similar vein, voters could also anonymously send their votes to other
  89. watchdog agencies to ensure that their vote is published.
  90.  
  91.  
  92. ----
  93.  
  94. It might be worth discussing the cryptographic guarantees at each 
  95. step of the process, and whether we feel that RSA is up to the job.
  96.  
  97.  
  98. What do you think?
  99.  
  100.  
  101. [ Marc Ringuette | Cranberry Melon University, Cucumber Science Department  ]
  102. [ mnr@cs.cmu.edu | 412-268-3728 |      ".surivorter erutangis a ma I"       ]
  103.