Private Set Intersection (PSI)

Correctness guarantees that the protocol's output is accurate. If an item is in the intersection of all parties' private sets, the protocol will correctly include it. Conversely, items not in the intersection are excluded. This property ensures the utility of the protocol for downstream tasks like aligning user cohorts in vertical federated learning, where accurate data matching is critical for joint model training. A failure in correctness would render the protocol useless for its intended analytical purpose.

Privacy is the paramount security guarantee. It ensures that no party learns anything about the other parties' set elements beyond what is revealed by the final intersection itself. Formally, a party's view of the protocol (all messages received) should be computationally indistinguishable from a simulation that uses only that party's input and the final output. This prevents inference about non-intersecting items. Strong privacy definitions often require security against malicious adversaries who may arbitrarily deviate from the protocol, not just semi-honest ones who follow it but try to learn extra information.

A stricter subset of the general privacy property, input privacy specifically guarantees that nothing is leaked about the size of any party's private set. This is crucial because the cardinality of a dataset can be sensitive metadata. For example, in a healthcare federation, revealing that a hospital has 10,000 records for a specific rare disease could be a privacy breach. Advanced PSI protocols like those using oblivious transfer or homomorphic encryption can achieve input privacy, while simpler hash-based methods may leak set sizes.

Unlinkability ensures that if the protocol is executed multiple times, an adversary cannot determine if the same element was used by a party across different executions. This prevents long-term profiling. For instance, in a federated continual learning system where PSI is run periodically to find new overlapping users, unlinkability prevents a server from tracking a specific user's persistent presence across rounds. This property is often achieved through the use of fresh, random cryptographic tokens for each protocol execution.

This property defines what is revealed to each participant. In mutual PSI, all parties learn the intersection. In one-way PSI (or PSI with Authorization), only one designated party learns the intersection, while the other learns nothing. The latter is common in client-server architectures where a server holds a large dataset (e.g., a malware hash list) and a client wants to check its private data against it without revealing the server's entire set. The choice between mutual and one-way PSI is a key architectural decision.

These are practical performance properties critical for adoption.

• Computational Complexity: The runtime cost for each party, often measured in big O notation relative to set sizes (n, m). Modern PSI protocols aim for linear or near-linear complexity (O(n)).
• Communication Complexity: The total amount of data transmitted between parties. High communication overhead is a bottleneck in wide-area networks. Efficient protocols use techniques like hashing, bloom filters, and oblivious transfer extension to minimize rounds and bandwidth, making them feasible for large-scale federated learning deployments with millions of elements.

Financial institutions and cybersecurity firms can collaboratively identify common threats (e.g., fraudulent transaction IDs, malicious IP addresses, compromised accounts) without disclosing their full internal watchlists. Using PSI, each party learns only the intersecting indicators of compromise. This enables a collective defense posture while preserving competitive and regulatory boundaries that prevent raw data sharing. Multi-party PSI variants allow more than two entities to participate in this secure intelligence fusion.

Advertisers and publishers can measure the effectiveness of ad campaigns by calculating how many users who saw an ad (publisher's set) later made a purchase (advertiser's set). PSI allows this conversion calculation without the publisher learning who purchased or the advertiser learning the browsing history of users who didn't purchase. This addresses growing privacy regulations that restrict third-party cookie tracking and user identity linkage.

PSI is a core enabling technology for secure data clean rooms, which are controlled environments for joint data analysis. It provides the foundational 'join key' operation. Enterprises can combine first-party datasets (e.g., customer IDs) to enable joint analytics, audience segmentation, and model training within the clean room's trust boundary, ensuring raw data never leaves its origin. This is critical for media, retail, and cloud partnerships.

Vertical Federated Learning is a scenario where different organizations hold different features for the same or overlapping sets of users. PSI is a critical pre-processing step in VFL to securely identify the overlapping user cohort without exposing non-intersecting records. For example, a bank and an e-commerce company could use PSI to find their common customers before jointly training a model using the bank's credit history and the company's purchase data, aligning their datasets in a privacy-preserving manner.

Differential Privacy provides a statistical guarantee that the presence or absence of any single individual's data in a dataset does not significantly affect the outcome of an analysis. While PSI protects the raw sets during the alignment phase, DP is often applied afterward to the computation on the intersected data (e.g., model training or analytics). A common pattern is PSI + DP, where PSI securely finds the overlap, and DP-SGD is used to train a model on that overlap, ensuring end-to-end privacy.

Federated Analytics involves performing data analysis tasks (e.g., computing aggregates, histograms, or unique counts) over decentralized datasets without centralizing raw data. PSI is a core primitive for analytics tasks like cardinality estimation (e.g., 'How many unique users do both companies share?') or attribute concatenation for overlapping users. It enables businesses to gain collaborative insights, such as joint marketing reach analysis, while complying with data residency and privacy regulations.

Private Join and Compute is an advanced cryptographic protocol that extends PSI. It not only computes the intersection of two private sets but also allows the parties to perform a computation (e.g., sum, average, standard deviation) on associated attribute values for the matched records—all in a single privacy-preserving step. This is directly applicable to vertical federated learning, where after the private join, the parties can immediately compute aggregated statistics or gradients for the overlapping cohort.