Private Set Intersection

Two retailers want to know how many customers they share and what that group spends. Neither may see the other's customer list, and neither is willing to hand it to the other's data team under an agreement. Any design where one party holds both lists at once fails the requirement as stated, no matter how trustworthy that party is.

Private set intersection computes over the overlap without revealing membership. Extensions commonly called private join and compute return a sum over the matched rows, so the answer can be "the overlap is 412k customers and their average basket is £38" with neither list disclosed.

Why it matters

It changes what a partnership can be. Measurement, audience overlap, fraud-signal sharing between banks and supply-chain matching are all blocked by a rule that the lists must not be combined. PSI removes the blocker with cryptography rather than with a contract, which matters exactly when the counterparty is a competitor or the regulator has said no.

It also disciplines the question. The computation is agreed in advance and cannot be explored, which is the privacy property rather than a limitation to engineer around.

Implementation patterns

• Blinded identifier exchange. Both sides apply a commutative or oblivious transformation to their identifiers so matched elements can be counted without unmatched ones being learned.
• Cardinality-only versus aggregate output. Cardinality is simpler; private join and compute adds homomorphic accumulation over the matched rows. Google published and open-sourced such a protocol in 2019.
• Identifier normalisation first. Lower-cased, trimmed, country-normalised phone numbers. Match rates collapse on formatting differences and the protocol cannot tell you why.
• Differential privacy on the output where a small intersection is itself identifying: noise on a count of 3 is the difference between a statistic and a disclosure.
• Batch scheduling. Communication is roughly linear in set size, so tens of millions of identifiers is a job measured in minutes to hours, run nightly rather than called from an API.

Industry example

Advertising measurement is where this reached production first: matching an advertiser's customer list against a platform's users to count conversions is precisely the overlap problem, and the industry moved from list uploads to protocol-based matching and clean rooms as regulation tightened through the 2020s. Interbank fraud consortia use the same shape for shared indicators, where the membership of a watchlist is more sensitive than the count.

Failure scenarios

• Repeated small queries. Running the protocol many times with slightly different inputs reconstructs membership one element at a time. Rate limits and query allowlists are part of the design, not operational polish.
• Identifier skew. One side's list is 50x larger, so the intersection reveals almost everything about the smaller one.
• Normalisation drift between the parties, producing a low match rate that is read as a business result rather than a bug.
• Protocol run on stale extracts, so the answer describes a population that no longer exists.
• Treating the output as anonymous when the intersection is small enough to identify people.

Trade-offs

PSI costs engineering on both sides, a fixed query shape and batch latency. A clean room hosted by a neutral operator with an agreed allowlist, thresholds and audit costs a fraction of that, supports many questions, and is operable by analysts — while moving trust rather than removing it. Most real partnerships use the clean room, and that is usually the right call.

When not to use it

When a contract, a neutral operator and audit logs are acceptable to both parties and to the regulator, use a clean room instead. Reach for PSI when the counterparty is a competitor, when a supervisory authority has objected to combining the lists, or when the membership itself is the sensitive asset — a watchlist, a patient cohort, a set of compromised accounts.

Interview question

Q: Two banks want to share indicators of fraudulent accounts without either learning the other's customer base. Design it, and tell me how you would stop the protocol being used to enumerate membership.

What a strong answer covers: PSI over normalised identifiers with an aggregate rather than a membership output · query allowlists, rate limits and minimum intersection thresholds to block enumeration · differential privacy on small counts · the batch, not API, execution model · and the honest comparison with a neutral-operator clean room, including why a consortium might still choose the cryptographic version.

Quick check

Quiz: Why does adding differential privacy noise to each party's exported list not solve the overlap problem? Joins need exact identifiers, so the noise either breaks the match or leaves the list exposed; DP belongs on the output statistic.

Flashcard: When is a clean room the better answer than PSI? — Whenever a neutral operator with an audited query allowlist is acceptable, because it costs far less and answers more than one question.