Multi-party Private Set Intersection

Given \(n\) parties \(P_1, P_2, \ldots, P_n\), where each party \(P_i\) holds a private set \(X_i\) over a common domain \(\mathcal{U}\), MPSI computes the intersection \(\bigcap_{i=1}^n X_i\) such that:

• Correctness: The designated output party (typically \(P_1\)) learns exactly \(\bigcap_{i=1}^n X_i\).
• Privacy: No party learns any information about elements in other parties' sets beyond what can be inferred from the intersection and their own input.

The corruption model varies across protocols:

• Semi-honest: Adversaries follow the protocol but try to extract additional information from the transcript.
• Malicious: Adversaries may deviate arbitrarily from the protocol.
• Collusion resistance: Security holds even if up to \(t\) parties collude (with or without an honest majority).

The key challenges over two-party Private Set Intersection are:

• Scalability: Communication and computation tend to scale with the number of parties \(n\).
• Collusion: In two-party PSI, security is binary: one party is honest, one may be corrupt. In MPSI, any subset of parties may collude and combine their protocol views to extract information about honest parties' sets. The protocol must be simulatable for every possible coalition, which is a combinatorially harder security requirement. This is why many MPSI protocols restrict the corruption threshold or require an honest majority.

See [1] for a comprehensive classification. The main approaches are:

• Private homomorphic set representations (polynomials, hash sets, sorted multisets). Encode each set into a representation that supports a homomorphic operation \(+\) such that \(\mathsf{Dec}(\mathsf{Enc}(X_1) + \cdots + \mathsf{Enc}(X_n))\) yields the intersection. For example, represent sets as polynomials with elements as roots and use the property that a random linear combination \(r_1 P_1 + r_2 P_2\) preserves common roots while randomizing the rest.
• Leaky homomorphic set representations (Bloom filters, garbled Bloom filters). Same idea as above, but the encoding leaks some information (e.g., Bloom filters leak false positives through hash collisions).
• Aggregatable membership queries (Oblivious Programmable PRF, Oblivious Key Value Store, polynomial embeddings). Instead of combining set representations, test each candidate element for membership across all parties and aggregate the results. For example, using zero-sharing ([2]): each party \(P_i\) obtains a share \(s_i(x)\) for every element \(x\) such that \(\bigoplus_{i=1}^n s_i(x) = 0\). Each party then masks its set elements with its share via an Oblivious Programmable PRF. For an element in the intersection, all parties hold it, so the shares XOR to zero and the element is recognizable. For non-intersection elements, at least one share is pseudorandom, making the XOR indistinguishable from random.