Mix Zones & Path Confusion for Location Services

A mix zone is a region in which a location service stops reporting, devices swap pseudonyms, and reporting resumes — so that an adversary watching the exits cannot tell which entering device became which leaving one. It is the one trajectory control that attacks the linkage between segments rather than the precision of any single point.

When a Mix Zone Is the Right Control # permalink

Perturbation and generalization both degrade a point. Neither touches the fact that consecutive points carry the same identifier, and it is that identifier which turns a set of observations into a trajectory. If a service must keep publishing accurate positions — a navigation app, a fleet dispatcher, a transit vehicle feed — then degrading the position is not available, and the only remaining lever is to break the chain.

Mix zones do exactly that. A device entering the zone is silent for the crossing, and on exit it carries a fresh pseudonym. If $m$ devices are inside the zone during overlapping intervals, an adversary observing the exits faces up to $m!$ possible assignments, and the achievable anonymity is bounded by how uncertain that assignment really is.

The critical word is really. A mix zone placed where nobody else is crossing achieves nothing: the single device that enters is the single device that leaves, and the pseudonym change is cosmetic. This is why mix zones are the control most often deployed with confident parameters and no measurement, and why the entropy calculation below is not optional.

Reach for a mix zone when:

• positions must remain accurate, so coordinate jittering and spatial fuzzing are unavailable;
• the service is continuous, so a per-release control like trajectory k-anonymity does not apply;
• the threat is an observer who can see the whole feed, not one who holds a single snapshot.

Do not reach for one when the device population is thin, when the road geometry forces a unique entry-to-exit mapping, or when the adversary also holds a timetable or a schedule that resolves the assignment for them.

Algorithmic Specification # permalink

Mixing entropy # permalink

Let $A$ be the set of devices entering a mix zone during an observation window and $D$ the set leaving it. An adversary assigns a probability $p_{ij}$ that arrival $i$ is departure $j$, derived from transit-time plausibility and turn probabilities. The anonymity delivered to arrival $i$ is the Shannon entropy of its row:

The zone’s achieved anonymity is the worst row, not the average:

Reporting the mean here is the standard mistake. A zone can average two bits while one device — the one that arrived at an unusual hour, or took the only left turn — sits at zero.

The uniform upper bound # permalink

If all $m$ devices are mutually indistinguishable, every $p_{ij} = 1/m$ and

This is the ceiling any zone can reach, and it is why a zone crossed by two devices delivers at most one bit no matter how large it is. The ratio $H_{\text{zone}} / \log_2 m$ is the useful diagnostic: it separates “not enough traffic” from “the geometry is leaking”.

Transit-time plausibility # permalink

The dominant source of assignment information is timing. If arrival $i$ enters at $t_i$ and departure $j$ leaves at $s_j$, the implied transit time is $\Delta_{ij} = s_j - t_i$. With an empirical transit-time density $f(\Delta)$ for the zone,

A tight $f$ — a small zone on a fast road — concentrates the assignment and destroys the entropy. This is the counter-intuitive design result: larger zones mix better because their transit-time distribution is wider, not merely because more devices fit inside.

Zone radius from a target population # permalink

To hold $m$ devices in a zone of radius $R$ given a flow rate $\lambda$ (devices per second entering) and a mean transit time $\bar{\Delta}$, Little’s law gives the expected occupancy:

so the radius required for a target occupancy $m^{*}$ at mean speed $\bar{v}$ is

Parameter reference # permalink

Prerequisites & Data Requirements # permalink

• A measured flow rate per candidate zone, per hour. A zone that holds eight devices at 08:00 holds one at 03:00, so the parameters are time-varying and the gate must be evaluated per window — the same reasoning that drives window-by-window thresholds in temporal cloaking and time obfuscation.
• The turn-movement structure of the intersection. A T-junction offers fewer assignments than a four-way, and a slip road may offer exactly one. The geometry caps the entropy before any traffic is considered.
• An empirical transit-time distribution. Assume nothing here; measure it. Speed limits and free-flow estimates produce a distribution far tighter than reality and therefore overstate the mixing.
• Pseudonym rotation that is genuinely unlinkable. If the new pseudonym is derived deterministically from the old one, or if a session token, device fingerprint or MAC address survives the change, the mix zone is decorative. This is the single most common implementation failure.
• A metric CRS. Zone radii and transit distances are metres.

Step-by-Step Implementation # permalink

Step 1 — Enumerate candidate zones from the network # permalink

Choose intersections rather than arbitrary discs. Turn structure is what creates assignment ambiguity, and a zone placed mid-block offers a single entry and a single exit, which is an entropy of zero regardless of how many devices pass through.

Step 2 — Measure flow and transit time per hour band # permalink

import numpy as np
import pandas as pd

def zone_occupancy(entries: pd.DataFrame, transit_s: np.ndarray) -> pd.DataFrame:
    """Expected concurrent occupancy per hour band, by Little's law."""
    lam = entries.groupby("hour").size() / 3600.0          # devices per second
    return pd.DataFrame({
        "lambda_per_s": lam,
        "mean_transit_s": float(transit_s.mean()),
        "expected_occupancy": lam * float(transit_s.mean()),
        "entropy_ceiling_bits": np.log2(np.maximum(lam * float(transit_s.mean()), 1.0)),
    })

Step 3 — Build the assignment matrix an adversary would build # permalink

from scipy.stats import gaussian_kde

def assignment_matrix(t_in: np.ndarray, t_out: np.ndarray,
                      transit_sample: np.ndarray) -> np.ndarray:
    """Rows = arrivals, cols = departures, entries = normalised plausibility."""
    f = gaussian_kde(transit_sample)                        # empirical transit density
    delta = t_out[None, :] - t_in[:, None]                  # implied transit per pair
    p = np.where(delta > 0, f(delta.ravel()).reshape(delta.shape), 0.0)
    row_sums = p.sum(axis=1, keepdims=True)
    return np.divide(p, row_sums, out=np.zeros_like(p), where=row_sums > 0)

