A travel metasearch of Expedia's shape replaces every traveller email with a deterministic HMAC token before the data reaches the analytics warehouse and before any file goes to an advertising partner. Two years later an audit finds that one partner can name individual travellers. The token vault was never breached. What failed?

The trigger

Deterministic tokenisation exists so that the same input yields the same token everywhere. That is exactly what makes joins work across the warehouse, the event stream and the partner file. It is also the definition of a stable cross-context identifier, which is the thing pseudonymisation is supposed to remove.

Why it propagated

The partner never needed the key. Two paths are enough, and both were open:

• Enumeration where the key is shared. The key was distributed to every service that needed to join, which in practice included a vendor-hosted enrichment step. An email address carries almost no entropy against a known list: with the key, a partner holding 200 million addresses computes every token in minutes on one machine and inverts the whole scheme.
• Accumulation where it is not. Even without the key, a token that is stable across every file you send lets the partner build a profile over two years. Add three or four quasi-identifiers that travel with the row (origin city, device class, booking window, fare band) and a single named booking in the partner's own data collapses the token to a person.

GDPR Article 4(5) is precise about the condition that makes pseudonymisation count: the additional information that permits attribution must be kept separately and protected. A key held by every service that needs a join is not kept separately.

Why detection lagged

Nothing errors. There is no signal for "this identifier has become linkable", no failed request, no anomaly in any dashboard. It surfaces in a data-sharing review, a partner's own disclosure, or a complaint, which is why it ran for two years.

The structural fix

Token domain separation. Derive the token with a distinct key per recipient and per purpose, so the token given to partner A is uncorrelated with the token given to partner B and with the internal analytics token. Add scheduled rotation with a short overlap window, which bounds how long any accumulated linkage stays useful: rotate quarterly and a partner's profile can never span more than about two quarters.

What you give up is real. Per-recipient domains break the free cross-partner join that made deterministic tokens attractive. Where a join is genuinely needed, it becomes an audited call to a re-identification service that logs who asked and why, rather than an inner join anybody can write. That is the trade: a column join becomes a controlled operation with a queue and an approver.

The tempting fix that does not work

Swapping SHA-256 for HMAC, or adding a salt, changes nothing here. A single global salt or a single global key is still global, and linkability is a property of the token being the same everywhere, not of the strength of the function. Rotating the one key breaks every historical join at once without fixing the cross-recipient problem in between rotations.

When not to separate the token domains

For a purely internal warehouse with no external export and one team with access, a single token domain is fine and per-recipient keys buy nothing but key-management work. The rule flips the moment a token leaves the boundary of the system that holds the key, whether to an advertising partner, an offshore support tool or an acquirer during due diligence. Count the recipients. If the answer is one, stop here.