Limiting 'likes' sent anonymously - Part 3

Recap

For those who haven’t read the previous posts part 1 and part 2, this is a challenge which came up while trying to develop a secure version of a platform called Puppy Love. The introduction and the algorithmic challenge, taken from the previous 2 articles:

The queerly named Puppy Love platform has been running in my university since 2014, meant to help shy nerds meet their crush, made my the Programming Club (of which, I happen to be the current coordinator). The platform opens 1 week prior to the Valentine’s Day every year, and let’s people choose up to 4 of their crushes, encrypting their choices with their password. At the stroke of the midnight hour, everyone logs back, and their choices are decrypted, and are then matched to other people’s choices. Only the people who matched are informed about it. If your love was unrequited (the other person didn’t like you), you will not get to know. More importantly, if you did not like the other person, you would not know if that person liked you or not.

Limiting your likes: The challenge

In part 2, we ensured that the server would not get to know the individual choices of the users, and would only know if both of the parties matched. There still exists, an issue with this. Since the server has no idea about your choices, it cannot prevent you from sending a like to everyone you know. Theoretically, you could send one to everyone, and basically find out who likes you. Of course, this comes with the additional baggage of having to explain to the person that you actually cheated and do not like them back.

Interestingly, while solving this issue, I ended up with a solution which reduced the compution and data needed by almost half. The solution used to restrict choices to 4 will also let the server match people.

Updated algorithm:

Here is a possible solution to this challenge. To explain that, I shall go over the needed part of the algorithm (taken from Part 2):

• Both parties have public and private key pairs.
• Each party sends a random token to the other party (call these strings t0 and t1).
• The server will not know the these values due to asymmetric encryption.

When the user wants to submit, he/she will look at each of his/her choices, and fetch the corresponding token values. Let them be t0 and t1. Now, the user will send the value of hash(t0-t1) to the server (it can be any non-invertible function of the tokens). The user can send up to 4 such values to the server (can be checked on the backend).

In case 2 people like each other, the values they send will be exactly the same (because the ordering of t0 and t1 is decided by their roll numbers). The server can simply sort the list in the end, and inform all people whose values matched. The matching is accomplished!

The server will not find out your choices if there was no match. Profit.

The old algorithm for this (deprecated)

Note: This section is very similar to the above, but contains steps not needed anymore.

Here is a possible solution to this challenge. To explain that, I shall go over the needed part of the algorithm (taken from Part 2):

• Both parties have shared secret values A and B. These are not known to Eve by virtue of public key encryption.
• Parties agree to this protocol:
  • Alice sends value a = A to Eve if she likes Bob.
  • Alice sends value a = random to Eve if she does not like Bob.
  • Bob sends value b = B to Eve if he likes Alice.
  • Bob sends value b = random to Eve if he does not like Alice.
• Eve receives a and b. She stores hash(a*b) as result.
• Alice and Bob manually compute hash(A * B), and send it to server (server can verify malicious behavior if they don’t match)
• It is a match only if the result and the expected value by both parties are the same.

Note here, that the server shall not find out more than one of A, B if the two parties did not match. But if they match, this would be a cue for the server that there was a match. Now, this is a good point to ensure that both the users did not send more than 4 likes, and this match, indeed, was expected. Here is a sketch of how this could be done:

• Once you finalize your choices, you need to inform the server about them in a way that it cannot find out unless that choice actually matched.
• If your likes are m1, m2, m3 and m4, assume that the negotiated values A and B are: A1, B1 and so on.
• You send the value AES_enc('m1') encrypted with a password A1-password-B1 or some other function of both A1 and B1.
• The server shall accept only 4 of such terms.
• When the server detects a match, it shall look up in the list of terms you sent, and try decrypting them, to ensure that this particular match was among the 4 you had expected. It should ideally find exactly one term which gets decrypted.
• If there is a match which was not intended, it is simply dropped.

This way, only 4 of your likes can actually result in matches. The server still cannot detect your choices. Profit :)