SoK: Collusion-resistant Multi-party Private Set Intersections in the Semi-honest Model

SoK: Collusion-resistant Multi-party Private Set Intersections in the Semi-honest Model

Speakers: Jelle Vos; Mauro Conti; Zekeriya Erkin

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=cCt5978yfuE

Overview

This article delves into the Systematization of Knowledge (SoK) paper titled "SoK: Collusion-resistant Multi-party Private Set Intersections in the Semi-honest Model," presented by Jelle Vos in collaboration with his promoters Mauro Conti and Zekeriya Erkin. The work provides a comprehensive overview and analysis of Multi-party Private Set Intersection (MPSI) protocols, a critical area in privacy-preserving computation. MPSI protocols enable n parties, each holding a private set of at most K elements, to compute the intersection of their sets without revealing any information about elements not in the intersection. The focus of this SoK is specifically on collusion-resistant MPSI protocols operating within the semi-honest model, meaning parties honestly follow the protocol but may attempt to infer additional information from the data they observe.

The primary motivation behind this research is to address the current landscape of MPSI, which, despite a proliferation of proposed protocols, lacks practical deployments. The authors aim to provide a high-level overview, analyze the general performance characteristics of these protocols, and identify common pitfalls that hinder their real-world applicability. By classifying existing approaches and highlighting key insights, this paper serves as a vital resource for researchers and practitioners navigating the complexities of privacy-preserving set operations, ultimately striving to bridge the gap between theoretical advancements and practical implementations.

Background

▶ Watch: Introduction to MP-PSI and research goals (0:00)

The concept of Private Set Intersection (PSI) originated as a two-party problem, allowing two entities to find common elements in their datasets without exposing the non-common ones. Multi-party Private Set Intersection (MPSI) extends this to n parties, each contributing a private set. The goal is for a designated "leader" party to obtain the final intersection, or for all parties to learn it, while ensuring that no party learns any information beyond the intersection itself. This talk specifically focuses on MPSI in the semi-honest model, where all parties are assumed to follow the protocol specifications honestly, but may attempt to derive additional information from the messages they receive. A crucial aspect is collusion resistance, meaning the protocol remains secure even if up to T parties collude to pool their information.

The foundation of MPSI protocols often relies on various set representation techniques, which encode the input sets in a way that facilitates private computation. The paper categorizes and analyzes several key representations:

1. Bit Set Representation: This is the simplest method, where a set is represented as a bit vector corresponding to a universal set U. Each bit is set to 1 if the corresponding element is in the set and 0 otherwise. Intersection is computed via a simple bitwise AND operation. While highly efficient for intersection, bit sets suffer from a significant drawback: their size grows linearly with the size of the universal set U. For large universes, such as IP addresses (2^32 possible values), this becomes prohibitively large, requiring 2^32 bits of storage. However, for small, constrained universes (e.g., in voting systems), bit sets can be very efficient.

1. Bloom Filter: An approximate probabilistic data structure that compactly represents a set. It consists of a bit array that is initially all zeros. To insert an element, multiple hash functions are applied, and the bits at the resulting indices are set to 1. Combining Bloom filters for intersection also involves a bitwise AND operation. A key characteristic of Bloom filters is the potential for false positives: an element might appear to be in the set even if it was never inserted, though false negatives are not possible. Querying a Bloom filter for membership involves checking if all bits corresponding to an element are set. The trade-off is space efficiency versus the probability of false positives.

1. Hashed Bloom Filter: Similar to a Bloom filter but typically uses only a single hash function, making it less space-efficient than a standard Bloom filter for a given false positive rate. It can be analyzed using similar principles.

1. Polynomial Roots Encoding: This elegant technique represents a set by constructing a polynomial whose roots are precisely the elements of the set. For instance, if a set contains elements x1, x2, x3, the polynomial would be (X - x1)(X - x2)(X - x3). Membership can be checked by evaluating the polynomial at a given element; if the result is zero, the element is in the set. This method is particularly convenient for operations under arithmetic, making it well-suited for cryptographic schemes like homomorphic encryption.

The paper introduces a novel systematization of MPSI protocols by grouping them into three high-level constructions based on how and when information is aggregated and revealed:

1. Private Homomorphic Set Representations: In this paradigm, parties first aggregate their encrypted or secret-shared input sets into a combined, homomorphic representation. This aggregated representation itself directly encodes the intersection. Once this final representation is formed, it can be fully revealed, and the leader can then query it offline to extract the intersection elements. Bit sets are a prime example of this, as the bitwise AND of individual bit sets directly yields the bit set of the intersection.

