Measuring Mix-Zone Entropy for Location Queries

Mix-zone entropy is the Shannon entropy of the adversary’s assignment distribution for one arrival, and the zone is worth what its worst arrival gets. Building the matrix the adversary would build — from transit-time plausibility and turn probability — is the only way to find out whether a mix zone achieved anything.

Core Calculation # permalink

Let $A = \{a_1, \dots, a_n\}$ be arrivals and $D = \{d_1, \dots, d_n\}$ departures during one observation window. The adversary’s belief that arrival $i$ left as departure $j$ is

where $f$ is the empirical transit-time density, $\pi$ the turn-movement probability from approach $\theta_i$ to exit $\phi_j$, and the denominator normalises the row. Arrival $i$’s anonymity is

Reporting $2^{H_i}$ — the effective anonymity set size — makes the number readable: 1.4 effective devices is obviously inadequate where 0.49 bits is not.

Worked numeric example # permalink

Three arrivals and three departures at a T-junction, transit times measured to be $\mathcal{N}(28, 6^2)$ seconds. Arrival times 0, 4, 9 s; departure times 27, 34, 41 s. Turn probabilities are uniform because all three movements are permitted.

The ceiling is $\log_2 3 = 1.58$ bits, so the zone reaches 83% of it and the worst arrival still enjoys 2.5 effective candidates. Now tighten the transit distribution to $\mathcal{N}(28, 1.5^2)$ — a shorter, faster zone — and the first row becomes $(0.99, 0.01, 0.00)$: $H_1 = 0.08$ bits, effective set size 1.06. The occupancy did not change; the mixing vanished.

Python Implementation # permalink

from __future__ import annotations

import numpy as np
from scipy.stats import gaussian_kde

def mix_zone_entropy(
    t_in: np.ndarray,
    t_out: np.ndarray,
    transit_sample: np.ndarray,
    approach: np.ndarray | None = None,
    exit_leg: np.ndarray | None = None,
    turn_prob: dict[tuple[int, int], float] | None = None,
) -> dict:
    """Per-arrival mixing entropy from the adversary's own assignment matrix.

    The transit density is estimated from observed crossings rather than assumed:
    a free-flow model is far tighter than reality and overstates the mixing.

    Args:
        t_in, t_out: entry and exit epoch seconds for one observation window.
        transit_sample: observed transit durations used to fit the density.
        approach, exit_leg: optional leg indices enabling the turn-probability term.
        turn_prob: probability of each (approach, exit) movement; uniform if omitted.

    Returns:
        min/mean entropy in bits, the ceiling, and the effective anonymity set of
        the worst arrival — the figure a release gate should read.
    """
    n_in, n_out = t_in.size, t_out.size
    if n_in < 2 or n_out < 2:
        return {"min_bits": 0.0, "mean_bits": 0.0, "ceiling_bits": 0.0,
                "worst_effective_set": 1.0, "n_arrivals": int(n_in)}

    f = gaussian_kde(transit_sample)
    delta = t_out[None, :] - t_in[:, None]
    p = np.where(delta > 0.0, f(delta.ravel()).reshape(delta.shape), 0.0)

    if approach is not None and exit_leg is not None and turn_prob:
        weights = np.array([[turn_prob.get((int(a), int(e)), 0.0)
                             for e in exit_leg] for a in approach])
        p = p * weights                      # an impossible turn zeroes the pair

    rows = p.sum(axis=1, keepdims=True)
    p = np.divide(p, rows, out=np.zeros_like(p), where=rows > 0)

    with np.errstate(divide="ignore", invalid="ignore"):
        h = np.where(p > 0, -p * np.log2(p), 0.0).sum(axis=1)

    return {
        "min_bits": float(h.min()),
        "mean_bits": float(h.mean()),
        "ceiling_bits": float(np.log2(n_out)),
        "worst_effective_set": float(2.0 ** h.min()),
        "n_arrivals": int(n_in),
    }

Verification # permalink

The entropy is a model-based estimate, so verify it against an attack rather than trusting the number.

def continuation_attack_success(scores: list[dict], truth: list[int],
                                guesses: list[int]) -> dict:
    """Fraction of pseudonym changes a heading-and-speed tracker defeats.

    A zone reporting 2 bits whose continuation attack succeeds most of the time
    has geometry the timing model did not capture — usually a dominant movement.
    """
    correct = sum(int(t == g) for t, g in zip(truth, guesses))
    return {
        "n_crossings": len(truth),
        "attack_success_rate": correct / max(len(truth), 1),
        "implied_effective_set": max(len(truth), 1) / max(correct, 1),
        "reported_min_effective_set": min(s["worst_effective_set"] for s in scores),
    }

Compare implied_effective_set with reported_min_effective_set. A large gap means the assignment model is missing a signal the tracker is using — most often a turn distribution that is far from uniform, or a speed profile that persists across the zone.

Edge Cases & Adjustments # permalink

• Fewer than two arrivals. Entropy is zero by definition; the implementation returns it explicitly rather than raising, so the band appears in the report as a failure rather than as missing data.
• Unbalanced arrivals and departures. A device that entered and has not left yet leaves the matrix non-square. Restrict the window to complete crossings and record how many were dropped, because a systematically dropped subset biases the estimate.
• Non-uniform turns. The uniform assumption is optimistic almost everywhere. Estimate $\pi$ from the same crossings that produced $f$; a dominant movement is the most common reason a reported entropy overstates reality.
• Very long windows. Widening the window admits pairs whose transit time is implausible, which inflates entropy without any real ambiguity. Cap the window at a few multiples of the mean transit time.
• Cross-day accumulation. A commuter crossing the same zone daily has their assignments intersected across days, so the achieved anonymity is lower than any single day’s figure. Report the per-crossing entropy and a per-user cumulative figure over the retention window, as with the intersection attack in trajectory anonymization techniques.

FAQ # permalink

Why report $2^{H}$ rather than $H$?

Because a threshold in effective devices is reviewable by someone who does not work in information theory, and because it is directly comparable to a k floor. Two bits and 4 effective candidates are the same statement; only one of them survives a design review unexplained.

Should the turn probabilities come from the road geometry or from the data?

From the data. Geometry says which movements are legal; the observed distribution says which are used, and the gap between them is exactly the information an adversary exploits.

Can I compare mix-zone entropy against a k-anonymity floor?

Loosely, through the effective set size. They are not the same guarantee — k is about records sharing a generalisation, entropy is about an adversary’s assignment uncertainty — but both are empirical, adversary-model-dependent measurements rather than formal bounds, so they sit at the same tier in masking vs. differential privacy technique selection.

What if entropy is high but the attack still succeeds?

Then the model is wrong, and the attack is the ground truth. The usual causes are a non-uniform turn distribution, a speed signature that persists across the zone, or a leaked position from inside the silent period.

Related # permalink

• Mix Zones & Path Confusion for Location Services — the control this measurement evaluates
• Sizing Mix Zones at Road Intersections — choosing the radius the entropy is then measured against
• Estimating Uniqueness of Mobility Traces — the trace-level counterpart of this measurement
• Defending Against Map-Matching Attacks — the tracker whose success rate verifies the model

← Back to Mix Zones & Path Confusion for Location Services