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

[Mike Frank]

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> 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 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.


> 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."


> 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.


> 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.

Of course, a voter retraction signal opens up the possibility for coercion
> or buying of said signal, and it'd also be difficult to reconcile the goals
> of both having it possible for a voter to verify if his vote was counted and
> making it possible for the voter to annul his vote. If the annulment makes
> the signature return "you didn't vote" or "your vote didn't count", then a
> coercer could attack the voter for having retracted his vote, whereas if it
> still makes the signature return "you did vote and your vote counted", then
> that might be used for fraud (mass retraction after the polls have
> officially closed).


The philosophy of my system is not to outright prevent fraud in generating
the election results, but to allow it to be easily detected if it does
occur, so as to remove the incentive to commit it in the first place.


> Would the certificates differ for different Condorcet methods? How about
> IRV, which is very sensitive to changes in ballots?


The certificates could be done for any ballot type, but they might become
much larger for ranking-based systems like IRV, since a lot of information
may have to be kept about the rankings in one sub-population of voters in
order to effectively combine them with the rankings of another
sub-population.  I like range voting better, since it still allows voters to
rank their candidate preferences (and more information beyond this), but it
combines the preferences of different voters in what seems, to me, a much
more straightforward and intuitive (and flexible) and natural way.  IRV and
the whole concept of runoffs seems a lot more ad-hoc to me.


> If the certificates are unmanagable for IRV, that may still not be much of
> a problem, though, since (in my opinion) IRV is not a very good system.


I agree.

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?

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.

-- 
Dr. Michael P. Frank, Ph.D. (MIT '99)
820 Hillcrest Ave., Quincy FL  32351-1618
email: michael.patrick.frank at gmail.com
cell: (850) 597-2046, fax/tel: (850) 627-6585
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20081007/157bccb5/attachment-0003.htm>