4. Privacy Models

This module covers the formal privacy models that provide mathematical guarantees on top of the anonymization techniques from Module 03. Techniques are the mechanism — generalization, noise, suppression. Privacy models are the contract — they define what "private enough" means in terms an attacker can reason about. Without a model, there is no way to quantify how much privacy a dataset actually provides.

The four models covered here — k-anonymity, l-diversity, t-closeness, and differential privacy — form a progression. Each was created to address a specific weakness in its predecessor. In practice, production systems combine them: structural anonymization (k-anonymity family) for record-level datasets, differential privacy for aggregate outputs and external sharing.

---

K-anonymity

K-anonymity is the oldest and most widely deployed formal privacy model, introduced by Latanya Sweeney in 2002. Its guarantee is intuitive: a dataset satisfies k-anonymity if every record is indistinguishable from at least k−1 other records on all quasi-identifier fields. The number k sets the minimum group size — an attacker who knows a target's quasi-identifier values can narrow them down to a group of at least k records, but no further.

Equivalence classes and the k guarantee

The mechanism depends on equivalence classes — groups of records that share identical values on every quasi-identifier field. If the quasi-identifiers in a telco CDR dataset are {age_band, district, hour_bucket}, then all records with age_band=30-39, district=North, hour_bucket=14:00-15:00 form one equivalence class. If that class contains 50 records, then for those records the dataset is at least 50-anonymous on those quasi-identifiers.

The formal definition: a dataset D satisfies k-anonymity if, for every combination of quasi-identifier values present in D, at least k records share that combination.

Concrete example — telco CDRs with k=5:

Age band	District	Hour bucket	Call duration (sensitive)	Count in class
30–39	North	14:00–15:00	Various	47 records — passes k=5
60–69	East	03:00–04:00	Various	3 records — fails k=5

The second group has only 3 records. To achieve k=5, the anonymization algorithm has two options: generalize further (widen the age band to 50–69, or merge East with another district) until the group reaches 5 records, or suppress the 3 records entirely if generalization would destroy too much utility.

Choosing k

There is no universally correct value for k. The choice depends on the threat model, the dataset size, and the downstream use case:

Context	Typical k range	Rationale
Internal analytics with access controls	5–10	Insiders have limited motivation and capability for re-identification attacks
Shared with trusted partners under contract	20–50	Partner has domain knowledge that helps narrow targets
Published externally or used in open research	50–100+	Unknown attacker capability; assume auxiliary datasets are available
Location / mobility data	100+	Spatio-temporal data is structurally resistant to anonymization (4 data points identify 95% of people)

Higher k means more generalization and lower analytical resolution — the table above gives starting points, but the right k for a specific engagement depends on the data and threat model.

Implementation via generalization and suppression

K-anonymity is achieved by iteratively broadening quasi-identifier values (generalization) and removing outlier records (suppression) until every equivalence class meets the k threshold. Tools like ARX (Module 05) implement this as an optimization problem: find the minimum generalization level across all fields that achieves k-anonymity while minimizing information loss.

The process requires two inputs:

1. Generalization hierarchies — tree structures that define how each quasi-identifier can be broadened at successive levels (Module 03 covers these in detail). For example:

   Cell Tower  →  Cell Cluster  →  District  →  Region  →  *
   30-34       →  30-39         →  25-49     →  Adult   →  *
   14:23       →  14:00-15:00   →  Afternoon →  *

2. The quasi-identifier set — which fields an attacker might use for re-identification. This is a modeling decision, not a mechanical one. In telco, {age, district, time_of_day} is the minimum; {age, district, time_of_day, call_duration, device_type} is more realistic. Every field added as a quasi-identifier makes k-anonymity harder to achieve — the equivalence classes fragment into smaller groups.

Suppression handles the long tail. In any real dataset, some records have rare attribute combinations that would require extreme generalization to reach k. Rather than generalizing the entire dataset to the level needed by a handful of outliers, it is usually better to suppress those records. ARX's suppression limit parameter controls the maximum percentage of records that can be removed — typically 1–5%.

