Private Set Intersection and Federated Primitives: The Workhorses of Privacy-Preserving Joins

Abstract

This article covers the most deployed family of secure-computation protocols: private set intersection (PSI) and the federated primitives around it. PSI lets two parties, each holding a private set, learn only the elements they have in common, revealing nothing about the items that do not match. It explains the core construction through oblivious pseudorandom functions and the classic Diffie-Hellman approach — each side maps its elements through a keyed function neither can invert alone, so equal elements produce equal outputs that can be compared while unequal ones stay hidden. It then surveys the variants that leak even less: PSI-cardinality reveals only the size of the intersection, PSI-sum reveals only a sum of values associated with the common elements, and secure aggregation sums many parties' vectors so only the total is revealed — the primitive behind federated learning. It emphasizes that every variant is defined by exactly what it leaks, so the design task is choosing the minimal-leakage variant that still yields the needed answer, and notes that oblivious-transfer extension makes modern PSI scale to hundreds of millions of elements. It closes on the AI stakes: private data collaboration, deduplication, and federated analytics across organizations that cannot pool raw data. The theme: PSI and its relatives are the practical face of MPC, and using them well is a matter of matching the primitive's leakage to the question being asked.

Of all secure-computation protocols, private set intersection is the one most widely deployed in the real world. It answers a common and delicate question: two parties each hold a private list, and they want to know only what they have in common — which customers, which contacts, which compromised passwords — without either revealing the rest of its list. From this one primitive and its close relatives comes a whole toolkit of privacy-preserving joins and aggregations that let organizations collaborate on their data without pooling it. This article explains how PSI works, the lower-leakage variants built around it, and why matching the variant to the question is the essential design skill.

What PSI computes

Private set intersection lets two parties, each holding a set of items, jointly compute the intersection of their sets — the elements they both have — while learning nothing about the elements they do not share. Party A learns which of its items are also in B's set (and, in the basic version, so does B), but neither learns anything about the other's non-matching items, not even how those items compare. It is the MPC guarantee of the first article specialized to the intersection function: reveal the common elements, and nothing else.

The applications are everywhere private data must be compared. Contact discovery matches a user's address book against a service's user base without uploading the whole address book in the clear. Ad measurement finds which people who saw an ad later made a purchase, matching an advertiser's exposure list against a merchant's transaction list. Security tools check a user's passwords against a database of breached credentials without revealing the passwords. Two companies find their common customers to plan a partnership without exposing their full customer lists to each other.

In every case the value is that the sensitive lists never leave their owners in readable form, and only the agreed answer — the intersection — is revealed. This is exactly the collaboration-without-pooling that makes PSI so useful, and it is why PSI, more than any other MPC protocol, has crossed from research into large-scale production. The question is how two parties can compare items for equality without either being able to see the other's items, which is what the construction provides.

How PSI works

The core idea is to map each element through a keyed function that neither party can compute alone, so that equal inputs yield equal outputs while the inputs themselves stay hidden. In the classic Diffie-Hellman approach, both parties hash their elements to group elements and then raise them to their own secret exponents; after each side has applied both secret exponents (in a blinded exchange), an element common to both sets ends up as the same value on both sides, which can be matched, while the exponentiation hides the underlying items. Comparing the doubly-exponentiated values reveals the intersection and nothing more.

The modern, faster route uses an oblivious pseudorandom function (OPRF). One party holds the key to a pseudorandom function; the other obtains the function's output on each of its own elements without learning the key and without the key-holder learning the elements. Both parties then hold pseudorandom values for their sets under the same function, so common elements collide and can be found by comparing the outputs, while the pseudorandomness hides everything else. Because the function's output on a non-shared element looks random and reveals nothing, only the true intersection is exposed.

Both constructions rest on the primitives of the previous articles — oblivious transfer under the OPRF, made cheap by oblivious-transfer extension — which is why PSI has become so efficient. State-of-the-art protocols intersect sets of hundreds of millions of elements in seconds to minutes, using mostly symmetric cryptography. The pipeline is the same in outline regardless of the construction: map each item through the shared secret function, then compare the resulting values to find the matches.

Each party maps its items through a shared secret function; equal items produce equal values, which are compared to find the intersection.

\[\text{DH-PSI: both compute } H(x)^{ab}; \text{ equal iff same } x; \text{ exponents hide the item}\]

\[\text{OPRF-PSI: compare } F_k(x_i) \text{ values; a match} \Rightarrow x_i \in A \cap B\]

Variants and federated primitives

Plain PSI reveals the intersection itself, but often the parties do not need the elements — only some statistic over them — and revealing less is always safer. PSI-cardinality returns only the size of the intersection, not which elements it contains: enough to measure audience overlap or match rates without disclosing any identities. PSI-sum goes further and returns a sum of values associated with the common elements without revealing the elements or their individual values — the primitive behind privacy-preserving ad conversion measurement, where the answer is the total purchase value among matched users.

Secure aggregation generalizes the idea to many parties. Each participant contributes a private vector, and the protocol reveals only the sum across all participants, with no individual vector exposed — realized with the secret-sharing and threshold techniques of the earlier article. This is the workhorse of federated analytics: many parties compute a joint total, average, or histogram over their combined data while each keeps its own contribution hidden. The mindmap groups these federated primitives, all of which return an aggregate rather than raw data.

