# Design a OT-based Private Set Intersection protocol to obtain $A \cap B \cap C$?

This is a tutorial question for a Foundations of Privacy computer science course, I'm unsure on how to tackle it because we haven't talked much about these particular topics in class.

(a) Assume Alice, Bob and Carlo respectively have the data set $$A = \{ \ldots \}$$, $$B = \{ \ldots \}$$, $$C = \{ \ldots \}$$. How to use the OT-protocol to design a Private Set Intersection protocol among Alice, Bob, and Carlo, so that each one can obtain $$A \cap B \cap C$$. You can design your solution based on the OT-based PET (Private Equality Test) protocol in the figure below.

PET Figure

(b) How to use the OT-protocol to design a privacy-preserving integer comparison protocol between two parties, e.g., two integers $$x,\space y$$, both of them are $$n$$ bits, where $$x \gt y, \space x \lt y,$$ or $$x = y$$. You can design your solution based on the above OT-based PET protocol. (Hint: you may disclose two bits information in your solution!)

I think I understand what to do for (b):

• If Alice and Bob use a homomorphic encryption algorithm, Alice can use a private key pk and a public key sk. Bob would only have the public key pk.
• Alice then sends $$\text{E}(x)$$ and $$\text{E}(y)$$ to Bob. Bob computes $$\text{E}(r(x-y)) =$$ $$(\frac{\text{E}(x)}{\text{E}(y)})^r$$ using the homomorphic property, where $$r$$ is a random number, and returns $$\text{E}(r(x-y))$$ to Alice.
• Alice recovers $$r(x-y)$$, and if it is equal to $$0$$, then $$x = y$$, otherwise $$x \not= y$$.

With this solution, are the only bits disclosed the ones that are given in the comparison result? I'm a little more foggy on how to attempt (a). Any help is appreciated!

The real challenge is that the 2-party equality test reveals the outcome of the comparison in the clear to one party. This makes it hard to hide partial intersections. For example, if $$x \in A \cap B$$ but $$x\not\in C$$, then Alice must not learn that Bob also has $$x$$. This suggests that Alice and Bob can't simply use the 2-party equality test on their inputs. In our paper we had to go to extra lengths to hide these intermediate equality test results.