Tools like ARX quantify information loss across different anonymization configurations, letting you compare trade-offs (e.g., "cell towers to district level + timestamps to hourly" vs. "cell towers to cluster level + timestamps to 15-minute buckets"). Define the analytics requirements before running the anonymization — the algorithm optimizes for a metric, but only domain knowledge can tell you which metric matters.

Limitations — homogeneity attack and background knowledge attack

K-anonymity guarantees that an individual cannot be singled out from a group, but it says nothing about what an attacker can learn about the individual's sensitive attributes once they've been narrowed down to a group.

Homogeneity attack. If all k records in an equivalence class share the same sensitive attribute value, the attacker learns that value with certainty — even without identifying which specific record belongs to the target.

Example: An attacker knows a subscriber lives in District North, is aged 30–39, and made a call between 14:00–15:00. The anonymized CDR dataset has 50 records matching those quasi-identifiers (k=50, well above any threshold). But all 50 records show churn risk = "high." The attacker now knows the target's churn risk, despite the k-anonymity guarantee.

This extends to any sensitive attribute with low diversity within a group: diagnosis codes in healthcare data, credit scores in financial data, plan type in telco subscriber data.

Background knowledge attack. An attacker who has external information can eliminate possibilities within the equivalence class. If the attacker knows a target does not have a particular disease, and the equivalence class contains only two diseases, the attacker can infer the target has the other one — even though k might be 100.

Both attacks exploit the same gap: k-anonymity protects against identity disclosure (singling out) but not attribute disclosure (learning sensitive values about a person). L-diversity and t-closeness were designed to close this gap.

Engineer takeaway

K-anonymity is a baseline, not a complete solution. When a client says "our data is k-anonymized with k=50," the follow-up questions are: (1) What are the quasi-identifiers? (Missing fields mean undercounting the attack surface.) (2) What about the sensitive attributes — are they diverse within each group? If they're homogeneous, the k-anonymity provides no protection against attribute disclosure. (3) Is this for internal use or external sharing? For external sharing, k-anonymity alone is insufficient — combine with l-diversity or differential privacy.

---

L-diversity

L-diversity extends k-anonymity by adding a constraint on sensitive attributes: each equivalence class must contain at least l distinct, well-represented values for every sensitive attribute. Where k-anonymity ensures you can't single out an individual, l-diversity ensures you can't learn their sensitive values even after narrowing them to a group.

Extending k-anonymity to sensitive attributes

The intuition: if every group of k records contains a diverse mix of sensitive values, then knowing someone is in the group reveals little about their specific value. The group might contain churners and non-churners, high-value and low-value customers, multiple diagnosis categories — the attacker gains no precision.

Formally, a dataset satisfies l-diversity if every equivalence class (defined by quasi-identifiers) contains at least l distinct values for each designated sensitive attribute.

Building on the previous example:

Age band	District	Hour bucket	Churn risk (sensitive)	L-diverse?
30–39	North	14:00–15:00	High (20), Medium (18), Low (12)	Yes — 3 distinct values (l ≤ 3)
60–69	East	03:00–04:00	High (5), High (5), High (5)	No — 1 distinct value

The second group passes k=15 (15 records) but fails l=2 because all records have the same churn risk.

Variants and when l-diversity helps

The basic version (distinct l-diversity) just requires l distinct values per group — but one dominant value plus l−1 rare outliers technically passes while still leaking information. Stronger variants (entropy l-diversity, recursive (c,l)-diversity) require the values to be evenly distributed, not just present. Use entropy l-diversity as the default — ARX supports all three variants.

L-diversity is effective when:

• Sensitive attributes have many possible values (e.g., diagnosis code from a set of 50+ categories, account balance ranges)
• The equivalence classes are large enough to support l distinct values without extreme generalization
• The attack model involves an adversary who knows a target is in a specific equivalence class and wants to learn their sensitive attribute

L-diversity is not effective when:

• The sensitive attribute has few possible values. A binary attribute (churned / not churned) can only have l=2 diversity. An attacker who knows the base rate (say, 10% churn) and sees a group with 50/50 distribution now knows the target's churn probability is 50% rather than 10% — they've learned something, even with "perfect" l-diversity. T-closeness addresses this.
• The attribute values are semantically similar. If the sensitive attribute is "disease" and a group contains "stomach cancer, liver cancer, pancreatic cancer," l=3 is technically satisfied — but the attacker learns "the target has cancer" with certainty. This is the similarity attack described by Li et al. (2007).
• Multiple sensitive attributes exist. L-diversity is defined per sensitive attribute. With multiple sensitive columns, achieving l-diversity for each simultaneously can require extreme generalization, especially on smaller datasets.

Engineer takeaway

L-diversity is worth adding on top of k-anonymity when sensitive attributes have enough distinct values (at least 5–10 categories) and when attribute disclosure is a realistic threat. For binary or low-cardinality sensitive attributes — which are common in telco (churn yes/no, premium subscriber yes/no) and fintech (default yes/no) — l-diversity provides minimal additional protection. Consider t-closeness or differential privacy for these cases.

---

T-closeness

T-closeness is the strongest model in the k-anonymity family. It requires that the distribution of sensitive attribute values within each equivalence class be close to the distribution in the overall dataset. "Close" is measured by a distance metric — specifically, the Earth Mover's Distance (EMD), also known as the Wasserstein distance — and the maximum allowed distance is the threshold t.

Distribution distance as a privacy metric

The intuition: if every group's sensitive attribute distribution is close to the overall population's distribution, then knowing which group someone belongs to reveals at most a bounded amount of additional information beyond what the overall statistics (assumed public or easily estimated) already provide. The bound is parameterized by t — at t=0 the guarantee is perfect; in practice t > 0 allows bounded leakage.

Example with a financial dataset where the sensitive attribute is "account balance":

Overall distribution: 30% low (€0–€5k), 45% medium (€5k–€50k), 25% high (€50k+)

Equivalence class	Balance distribution	EMD from overall	T-close? (t=0.15)
Group A	28% low, 47% medium, 25% high	0.02	Yes
Group B	10% low, 20% medium, 70% high	0.38	No — skewed toward high

Group B reveals that individuals in this group are disproportionately wealthy. An attacker who knows someone is in Group B learns significant information about their account balance — even without identifying the specific individual. T-closeness prevents this by requiring Group B's distribution to match the overall distribution within tolerance t.

The Earth Mover's Distance is chosen because it respects the semantic distance between values. For numerical attributes, the EMD between "90% high, 10% medium" and "90% high, 10% low" is larger than between "90% high, 10% medium" and "80% high, 20% medium" — it accounts for how far values need to "move" to transform one distribution into the other.

Practical applicability and limitations

When t-closeness adds value:

• Sensitive attributes with rich distributions (continuous or many categories) where group-level distribution skew reveals information — financial balances, energy consumption levels, health indicators
• Regulatory contexts requiring strong protection against attribute inference, not just identity disclosure
• Datasets where the overall distribution of the sensitive attribute is non-trivial (if 99% of records share one value, t-closeness degenerates)

Practical limitations:

• Severe utility loss and computational cost. Forcing every group's distribution close to the overall distribution requires aggressive generalization — the resulting dataset is often too coarse for the intended analysis. The algorithm is also significantly more expensive than k-anonymity or l-diversity.
• Hard to parameterize. Unlike k (group size) or l (distinct values), t is a distribution distance metric with no intuitive "safe" value. Choosing t requires understanding the distribution shape and attribute semantics.

In practice, most production systems use k-anonymity (often with high k) as the structural anonymization layer and add differential privacy for aggregate outputs, rather than implementing the full k→l→t stack. T-closeness adds meaningful value primarily when the sensitive attribute distribution is highly skewed and distribution inference is a plausible attack.

---

Differential privacy

Differential privacy (DP) is a fundamentally different approach from the k-anonymity family. Instead of transforming the dataset so that individuals can't be singled out, DP adds calibrated noise to the outputs of queries or computations over the data. The underlying data can remain intact; the privacy guarantee applies to what anyone can learn from the outputs.

