13

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?

Robert Harvey
  • 178,213
  • 47
  • 333
  • 501
cmreigrut
  • 185
  • 2
  • 9
  • 1
    Is this supposed to be a distributed system? Because if you have a single trusted party (such as a website you run), this is trivial to implement. You need to define the parameters of your system better. – Nick Johnson Aug 17 '11 at 01:37
  • This question is probably better suited for the [cryptography stackexchange](http://crypto.stackexchange.com/). – Wyzard Aug 19 '11 at 05:37

4 Answers4

3

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.

Iterator
  • 20,250
  • 12
  • 75
  • 111
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.

DwB
  • 37,124
  • 11
  • 56
  • 82
  • How is it true that true anonymity guarantees you can never detect duplicate voting? Is it is that you'd have to know if a person voted, and therefore when the first vote is cast you'd know what their vote was? – cmreigrut Aug 19 '11 at 05:01
  • 1
    If somebody is truely anonymous, then there is no way to know that that individual does not have 2 or more anonymous accounts. – DwB Aug 19 '11 at 11:54
  • In the system you described, how do you subtract the user's vote from the tally when they unvote? You'd have to know what their original vote was, which breaks anonymity. If your point 4.3 is for that, and the "calculated" value means that it's garbled (but still reversible), then anyone with access to the source code (Ruby, Python) or a decompiler (Java, .Net) can trace it back. Otherwise, without the "unvoting" feature your system is the only one usable here amongst the answers. – Boris B. Aug 24 '12 at 08:09
  • In my system, there is no unvote. In real world elections, there is no unvote. For example, if you vote for Donald Duck to be president of the USA then push the button to commit your vote, you can not change your vote to be for the roadrunner. It is a one time event that is consumed when you commit the vote. In the context of a general election, unvoting makes zero sense; a vote is a one time (per voted on issue) decision. – DwB Aug 24 '12 at 11:17
  • There is a difference in determining IF a person voted and WHAT he voted. Talking about anonymity is confusing. We want that anyone can verify if some preson voted, and conceal the vote value. The difficulty is to be able to count the different vote values in a way verifiable by anybody. I have seen some suggested methods to achieve that. Can't put my finger on it now, but I had the impression it is possible. – chmike Jan 07 '17 at 15:06
1

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

Martin Shobe
  • 146
  • 2
0

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

erobwen
  • 71
  • 3
  • 1
    You should try to get that published and critiqued if you want people to adopt it. – Emre Jun 29 '16 at 02:14