Private Set Intersection (PSI)

The primary guarantee of a PSI protocol. It ensures that no party learns anything about the other party's set elements except for the items in the intersection. A secure protocol reveals nothing about the size or contents of non-intersecting items.

• Strong Guarantee: Even if one party's set contains a single, highly sensitive element not in the intersection, the other party cannot infer its existence or value.
• Formal Models: Security is proven under standard cryptographic models like the semi-honest (honest-but-curious) or malicious adversarial models, defining what an adversarial party is allowed to do.

The protocol must correctly compute the intersection. All items that are truly common to both input sets must be in the output, and no items that are not common should appear.

• Deterministic Output: For given input sets, the output intersection is always the same.
• Handling Errors: Protocols must be robust against communication failures or cryptographic errors to maintain correctness. Some advanced PSI variants introduce a controlled, negligible error rate for performance gains, but this is explicitly defined (e.g., in PSI with False Positives).

Practical PSI protocols must be computationally feasible and scale to large sets (millions or billions of items). Performance is measured along three key axes:

• Computational Complexity: The time required for cryptographic operations (e.g., public-key encryptions, elliptic curve operations). Modern PSI-CA (Circuit-based) and PSI-DDH (Diffie-Hellman based) protocols offer near-linear complexity.
• Communication Overhead: The total amount of data sent between parties. Efficient protocols have communication costs linear in the set sizes, not quadratic.
• Round Complexity: The number of sequential back-and-forth messages. Single-round or two-round protocols are preferred for low-latency environments.

A critical property for real-world applications where one party's set (e.g., a service provider's user database) is vastly larger than the other's (e.g., a client's list). Efficient protocols handle this asymmetry.

• Example: A hospital (large set of patient records) intersecting with a research institute (small set of study participants).
• Protocol Adaptation: Specialized constructions like PSI with Unbalanced Sets optimize computation and communication relative to the size of the smaller set, often using techniques like Cuckoo hashing and Garbled Bloom Filters.

PSI is not a single operation; different protocol variants provide different output formats to suit application needs.

• Plain PSI: Outputs the actual intersecting items.
• PSI-Cardinality (PSI-CA): Outputs only the number of intersecting items, not the items themselves, offering an extra layer of privacy.
• PSI with Data Transfer: Upon intersection, one party can securely transfer payload data associated with the intersecting keys to the other party (e.g., transferring user attributes after matching IDs).
• Threshold PSI: Reveals the intersection only if its size exceeds a predefined threshold, preventing inference from small matches.

Protocols are designed and proven secure under specific assumptions about participant behavior.

• Semi-Honest Security: Assumes parties follow the protocol but may try to learn extra information from the messages they receive. This is the most common model for business collaboration scenarios.
• Malicious Security: Protects against parties who may arbitrarily deviate from the protocol to cheat or learn private data. These protocols are more complex and costly but essential for high-stakes or adversarial environments.
• Composability: A desirable property where the protocol remains secure even when run concurrently with other instances or as part of a larger system (e.g., within a Vertical Federated Learning pipeline for entity alignment).

PSI is the critical first step in Vertical Federated Learning (VFL), allowing two or more parties to securely identify their overlapping users or entities without revealing their entire datasets. This enables the creation of a virtual aligned dataset for training, where each party contributes different features about the same users.

• Process: A healthcare provider (with diagnoses) and a pharmacy (with prescriptions) use PSI to find their common patients.
• Outcome: They can train a model predicting readmission risk without ever exposing the full patient lists of either party.

Financial institutions and cybersecurity firms use PSI to collectively identify malicious actors while protecting customer privacy and proprietary threat lists. By computing the intersection of private sets of fraudulent transaction IDs, IP addresses, or compromised accounts, participants can gain a comprehensive view of threats.

• Key Benefit: Dramatically improves detection rates by pooling intelligence.
• Privacy Guarantee: A bank learns only if a specific account appears on another's blocklist, not the entire list.

PSI enables privacy-centric public health initiatives. During an outbreak, individuals' devices can use PSI to determine if they have been in proximity to a confirmed case without revealing their location history or identity. Similarly, research institutions can compute disease prevalence across regions without sharing sensitive patient rosters.

• Mechanism: Devices exchange encrypted, ephemeral identifiers; only matches (contacts) are revealed.
• Compliance: Aligns with regulations like HIPAA by minimizing data exposure.