DP is the current gold standard for formal privacy guarantees. It is used by Google (search, maps, Chrome), Apple (keyboard and usage analytics), the US Census Bureau (2020 Census), and Microsoft (telemetry). Its adoption in enterprise data engineering is growing rapidly, particularly for external data sharing and aggregate analytics.

The core idea

The DP guarantee, in plain terms: adding or removing any single person's data changes the probability of any output by at most a controlled amount. An analyst looking at the output cannot reliably determine whether any specific individual was in the input data.

Unlike k-anonymity — which is a property of the anonymized dataset — DP is a property of the process that produces the output. You don't transform the data; you add noise to answers.

Example: "How many CDRs originated from District North between 14:00–15:00?" The true count is 4,721. The DP mechanism adds a small random number (say +3 or −2), so the reported count is 4,724. At these group sizes, the noise is negligible — aggregate accuracy is preserved, but no single person's presence or absence can be detected from the output.

ε and δ — the two knobs

ε (epsilon) controls how much noise is added. Smaller ε = more noise = stronger privacy = less accurate results. Think of it as a "privacy dial" — turn it down for more privacy, up for more accuracy.

ε range	Privacy strength	Used by
0.1–1.0	Strong	Google RAPPOR (Chrome), research datasets
1.0–3.0	Moderate	Standard starting point for enterprise analytics
4.0–8.0	Weaker	Apple local DP (iOS telemetry)
10+	Effectively none	Avoid for any privacy-sensitive use case

ε = 1.0 is a reasonable starting point for a single query. There is no universal "safe" value — the right ε depends on data sensitivity, the number of queries, and who sees the output.

δ (delta) is a failure probability — a tiny chance that the ε guarantee doesn't hold. Set it much smaller than 1/n (dataset size), e.g., δ = 10⁻⁷ for a million records. In practice, you set δ once and rarely revisit it.

The calibration question for engineers: "How much accuracy can this use case tolerate?" For aggregate traffic statistics shared with a telco partner, ε = 1.0 with reasonable group sizes produces results accurate to within a few percent. For an individual subscriber lookup, no amount of DP helps — the answer is inherently about one person.

How noise is added — mechanisms

The DP framework provides different noise mechanisms for different query types. In practice, you choose a mechanism based on whether the output is numerical or categorical; the library (Privacy on Beam, OpenDP — Module 05) handles the noise calibration.

Mechanism	What it does	Best for
Laplace	Adds random noise from a Laplace distribution	Counting queries, sums, histograms
Gaussian	Adds random noise from a normal distribution	Multi-dimensional queries, ML training (DP-SGD)
Exponential	Selects a category with randomized probability	"What is the most common X?" — mode, ranking

The noise is calibrated to the query's sensitivity — how much a single record can change the output. A counting query has sensitivity 1 (one person adds or removes one count), so it needs very little noise. A sum-of-revenue query where one customer can contribute millions has high sensitivity and needs more noise.

Deep dive

The formal guarantee and mechanism math

A mechanism $M$ satisfies ($\varepsilon$, $\delta$)-differential privacy if for any two datasets $D$ and $D'$ that differ by exactly one record, and for any set of possible outputs $S$:

