Glossary

Private Set Intersection (PSI)

A cryptographic protocol allowing two parties to compute the intersection of their private datasets without revealing any elements outside the intersection to the other party.

Get in touch Learn more

Data scientist building training data pipeline on laptop, data preprocessing visible, technical workspace.

CRYPTOGRAPHIC PROTOCOL

What is Private Set Intersection (PSI)?

A cryptographic protocol enabling two parties to compute the intersection of their private datasets without revealing any elements outside the intersection to the other party.

Private Set Intersection (PSI) is a secure multi-party computation protocol where two parties, each holding a private set, jointly compute the intersection of their sets while revealing nothing beyond the intersecting elements. The protocol ensures that Party A learns only which of its elements also exist in Party B's set, and Party B learns only which of its elements exist in Party A's set, with no additional information leakage.

PSI protocols are foundational to privacy-preserving machine learning and secure data collaboration, enabling use cases like private contact discovery, encrypted database joins, and fraud detection across institutions. Modern implementations leverage techniques such as Oblivious Transfer (OT) extensions, Diffie-Hellman key exchange, or Homomorphic Encryption (HE) to achieve linear communication complexity, making them practical for datasets containing millions of elements.

CRYPTOGRAPHIC GUARANTEES

Key Properties of PSI Protocols

Private Set Intersection protocols are defined by their security model, efficiency, and the specific guarantees they provide beyond the core intersection functionality. These properties determine suitability for different deployment scenarios.

Correctness

The fundamental guarantee that the protocol outputs the exact intersection of the two input sets. At the end of the computation, the client learns precisely which elements are common to both parties, and nothing else. Correctness must hold against semi-honest or malicious adversaries depending on the threat model. A protocol that misses elements or includes false positives is considered broken.

Receiver Privacy

The guarantee that the sender learns nothing about the receiver's private input set. The receiver's data remains indistinguishable from random throughout the protocol. This is typically proven under a simulation-based security definition, where the sender's view can be simulated without access to the receiver's set. This property is non-negotiable for any PSI construction.

Sender Privacy

The guarantee that the receiver learns only the intersection and nothing about the sender's non-intersecting elements. Without this property, a malicious receiver could extract the sender's entire dataset. Sender privacy is the defining feature that distinguishes PSI from simpler Private Information Retrieval (PIR) protocols.

Malicious Security

Protocols secure against malicious adversaries who may arbitrarily deviate from the protocol specification to extract additional information. Achieving this requires additional cryptographic machinery:

Cut-and-choose techniques to verify correct behavior
Zero-knowledge proofs to enforce honest computation
Consistency checks on encrypted values This adds significant overhead compared to semi-honest security.

Linear Communication Complexity

The total data exchanged between parties grows linearly with the size of the input sets, typically O(n) where n is the set size. This is achieved through efficient techniques like:

Cuckoo hashing to reduce the number of necessary comparisons
Oblivious Pseudorandom Functions (OPRF) to mask set elements
Bloom filters for compact set representation Sub-linear protocols exist but often sacrifice security guarantees.

Unbalanced PSI

A variant optimized for scenarios where one party's set is significantly smaller than the other's. Communication complexity scales with the smaller set size rather than the larger one. This is critical for applications like:

Contact discovery (user's small contact list vs. service's large user base)
Password breach checking (single password vs. billions of leaked credentials)
Private database querying

COMPARATIVE ANALYSIS

PSI vs. Related Privacy Technologies

How Private Set Intersection compares to other privacy-preserving computation techniques for secure data matching and analysis.

Feature	Private Set Intersection (PSI)	Fully Homomorphic Encryption (FHE)	Multi-Party Computation (MPC)	Differential Privacy
Primary Function	Compute set intersection without revealing non-matching elements	Compute arbitrary functions on encrypted data without decryption	Jointly compute a function over private inputs from multiple parties	Add calibrated noise to query results to mask individual contributions
Data Revealed to Other Parties	Only elements present in all parties' sets	Nothing; result remains encrypted until threshold decryption	Only the agreed-upon function output	Aggregate statistics with privacy guarantees
Typical Use Case	Contact discovery, private matching, fraud detection across institutions	Encrypted inference on cloud-hosted models	Secure auctions, collaborative analytics, key management	Releasing statistical summaries of sensitive datasets
Cryptographic Foundation	Oblivious Transfer, Diffie-Hellman, Bloom Filters	Lattice-based cryptography (RLWE)	Secret sharing, garbled circuits, oblivious transfer	Laplace or Gaussian noise mechanisms
Computational Overhead	Moderate; linear in set size	Extremely high; 10,000x-1,000,000x slowdown	High; dominated by communication rounds	Negligible; statistical post-processing
Communication Complexity	O(n) where n is set size	Low; ciphertext size is compact	High; multiple rounds between parties	None; local computation only
Supports Arbitrary Computation
Post-Quantum Security	Depends on implementation; ECDH-based PSI is vulnerable		Depends on implementation; garbled circuits are symmetric-key based

PRIVATE SET INTERSECTION

Frequently Asked Questions

Clear, technically precise answers to the most common questions about Private Set Intersection protocols, their security models, and real-world deployment considerations.

Private Set Intersection (PSI) is a cryptographic protocol that allows two parties, each holding a private dataset, to compute the intersection of their sets without revealing any elements outside that intersection to the other party. The protocol ensures that Party A learns only which of its elements also exist in Party B's set, while Party B learns only which of its elements exist in Party A's set—and nothing more. This is achieved through a variety of underlying cryptographic primitives, including Oblivious Transfer (OT) , Diffie-Hellman key exchange variants, and homomorphic encryption. In a typical OT-based PSI, the sender encodes its set into a data structure, and the receiver obliviously queries each of its elements against that structure, learning only whether a match exists. The protocol's security is defined by the ideal functionality where a trusted third party computes the intersection and distributes only the result, with real-world protocols proven secure under the semi-honest or malicious adversary models.

Enabling Efficiency, Speed & Accuracy

Intelligent Analysis, Decision & Execution

We build AI systems for teams that need search across company data, workflow automation across tools, or AI features inside products and internal software.

Talk to Us

Search across company data

Give teams answers from docs, tickets, runbooks, and product data with sources and permissions.

Useful when people spend too long searching or get different answers from different systems.

Enterprise searchRAGPermissions

Automate internal workflows

Use AI to route work, draft outputs, trigger actions, and keep approvals and logs in place.

Useful when repetitive work moves across multiple tools and teams.

AI agentsWorkflow automationGovernance

Add AI to products and internal tools

Build assistants, guided actions, or decision support into the software your team or customers already use.

Useful when AI needs to be part of the product, not a separate tool.

AI integrationDecision supportModel routing

CRYPTOGRAPHIC PRIMITIVES

Related Terms

Private Set Intersection relies on a stack of foundational cryptographic protocols. Understanding these building blocks is essential for evaluating the security, performance, and trust assumptions of any PSI implementation.

Oblivious Transfer (OT)

A fundamental two-party protocol where a sender inputs two messages and a receiver selects one. The receiver learns only their chosen message, and the sender remains oblivious to the choice. OT is the core building block for Garbled Circuits and many efficient PSI protocols, enabling secure evaluation of the intersection logic without revealing non-matching elements.

OT Extension

Amortizes base OTs into millions of cheap transfers

Diffie-Hellman Key Exchange

The cryptographic workhorse behind many practical PSI protocols. Both parties agree on a cyclic group and a generator. Each party exponentiates their private set elements with their own secret key and exchanges the results. The intersection is revealed where the doubly-exponentiated values match, relying on the Decisional Diffie-Hellman assumption for security against passive adversaries.

O(n)

Linear communication complexity

Homomorphic Encryption (HE)

Enables computation directly on ciphertexts. In PSI, the client encrypts their set under a homomorphic encryption scheme and sends it to the server. The server evaluates a polynomial representing its own set on the encrypted data, producing an encrypted result that only the client can decrypt to reveal the intersection. This approach minimizes data leakage to a single encrypted polynomial evaluation.

Asymmetric

Computation heavily weighted to the server

Garbled Circuits

A constant-round MPC technique where one party 'garbles' a Boolean circuit representing the intersection function and sends it to the other party. The second party evaluates the garbled circuit using Oblivious Transfer to input its private set, learning only the final output. Garbled circuits are highly efficient for evaluating complex, non-linear matching predicates beyond simple equality.

Constant Rounds

Interaction complexity independent of circuit depth

Bloom Filters

A probabilistic data structure used to optimize the communication footprint of PSI. A party encodes its set into a Bloom filter—a bit array with multiple hash functions—and sends it to the other party. The receiver queries their elements against the filter. This introduces a configurable false positive rate, trading perfect accuracy for dramatically reduced bandwidth in unbalanced set size scenarios.

Sub-linear

Bandwidth relative to set size

Cuckoo Hashing

A dense hashing scheme that maps elements to one of two possible bins in a fixed-size table. In PSI, Cuckoo hashing ensures that each bin holds at most one element, enabling the use of 1-out-of-2 Oblivious Transfer for efficient secure comparison. This technique is critical for protocols that require exact matching without the false positives inherent to Bloom filters.

Constant Lookup

Worst-case O(1) query time

About the author

Prasad Kumkar

CEO & MD, Inference Systems

Prasad Kumkar is the CEO & MD of Inference Systems and writes about AI systems architecture, LLM infrastructure, model serving, evaluation, and production deployment. Over 5+ years, he has worked across computer vision models, L5 autonomous vehicle systems, and LLM research, with a focus on taking complex AI ideas into real-world engineering systems.

His work and writing cover AI systems, large language models, AI agents, multimodal systems, autonomous systems, inference optimization, RAG, evaluation, and production AI engineering.

Limited slotsGet a Free AI Consultation

How We Work

Custom AI workflows for your Business

One-fit-all AI don't work for modern businesses. At Inferensys, we aim to understand your business & custom requirements; which we use to define most efficient agentic workflows, the data, and the tools for your business.