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

Question

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!

Answer 1

I worry that the first problem is harder than your instructor suspects. We had to work a little hard to get a multi party PSI protocol based on efficient OT in our paper

Practical Multi-party Private Set Intersection from Symmetric-Key Techniques, by Vladimir Kolesnikov, Naor Matania, Benny Pinkas, Mike Rosulek, Ni Trieu

If I remember correctly, we may have some optimizations for the 3-party case, but I don't think it falls to the level of a homework assignment.

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.