Zero-trust - Safe and anonymous ANDing bits - Part 2

Recap

For those who haven’t read the previous post, 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 article:

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.

The above seemed like a very rosy thing, till people began to find flaws. Some of the issues were with the code, and nothing too serious. But as would have, people began to get doubtful about the trust worthiness of the server admins. This year, being my turn to face the onslaught of accusations of looking at people’s choices, I, with Vinayak Tantia, a friend and fellow Coordinator, came up with a much improved algorithm to implement the same thing.

Here’s the biggest issue with such a platform:

You do NOT trust me when I say my code on the server is NOT seeing your choices

What is required is, how I call it, a zero-server-trust based algorithm. Regardless of what code is running on the server, the client should be able to prove that any information it sends to the server shall not reveal any information about the client’s choices.

Possible algorithms

We basically need a way to compute the AND of two bit values residing on two hosts (call them Alice and Bob), in the presence of a central server named Eve.

• One simple way is for Alice and Bob to share their bits to Eve, and trust Eve to not store the bits for the eyes of the admin of Eve, and only compute the AND of the bits, and send the AND value back to Alice and Bob. This is simple, but requires you to trust the server to not look at your choices. In case of naming your crushes, this is certainly not an option.
• Use Garbled Circuit technique, along with Oblivious Transfer, but modified to keep the last step on the central server. This technique is quite complicated at first, but has a major drawback. There is no guarantee of secrecy of choices if one party does not play by the protocol and cheats instead. This would be outlined in a future article.

The second solution is promising, but can possibly be exploited to reveal the choice of the other party without them knowing your choice. What is required to prevent that attack is randomness in the case where a party is not interested. We outline the new algorithm in the next section.

Shared knowledge based expected-result algorithm

Note: Some part of this algorithm was later found to be redundant, and removed. The algorithm is still of interest theoretically.

As a preface, I did read a couple of papers on this topic, but did not find a fair, secure and practical solution. This particular algorithm solves a weaker problem than most papers I found, which is: Computing AND of 2 secret bits in presence of an honest-but-curious server. This algorithm was designed originally as a modification of the one based on garbled circuits after I came to know of the violation of secrecy in that, and has been significantly simplied since then. Onto:

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

A few comments about the safety of the protocol

I do plan to formally prove this soon enough, but till then, here are some thoughts.

• Hash is not invertible. So if there was no match, Alice can not invert the result to get Bob’s sent value.
• The hashing step needs to be secure against brute force attacks, especially because each party already knows one multiplicative factor of the number hashed. Either the values of A and B need to be very large (experiments/data needed), or the hash function has to be very slow computationally (preventing inversion by computational bottleneck).
• Selecting random, and different values for A and B is important because Eve should not be able to see whether the values sent by Alice and Bob are same or different, and thus infer whether they matched or not.
• The protocol itself is fully symmetric. Both Alice and Bob execute the exact same steps, regardless of who starts the protocol.
• If Alice did not send A, she has no way of knowing whether Bob sent B or not, since the hash cannot be inverted (theoretically). The same is true for Bob.
• The server does come to know the result of the computation here. But it should be possible to generalize. More on it later.

Conclusion

This algorithm is very simple to say the least, and seems secure to me. A formal proof ought to confirm this as well, though that is untrodden territory for me as of now. Do let me know in the comments or on email if something like this (fair and anonymous AND of bits) has been done before, or if you find a bug in this algorithm (if it is so, I cannot stress how important it is for me to know).