Thread View: sci.crypt
4 messages
4 total messages
Started by Marc.Ringuette
Sun, 16 Aug 1992 21:49
Cryptographic voting
Author: Marc.Ringuette
Date: Sun, 16 Aug 1992 21:49
Date: Sun, 16 Aug 1992 21:49
92 lines
4630 bytes
4630 bytes
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" ]
Re: Cryptographic voting
Author: Michael Fischer
Date: Tue, 18 Aug 1992 18:30
Date: Tue, 18 Aug 1992 18:30
43 lines
3185 bytes
3185 bytes
Marc.Ringuette@daisy.learning.cs.cmu.edu wrote:
: 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?
A former student of mine, Josh Cohen Benaloh, did a Ph.D. dissertation
on this problem at Yale back in 1987. The title is "Verifiable
Secret-Ballot Elections". A preliminary version of this work appeared
in J. D. Cohen and M. J. Fischer, ``A Robust and Verifiable
Cryptographically Secure Election Scheme,'' {\it Proc. 26th IEEE
Symposium on Foundations of Computer Science} (October 1985), 372-382.
The problem is much trickier than might appear at first sight. In
addition to privacy, two important requirements in a practical voting
scheme are verifiability and robustness. Verifiability means that all
voters can verify that the votes were counted correctly. Robustness
means that no small group of participants can invalidate the election,
disenfranchise valid voters, or otherwise have greater influence over
the outcome than their alloted votes would allow.
While the proposed scheme does allow every voter to verify that his or
her vote is among those posted by the government, it appears to be
subject to various abuses by the government. For example, the
government can fabricate votes and count them in the final tally. No
individual or small group of voters can detect that they are
fabricated since they could be legitimate votes of all other voters.
For another, the government might change the value of legitimate
votes, or fail to return a signed vote to the voter. While the voter
could detect such abuses, there would be no way to prove it to others,
at least without compromising the privacy of the vote.
==================================================
| Michael Fischer <fischer-michael@cs.yale.edu> |
==================================================
Re: Cryptographic voting
Author: Gordon Burditt
Date: Thu, 20 Aug 1992 23:49
Date: Thu, 20 Aug 1992 23:49
21 lines
1622 bytes
1622 bytes
>The problem is much trickier than might appear at first sight. In >addition to privacy, two important requirements in a practical voting >scheme are verifiability and robustness. Verifiability means that all >voters can verify that the votes were counted correctly. Robustness >means that no small group of participants can invalidate the election, >disenfranchise valid voters, or otherwise have greater influence over >the outcome than their alloted votes would allow. Another property of the current voting system (except for absentee ballots) is that voter A cannot conspire with candidate B to have A prove to B how A voted. In the current system, B can bribe A to vote for him, but B can't get a guarantee that A didn't cheat and vote for someone else (except in the unlikely event that B doesn't get ANY votes). It's probably impossible to do this with electronic voting, since A will voluntarily let B listen to *ALL* of his communications. The only thing preventing this in the current system is that A can't take B into the voting booth with him. Gordon L. Burditt sneaky.lonestar.org!gordon
Re: Cryptographic voting
Author: Bruce Schneier
Date: Fri, 21 Aug 1992 06:28
Date: Fri, 21 Aug 1992 06:28
21 lines
1493 bytes
1493 bytes
In article <9208162214.AA21945@news.cis.ohio-state.edu> Marc.Ringuette@daisy.learning.cs.cmu.edu writes: >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, There is a secure voting protocol in _Security_in_Computing_, by Charles Pfleeger (Prentice Hall, 1989), pages 144-145. As written, the protocol has a problem but it can be fixed. Bruce **************************************************************************** * Bruce Schneier * Counterpane Systems For a good prime, call 391581 * 2^216193 - 1 * schneier@chinet.chi.il.us ****************************************************************************
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads