Rotating Pseudonyms Without Leaking the Join Key

A rotation is only as good as the weakest channel that survives it. Five channels routinely do: the new identifier is derived from the old one, the emission order preserves it, a session or sequence counter carries across, a device fingerprint identifies the client independently, and the record schema differs between segments. Any one of them makes a mix zone decorative.

Core Specification # permalink

Let $u$ be a stable internal user key and $s$ a rotation epoch. The released pseudonym must satisfy two properties.

Unlinkability. For any two epochs $s \ne s'$, an adversary holding the released feed cannot do better than chance at deciding whether $p(u, s)$ and $p(u', s')$ share a $u$. The construction that gives this is a keyed hash over a per-epoch salt:

The salt must be random, not derived. HMAC(u, s) with a public epoch number is linkable by anyone who can guess the epoch scheme and enumerate candidate $u$ values — and in a fleet of ten thousand vehicles, $u$ is enumerable.

Non-invertibility of the ordering. Emission order is a channel in its own right. If segment records are written in stable internal-key order, a reader sorts two epochs identically and reads the mapping straight off the row positions:

Shuffle within the epoch, and shuffle with a source of randomness the release does not also publish.

The five channels # permalink

The fingerprint channel is the subtlest. A device reporting every 4.7 seconds because of a specific firmware quirk is identifiable by its cadence alone, and cadence survives every identifier change because it is a property of the data rather than of the key.

Worked numeric example # permalink

A fleet feed, 8 400 vehicles, rotation at every mix-zone crossing. An adversary attempts to link consecutive segments:

Random salting alone leaves 63% linkability — the ordering channel was carrying most of it. That ordering is not something anybody designs in; it is what a GROUP BY user_id produces by default.

Python Implementation # permalink

from __future__ import annotations

import hmac
import os
import secrets
from hashlib import sha256

import numpy as np
import pandas as pd


class EpochPseudonymiser:
    """Per-epoch keyed pseudonyms with the four non-identifier channels closed.

    The salt is generated, not derived: HMAC over a public epoch number is
    invertible by anyone who can enumerate the user space, and a vehicle fleet
    or a city's transit cards is entirely enumerable.
    """

    def __init__(self, cadence_quantum_s: float = 5.0, schema: tuple[str, ...] = ()):
        self._keys: dict[str, bytes] = {}
        self.cadence_quantum_s = cadence_quantum_s
        self.schema = schema

    def _key(self, epoch: str) -> bytes:
        if epoch not in self._keys:
            self._keys[epoch] = secrets.token_bytes(32)
        return self._keys[epoch]

    def pseudonym(self, user_key: str, epoch: str) -> str:
        return hmac.new(self._key(epoch), user_key.encode(), sha256).hexdigest()[:16]

    def emit(self, segment: pd.DataFrame, epoch: str,
             user_col: str = "user_key") -> pd.DataFrame:
        """Rotate, reset, coarsen, normalise and shuffle — in that order."""
        out = segment.copy()
        out["pseudonym"] = [self.pseudonym(u, epoch) for u in out[user_col]]
        out = out.drop(columns=[user_col])

        # Any counter that spans the boundary re-links the segments for free.
        for col in ("session_id", "trip_index", "seq", "leg_index"):
            if col in out:
                out[col] = out.groupby("pseudonym").cumcount()

        # Sampling cadence is a device fingerprint that survives every id change.
        if "sample_interval_s" in out:
            q = self.cadence_quantum_s
            out["sample_interval_s"] = (np.round(out["sample_interval_s"] / q) * q)

        # An optional column present for only some clients is itself a selector.
        for col in self.schema:
            if col not in out:
                out[col] = None
        out = out[[*self.schema, "pseudonym"]] if self.schema else out

        # Emission order in stable-key order reproduces the mapping exactly.
        rng = np.random.default_rng(int.from_bytes(os.urandom(8), "big"))
        return out.iloc[rng.permutation(len(out))].reset_index(drop=True)

Verification # permalink

The only meaningful test is to attempt the join yourself, with full knowledge of the implementation, and measure the success rate.

def linkage_attack(seg_a: pd.DataFrame, seg_b: pd.DataFrame,
                   truth: dict[str, str]) -> dict:
    """Try every channel an adversary would, and report which one worked.

    `truth` maps a pseudonym in segment A to its counterpart in B. A red-team
    result of "chance" is the only passing outcome; anything else names the
    channel still open.
    """
    n = len(truth)
    results = {}

    # 1. Ordering: does row position carry across?
    order_hits = sum(1 for i, (a, b) in enumerate(truth.items())
                     if seg_a.index.get_loc(seg_a.index[i]) ==
                        seg_b.index.get_loc(seg_b.index[i]))
    results["by_row_order"] = order_hits / max(n, 1)

    # 2. Fingerprint: a rare cadence or schema signature identifies the client.
    for col in ("sample_interval_s", "schema_hash", "device_class"):
        if col in seg_a and col in seg_b:
            rare = seg_a[col].value_counts()
            singles = set(rare[rare == 1].index)
            hits = sum(1 for a, b in truth.items()
                       if seg_a.loc[seg_a["pseudonym"] == a, col].iloc[0] in singles)
            results[f"by_{col}"] = hits / max(n, 1)

    results["chance"] = 1.0 / max(n, 1)
    results["worst_channel"] = max(
        (k for k in results if k != "chance"), key=lambda k: results[k], default=None)
    results["passes"] = all(v <= 3 * results["chance"]
                            for k, v in results.items() if k != "chance"
                            and isinstance(v, float))
    return results

The passes criterion — no channel better than three times chance — is deliberately loose, because a strict equality would fail on sampling noise. What matters is the shape of the result: a channel at 60% is an open door, and a channel at 1.2× chance is not.

Run the attack against a held-out segment pair, not the one used to tune the pseudonymiser, and re-run it whenever the record schema changes. A new optional column is a new channel.

Edge Cases & Adjustments # permalink

• Salt storage. The per-epoch keys must be retained if you ever need to re-link internally — for a deletion request, say — and retained keys are a re-identification capability. Store them under the same controls as raw location, with a documented expiry, and delete them on the retention boundary rather than keeping them indefinitely “just in case”.
• Rotation frequency versus utility. Rotating at every crossing maximises unlinkability and fragments every trajectory. Rotating daily preserves trip structure and gives an adversary a whole day of trace to work with. Pick from the analysis, and state the choice — it is the single most consequential parameter in the design.
• Enumerable user spaces. A fleet of 8 000 vehicles or a transit system’s card population is small enough to brute-force. That is why the salt must be random rather than a derivation over a guessable epoch label: with a derivable scheme, an adversary computes all 8 000 candidate pseudonyms and matches directly.
• Downstream re-identification. A consumer who joins two segments on a coincidental field — a route id plus a timestamp — re-links without touching the pseudonym. Run the attack over the published schema, not over the pseudonym column alone.
• Deletion requests after rotation. Once the salts are gone, a subject’s records cannot be located to delete them. Decide before launch whether the design supports erasure; if it does, the salts are retained and the compliance story is about their protection rather than their absence.

FAQ # permalink

Is a UUID per epoch enough?

A freshly generated UUID per user per epoch is unlinkable through the identifier channel and does nothing about the other four. It is exactly as good and exactly as insufficient as the salted HMAC.

Why not hash with a per-epoch counter as the salt?

Because the counter is guessable. An adversary who knows the epoch scheme computes the pseudonym for every candidate user directly. Randomness is what makes the mapping unavailable without the stored key.

Does shuffling really matter if the file is large?

Yes, and size does not help. Sorting both segments by pseudonym and comparing positions recovers the mapping exactly when the underlying order was stable, regardless of how many rows there are.

How does this interact with the mix-zone entropy figure?

The entropy calculation assumes the pseudonym change is unlinkable. If any of these five channels is open, the measured entropy is an upper bound the release does not achieve — which is why the continuation attack is run against the real feed rather than the model.

Related # permalink

• Mix Zones & Path Confusion — the control this rotation is the mechanism for
• Measuring Mix-Zone Entropy for Location Queries — the figure this makes real or decorative
• Trajectory Anonymization Techniques — the intersection attack a stable pseudonym enables
• Automating Spatial Privacy Checks in CI — running the linkage attack as a blocking check

← Back to Mix Zones & Path Confusion for Location Services