3
$\begingroup$

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!

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.