tag:blogger.com,1999:blog-6555947.post116262230409696138..comments2024-03-14T01:32:43.610-06:00Comments on The Geomblog: Tamper-proof voting systemsSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-6555947.post-44705655507736309252007-06-30T05:35:00.000-06:002007-06-30T05:35:00.000-06:00hi suresh and others. If you are interested in tam...hi suresh and others. If you are interested in tamper-proof voting systems, have a look at www.cd3wd.com/SEEV/ - this system is so good it was banned from a washington DC Global Electoral Organisation Conference March 2007. Best regards, mr alex weir, Guinea Conakry and HarareUnknownhttps://www.blogger.com/profile/03106470746792640331noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1164362851672336622006-11-24T03:07:00.000-07:002006-11-24T03:07:00.000-07:00designing search result  Here's some useful i...<B>designing search result </B> <BR/><BR/>Here's some useful info on <A HREF="http://www.jaldisearch.com" REL="nofollow">designing search result </A>  <BR/>which you might be looking for. The url is:<A HREF="http://www.jaldisearch.com/" REL="nofollow"> http://www.jaldisearch.com/ </A><BR/>  <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://www.jaldisearch.com" REL="nofollow" TITLE="shiv22 at gmail dot com">shiv</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1163540525814140352006-11-14T14:42:00.000-07:002006-11-14T14:42:00.000-07:00Aspiring cryptographer: just a language point, but...Aspiring cryptographer: just a language point, but I believe most people would say standard crypto assumptions are *stronger* than the assumption of worst-case hardness of NP-complete problems. It's the plausibility of those assumptions that's weaker. <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="www.andysresearch.blogspot.com" REL="nofollow" TITLE="add3993 at yahoo dot com">Andy D</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1162876210182909522006-11-06T22:10:00.000-07:002006-11-06T22:10:00.000-07:00I'll ditto Aspiring Cryptographer. The real probl...I'll ditto Aspiring Cryptographer. The real problem with manipulation at Digg is that it is trivial to add more users to vote for your preferred story. Bartholdi, Tovey, and Trick ("How Hard is it to Control an Election"), showed that this would be computationally easy for plurality. I don't see this particular aspect changing in sites like Digg unless they make it a LOT harder to get an account.<BR/><BR/>And, right, deterministic voting systems can always be manipulated - in the sense that one gets a more preferred result by lying in their preferences - this is known as the <A HREF="http://en.wikipedia.org/wiki/Gibbard%E2%80%93Satterthwaite_theorem" REL="nofollow">Gibbard-Satterthwaite theorem</A> (follows from Arrow's). Some work has been done by Conitzer and Sandholm ("How many candidates are needed to make elections hard to manipulate?") on the computational difficulty of manipulation. For plurality it is always in P to do so, but for many voting systems it is NP-complete over three candidates. <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://geomblog.blogspot.com/2006/11/tamper-proof-voting-systems.html" REL="nofollow" TITLE="eab3572 at rit dot edu">eric</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1162689912633347482006-11-04T18:25:00.000-07:002006-11-04T18:25:00.000-07:00I think there may be a little bit of confusion bet...I think there may be a little bit of confusion between the different problems in constructing voting schemes:<BR/><BR/>Arrow's theorem is a statement about the impossibility of finding a reasonable voting scheme that doesn't admit "paradoxes" (e.g., when using majority as the voting function: most voters can prefer A to B, B to C and C to A simultaneously). Arrow's theorem doesn't say anything about gaming a specific voting system (as in trying to bias it in favor of some candidate), or anything about "secure" implementations. <BR/><BR/>When constructing a voting protocol, usually the function is already known (e.g., plurality), and the problem is in securely implementing a computation of this function.<BR/><BR/>For internet sites such as digg, the most significant problem is identification: it's almost impossible to make sure every human is voting only once (or only as him/herself). Note that cryptography can't really solve this problem for sites which allow anyone to vote: one person can always pretend to be two or more people (although cryptography can help prevent automated cheaters using things like CAPTCHAs). <BR/><BR/>For "real-life" voting, identification is also a problem, but most of the cryptographic effort has gone into providing methods for "universal verifiability" (so any voter can verify that her vote was both cast and tallied according to her wishes) while still preserving ballot secrecy (in fact an even stronger "receipt-freeness" property is usually required, in order to prevent vote-buying and coercion). In this case there are quite a number of systems that use cryptography to prevent voters from cheating (see, for example, <A HREF="http://www.voterverifiable.com/article.pdf" REL="nofollow">Chaum's scheme</A>  and <A HREF="http://www.votehere.net/vhti/documentation/vsv-2.0.3638.pdf" REL="nofollow">Neff's scheme</A>)<BR/><BR/>The game-theoretic version of "gaming" (systems where it is advantageous to falsely report your preference in order to bias the result) is far less studied, AFAIK. IIRC, there was some proof that deterministic systems can always be gamed in this way, but there are some probabilistic systems that cannot (a trivial example is to pick a voter at random and use only her choice).<BR/><BR/>P.S. for whoever's interested -- almost all cryptographic assumptions seem to be weaker than NP-hardness. In particular, there is some evidence that one-way functions (the most basic cryptographic assumption) cannot be based on P<>NP.  <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>Aspiring CryptographerAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1162680508615207042006-11-04T15:48:00.000-07:002006-11-04T15:48:00.000-07:00hah! some prognosticator you are. This device alre...hah! some prognosticator you are. This device already exists !<BR/><BR/><A HREF="http://www.miami.com/mld/miamiherald/news/local/states/florida/counties/broward_county/15869924.htm" REL="nofollow"> Touch Screen Hopping in Florida</A><BR/><BR/>Posted by SureshSuresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1162662379085971392006-11-04T10:46:00.000-07:002006-11-04T10:46:00.000-07:00Yes, a cryptographic assumption would work just fi...Yes, a cryptographic assumption would work just fine. On a related note, what kinds of cryptographics assumptions *are* there that are weaker than NP hardness ?  <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>SureshSuresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1162658685789497562006-11-04T09:44:00.000-07:002006-11-04T09:44:00.000-07:00Vince Conitzer has done some work in this area. If...Vince Conitzer has done some work in this area. If I remember correctly, it is possible to design voting schemes that are hard to manipulate in the worst case, but it is impossible to design schemes that are hard to manipulate "on average". See for example http://www.cs.cmu.edu/~conitzer/nonexistenceAAAI06.pdf<BR/><BR/>It would be interesting to have something based on a cryptographic assumption and not NP-hardness. <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>Shuchi ChawlaAnonymousnoreply@blogger.com