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

Actually, online voting is pretty tricky.

If you want the most extreme approach to voting safety, you may need to consider something like this:

https://docs.google.com/document/d/1SPYFAkVNjqDP4HOt_A_YGFZy-SFXVxHoN1hpLGNFKXI/pub

It is an algorithm that distributes the voting secret among n distinct servers that each cannot break the voting anonymity by themselves. All n servers would have to cooperate in order to break anonymity, and if only one of the server cover its tracks ans wipes all cryptographic data away, the voting secret is lost/hidden forever.

The system can also deal with re-sending of votes, with some limitations inherent to any secure system for online voting:

For voting security online there is always an ultimate limitation in that it is vulnerable to traffic analysis. For example, if one day only one person votes, it can be concluded that any update of the voting result is a result of that persons voting.

A perfect secure online voting system should be viewed as a one-time vote-mixer. It takes a number of votes. Buffers them, and when the voting is finally closed, it mixes all of them in one go. This makes it extremely difficult to associate a vote with a voter. This can be achieved with pretty solid technology.

However, when we want to update votes things get much more tricky. There would be an intrinsic need for synchronization if we want to avoid the possibility of traffic analysis. Ideally all voters would have to re-send an update at regular intervals (even if their update is actually not an update).

Answer 2

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

Answer 4

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.