$$P[M(D) \in S] \leq e^{\varepsilon} \cdot P[M(D') \in S] + \delta$$

The $e^{\varepsilon}$ factor is why $\varepsilon$ matters so much: at $\varepsilon = 1.0$, $e^{\varepsilon} \approx 2.7$ (output probabilities can differ by at most 2.7×); at $\varepsilon = 10.0$, $e^{\varepsilon} \approx 22{,}000$ (effectively no privacy).

Laplace mechanism: Adds noise $\text{Lap}(\Delta f / \varepsilon)$, where $\Delta f$ is the query sensitivity. Provides pure $\varepsilon$-DP ($\delta = 0$).

Gaussian mechanism: Adds noise $\mathcal{N}(0, \sigma^2)$ where $\sigma = \Delta f \cdot \sqrt{2 \ln(1.25/\delta)} \,/\, \varepsilon$. Requires $\delta > 0$, but composes more tightly across multiple queries — preferred for high-dimensional analytics and ML training.

Exponential mechanism: For non-numerical outputs, selects with probability proportional to $e^{\varepsilon \cdot u / 2\Delta u}$, where $u$ is the utility score. Provides pure $\varepsilon$-DP.

Privacy budget

Every DP query over a dataset consumes part of the privacy budget. Run enough queries and the cumulative privacy loss degrades to the point where individual records become detectable. This is the key operational constraint: a DP pipeline cannot answer unlimited queries — it has a finite budget.

The core rules are intuitive:

• Queries on the same data add up. Run 10 queries each with ε = 0.5, and your total budget spend is somewhere between 0.5 (best case, disjoint data) and 5.0 (worst case, same data).
• Queries on disjoint partitions are free. If each person's data falls in exactly one partition, queries on different partitions use independent budgets. For example, partitioning subscribers by account region (where each subscriber belongs to one region) means a per-region query uses only that region's budget. Partitioning CDRs by cell tower district does not qualify — a subscriber can appear in multiple districts.
• Once the budget is exhausted, no more queries can be served without violating the guarantee.

This means pipeline design must account for budget allocation upfront: how many queries will be supported, at what ε each, and how often the budget resets. Google's Privacy Loss Distribution tool (Module 05) automates budget tracking.

Deep dive

Composition theorems and budget management

Sequential composition (basic). $k$ queries with budgets $\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_k$ on the same dataset use total budget $\varepsilon_1 + \varepsilon_2 + \cdots + \varepsilon_k$.

Advanced composition. For $k$ identical queries each with budget $\varepsilon$, total privacy loss grows as $O(\varepsilon\sqrt{k})$ rather than $O(\varepsilon k)$ — critical for interactive analytics with hundreds of queries.

Parallel composition. Queries on disjoint data subsets don't compose — budgets don't add.

Budget management strategies in production:

• Fixed allocation. Pre-allocate ε to specific reports. A monthly mobility report gets ε = 0.5; a quarterly partner export gets ε = 1.0. Predictable and auditable, but no room for ad hoc queries.
• Per-release budgeting. The dataset is refreshed periodically (daily, weekly). Each refresh gets its own budget, and once exhausted, consumers wait for the next release. Caveat: this only provides a clean budget reset if each release covers a disjoint time window with no overlapping individuals. If the same people appear across releases, privacy loss composes across them — either use disjoint cohorts or track cumulative budget longitudinally.
• Rényi DP (RDP) accounting. Tighter composition bounds using Rényi divergence. Google's Privacy on Beam and OpenDP both support it — can unlock 20–40% more queries for the same total ε.

The budget question surfaces early in client engagements: "How many reports can we generate before the privacy guarantee degrades?" Plan this during architecture design, not after deployment.

Central vs local differential privacy

Central DP. A trusted curator holds the raw data and adds noise to query outputs. This is the standard model for enterprise analytics — the data warehouse holds unmodified data, and a DP layer sits between the data and any external consumer.

Local DP. Each data source adds noise before sending data anywhere. No central party ever sees raw individual data. This is how Apple and Google collect usage statistics — each device randomizes its response before reporting. The trade-off: local DP needs much more data to achieve comparable aggregate accuracy.

Scenario	Model	Rationale
Data warehouse analytics, partner exports	Central DP	Data already centralized; curator is trusted
Collecting data from end-user devices / IoT	Local DP	Users don't trust a central party with raw data
Federated learning	Local DP	Gradients are randomized before aggregation

For Aliz client engagements, central DP is almost always the relevant model — clients already hold the data centrally and want to share aggregates safely. Local DP arises only when designing data collection from end users or IoT devices.

Post-processing immunity

Any computation applied to the output of a DP mechanism preserves the DP guarantee. Filter it, transform it, join it with other data, train a model on it — the result is still DP-protected. This means you enforce privacy once (at query time) and trust everything downstream. Compare this to k-anonymity, where joining an anonymized dataset with auxiliary data can destroy the privacy guarantee entirely.

Engineer takeaway

Differential privacy is the right model when the output leaves a controlled environment — shared with partners, published externally, used in a product visible to end users. Its post-processing immunity means you enforce privacy once and it holds regardless of what consumers do with the data. For internal analytics where access is controlled and the data stays in the warehouse, k-anonymity with role-based dynamic masking (Module 05) is often simpler and sufficient. Module 10 covers the operational side of budget management and monitoring.

---

Choosing and combining models

No single privacy model covers all use cases. The choice depends on what data is being released, who the consumer is, and what level of guarantee is defensible.

k-anonymity as baseline, DP for analytical outputs

The most common production pattern layers two models:

1. Structural anonymization (k-anonymity, optionally with l-diversity) for record-level datasets — the output contains individual records with generalized quasi-identifiers. Use this when the consumer needs row-level data for joins, filtering, or per-record analysis.

2. Differential privacy for aggregate outputs — counts, sums, averages, histograms, model predictions. Use this when the consumer needs statistics, not individual records.

These serve different stages of a data pipeline. In a telco architecture (Module 06):

Data zone	Privacy model	What it protects	Consumer
Raw zone	None (access-controlled)	N/A	ETL pipelines only
Pseudonymized zone	Access controls + dynamic data masking (DDM)	Identity (operational pseudonymization)	Internal analysts with appropriate roles
Anonymized zone	k-anonymity (k=50+)	Identity + partial attribute	Internal analytics, broad access
External sharing	Differential privacy	Formal guarantee against any inference	Partners, regulators, public

Selection guide

When formal guarantees matter vs when they're overkill

Formal privacy models add complexity — parameter tuning, utility loss, budget management, specialized tooling. They are not always necessary:

Formal models are essential when:

• Data leaves the organization (partner sharing, publication, regulatory submission)
• There is a contractual or regulatory requirement for "anonymized" data with a defensible definition
• The data is high-sensitivity (location/mobility, health, financial) and re-identification would cause material harm
• The data will be linked with external datasets by the consumer

Formal models are typically overkill when:

• Data stays within a controlled environment with access controls and audit logging
• The use case is dev/test environments (static masking or synthetic data is sufficient — Module 03)
• The consumer is a production system doing operational lookups, not analytics (pseudonymization + access controls is the pattern)
• The dataset is ephemeral (e.g., a one-time analysis that produces aggregate results and is then deleted)

The practical test: if the data were breached or misused by the consumer, would the absence of a formal privacy guarantee be a defensible position? If yes, access controls + pseudonymization may suffice. If no, invest in k-anonymity, DP, or both.

Engineer takeaway

In client conversations, map the privacy model to the data zone. Raw and pseudonymized zones use access controls — the data is still personal data, and the protection is organizational. The anonymized zone and external outputs need formal models — the data must be defensibly non-personal. Don't over-engineer internal zones with formal models (it adds cost and reduces utility for no regulatory benefit), and don't under-protect external outputs with just pseudonymization (it's not anonymization, and regulators know the difference).

---

Summary comparison

Model	Protects against	Mechanism	Key parameter	Primary use case	Main limitation
k-anonymity	Identity disclosure (singling out)	Generalization + suppression	k (minimum group size)	Record-level datasets for analytics	No protection against attribute disclosure
l-diversity	Attribute disclosure (homogeneity)	Enforce diverse sensitive values per group	l (minimum distinct values)	Datasets with rich sensitive attributes	Fails for low-cardinality or semantically similar values
t-closeness	Attribute inference (distribution skew)	Enforce distribution similarity per group	t (max EMD distance)	High-sensitivity, tightly regulated contexts	Severe utility loss; hard to parameterize
Differential privacy	Any inference from output	Calibrated noise addition	ε (privacy budget), δ (failure probability)	Aggregate outputs, external sharing, ML	Budget management; utility loss for small groups

Next: Module 05 covers the tooling landscape — GCP Sensitive Data Protection, BigQuery security features, Cloud KMS, Dataflow, and the open-source alternatives (ARX, OpenDP, Presidio) that implement these models.

---

Created by Claude Opus with ❤️ for the Aliz Data Engineering team.