Choosing Between k-Anonymity and Differential Privacy for Location Data

Q: Is there an epsilon that equals a given k?

No exact equivalence exists because the two guarantees quantify different things. k bounds the chance of singling out a target within a released class under a bounded adversary; epsilon bounds the influence of any one record on the output distribution under any adversary. A rough intuition is that small epsilon (0.1 to 1) corresponds to strong protection comparable to large k, but the mapping is not formal and should not be presented as one.

Use k-anonymity when the audience is trusted, the adversary’s auxiliary knowledge is bounded, and no regulator demands a proof; use ε-differential privacy whenever the release is public, the adversary is unbounded, or a provable guarantee is required — because only the latter holds against an attacker whose side information you cannot enumerate.

This page gives the concrete rule of thumb, the parameter equivalences people ask for, and a worked residual-risk comparison. It is the deep-dive companion to the broader masking versus differential privacy technique selection guide.

Core Calculation permalink

The two guarantees permalink

k-anonymity groups records into equivalence classes of size at least $k$ on their quasi-identifiers (for location data, typically a spatial cell plus coarsened attributes). Within a released class, the probability that an adversary singles out a specific target by matching quasi-identifiers is bounded by:

\Pr[\text{re-identify} \mid \text{class}] \le \frac{1}{k}

This bound is conditional: it assumes the adversary’s knowledge is confined to the quasi-identifiers used to build the class. It says nothing about an adversary holding an extra attribute.

ε-differential privacy makes an unconditional statement about a randomized mechanism $M$ . For neighboring datasets $D, D'$ differing in one record and any output set $S$ :

\Pr[M(D)\in S] \le e^{\varepsilon}\,\Pr[M(D')\in S]

The multiplicative gap $e^{\varepsilon}$ is the entire guarantee, and it holds for every neighboring pair — so no auxiliary dataset can weaken it. For a count query with sensitivity $\Delta f = 1$ , the Laplace mechanism adds noise of scale $b = \Delta f / \varepsilon = 1/\varepsilon$ .

Parameter equivalence people ask for permalink

There is no exact $k \leftrightarrow \varepsilon$ mapping, because the quantities measure different risks. The useful intuition, not a formal identity, is:

k (bounded adversary)	Posterior singling-out	Comparable ε posture	Interpretation
k = 2	≤ 0.50	ε ≳ 3 (weak)	Minimal protection
k = 5	≤ 0.20	ε ≈ 1–2	Common minimum for release
k = 10	≤ 0.10	ε ≈ 0.5–1	Health / demographic data
k = 20	≤ 0.05	ε ≈ 0.1–0.5	Strong, near-DP posture

The right column is a posture comparison, not an equation: a small $\varepsilon$ delivers strong protection comparable to a large $k$ , but against every adversary rather than a bounded one.

Worked residual-risk example permalink

Take a released spatial equivalence class with $k = 5$ records in one grid cell, and an adversary who knows one auxiliary bit — say, whether the target visited a location tagged “clinic” — that happens to hold for exactly 1 of the 5 members.

Under k-anonymity, no auxiliary data: residual singling-out probability $\le 1/5 = 0.20$ .
Under k-anonymity, with the auxiliary bit: the class of 5 splits into a subclass of 1. Residual probability jumps to $1.0$ — full re-identification.
Under ε-DP on the same cell’s count, ε = 0.5: the released count is $c + \text{Lap}(0, 1/0.5) = c + \text{Lap}(0, 2)$ . The adversary’s posterior belief about whether the target is in the cell changes by at most $e^{0.5} \approx 1.65\times$ , regardless of the auxiliary bit. The auxiliary attribute does not move the guarantee.

The gap between “0.20 that silently becomes 1.0” and “bounded by $e^{0.5}$ against any side knowledge” is exactly why the audience and adversary model decide the technique.

Python Implementation permalink

The function estimates a k-anonymity re-identification risk from dataset statistics and, in parallel, the Laplace noise a target ε would require, then emits a recommendation from the threat-model flags.

from dataclasses import dataclass
from typing import Literal
import math


@dataclass(frozen=True)
class ReleaseProfile:
    """Inputs describing a location-data release and its threat model.

    All flags come from threat modeling, not from tuning for utility.
    """
    min_class_size: int          # smallest spatial equivalence class (k achieved)
    adversary_arbitrary_aux: bool  # attacker may hold unknown auxiliary attributes
    public_release: bool          # released beyond a trusted, access-controlled audience
    proof_required: bool          # regulator/contract demands a provable bound
    target_epsilon: float = 0.5   # epsilon to cost out if DP is chosen
    count_sensitivity: float = 1.0  # L1 sensitivity of a count query (one record)


def compare_kanon_and_dp(p: ReleaseProfile) -> dict:
    """Compare residual risk under k-anonymity vs epsilon-DP and recommend one.

    Returns the k-anonymity singling-out bound, the Laplace noise scale a
    target epsilon implies, and a recommendation keyed to the threat model.
    """
    if p.min_class_size < 1:
        raise ValueError("min_class_size must be >= 1")
    if p.target_epsilon <= 0:
        raise ValueError("target_epsilon must be > 0")

    # k-anonymity: best-case bound assumes NO distinguishing auxiliary attribute.
    k_bound = 1.0 / p.min_class_size

    # If the adversary can hold arbitrary aux data, the k bound is not trustworthy:
    # a single distinguishing attribute can collapse the class toward re-identification.
    k_trustworthy = not p.adversary_arbitrary_aux

    # epsilon-DP: Laplace scale for a count query, b = sensitivity / epsilon.
    # This is the noise cost of the formal, adversary-agnostic guarantee.
    dp_noise_scale = p.count_sensitivity / p.target_epsilon
    dp_posterior_multiplier = math.exp(p.target_epsilon)  # e^epsilon belief-change cap

    # Recommendation: formal DP dominates whenever the adversary is unbounded,
    # the release is public, or a proof is demanded. Otherwise k-anonymity suffices.
    if p.proof_required or p.public_release or p.adversary_arbitrary_aux:
        recommended = "differential_privacy"
        reason = "public / unbounded adversary / proof required"
    else:
        recommended = "k_anonymity"
        reason = "trusted audience, bounded adversary, no proof demanded"

    return {
        "k_singling_out_bound": round(k_bound, 4),
        "k_bound_trustworthy": k_trustworthy,
        "dp_laplace_noise_scale": round(dp_noise_scale, 4),
        "dp_posterior_multiplier": round(dp_posterior_multiplier, 4),
        "recommended": recommended,
        "because": reason,
    }


# Example: public open-data release, attacker may hold auxiliary data.
profile = ReleaseProfile(
    min_class_size=5,
    adversary_arbitrary_aux=True,
    public_release=True,
    proof_required=True,
    target_epsilon=0.5,
)
print(compare_kanon_and_dp(profile))
# {'k_singling_out_bound': 0.2, 'k_bound_trustworthy': False,
#  'dp_laplace_noise_scale': 2.0, 'dp_posterior_multiplier': 1.6487,
#  'recommended': 'differential_privacy', 'because': 'public / unbounded adversary / proof required'}

The function reports k_bound_trustworthy: False precisely when the adversary is unbounded — a reminder that the numeric $1/k$ bound is only as good as the assumption behind it.

Verification permalink

Confirm the chosen technique matches the threat model before release:

Audience classified. Public or partner release → default to differential privacy; strictly internal and access-controlled → k-anonymity is a candidate.
Adversary bounded in writing. If you cannot enumerate the auxiliary data an attacker could hold, the $1/k$ bound is not trustworthy and DP is required.
k floor achieved, not just targeted. Measure the minimum realized class size across the whole release; a single class of size 1 breaks the guarantee for everyone in it.
ε fixed against the threat model, not utility. The budget was chosen before measuring output quality, and composition across repeated releases is tracked.
Residual risk cross-checked. Run the re-identification risk assessment with the actual auxiliary datasets in scope, not a hypothetical one.
Regulatory basis recorded. The de-identification record states which guarantee was used and why, per your GDPR/CCPA compliance mapping.

Edge Cases & Adjustments permalink

Auxiliary data breaks k-anonymity. The classic failure: an attribute the designer did not treat as a quasi-identifier (a distinctive co-location, a rare visit) distinguishes members of a k-class and collapses the $1/k$ bound to near 1. If such attributes are plausible, escalate to differential privacy, whose guarantee is unaffected. Model these paths with a spatial linkage attack analysis.
Sparse cells force suppression. In low-density regions a k-anonymity grid suppresses most cells, and the pattern of suppression can itself leak where sparse populations live. Grid aggregation with adaptive cell sizes helps, but count-level Laplace or Gaussian noise avoids the all-or-nothing suppression edge entirely.
Composition under DP. Two ε-DP releases of the same subjects compose to at most $2\varepsilon$ under basic composition; many queries motivate zero-concentrated or Rényi accounting for a tighter bound. Track cumulative spend against the privacy budget. k-anonymity has no comparable composition calculus, which makes recurring releases a weak spot for it.
Sequential releases of the same population. Publishing the same cohort at successive time windows lets an adversary intersect the k-classes across releases, shrinking the effective anonymity set below the nominal $k$ . Either fix the equivalence classes across all releases or move to a formal mechanism with tracked composition.

FAQ permalink

Is there an ε that equals a given k?

No exact equivalence exists, because the two guarantees quantify different things. $k$ bounds the chance of singling out a target within a released class under a bounded adversary; $\varepsilon$ bounds the influence of any one record on the output distribution under any adversary. The intuition that small $\varepsilon$ (0.1–1) corresponds to strong protection comparable to large $k$ is useful for calibration, but it is not a formula and should not be documented as one.

When is k-anonymity actually enough for location data?

When the release is internal to a trusted, access-controlled audience, the adversary cannot hold auxiliary attributes that distinguish members of an equivalence class, and no regulator demands a provable bound. In that setting a k floor of 5–10 on spatial equivalence classes is a defensible, low-cost control.

Why does auxiliary data break k-anonymity but not differential privacy?

k-anonymity hides a target inside a class defined on chosen quasi-identifiers. An auxiliary attribute the designer did not treat as a quasi-identifier can distinguish members of that class, collapsing the $1/k$ bound. Differential privacy bounds the output distribution over all neighboring datasets, so no auxiliary dataset changes the guarantee.

Related

Masking vs. Differential Privacy: Choosing a Spatial Privacy Technique — the full technique-selection framework
k-Anonymity Grouping for Location Traces — building and validating spatial equivalence classes
Laplace & Gaussian Noise for Coordinate Data — calibrating the DP mechanism
Re-identification Risk Assessment for Geospatial Datasets — measuring residual risk under either choice
Privacy Budget Allocation for Spatial Queries — tracking ε across composed releases

← Back to Masking vs. Differential Privacy: Choosing a Spatial Privacy Technique

Choosing Between k-Anonymity and Differential Privacy for Location Data

Core Calculation # permalink

The two guarantees # permalink

Parameter equivalence people ask for # permalink

Worked residual-risk example # permalink

Python Implementation # permalink

Verification # permalink

Edge Cases & Adjustments # permalink

FAQ # permalink