Re: Vote verification --- a futile exercise?
On Wed, 2002-04-03 at 00:16, Anthony DeRobertis wrote:
> I assume the following are the goals of verifying a vote. I
> believe these goals are justified:
All the fun discussion tweaked my curiosity, so I pulled Schneier down
from the shelf and did some reading. The results are interesting. For
posterity, here's a brief summary. This is from _Applied Cryptography_,
2nd edition, section 6.1. (In my printing, it starts on page 125.)
NOTE: I am NOT criticizing the current voting protocol, or anyone's
integrity or anything; this is an intellectual exercise.
First off, Schneier has six requirements for a secure election, and one
sometimes requirement.
> 1) No voter can vote twice
This is number two.
> 4) No person not registered to vote may vote.
This is number one.
> 6) Every voter can verify the correct counting of the votes
This is number six, sort of. Schneier actually is only concerned with
each voter being able to see that his/her vote was counted.
> 7) No one can determine how another person voted
This is number three.
> [ I really should grab Applied Crypto and make sure I didn't
> miss any ]
You missed two:
4. No one can duplicate anyone else's vote.
5. No one can change anyone else's vote without being discovered.
And the "optional requirement":
7. Everyone knows who voted and who didn't.
Interestingly, Schneier considers number four to be the tough
requirement.
> All the shared keys schemes proposed so far have failed to
> follow 5 and 9, and perhaps others. The reason is that nothing
> stops the secretary from adding additional votes.
Your steps 5 and 9 aren't "important"; however, steps 5 and 6 are pretty
much identical if you define "the vote" as "the voter's intent", and
step 9 is sort of assumed in all cryptographic protocols - that no one
can break the rules without someone else knowing.
Several protocols are discussed in the chapter. The first ones are
flawed in some way. The last protocol discussed that assumes a central
tabulator is claimed to meet all six of the "real" requirements and has
two other nice features:
8. A voter can change his mind within a certain time frame.
9. Voters can correct misvotes without compromising the ballot's
secrecy.
The basic protocol goes something like this: All voters register their
intent to vote, and the central tabulating facility (CTF) publishes the
list of voters intending to vote. Each voter gets a unique ID number
anonymously; the CTF has the list of IDs, but only the voter can
associate himself with a particular ID. The voter generates a
public/private key pair, combines the ID with his/her vote, encrypts
that with the public key (s)he generated, and sends that anonymously to
the CTF along with the plaintext ID. The CTF then publishes the
encrypted message. Finally, all the voters send their private keys and
IDs to the CTF (again, anonymously), who decrypts all the votes and
publishes the results, along with all the encrypted messages.
If the voter wants to change his/her vote or notices it is wrong, (s)he
combines the vote with the ID, encrypts that, then sends the plaintext
ID, the encrypted message, and the private key to the CTF, again
anonymously.
The trick is distributing unique IDs securely and anonymously. Two
techniques are mentioned: blind signatures and all-or-nothing disclosure
of secrets (ANDOS). Schneier goes into more detail with the ANDOS
version. Blind signatures amount to a way of signing something without
knowing what it is, but with confidence that it isn't something you
don't want to sign. ANDOS is a way of distributing a set of secrets
such that another person can learn one secret of his/her choice, but no
others.
Voters can't cheat with this. They can't use the same ID twice, or pick
their own ID, because the plaintext ID is embedded in the encrypted
message containing the vote, and the CTF knows all the valid IDs. They
can't pretend to be someone else, because they'd need to guess a valid
ID held by someone else. If the same ID comes in encrypted with two
different private keys, the CTF picks one, generates a new unique ID,
and publishes the new ID together with that original encrypted vote.
That voter is then responsible for noticing the new ID and sending in a
new vote, using the new ID from the CTF instead of the original one;
otherwise, the vote is discarded. Thus, at most, one person could get
multiple votes; if the IDs are random enough, this won't be a serious
problem.
This doesn't eliminate the problem of trusting the CTF, although it
limits the CTF's options; the CTF may still "proxy vote" all non-voting
IDs at the end of the election. Having voters declare their intention
to vote mitigates this somewhat, since this reduces the number of unused
IDs; if a voter declares his/her intention and then doesn't vote,
however, that vote is the CTF's for the taking. Also, the CTF may drop
votes, and the voter cannot prove that (s)he actually voted properly;
one would think, though, that if this happened enough to influence the
election, enough of a public stink would be raised that the election
results would be suspect.
> The easiest solution is to make sure we can trust our vote
> counter. For other solutions, I will have to pull out Applied
> Crypto.
There is a method described in _AC_ that does not require a CTF. It's
not practical, though. for any more than a few people.
--
To UNSUBSCRIBE, email to debian-vote-request@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org
Reply to: