# Secure multi-party private set intersection: Protocols supporting MULTI-party VS supporting TWO-party

Let assume party $$B$$ wants to receive secure multi-party computation (MPC) output.

The are many private set intersection (PSI) protocols that support only two parties but they cannot support multi-party. In this case, party $$B$$ needs to run PSI with party $$A$$. Then $$B$$ uses the result as the input and runs two-party PSI with party $$C$$ and, so on. However, this setting leaks more information to client $$B$$, than the protocol supporting, multi-party PSI.

• Example: let computation be "set intersection"

Assume party $$A$$ has $$S_{A}=\{1,2,3\}$$

party $$B$$ has $$S_{B}=\{1,2\}$$

party $$C$$ has $$S_{C}=\{2,5\}$$

Party $$B$$ in the protocol only supporting two-party receives:

1- $$K=S_A\cap S_B=\{1,2\}$$

2- $$K'=S_C \cap S_B=\{2\}$$

Then, it finds $$K\cap K'=\{2\}$$. So it learns party A has $$1$$ but party C does not have $$1$$.

In contrast, if a protocol could support multi-party client B would only learn the intersection of all sets that is $$\{2\}$$.

Question: What are the real-world applications (examples) of multiple-party PSI?

So I can use the examples to show/justify that protocol supporting multi-party PSI is better (in terms of security) than those only supporting two-party.

• Do you have any justifiable application for two-party PSI? If so, would it not naturally extend to the multi-party setting? Aug 15 '16 at 12:03
• @GuutBoy may be may be not!!! Aug 15 '16 at 12:09
• @GuutBoy Because the party who recieves the result can run two-party protocol so it engages with one of the parties and do the same for the other parties. According to PSI definition, this is secure. Bu t, as we can see from the question there are some data leakage. Thus, I need a concret example to justify multiple PSI protocol. Aug 15 '16 at 12:20
• I disagree, your example clearly shows that simply using two-party PSI multiple times is not secure in the multi-party setting. The party learning the output learns more than he is supposed to, i.e., the intersection of the three sets. Aug 15 '16 at 12:29

I think that you are mixing between the terms "applications" and "implementation", let me explain.

In your question you took some secure two-party computation (2PC) and you showed that when using it in a "black-box" fashion and also each party gets the result of the computation on each pair of the inputs then the protocol leaks a lot of information that should not be leaked. This is true. But it doesn't mean that a secure multi-party computation (MPC) is useless! It just simply means that the protocol that you described (using 2PC) is leaking information and thus it is not secure!.

This multiparty set intersection is INDEED an application for MPC, it is just not implemented as you said but has some designated protocol that implements it (not necessarily through 2PC).

I hope that it clarifies the things.

• Thank you for the answer. But, the two party protocol outlined above is secure that is why client B only learns the intersection. I did not say secure MPC is useless (in any setting). I want to find some applications to justify a secure MPC protocol supporting multi-client leaks less information that if we have to run two-party computation multiple times with different parties. Aug 14 '16 at 12:30
• So your question is not well-defined. You are not looking for applications for MPC but rather applications for MPC that computes some function $y_1,\ldots,y_n=f(x_1,\ldots,x_n)$ by computing the functions $y_i,y_j=f(x_i,x_j)$ for all $i,j\in[n]$ and leaks $f(x_i,x_j)$ to party $p_i$ for all $j\in[n]$ such that these leaks don't harm the privacy.
– Bush
Aug 14 '16 at 12:46
• Yes, I need some application of multi-party PSI. I will edit the question. Aug 14 '16 at 12:49