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.
(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!