<div dir="ltr">Hello, Thank you for the detailed and thoughtful critique.  <br><br><div class="gmail_quote">On Tue, Oct 7, 2008 at 9:16 AM, Kristofer Munsterhjelm <span dir="ltr"><<a href="mailto:km-elmet@broadpark.no">km-elmet@broadpark.no</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
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? </blockquote><div><br>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.<br>
 <br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">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. </blockquote>
<div><br>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.<br>
 </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">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.<br>
<div class="Ih2E3d"></div></blockquote><div><br>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." <br>
 </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">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). </blockquote>
<div><br>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.<br>
 </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">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).</blockquote>
<div><br>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.  <br>
<br>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.<br>
<br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
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).</blockquote>
<div><br>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.<br>
 </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Would the certificates differ for different Condorcet methods? How about IRV, which is very sensitive to changes in ballots?</blockquote><div><br>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.<br>
 <br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">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. </blockquote>
<div><br>I agree. <br>
<br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
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.<br>

</blockquote></div><br>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.<br>
<br>By impersonation, do you mean impersonation of a voter by another party, or impersonation of the official website by another site?<br><br>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.<br clear="all">
<br>-- <br>Dr. Michael P. Frank, Ph.D. (MIT '99)<br>820 Hillcrest Ave., Quincy FL  32351-1618<br>email: <a href="mailto:michael.patrick.frank@gmail.com">michael.patrick.frank@gmail.com</a><br>cell: (850) 597-2046, fax/tel: (850) 627-6585<br>

</div>