Advertisers and publishers leverage PSI to measure campaign effectiveness—such as calculating how many users who saw an ad later made a purchase—without building cross-site user profiles. The advertiser (with purchase records) and the publisher (with ad impression logs) compute the intersection of their user IDs.

• Industry Shift: Moves away from third-party cookies and pervasive tracking.
• Output: The advertiser learns only the aggregate conversion count, not which specific users converted.

Research hospitals and biobanks use PSI to find patients with specific genetic markers across institutions without disclosing full genomic sequences. This enables cohort discovery for clinical trials or genome-wide association studies (GWAS) while preserving patient confidentiality.

• Precision: Can intersect sets based on specific variant carriers (e.g., BRCA1 mutation).
• Scale: Modern PSI protocols can efficiently handle sets containing millions of genetic identifiers.

Companies in a supply chain can use PSI to identify shared bottlenecks, like commonly out-of-stock parts, without revealing full inventory or supplier lists. A manufacturer and a distributor can find intersecting part numbers that are critically low, enabling proactive coordination.

• Business Intelligence: Reveals overlapping dependencies without exposing competitive sourcing data.
• Efficiency: Reduces the need for manual, trust-based data-sharing agreements.

Secure entity resolution is the privacy-preserving process of identifying records that refer to the same real-world entity (e.g., a customer ID) across multiple databases without revealing non-matching records. It is a critical prerequisite for entity alignment in Vertical Federated Learning (VFL).

• Core Function: Determines the overlapping set of entities between parties' datasets.
• Privacy Guarantee: Parties learn only which entities they have in common, not the full contents of each other's databases.
• Common Techniques: Often implemented using PSI protocols, but can also involve private matching based on fuzzy or composite keys.

A vertical data partition is a dataset split where different features (columns) of the same samples (rows/entities) are held by different parties. This structure is the defining characteristic of Vertical Federated Learning.

• Contrast with Horizontal FL: In horizontal FL, parties have different samples but the same features.
• Example: Hospital A holds patient lab results (features), while Hospital B holds patient imaging data (different features) for the same set of patients (entities).
• Implication: Training requires secure alignment of entities first, followed by collaborative computation across the split feature space.

A split neural network is a model architecture used in VFL where the neural network is divided into multiple parts, each residing on a different party that holds a specific subset of the features.

• Cut Layer: The specific layer where the model is divided. The feature owner computes the forward pass up to this layer, producing an intermediate output.
• Forward Propagation: The intermediate output is securely sent to the label owner, who completes the forward pass and computes the loss.
• Backpropagation: Gradients are passed backwards through the network across parties to update their respective model segments, a process known as vertical backpropagation.

Homomorphic Encryption (HE) is a cryptographic technique that allows computations to be performed directly on encrypted data. In VFL, it enables parties to train on encrypted intermediate outputs or gradients.

• Core Benefit: The label owner can perform computations (e.g., activation functions) on encrypted data from feature owners without decrypting it, preserving privacy.
• Trade-off: Introduces significant computation and communication overhead due to the size and complexity of ciphertext operations.
• Common Use: Often used to protect the intermediate results sent from feature owners to the label owner in a split neural network architecture.

Vertical secure aggregation refers to cryptographic protocols used to combine model updates (e.g., gradients from feature owners) in VFL without revealing any individual party's contribution.

• Privacy Goal: The label owner learns only the aggregated update (e.g., the sum of gradients), not the update from any single feature owner.
• Techniques: Can be implemented using Secure Multi-Party Computation (MPC) or masking techniques where individual updates are obscured by random values that cancel out upon summation.
• Contrast with Horizontal FL: In horizontal FL, secure aggregation protects client model weights; in VFL, it often protects feature-space gradients or intermediate results.

A vertical training protocol is the defined sequence of communication and computation steps that coordinating parties follow to execute a complete training round in a VFL system.

• Standard Steps: 1) Entity Alignment via PSI, 2) Vertical Forward Propagation, 3) Loss calculation by label owner, 4) Vertical Backpropagation, 5) Secure Aggregation of updates, 6) Model segment updates.
• Orchestration: Typically dictated by the label owner or a central coordinator.
• Framework Role: This protocol is the core logic implemented by Vertical FL frameworks like FATE or TensorFlow Federated for vertical scenarios.