Step 4 — Score the zone on its worst row # permalink

def zone_entropy_bits(p: np.ndarray) -> dict:
    """Per-arrival entropy; the zone is judged on the minimum, never the mean."""
    with np.errstate(divide="ignore", invalid="ignore"):
        terms = np.where(p > 0, -p * np.log2(p), 0.0)
    per_arrival = terms.sum(axis=1)
    return {
        "min_bits": float(per_arrival.min()),
        "mean_bits": float(per_arrival.mean()),
        "ceiling_bits": float(np.log2(p.shape[1])) if p.shape[1] else 0.0,
        "n_arrivals": int(p.shape[0]),
    }

Step 5 — Gate the feed on the measured entropy # permalink

def admit_zone(scores: dict, min_bits: float = 1.5) -> bool:
    """A zone below the floor must widen, merge with a neighbour, or stop
    being used as a mix zone during that hour band."""
    return scores["n_arrivals"] >= 3 and scores["min_bits"] >= min_bits

Validation & Re-identification Testing # permalink

Trace-continuation attack. The direct test: take the released feed, run a tracker that links segments by extrapolating heading and speed across each zone, and measure the fraction of pseudonym changes it defeats. A zone whose entropy calculation says two bits but whose continuation attack succeeds 80% of the time has a geometry problem the timing model did not capture.

Silent-period sufficiency. Verify that no report is emitted between entry and exit. A single position inside the zone can collapse the assignment entirely, and these leak through in practice via a separate telemetry channel, a crash report, or a cached last-known-location.

Pseudonym unlinkability. Confirm that nothing survives the rotation: no incrementing counter, no shared session, no stable ordering in the feed. Test by attempting the join yourself with full knowledge of the implementation.

Long-run intersection. Devices that repeat the same commute cross the same zones daily. Over a week the set of plausible assignments intersects across days, and the achieved anonymity falls. Measure it over the retention window, not over one crossing — the same accumulation that drives the intersection attack in trajectory anonymization techniques.

Common Failure Modes & Gotchas # permalink

Reporting mean entropy. The worst arrival is the one who gets re-identified. Gate on the minimum.

Zones sized by area rather than by occupancy. A large zone in an empty suburb is a large zone with one device in it. Size from the measured flow rate.

Pseudonyms that rotate but stay linkable. A fresh identifier that is derived from, ordered after, or transmitted alongside the old one provides nothing.

Mid-block zones. Without a turn choice there is no assignment ambiguity, only a gap in the trace that interpolation fills.

Ignoring the timetable. For transit vehicles the schedule is public and resolves the assignment directly. Mix zones are a poor fit for scheduled fleets; suppression and stop-location and POI suppression fit better.

Treating the entropy as a per-release property. It is per hour band, per zone, per day. A single global figure hides every case where the control did nothing.

Deploying Zones Across a Network # permalink

A single well-sized zone is easy. A network of them raises two questions that the per-zone calculation does not answer.

How many zones does a device cross? Each crossing is a pseudonym change, and each change costs the downstream analysis a broken trajectory. A network dense enough to mix well is a network that fragments every trip into short segments, which is exactly what a routing or origin-destination analysis cannot use. The practical resolution is to place zones where the analysis has least to lose — at trip boundaries rather than mid-journey — and to accept that a continuous-tracking use case and a mix-zone deployment are in genuine tension.

Do the zones cover the trips that matter? A device that never crosses a zone never changes pseudonym, so the control does nothing for it. Suburban and rural trips frequently avoid every candidate intersection. Measuring coverage — the share of trips that cross at least one zone with adequate entropy — is as important as measuring the entropy itself, and it is the figure most often absent from a deployment report.

Compliance Alignment # permalink

The entropy log is the artefact an assessment should reference. It is the only evidence that the rotation achieved anything, and it is the number that changes when traffic patterns shift.

FAQ # permalink

How large should a mix zone be?

Large enough that the expected occupancy reaches your target during the quietest band in which the service runs. Solve $R^{*} = m^{*}\bar{v} / 2\lambda$ with the flow rate for that band, not the daily average. A zone sized on the peak will be empty at night, which is exactly when a single crossing is most identifying.

Do mix zones give a formal privacy guarantee?

No. Mixing entropy is an empirical measurement against a specific adversary model, in the same family as k-anonymity rather than as geo-indistinguishability. An adversary with a better transit-time model or extra side information gets a different number, so the measurement has to be re-run when the model changes.

Can mix zones be combined with coordinate perturbation?

Yes, and they address different attacks — one breaks linkage, the other degrades precision. Combining them is sound engineering, but only the perturbation carries a bound, so do not describe the pair as having a stronger formal guarantee than the perturbation alone.

What entropy floor is defensible?

There is no regulatory number. Two bits corresponds to roughly four equally plausible assignments and is a common working floor; three bits is a strong posture for a public feed. What matters more than the value is that the floor is measured per band and that bands failing it are documented rather than quietly published.

Related # permalink

• Rotating Pseudonyms Without Leaking the Join Key — the five channels that survive a rotation and hand the join key back
• Sizing Mix Zones at Road Intersections — the radius calculation with a worked example
• Measuring Mix-Zone Entropy for Location Queries — building the assignment matrix and reading it honestly
• Trajectory Anonymization Techniques — sequence-level controls for batch releases
• Temporal Cloaking & Time Obfuscation — the time-axis control that complements a silent period
• Geo-Indistinguishability & the Planar Laplace Mechanism — the formal alternative when a bound is required

← Back to Trajectory & Mobility Data Privacy