Is there an algorithm for anonymous, changeable, secure voting?

Question

I'd like to implement a feedback mechanism in my application--basically, a score. The requirements are:

1. A total exists, and can be read
2. A user can add his score to the total
3. A user cannot add a second score, but could change his original score, again updating the total by removing (subtracting) the original score, and adding the new one.
4. It is impossible to determine what a given user's vote was

It seems that this borders on (or even overlaps) cryptography theory, but I haven't been able to find anything that would address this. Does anyone have any specific algorithms that would address this? Or even additional search vectors I could use to pursue it?

Answer 1

You can never have anonymous voting without the ability to trust that the anonymous individuals will not vote twice. By definition, true anonymity guarantees that you can never detect duplicate voting.

If you instead force the user to identify themself, you can implement a voting system that prevents duplicate voting and provides anonymity within the context of the vote. Here is a simple algorithm.

1. User logs in. The onus is on your system to prevent one user from obtaining multiple user accounts.
2. User (not anonymous) selects an issue on which to vote.
3. User (not anonymous) casts a vote.
4. Your system stores the following:
   • An indication that the user voted on the selected issue. This prevents duplicate voting.
   • The value of the users vote on the selected issue (this is the score you mentioned). This value is stored without reference to the user who cast the vote.
   • The value of the user's score if they voted on an issue. You probably need this to be a calculated value

If the user wants to change their vote, they login, select the issue, then unvote (your system knows they voted because it stored this). At this point they can choose the issue again (their vote indication was cleared) and vote.

Note that your system will need to subtract the value of the user's vote from the tally for the issue when they unvote.

Answer 2

If there is an anonymous ID, such as a hash of a value that the user supplies, then anyone who can produce something that yields the same hash could modify the corresponding vote.

In this sense, there is still anonymity, because the hash doesn't reveal the source. Instead of listing (userName, vote), list (hashValue, vote). If there is some concern that tracking the hashValue is traceable across many polls, then encode an additional poll-specific wrapping for the hash, which is not revealed publicly. Or let the user embed (e.g. prepend) that into their string to be hashed, so they are still producing a unique submission.

Answer 3

You don't give enough information on what a legal vote is, but if it's, say, an integer, then you can just keep a sum and allow multiple votes. This works because changing a vote from A to B has the exact same effect as voting A and then voting (B - A).