The unifying principle is that each primitive is defined precisely by what it reveals. Full PSI reveals the common elements; PSI-cardinality reveals only their count; PSI-sum reveals only an aggregate over them; secure aggregation reveals only a grand total. Choosing among them is choosing how much to leak, and the discipline is to pick the primitive that reveals the least while still answering the question — because the output, as the first article stressed, is exactly what MPC does not protect, so minimizing what the output discloses is the real privacy lever.

Lower-leakage relatives of PSI return only a count, a sum over the overlap, or a grand total across many parties.

PSI and its federated relatives, by what they reveal.
Primitive	Reveals	Example use
PSI	the common elements	contact discovery
PSI-cardinality	only the count	audience overlap size
PSI-sum	a sum over the overlap	ad conversion value
Secure aggregation	the sum of all inputs	federated learning updates

Leakage, efficiency, and the AI stakes

Because the output is the one thing MPC does not hide, the leakage of the chosen variant is the crux of a safe deployment. Revealing the full intersection discloses which specific items match; revealing only the cardinality discloses just a number; revealing only an aggregate discloses even less. The spectrum runs from most to least leakage, and the right point on it is the least-leaking primitive that still answers the business question. A common mistake is to use full PSI when PSI-cardinality or PSI-sum would suffice, disclosing identities that were never needed.

Efficiency is no longer the barrier it once was. Thanks to oblivious-transfer extension and specialized data structures, PSI and its variants run at scale on commodity hardware, intersecting or aggregating over enormous sets quickly and mostly with symmetric cryptography — which, as a bonus, gives the same information-theoretic or symmetric-security durability the series favors for the post-quantum era. The practical constraint has shifted from can we compute this privately to which minimal-leakage variant do we actually need.

For AI, these primitives are the everyday tools of private data collaboration. Federated learning uses secure aggregation so a server combines model updates from many devices or organizations into a global update while seeing no individual contribution. Building a joint training set across organizations uses PSI to find overlapping records — the same patients, the same transactions — without exposing the non-overlapping ones, and PSI-based deduplication removes duplicate training examples held by different parties without revealing either party's full data. Cross-organization analytics over combined datasets use PSI-sum and secure aggregation to compute shared statistics with minimal disclosure. In each case the enabling move is the same one this article teaches: express the collaboration as a set operation or aggregate, then choose the primitive that answers it while leaking the least. That discipline — the practical face of the MPC guarantee — is what makes privacy-preserving collaborative AI deployable at scale, and it is why PSI and its federated relatives are the workhorses of the field.

📌

Choose the least-leaking primitive. PSI reveals the common elements; PSI-cardinality only their count; PSI-sum only an aggregate over them; secure aggregation only a grand total. Since the output is what MPC does not hide, pick the variant that answers the question while revealing the least — the real privacy lever in federated analytics and learning.

Key takeaways

Private set intersection lets two parties learn only their common elements, revealing nothing about non-matching items — the intersection specialization of the MPC guarantee.
PSI powers contact discovery, ad measurement, breached-credential checks, and cross-organization customer matching without exposing full lists.
It works by mapping each element through a shared secret function (Diffie-Hellman exponentiation or an oblivious PRF) so equal items collide while unequal ones stay hidden.
Lower-leakage variants reveal less: PSI-cardinality only the count, PSI-sum only an aggregate over the overlap, and secure aggregation only a grand total across many parties.
Each primitive is defined by what it reveals, so the design task is choosing the minimal-leakage variant that still answers the question.
For AI, secure aggregation drives federated learning and PSI enables private joins and deduplication across organizations that cannot pool raw data.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

✅Designing a PSI deploymentchecklist

Questions that pick the primitive and bound leakage.

Do you need the actual common elements, or only a count or aggregate over them?
Which is the minimal-leakage variant that still answers the question?
Does the chosen output disclose more about the inputs than intended?
Is the protocol secure against the relevant adversary (semi-honest or malicious)?
Does the set size fit the efficient OT-extension-based protocols?

🚀The PSI mental modelquickstart

Three facts to hold onto.

PSI reveals the common elements and nothing else.
Map items through a shared secret function so equal items collide.
Prefer PSI-cardinality, PSI-sum, or secure aggregation to leak less.

🔒Privacy-preserving-join stancepolicy

A stub recording the PSI variant decision.

private_join:
  primitive: [psi, psi_cardinality, psi_sum, secure_aggregation]
  selection_rule: minimal_leakage_that_answers
  construction: [dh, oprf]
  scale: ot_extension_based
  ml_use:
    federated_learning: secure_aggregation
    cross_org_join: psi

Illustrative documentation template, not a product config.

Glossary

Private set intersection (PSI): A protocol letting two parties learn only the elements common to their private sets, revealing nothing about the rest.
Oblivious pseudorandom function (OPRF): A protocol where one party evaluates a keyed pseudorandom function on the other's inputs without learning them or revealing the key.
PSI-cardinality: A PSI variant revealing only the size of the intersection, not its elements.
PSI-sum: A PSI variant revealing only a sum of values associated with the common elements, not the elements themselves.
Secure aggregation: A multi-party protocol revealing only the sum of all participants' inputs, the primitive behind federated learning.
Output leakage: The information the agreed output itself discloses about the inputs — the part MPC does not hide, minimized by choosing the right variant.