Private Set Intersection (PSI)

The core security property of PSI ensures that participants learn only the intersection of their datasets. No information is revealed about the elements that are unique to any party. This is achieved through cryptographic techniques like oblivious transfer, homomorphic encryption, or Diffie-Hellman key exchange combined with hash functions.

PSI protocols can be configured to produce different types of outputs:

• Plain PSI: Parties learn which specific items they have in common.
• PSI-Cardinality: Parties learn only the number of intersecting items, not the items themselves.
• PSI with Associated Data: When an intersection is found, one party can reveal associated data (e.g., a user's risk score) for the matched item.

PSI scales beyond two participants:

• Two-Party PSI: The most common and efficient variant, involving a direct computation between two entities.
• Multi-Party PSI (MPSI): Allows three or more parties to compute the common intersection of all their private sets. This is significantly more complex and computationally intensive but enables broader consortium analysis.

PSI protocols are designed with different adversarial models:

• Semi-Honest (Passive) Security: Assumes parties follow the protocol but may try to learn extra information from the messages they receive. Most practical PSI implementations use this model for efficiency.
• Malicious (Active) Security: Protects against parties who may arbitrarily deviate from the protocol to cheat or learn private data. These protocols are more robust but come with higher computational and communication overhead.

Modern PSI protocols are optimized for large datasets. Key performance metrics include:

• Communication Complexity: The total data sent between parties. Modern protocols like ECNR or KKRT16 achieve linear communication overhead.
• Computational Complexity: The processing time required, often dominated by cryptographic operations like hashing or public-key encryption. Garbled Circuit-based PSI can be computationally heavy.
• Preprocessing: Some protocols allow for one-time, dataset-independent setup to drastically speed up future executions.

PSI is not a single algorithm but a family of protocols built from cryptographic primitives:

• Oblivious Transfer (OT): A fundamental primitive where a receiver gets one of several messages from a sender without the sender learning which was chosen.
• Homomorphic Encryption (HE): Allows computation on encrypted data; used in some PSI variants for set operations under encryption.
• Bloom Filters & Cuckoo Filters: Probabilistic data structures used in efficient, heuristic-based PSI to reduce communication costs, sometimes at the expense of perfect accuracy.

During pandemics, health authorities can use PSI to identify individuals who have been in contact with infected persons without exposing the identities of healthy individuals. For example, a user's phone can compute an intersection with a health authority's list of infection location hashes, revealing only if a match occurred. This protects user privacy while enabling epidemiological analysis.

• Privacy-Preserving Alerting: Users are notified of exposure without revealing their location history to the authority.
• Data Minimization: Authorities learn only the count of contacts, not their identities, unless a user voluntarily reports.

Financial institutions can collaboratively detect synthetic identity fraud or money laundering rings without sharing sensitive customer data. Using PSI, multiple banks can discover if the same identity (e.g., SSN, phone number) appears in their separate fraud alert lists.

• Regulatory Compliance: Enables collaboration for Anti-Money Laundering (AML) checks while adhering to data privacy laws like GDPR.
• Cross-Institutional Analysis: Uncovers coordinated fraud attacks across banks without leaking each bank's full client list or internal risk scores.

Advertisers and publishers (e.g., social media platforms) can measure campaign effectiveness—such as which ad viewers made a purchase—without sharing user-level data. They use PSI to find matches between the advertiser's customer database and the publisher's ad impression logs.

• Attribution Analysis: Determines conversion rates without the publisher learning who bought what, or the advertiser learning users' browsing habits.
• Privacy-First Analytics: Replaces traditional tracking pixels, aligning with increasing restrictions on third-party cookies and user tracking.

Research institutions or genealogy services can find genetic relatives by intersecting encoded DNA markers while keeping the vast majority of an individual's genetic data private. This is crucial for medical research and family tree building.

• Confidential Queries: A patient can query a research database for specific genetic disease markers without revealing their full genome.
• Kinship Discovery: Services like ancestry.com could implement PSI to let users find relatives without either party exposing their raw DNA data to the other.

Organizations can verify if a user's credential (e.g., email, ID number) is on a private watchlist or has been compromised in a breach. The service holding the breach database learns nothing about the querying user's credential if it is not on the list.

• Password Checkers: Services like 'Have I Been Pwned' can be enhanced with PSI, allowing users to check passwords against breach corpuses without sending the password in plaintext.
• Secure Onboarding: A company can screen a potential employee's ID against a confidential industry blacklist without obtaining the list itself.

Messaging apps (e.g., Signal, WhatsApp) need to discover which of a user's contacts are also on the platform. Naively uploading the entire address book to the server is a privacy risk. PSI allows the server to compute the intersection and inform the user of matches without learning the user's full contact list or the non-members' phone numbers.

• User Privacy: The service provider cannot build a social graph of non-users.
• Efficiency: Modern PSI protocols like ECDH-based PSI are efficient enough for mobile devices with large contact lists.

The security of a PSI protocol depends on its underlying trust model. Semi-honest (passive) adversaries follow the protocol but try to learn extra information, while malicious (active) adversaries may deviate arbitrarily. Most efficient PSI protocols assume a semi-honest model, requiring additional zero-knowledge proofs for malicious security, which significantly increases computational overhead. The choice of model directly impacts the required cryptographic primitives and the protocol's resilience to real-world attacks.

Achieving cryptographic privacy introduces inherent performance costs. Oblivious Transfer and Homomorphic Encryption-based PSI can require substantial computation per element. Communication complexity is also critical; naive protocols scale quadratically (O(n²)). Modern protocols like ECDH-PSI or KKRT16 achieve linear or near-linear scaling but still involve transmitting encrypted data structures like Bloom filters or Cuckoo filters, which can be large (e.g., several megabytes per million items). This limits real-time applicability for very large datasets.

Even a "leakage-free" PSI protocol can reveal metadata. The cardinality (size) of each party's input set is often revealed. The timing of protocol execution or network traffic patterns (side-channel attacks) could leak information about set sizes or similarities. Furthermore, if the intersection result itself is sensitive (e.g., a very small or very large result), that outcome conveys information. Protocols must be analyzed for what they explicitly leak beyond the intended intersection.

The theoretical security of a PSI protocol can be undermined by implementation flaws. Common issues include:

• Insecure randomness: Weak random number generation for cryptographic nonces or keys.
• Timing attacks: Execution time variations that correlate with secret data.
• Memory handling: Failure to securely wipe sensitive intermediate values from memory.
• Protocol misuse: Incorrect parameter selection (e.g., filter false-positive rates) that weakens security guarantees. These require rigorous code auditing and testing beyond the cryptographic design.

Many high-performance PSI protocols are designed for two parties with static input sets. Extending to multi-party PSI (MPSI) where N > 2 parties compute the common intersection introduces exponential complexity in rounds or communication. Supporting dynamic sets where inputs can be added or removed without re-running the entire protocol is non-trivial and often requires sacrificing efficiency or privacy. These settings often demand custom protocol designs with different trade-offs.

PSI security rests on the assumed hardness of mathematical problems. Most protocols rely on the Decisional Diffie-Hellman (DDH) assumption, Learning With Errors (LWE), or the security of specific symmetric cryptographic primitives. A future breakthrough in cryptanalysis (e.g., quantum algorithms breaking DDH) could retroactively compromise the privacy of all past PSI executions. This necessitates careful selection of post-quantum secure PSI protocols for long-term confidentiality.

Secure Multi-Party Computation (MPC) is the broader cryptographic framework that enables parties to jointly compute a function over their private inputs while keeping those inputs concealed. PSI is a specific, widely-used application of MPC. Key principles include:

• Input Privacy: No party learns anything beyond the output of the computation.
• Correctness: The output is guaranteed to be accurate as if computed by a trusted third party.
• Applications: Beyond set intersection, MPC is used for private auctions, fraud detection, and genomic analysis.

Zero-Knowledge Proofs (ZKPs) are cryptographic methods allowing one party (the prover) to prove to another (the verifier) that a statement is true without revealing any information beyond the validity of the statement. While distinct from PSI, they are often used in conjunction for enhanced privacy. For example, a ZKP can prove that an element is in a PSI result without revealing the element itself. Common types include zk-SNARKs and zk-STARKs, which are foundational to private blockchain transactions and identity systems.

Homomorphic Encryption is a form of encryption that allows computations to be performed directly on ciphertext, generating an encrypted result that, when decrypted, matches the result of operations performed on the plaintext. This property is crucial for certain PSI protocol constructions, particularly in cloud-based or outsourced computation scenarios. A server can compute the intersection over encrypted client data without ever decrypting it, ensuring end-to-end data confidentiality. It's classified by the operations it supports: partially, somewhat, or fully homomorphic.

Differential Privacy is a statistical technique that adds carefully calibrated noise to query results or datasets to prevent the identification of any single individual's data. It is complementary to PSI, which provides cryptographic privacy for the process of computing an intersection. Differential privacy is often applied after a PSI protocol to protect the output of the intersection, especially when releasing aggregate statistics, ensuring that the published results do not leak information about specific members of the private sets.

Private Information Retrieval (PIR) allows a client to retrieve an item from a database held by a server without the server learning which item was retrieved. This contrasts with PSI, where both parties hold private sets and want to learn their intersection. PIR is a one-sided privacy protocol focused on query privacy, while PSI is a two-party protocol focused on input privacy during a joint computation. Both are essential building blocks for privacy-preserving data systems.

Oblivious Transfer (OT) is a fundamental cryptographic primitive where a sender transmits one of several potential messages to a receiver, but remains oblivious to which message was received. It is a critical building block for many PSI protocols and MPC constructions. For instance, in a PSI protocol based on OT, one party can selectively retrieve only the elements corresponding to the intersection, without the other party learning the selection pattern. Efficient OT Extension protocols make large-scale PSI feasible in practice.

Variants of PSI that reveal only aggregated information, offering stronger privacy guarantees.

• PSI-Cardinality: Reveals only the size of the intersection (e.g., "We have 50 customers in common"), not the members themselves.
• PSI-Sum: Reveals the sum of associated values for intersecting items (e.g., "Our shared customers have a total balance of 1M tokens"), without identifying the individuals. These are crucial for privacy-preserving business intelligence.

Different PSI protocols optimize for specific constraints.

• Computation vs. Communication: Some protocols are computationally heavy but require few communication rounds, while others are lighter on CPU but require more data exchange.
• Semi-Honest vs. Malicious Security: Protocols are designed for different adversarial models, with malicious-secure versions being more robust but slower.
• Set Size Scalability: Techniques like hashing, bloom filters, and cuckoo hashing are used to handle sets with millions of items efficiently.

PSI is part of a broader toolkit for private computation.

• Zero-Knowledge Proofs (ZKPs): Prove a statement is true (e.g., "my data is in the set") without revealing the data itself. Complementary to PSI.
• Federated Learning: Train ML models on decentralized data; PSI can privately align datasets before training.
• Secure Enclaves (TEEs): Trusted Execution Environments like Intel SGX can be used to implement PSI, though they rely on hardware trust assumptions different from pure cryptography.