1. Leaky Homomorphic Set Representations: Here, parties also aggregate their inputs into a combined representation. However, this aggregated representation does not directly or perfectly represent the intersection in a way that can be revealed without leaking additional information. Therefore, queries against this representation must be performed privately, typically using secure computation techniques (e.g., homomorphic encryption or secure multi-party computation). Only the output of these private queries (i.e., whether an element is in the intersection) is revealed. Bloom filters fall into this category because a combined Bloom filter might indicate the presence of an element that is not truly in the intersection, due to false positives. Revealing the combined Bloom filter directly would leak information about individual sets.

1. Aggregatable Membership Queries: This approach reverses the flow. Instead of aggregating set representations first, individual parties first perform private membership queries on their own sets. The results of these individual (and private) membership queries are then aggregated, and finally, the aggregated query results are revealed. Polynomial roots encoding can be used in this manner, where parties privately evaluate their polynomials for a candidate element, and these evaluations are then combined to determine if the element is in the global intersection.

These three high-level constructions are argued to encompass all possible MPSI protocol designs. The reasoning is that if aggregation occurs after revealing individual set representations, there is an inherent risk of leaking information about the individual sets, which violates the privacy requirements of MPSI.

Key Findings

▶ Watch: Understanding Bloom filter approximate set data structures (2:45)

The SoK paper presents three crucial takeaways that highlight the current state and future directions of MPSI research:

1. Parameters for MPSI Protocols Are Not Yet Known

Despite the existence of dozens of MPSI protocols in academic literature, there is a striking absence of practical deployments. One significant reason is the lack of clarity regarding real-world parameters. The authors note that it is relatively straightforward to design a new MPSI protocol by combining any set representation with any secure computation technique. However, choosing the "right" protocol for a given application is exceedingly difficult because critical variables influencing performance are not well understood in practical settings. These variables include:

• Number of parties (n)
• Number of elements per set (K)
• Number of colluding parties (T)
• Desired false positive probability (ε)
• Hardware specifications (e.g., CPU, number of threads)
• Network characteristics (e.g., latency, throughput)

Different protocols perform optimally under different conditions. For instance, some protocols might scale better with a high number of threads, while others are efficient even with limited parallelism. This makes direct comparisons challenging and prevents the identification of a universally "best" protocol, emphasizing that the optimal choice is always context-specific.

2. Old Insights Are Still Relevant

A notable observation is that many recent MPSI papers tend to overlook or not fully account for earlier, foundational works. To illustrate this, the authors instantiate and compare three different MPSI protocols, all relying on additively homomorphic encryption, specifically elliptic curve-based ElGamal:

• Chet all (2012): Uses a polynomial roots encoding as a private homomorphic set representation.
• B all (2016): Leverages Bloom filters as a leaky homomorphic set representation.
• J all (2018): Employs polynomial roots encoding as an aggregatable membership query protocol.

By instantiating these diverse protocols with the same underlying cryptographic primitive, the authors are able to measure and compare their costs in a standardized manner, specifically in terms of the number of elliptic curve multiplications. The comparison reveals that each protocol demonstrates strengths in different areas:

| Protocol (Year) | Set Rep. / Protocol Type | Colluders (T) | Parties (N) | False Positive (E inverse) | Leader Ops (EC Mults) | Assistant Ops (EC Mults) | Total Complexity (EC Mults) |

| :-------------- | :----------------------- | :-------------- | :------------ | :--------------------------- | :--------------------- | :----------------------- | :--------------------------- |

| B all (2016) | Bloom Filter / Leaky HSR | T | N | E | Low | Moderate | Moderate |

| Chet all (2012) | Poly Roots / Private HSR | T | N | K | Moderate | Low | Moderate |

| J all (2018) | Poly Roots / Aggregatable MQ | T | N | K | Moderate | Moderate | Lowest (often) |

