2
$\begingroup$

I can understand the usefulness of one-way private set intersection methods. Where Alice and Bob both have listed but only Alice learns the intersection of those lists while Bob learns nothing.

I don't understand the usefulness of two-way private set intersection protocols though. If Alice and Bob both learn the intersection of their lists, can't the same result be achieved by a much more simpler method of using a one way hash on the lists, exchanging them and allowing each party to compute the intersection?

What are the privacy advantages of more complicated protocols? I feel like I'm missing something simple here...

I found this related question, however, none of the answers seem to address the question of whether these more sophisticated protocols offer security advantages over the matching hashes method. Private set intersection, using a semi-trusted server

$\endgroup$
1
$\begingroup$

Naive hashing protocol

Suppose Alice has items $x_1, \ldots, x_n$ and Bob has items $y_1, \ldots, y_n$. In the naive hashing protocol, they agree on a common hash function $H$, and Alice sends $H(x_1), \ldots, H(x_n)$ to Bob. Bob can compute $H(y_1), \ldots, H(y_n)$ and then calculate the plaintext intersection between these two lists.


Insecurity of naive hashing

First of all, there is nothing inherently symmetric about this protocol. Bob doesn't have to send $H(y_1), \ldots, H(y_n)$. If he doesn't, then Alice doesn't learn anything. I think two-sided output vs one-sided output is a red herring for this question.

The naive hashing protocol is vulnerable to the following kind of attack. Suppose that after the protocol is finished Bob learns of a special value $v$ that he couldn't have predicted before the protocol (e.g., the $x_i$'s and $y_i$'s are email addresses and he just learned the email address $v$ of an important person, which he didn't know before). Now Bob can test with certainty whether $v$ was in Alice's set, by checking whether $H(v)$ was among the values she sent. The protocol continues leaking information after it's over.

In the extreme case, the $x_i$ values can come from a small domain (e.g., phone numbers, SSNs) and Bob can simply do an exhaustive brute force attack to learn all of Alice's $x_i$'s.


Difference with secure PSI

The important property of real PSI protocols is that they prevent this kind of an attack, where one of the parties can check after the fact whether their opponent was holding some value. In a truly secure PSI protocol, if Bob wants to know whether Alice has an item $v$, he has to include $v$ in his set at the time of interaction. It should do him no good to speculate about $v$ after the protocol is finished. The PSI protocol leaks the intersection of $X \cap Y$ once, and no more information about $X$ and $Y$ is leaked thereafter.


Example / better mental model for PSI

A good way to think about PSI protocols is that they do the naive hashing protocol, except the common hash function $H$ is something that requires a secret key from both parties. Something like $H(x) = H_{\alpha,\beta}(x)$ where $\alpha$ is a key that only Alice knows and $\beta$ is a key that only Bob knows. Since both parties contribute a secret key to the computation, you have to assume that Alice & Bob have a way of computing such an $H$ interactively, in a way that no one learns the inputs to $H$ -- only the outputs.

(Note: not all PSI protocols actually work this way, but this approach is secure and it gives the right intuition about PSI security.)

If Bob tries to do this after-the-fact attack, he will find that he can't compute $H(v)$ on his own. He doesn't have Alice's key to this $H$. This is why the computation of $H$ was interactive in the protocol. And, since the protocol has terminated, Alice will not agree to help compute $H$ on additional inputs.

$\endgroup$
  • $\begingroup$ I don't know why you went so far as to computing information after the protocol. Upon receiving $H(x_1),...,H(x_n)$ from Alice, Bob can brute force the possible values of $x_i$ in order to learn Alice's input. Unless the $x_i$ are guaranteed to have high entropy (which is rarely the case), this reveals everything to Bob. $\endgroup$ – Yehuda Lindell Dec 16 '18 at 17:22
  • $\begingroup$ True, if Bob never sends anything then there is no difference between "after the fact" and "upon receiving $H(x_i)$'s from Alice." $\endgroup$ – Mikero Dec 16 '18 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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