Private Set Intersection (PSI)

PSI protocols provide formal cryptographic security guarantees, typically defined under the semi-honest (honest-but-curious) or malicious adversarial models. The core guarantee is that parties learn only the intersection of their sets. For items not in the intersection, they learn nothing—not even the size of the other party's set, unless the protocol is specifically designed to reveal it. This is stronger than simple data masking, as it prevents inference from the protocol's output pattern.

A primary differentiator between PSI protocols is their scalability, measured in computation (CPU time) and communication (data transferred).

• Early protocols (e.g., based on Diffie-Hellman) had linear communication overhead relative to set size.
• Modern protocols leverage oblivious transfers (OT), homomorphic encryption, or garbled circuits to achieve sub-linear or even constant communication overhead for large sets. Computation is often the bottleneck, with faster protocols using symmetric-key operations (like hashing) instead of expensive public-key cryptography.

While the core output is the intersecting items, protocol variants control what auxiliary information is revealed:

• Plain PSI: Reveals only the intersecting items to one or both parties.
• PSI-Cardinality: Reveals only the number of intersecting items, not the items themselves.
• PSI-Sum/PSI with Associated Data: For each intersecting item, also reveals a corresponding aggregated value (e.g., a sum of associated data) from the other party's set.
• Threshold PSI: Reveals the intersection only if its size exceeds a predefined threshold.

PSI protocols are designed for different collaboration scales:

• Two-Party PSI: The most common and optimized scenario, involving exactly two entities (e.g., a hospital and a research institute).
• Multi-Party PSI (MPSI): Allows three or more parties to compute the common intersection across all their private sets. This is significantly more complex, often requiring a star topology with a central aggregator or sophisticated peer-to-peer cryptographic routines.

In many real-world applications, one party has a large set (e.g., a service provider's user database) and the other a small set (e.g., a client's query list). Unbalanced PSI protocols are optimized for this scenario, shifting computational load to the party with the larger set to minimize work for the smaller, often client-side, party. This is crucial for mobile or edge computing applications where client resources are constrained.

PSI is not an isolated construct; it builds upon and relates to other core privacy-enhancing technologies (PETs):

• Secure Multi-Party Computation (MPC): PSI is a specific function computed under MPC frameworks.
• Oblivious Transfer (OT): A fundamental building block for many high-performance PSI protocols.
• Homomorphic Encryption (HE): Allows set elements to be encrypted and compared without decryption.
• Private Information Retrieval (PIR): Complementary to PSI; PIR hides what is retrieved, while PSI hides everything else.

During health crises like COVID-19, PSI protocols enabled decentralized contact tracing without centralized surveillance. Individuals' device logs of proximity encounters could be compared to a health authority's list of diagnosed cases to determine exposure risk, revealing only a binary 'exposed' or 'not exposed' result. This preserved individual location history while providing vital public health information.

• Key Mechanism: Private Information Retrieval (PIR)-style PSI, where the individual's device queries the health authority's set.
• Privacy Guarantee: The health authority learns nothing about an individual's movement patterns unless they are a confirmed case.
• Example: The PACT protocol (Private Automated Contact Tracing) used in several exposure notification systems.

Banks and financial institutions use PSI to collaboratively identify fraudulent actors or money laundering patterns without sharing their sensitive customer lists. Each bank holds a private set of account identifiers flagged for suspicious activity. By computing the intersection, the consortium can identify accounts or entities appearing across multiple institutions—a strong indicator of coordinated fraud—while keeping each bank's full internal watchlist confidential.

• Key Benefit: Enables cross-institutional threat intelligence while complying with data protection regulations like GDPR.
• Technical Nuance: Often employs Unbalanced PSI protocols optimized for the scenario where one party (e.g., a regulatory body) has a much smaller set than the other (a large bank).

In medical research, PSI allows hospitals or biobanks to find common patients or genomic sequences across institutions to enable larger cohort studies. For instance, a researcher can discover if patients with a specific rare genetic variant exist in multiple private genomic databases. Only the identifiers of matching patients are revealed (with consent), not the full genetic data of non-matches, preserving patient privacy and institutional data sovereignty.

• Application: Accelerating rare disease research by finding sufficient patients across fragmented healthcare systems.
• Related Protocol: Private Set Intersection-Cardinality (PSI-CA) can be used first to determine if a statistically significant overlap exists before revealing specific matches.

PSI solves a core privacy challenge in digital advertising: measuring which users who saw an ad later made a purchase, without the advertiser and publisher fully merging their customer lists. The advertiser provides a set of user identifiers who converted (e.g., purchased a product). The publisher (e.g., a social media platform) provides a set of identifiers who were shown the ad. PSI computes the overlap—the conversion rate—without either party learning the other's full list.

• Industry Shift: A foundational technology for privacy-centric advertising models post third-party cookie deprecation.
• Efficiency Requirement: Demands high-performance PSI capable of intersecting sets with millions of entries in near real-time.

Services like 'Have I Been Pwned' use a form of PSI to allow users to safely check if their passwords or email addresses have been exposed in a data breach. The user submits a transformed version of their credential (e.g., a hash prefix). The service, which holds billions of breached records, performs a private lookup and returns only the information relevant to that user's query. The user's full credential is never sent to the service in plaintext, and the service learns nothing about the user's query if there is no match.

• Protocol Used: Often a client-server PSI with hashing and bloom filters for efficient, private membership testing.
• Security Impact: Prevents users from inadvertently exposing their current passwords to a third-party service during a breach check.

Competing companies in a shared supply chain can use PSI to identify common, high-risk vendors or geopolitical exposures without disclosing their full supplier lists. For example, automotive manufacturers could privately determine if they all rely on a single sub-component factory in a region prone to disruptions. This enables collective risk mitigation and business continuity planning while protecting strategic supplier relationships and competitive information.

• Multi-Party Use Case: Often extends beyond two parties to Multi-Party PSI (MPSI), involving several entities.
• Integration: Can be combined with Secure Multi-Party Computation (MPC) to privately compute aggregate statistics (e.g., total spend) on the intersecting set.