Mike Frank wrote:
Hello, Thank you for the detailed and thoughtful critique.
On Tue, Oct 7, 2008 at 9:16 AM, Kristofer Munsterhjelm
<[EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>> wrote:
How would this system work? I guess you could use blind signatures
to submit the actual votes, but how would it ensure the voters that
their votes are counted?
This can done using cryptographic hash functions, for example by adding
votes together in a tree structure, where each node in the tree includes
a hash of the data at the child nodes. The hash guarantees that the
given results could only have been generated by that specific tree of
ballots (in the sense that finding an alternative tree that yields the
same hash is computationally intractable). The root hash in the tree
(summarizing the overall election results) is publicly viewable, and it
is sufficient for a given voter's certificate to concisely show just the
roots of the subtrees that were combined with that specific voter's
ballot data to produce the final result. The specific hashes and
vote-aggregation operations (e.g. addition of tallies) shown in a given
certificate can be checked easily, and if a substantial amount of
miscounting occurs, then many different voters' certificates will reveal
it, so it will be likely to be caught.
I'm not completely sure how that would work. Say that you're a voter x
whose ballot is A > B > C. Now, if you're the only one with the ballot A
> B > C, then you can check that the A > tree has at least one A > B
part. So say that you're not, that there's another voter y who also
voted A > B > C. Even if your (x's) ballot is miscounted, there'll be an
entry for A > B > C. How do you know that your ballot was or wasn't
counted? You don't know about y, so if you see "one person voted A > B >
C", you could easily think that that person was you.
There are two ways to solve this that I can see. Either you could have
an unique ID, or somehow the existence of y will be known to you before
you vote. In the former case, the days of the secret ballot would be
over. In the latter case, I can't quite see how that would work either,
but there might be some cryptographic magic that allows for it. I don't
pretend to understand the AACS subset difference algorithm, for
instance. The cryptographic magic would in any case be limited, since if
y submits his ballot after yours, you can't know about y.
There may be another option, also: have the record of the ballots
themselves be hashes. The idea would be that if you vote A > B > C and
know this (and your ID), then you could look up your {ID, hash} pair and
check against "A > B > C". But so can any other party if there are
sufficiently few candidates, and in any event, you don't know if they're
"using two books" -- calculating the result from a subset of the
ballots, for example.
If you don't care about the secret ballot, you could make all the
ballots public. The election service would be replaced with numerous
"services", checking each other's results. But the secret ballot is
secret for a reason.
I know of some systems to produce proofs for Plurality, but I'm not
sure how they could be turned into proofs for, say, Schulze.
In my system, the proofs are of a very generic nature; they only require
the ability to run a cryptographic hash function on input strings which
contain the aggregated summaries of two disjoint subsets of ballots.
This is most convenient to do if the aggregate results can be concisely
summarized.
Like Condorcet, but not IRV, I assume.
If the system permits ranked or rated votes, you'll also have to
deal with the "fingerprint attack", where a vote-seller asks the
voter to vote in a particular manner, using a rank that with high
probability will be unique.
Well, my system does not itself prevent vote-selling, which can perhaps
be kept under control sufficiently well by ordinary enforcement methods,
since some fraction of parties who are approached for buying or selling
of votes may report the other party to the local law enforcement or
media (or to international election observers). And anyway, politicians
effectively "buy votes" all the time already, whenever they promise
certain classes of voters goodies such as tax rebates and the like, and
the wealthy can already heavily influence the voting anyway, by funding
misleading ad campaigns, e.g., "swift boating."
In some sense, that's true, but I would say that direct vote buying is
much more powerful than indirect vote buying (through advertising,
patronage, etc.). One of the reasons for why that is the case is that
direct vote buying is completely certain: the vote-seller knows if you
did what he wanted, whereas you may resist advertising or cynically
think it's just politician-speak anyway, without any repercussions.
Other possible attacks from the outside could involve coercion (vote
my way while I watch) or bribery (same as above, but with a payment
if you do what I say), and identity confusion (where the person's
computer is zombified so that the ballot cast differs from what the
voter intended).
With my system, if the system corrupts the ballot data, this will become
evident to the voter later, when he checks his certificate, since the
hash for his ballot won't match up with how he knows he voted. If a
voter is uncertain whether he can trust the software that checks the
certificate, he can have it checked by many independent services.
Those whose computers are often infected by malicious software are
probably less likely to check their ballots than people in general.
Also, let's say that a person votes "A > B > C". His computer has been
compromised, so the hacker (or his bot) replaces the vote with "B > A >
C". Time passes, and after the election, the voter checks his
certificate and finds that it's wrong. Now what? How can he prove that
he voted A > B > C? The voting site recorded him as voting B > A > C,
because the compromise was local to his computer. He might have taken a
screenshot, but then he would have needed to know in advance that his
vote might be stolen later. If your method is designed to inform about
fraud rather than prevent it, it might be possible to capture the
modifier software and determine who wrote it, but that's still improbable.
If you want to be sophisticated, you could have a vote retraction
signal (a number or similar) which would nullify your vote if you
send it before the election, and an external device to confirm the
ballot just before you submit it (so that you can see it's what you
actually wanted).
In my system, the second type of device is not needed, since you can go
back and check your ballot later. The idea of vote retraction or more
generally modifying your vote after you've submitted it is an
interesting concept, but it won't work in my system since the
certificate (issued after the election) is based on your final choice,
and so it still could be used to prove to a vote-buyer that you did what
was requested.
Smith and Rivest appear to have an interesting method for preventing
vote-buying, although it may need some additional assurances against
fraud. Right now I am thinking about how to combine it with my system
to get the best of both worlds.
Perhaps this would work: each voter has three voter IDs, one for each
ballot, so that the first is 0 mod 3, the second 1 mod 3, and the third
2 mod 3. The software (or device) turns the voter's choice into one
ballot and two cancelling ballots (that together have no effect), and
they're submitted, encrypted in a way that it's impossible to have the
two other votes not cancel each other out.
After the election, some authority rolls a tetrahedral dice. Call the
result number x. Then all ballots with IDs congruent to x modulo 3 are
published. Voters can now check if their ballots were tampered with, but
there's only 1/3 chance that a vote-buying effort would work.
It's very important that the dice is truly random, so that a potential
fraudster can't just mess with all ballots that don't have ID congruent
to y mod 3, where y is what the dice will turn out later. If you need
security, perhaps a bit commitment scheme could be used to ensure
randomness.
1/3 may still be too high a chance of vote-buying or fraud working. To
decrease the chance of fraud, one could change mod 3 to mod 3 when XORed
with some value that doesn't get revealed until after the election. That
wouldn't reduce the probability of after-the-fact vote buying; for that,
you'd need to make the ballot n-ballot instead of ThreeBallot.
As for that setup, I think that it would be fine for small or
informal elections. For larger scale elections, the security doesn't
suffice unless you find a way of dealing with the attacks from
without (coercion, vote-selling, and impersonation). Even if you
limit access to the site to polling place computers, you get the
problem that the voters may not trust the machines or not know or
care to verify their signatures.
My system doesn't require signatures per se, but it rather uses
standard, publicly-known cryptographic hash functions; any of a number
of independent services can check these. If the voter doesn't trust
the voting machines or central website, he can turn for assurance to
whatever party he trusts the most that is knowledgeable enough to verify
the certificates.
By impersonation, do you mean impersonation of a voter by another party,
or impersonation of the official website by another site?
By impersonation I mean a man-in-the-middle attack between the voter and
the website. The voter provides his information and votes, but another
vote is registered. Similarly, unless the certificate is signed, the man
in the middle also provides a fake certificate to the voter (if the
voter gets those from the same website).
The former can be noticed by the voter by checking of certificates. The
latter requires individual voters to just be careful typing the URL, but
if they catch their mistake before the election is over, they can always
go back and do it over.
How do you deal with a combination of the two?
----
Election-Methods mailing list - see http://electorama.com/em for list info
