[EM] Idea for a free web service for (relatively) secure online voting

[Kristofer Munsterhjelm]

Mike Frank wrote:
> Hello, Thank you for the detailed and thoughtful critique. 
> 
> On Tue, Oct 7, 2008 at 9:16 AM, Kristofer Munsterhjelm 
> <km-elmet at broadpark.no <mailto:km-elmet at broadpark.no>> 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?