The problem Fruity Friends solves

This project intends to solve the case when two people share common interests, such as fruits they like, but are unwilling to reveal any of them unless it matches the other person's interests. This is a common problem known as Private Set Intersections or PSI. The idea is to let people know whether they share something in common with someone else while keeping their preferences private. There are multiple approaches to the problem, and we focused primarily on checking if the size of the intersection (i.e. cardinality) is greater than 0.

Challenges we ran into

While at first, it seemed a great idea to implement using zero-knowledge proofs the problem became harder to solve as we dug deeper into it.

The literature on Private Set Intersections (PSI) seemed to indicate that the most practical solutions must include a third party, someone in addition to the two parties who want to check their sets. The idea is to use this third party to check if there exists any intersection between the two sets. Unfortunately, this introduces some major issues.

The first one is privacy. We don't want to trust this third party but he needs to know both sets to make this proof. Let's call our two participants Alice and Bob, and the third party Steve. If Alice and Bob want to keep Steve from discovering what their sets contain, they can encrypt these sets. But to make sure Steve can make the proof, he still needs to be able to compare both sets, and elements that are identical should be identified by Steve as such. A solution we decided to go for is to make Alice and Bob agree on a secret that Steve doesn't know. They use this secret as a salt to hash each item in their set. Then they pass the sets with their items hashed to Steve. Since the salt is the same for Alice and Bob, identical items will result in the same hash. Steve will be able to tell if they are identical but won't know what exactly these items are. This somewhat solves the problem, although the secret needs to be kept safe.

One other problem is that Steve can decide to send Alice's hashed set to Bob who, having the same secret, can then deduce Alice's set content as the list of possible elements is most likely known and limited in size. However, we weren't able to implement a solution to prevent this.

A better solution for our project could have been through the use of homomorphic encryption and/or multi-party computation, but too complex for this first proof of concept and probably a bit out of scope for the theme of this hackathon.