(Note: The table above is a conceptual representation based on the speaker's discussion and general findings, as exact numerical values for all cells were not provided for all protocols, but the relative strengths were highlighted.)

For example, the work by B all might require fewer operations on the leader side, while Chet all might be more efficient for assistant parties. J all's protocol, in some configurations, could offer the lowest total complexity. This underscores that there is no single "best" protocol; the optimal choice depends on which computational burden (e.g., leader, assistant, total) needs to be minimized for a specific application.

3. Protocol Descriptions Should Be Sufficiently General

The final takeaway advocates for more abstract and general descriptions of MPSI protocols. The authors identify two useful abstract primitives:

• Oblivious Key-Value Stores: These stores hold key-value pairs. When queried with an unknown key, they return randomness. When queried with a known key, they return the exact stored value, without revealing which key was queried.
• Encrypted Membership Query Filters (EMQFs): These filters store sets and, when queried on an element, return a ciphertext encrypting zero if the element is in the set, and a non-zero encryption with high likelihood otherwise.

The paper also critiques the common development paradigm: starting with a two-party PSI (2PC PSI), extending it to multi-party semi-honest, and then to the malicious model. While this progressive approach can be beneficial, some papers directly propose malicious MPSI protocols, which significantly complicates analysis and obscures the high-level understanding. Using general primitives (e.g., treating additively homomorphic encryption as a black box) rather than specific instantiations (e.g., Paillier encryption) makes protocols easier to compare and analyze. Furthermore, some protocols are so high-level that they might be better described using abstract arithmetic circuits rather than specific secure computation primitives, enhancing clarity and generality.

Technical Deep Dive

▶ Watch: Polynomial roots encoding for set elements (4:10)

The systematization proposed by Vos, Conti, and Erkin provides a crucial framework for understanding the diverse landscape of MPSI protocols. Let's delve deeper into the technical nuances of their classification and the comparative analysis.

MPSI Protocol Classification

The three high-level constructions — Private Homomorphic Set Representations, Leaky Homomorphic Set Representations, and Aggregatable Membership Queries — are not merely descriptive categories but define fundamental architectural differences in how privacy and intersection are achieved.

1. Private Homomorphic Set Representations (PHSR):

• Mechanism: In PHSR, each party P_i holds a set S_i. They transform their S_i into a homomorphic representation R_i (e.g., an encrypted bit set or a secret-shared polynomial). These R_i are then combined or aggregated into a final representation R_intersection. The critical property here is that R_intersection is intrinsically the representation of the desired intersection S_1 ∩ S_2 ∩ ... ∩ S_n.
• Privacy: Since R_intersection only contains information about the intersection, it can be fully revealed to the designated leader (or all parties). The leader can then deterministically extract the intersection elements from R_intersection without any further private computation.
• Example: Bit sets are the canonical example. If R_i is a bit set for S_i, then R_intersection = R_1 AND R_2 AND ... AND R_n (bitwise AND) directly yields the bit set for the intersection. The challenge lies in performing this AND operation homomorphically or securely. For instance, parties could secret-share their bit sets, and then perform distributed AND operations, revealing the final secret-shared result to the leader.

1. Leaky Homomorphic Set Representations (LHSR):

• Mechanism: Similar to PHSR, parties aggregate their input sets into a combined representation R_combined. However, unlike PHSR, R_combined is not a perfect representation of the intersection. It might contain "noise" or "leakage" that would reveal information beyond the intersection if revealed directly.
• Privacy: To extract the intersection, private queries must be performed on R_combined. This means that if the leader wants to check if element x is in the intersection, they must perform a secure computation (e.g., using homomorphic encryption or secure multi-party computation) to query R_combined for x. Only the result of this query (e.g., yes/no) is revealed. The underlying representation R_combined itself is never fully revealed.
• Example: Bloom filters are the primary example. If parties combine their Bloom filters via bitwise AND, the resulting Bloom_combined can have false positives. If Bloom_combined were revealed, an adversary could learn about elements that were not in the intersection but appear to be due to false positives. Therefore, to ensure privacy, queries like "Is x in Bloom_combined?" must be answered using techniques like private information retrieval (PIR) or homomorphic encryption, where the query itself and the intermediate computation remain private.

1. Aggregatable Membership Queries (AMQ):

• Mechanism: In AMQ, the focus shifts from aggregating representations to aggregating query results. For a given candidate element x, each party P_i privately determines if x is in their set S_i. This check produces a private "membership bit" (e.g., 1 if x is in S_i, 0 otherwise). These individual membership bits are then securely aggregated (e.g., summed up, or ANDed) to determine if x is in the global intersection (i.e., if all parties have x).
• Privacy: Only the aggregated result of the membership query for x is revealed. No individual party's membership bit for x is ever disclosed. This is particularly effective when the set of candidate elements to check is known or can be privately generated.
• Example: Polynomial roots encoding fits well here. For a candidate element x, each party P_i evaluates their polynomial P_i(x) (which is 0 if x is in S_i). These P_i(x) values (or transformations thereof) are then combined using homomorphic properties. If the combined result indicates x is a root for all polynomials, then x is in the intersection. For instance, parties could homomorphically encrypt P_i(x) and send them to the leader, who then homomorphically sums them. If the sum is zero, x is in the intersection.

Comparative Analysis with Elliptic Curve ElGamal

The speaker's comparison of protocols by Chet all, B all, and J all, instantiated with elliptic curve-based ElGamal, provides concrete insights into their performance trade-offs. ElGamal is an additively homomorphic encryption (AHE) scheme, meaning E(a) * E(b) = E(a+b). This property is fundamental for many MPSI constructions, allowing encrypted values to be combined without decryption.

The cost metric, elliptic curve multiplications, is a standard measure of computational complexity for such schemes. The concept of "cheap multiplications" (valued at 0.25 standard multiplications) refers to operations that can leverage pre-computation or specific curve properties to be performed more efficiently.

• B all (Bloom Filters): This protocol's strength often lies in potentially lower communication overhead due to the compact nature of Bloom filters. However, managing false positives and performing secure queries on a combined Bloom filter can introduce significant computational complexity, especially for the leader who might be responsible for querying. The speaker notes it requires "very few operations on the leader" in some contexts, suggesting an optimized distribution of work.

• Chet all (Polynomial Roots - PHSR): This protocol might involve more complex polynomial operations but, as a PHSR, once the final intersection polynomial is formed (potentially through complex homomorphic operations), the extraction of elements might be simpler than repeated private queries. The speaker indicates "few operations on the assistant," implying assistants contribute significantly to the initial homomorphic aggregation.

• J all (Polynomial Roots - AMQ): This approach, by querying individual sets and aggregating results, might distribute computation more evenly. The claim that it often yields the "lowest total complexity" suggests that its strategy of aggregating membership queries, possibly through homomorphic sums of encrypted P_i(x) values, is efficient overall, even if individual steps are complex.

This detailed comparison underscores the point that no single MPSI protocol is universally superior. The optimal choice is a function of the specific operational constraints: whether minimizing leader burden, assistant burden, or total computation is paramount, alongside considerations like network bandwidth and the acceptable level of false positives.

General Primitives

The call for more general protocol descriptions is a critical plea for standardization and clarity in MPSI research.

• Oblivious Key-Value Stores: These are powerful abstractions. An MPSI protocol could, for example, use an OBLIVIOUS KEY-VALUE STORE to store elements from combined sets, allowing parties to query for intersection elements without revealing which elements they are querying or what values are stored for non-intersection elements. This simplifies the high-level design by abstracting away the complex cryptographic primitives used to build the OBLIVIOUS KEY-VALUE STORE itself.

• Encrypted Membership Query Filters (EMQFs): These primitives are directly applicable to the AMQ paradigm. Instead of detailing how parties homomorphically evaluate polynomials or combine Bloom filters, one could simply state that the protocol uses an EMQF to check for membership. The EMQF would hide the actual set content and only reveal an encrypted zero if an element is present, allowing for secure aggregation of query results. This level of abstraction enables researchers to focus on the MPSI logic rather than the underlying cryptographic mechanics.

The shift from specific cryptographic instantiations (like Paillier) to general primitives (like AHE as a black box) is crucial for facilitating comparisons and preventing the "reinvention of the wheel." Furthermore, describing high-level protocols using arithmetic circuits provides a language-agnostic and cryptosystem-agnostic way to express computation, which can then be instantiated with various secure computation techniques.

Demo / Proof of Concept

▶ Watch: Takeaway 1: MP-PSI protocol parameters are unknown (7:50)

As this talk presents a Systematization of Knowledge (SoK) paper, it focuses on analyzing, classifying, and comparing existing MPSI protocols rather than introducing a new one or demonstrating a specific implementation. Therefore, no live demo or proof of concept was presented as part of this research. The contribution lies in the comprehensive analytical framework and insights derived from existing literature.

Defensive Implications

▶ Watch: Takeaway 2: Older MP-PSI insights remain relevant (9:20)

The insights from this SoK paper offer several crucial defensive implications for practitioners and researchers building or deploying MPSI systems:

1. Beware of Leaky Set Representations: The most direct defensive implication is to never treat leaky homomorphic set representations (like Bloom filters) as if they were private ones. Releasing an aggregated Bloom filter directly, without performing queries under encryption, constitutes a significant privacy breach. As the talk highlights, this leaks substantial information about the input sets beyond the actual intersection due to the inherent probabilistic nature and false positives of Bloom filters. Defenders must ensure that any aggregated representation that is not a perfect, deterministic encoding of the intersection is only queried via secure computation mechanisms.

1. Ensure Robust Randomness Generation: The security of many MPSI protocols hinges on the quality and independence of randomness. A critical pitfall identified is the use of unsafe randomness.

• Leader-Provided Randomness: Never allow the leader party to be the sole source of randomness, especially if the leader might collude with assistant parties. If the leader, who eventually holds combined values, can also control the randomness, they can potentially "derandomize" the protocol's operations and learn sensitive information that would otherwise be protected.
• Set-Dependent Randomness: Randomness should be independent of the parties' input sets. If randomness is only introduced or altered based on the presence or absence of specific elements in a party's set, it reduces the overall security of the protocol. A small number of parties having a certain element could lead to "less secure randomness" for that element, making it vulnerable to attacks. Defenders must implement robust, cryptographically secure pseudo-random number generators (CSPRNGs) and ensure that randomness is generated in a distributed, independent, and verifiable manner.

1. Understand Malicious Model Challenges: While the paper primarily focuses on the semi-honest model, it explicitly warns that adapting protocols to the malicious model introduces significant additional challenges. Malicious adversaries might deviate from the protocol arbitrarily to learn information or disrupt computation. The examples of Abadi et al. (showing fragilities in polynomial roots encoding) and Q et al. (demonstrating attacks where malicious assistants can learn the intersection when only the leader should) underscore this. Defenders planning to deploy MPSI in adversarial environments must perform rigorous security analyses specifically for the malicious model, as semi-honest security guarantees do not automatically translate. This might necessitate the use of zero-knowledge proofs or other more complex cryptographic tools, increasing computational overhead.

1. Context-Specific Protocol Selection: There is no one-size-fits-all MPSI protocol. Defenders must perform a thorough analysis of their specific application context to choose the most appropriate protocol. This involves evaluating:

• The number of parties and their computational capabilities.
• Network latency and bandwidth constraints.
• The size of input sets and the universal set.
• The acceptable level of false positives (if using probabilistic structures).
• The security model (semi-honest vs. malicious) and the maximum number of colluders (T).
• The specific performance metrics to optimize (e.g., total computation time, leader's burden, communication costs).

This requires a deep understanding of the trade-offs highlighted in the SoK paper.

1. Embrace General Primitives for Design and Auditing: When designing or integrating MPSI solutions, defenders should advocate for and leverage abstract primitives like Oblivious Key-Value Stores and Encrypted Membership Query Filters. This approach simplifies protocol descriptions, makes security analysis more manageable by abstracting away low-level cryptographic details, and facilitates comparison with other designs. Using well-defined, abstract building blocks can lead to more robust and auditable MPSI implementations.

Key Takeaways

• Real-world parameters for Multi-party Private Set Intersection (MPSI) protocols remain largely unknown, hindering practical deployments and making it difficult to select the optimal protocol for specific applications.
• Despite numerous MPSI protocols, no single solution is universally "best"; performance is highly dependent on diverse variables including hardware, network, number of parties, and desired security properties.
• Foundational insights from older MPSI research are still highly relevant and should not be overlooked by modern protocol designers, as demonstrated by the comparative analysis of existing schemes.
• Protocol descriptions should be sufficiently general and abstract, utilizing primitives like Oblivious Key-Value Stores and Encrypted Membership Query Filters (EMQFs), to facilitate easier comparison, analysis, and understanding.
• The secure generation and management of randomness are paramount; protocols must avoid unsafe practices such as leader-dependent or set-dependent randomness, which can lead to privacy breaches.
• Defenders must be acutely aware that adapting MPSI protocols from the semi-honest to the malicious model introduces significant new vulnerabilities and requires dedicated security analysis beyond semi-honest guarantees.

About the Speaker(s)

Jelle Vos is a PhD student who presented this Systematization of Knowledge (SoK) paper. This work was conducted closer to the start of his PhD research.

Mauro Conti is one of Jelle Vos's promoters, collaborating on this research.

Zekeriya Erkin is also one of Jelle Vos's promoters, contributing to the development of this SoK paper.