Privacy Lab 02 — k-Anonymity / Re-identification Evaluator

WARMUP: Chapters 7–8 (de-identification, k-anonymity, l-diversity, DP).

Threat model

"We removed the names, so it's anonymous" is the most common — and most wrong — privacy claim. Quasi-identifiers (ZIP + birthdate + sex uniquely identify ~87% of Americans) re-identify people by joining a "de-identified" dataset with another. The "attacker" is re-identification by linkage. This engine measures anonymity: it groups records into equivalence classes on their quasi-identifiers, computes the achieved k (smallest class), rates re-identification risk, and checks l-diversity (k-anonymity's homogeneity blind spot).

What you build (lab.py)

  • equivalence_classes / k_anonymity / is_k_anonymous / num_unique — the core k-anonymity computation (achieved k = smallest equivalence class; uniques = trivially re-identifiable).
  • reidentification_risk — high (k≤1) / medium (k<5) / low (k≥5).
  • l_diversity / is_l_diverse — distinct sensitive values per class (catches homogeneity).
  • describe_deidentification(has_mapping) — pseudonymized vs anonymization-candidate.

Attack cases the tests cover

  • A dataset with unique quasi-identifier rows has k = 1 (high risk, uniques counted); a dataset where all rows share quasi-identifiers has k = N (lower risk).
  • l-diversity catches the homogeneity attack: a k-anonymous group where everyone has the same sensitive value (e.g. all "HIV") has l = 1 — identity is hidden but the diagnosis is not.
  • Pseudonymized (mapping exists) vs anonymization-candidate; empty-dataset edge case.

Run

pip install -r requirements.txt
LAB_MODULE=solution pytest -q
pytest -q

Hardening / extensions

  • Implement generalization/suppression to achieve a target k (the Mondrian algorithm) and report the information loss.
  • Add t-closeness (sensitive-value distribution close to the global one).
  • Add a differential-privacy count query (Laplace noise for a chosen ε) and compare guarantees.
  • Simulate a linkage attack against an auxiliary dataset to demonstrate re-identification.

Interview / resume

"Built a k-anonymity / re-identification evaluator that computes achieved k and l-diversity over a dataset's quasi-identifiers — demonstrating that 'removing names' isn't anonymization and that k-anonymity hides identity but not (without l-diversity) the sensitive attribute."

Limitations: measures k/l on given quasi-identifiers (doesn't choose them or generalize to reach a target); no differential privacy / linkage simulation in the core (left as extensions).