k-anonymity is a formal privacy model for released datasets which requires that every record be indistinguishable from at least k-1 other records with respect to its quasi-identifiers, the attributes that could be linked to outside data to reveal identity. In privacy engineering, it is one of the earliest and most widely taught criteria for de-identification of tabular data, and it remains a common baseline in health, census and research data sharing.
The model was formalized around 1998 by Latanya Sweeney and Pierangela Samarati in response to linkage attacks, in which supposedly anonymous records were matched with public registers. Its core promise is limited but clear: an attacker who knows a person’s quasi-identifiers can narrow that person down only to a group of at least k.
How k-anonymity groups records
k-anonymity works by transforming the quasi-identifier columns until every combination of their values occurs at least k times. The records that share one combination form an equivalence class, and the smallest class size determines the k that the dataset achieves.
Attributes in a dataset are usually sorted into three roles before any transformation, as the following table shows.
| Attribute role | Examples | Typical treatment |
|---|---|---|
| Direct identifiers | Name, national ID number, email address | Removed or replaced before release |
| Quasi-identifiers | ZIP code, birth date, sex, occupation | Generalized or suppressed to reach k |
| Sensitive attributes | Diagnosis, salary, criminal record | Released unchanged under basic k-anonymity |
| Other attributes | Non-linkable measurements | Usually released unchanged |
The choice of quasi-identifiers is the decisive modeling step. A widely cited analysis of United States census data estimated that roughly 87 percent of residents were uniquely identified by five-digit ZIP code, birth date and sex, which shows how ordinary attributes combine into identifiers.
Generalization and suppression
Two operations achieve k-anonymity. Generalization replaces precise values with broader ones, for example an exact age with a ten-year band. Suppression removes whole records or individual cells that would otherwise form classes smaller than k.
| Quasi-identifier | Original value | Generalized value |
|---|---|---|
| Age | 37 | 30 to 39 |
| ZIP code | 02139 | 021xx |
| Birth date | 14 March 1986 | 1986 |
| Occupation | Pediatric nurse | Health professional |
| Admission date | 9 June 2024 | Second quarter of 2024 |
Algorithms such as Datafly, Incognito and Mondrian search for transformations that reach the target k with the least information loss. Mondrian, for example, partitions the multidimensional value space recursively, which often keeps more detail than applying one global hierarchy to every record. Finding an optimal solution is computationally hard in general, so practical tools use heuristics.
Choosing the value of k
The value of k expresses a re-identification risk threshold: under a simple model, the probability of correctly picking one person within a class is at most 1/k. Higher k lowers that risk but forces coarser data and more suppression.
| Value of k | Typical use | Trade-off |
|---|---|---|
| k = 2 to 3 | Internal analysis with strong access controls | High utility, weak protection |
| k = 5 | Shared research datasets | Moderate utility, moderate protection |
| k = 10 to 11 | Public statistical tables and health releases | Lower detail, stronger protection |
| k above 20 | Open data with highly sensitive content | Heavy generalization and suppression |
Some public health agencies apply a small-cell suppression rule that hides counts below 11, which is a k-anonymity-like threshold for aggregated tables. The right k depends on the release context: who receives the data, what outside data they hold and what contractual controls apply.
k-anonymity compared with stronger models
k-anonymity protects against identity disclosure but not always against attribute disclosure. Successor models address the gaps, and differential privacy takes a fundamentally different approach.
| Model | Guarantee | Main weakness addressed |
|---|---|---|
| k-anonymity | Each record hides in a group of at least k | Linkage on quasi-identifiers |
| l-diversity | Each group has at least l distinct sensitive values | Homogeneity of sensitive values |
| t-closeness | Sensitive value distribution per group stays close to the overall distribution | Skewed distributions within groups |
| Differential privacy | Output changes little whether any one person is included | Arbitrary background knowledge |
Unlike differential privacy, k-anonymity is a property of one released table, not of a randomized mechanism, so it offers no formal bound when the same data is released several times or combined with other releases.
Measuring utility and residual risk
A k-anonymized release is only useful if analysts can still answer their questions, so engineers measure information loss alongside risk. Common metrics include the discernibility metric, which penalizes large equivalence classes, the share of suppressed records and the generalization height reached in each hierarchy.
Risk is assessed in more than one way. The prosecutor model assumes the attacker knows the target is in the dataset, while the journalist model assumes the attacker only knows the target is in a wider population, which usually gives lower risk. Open-source tools such as ARX compute these measures and let engineers compare candidate transformations before choosing one.
A sound workflow records the chosen quasi-identifiers, the target k, the suppression limit and the risk model assumed, so that a later reviewer can reproduce and challenge the decision.
Known attacks and limitations
Several well-understood attacks show why k-anonymity alone is rarely sufficient for public release of rich data.
- Homogeneity attack: if all k records in a class share the same diagnosis, the attacker learns the diagnosis without identifying the row.
- Background knowledge attack: outside facts, such as a rare condition being unlikely for a given age, can rule out records within a class.
- Composition attack: two independently k-anonymized releases of overlapping data can be intersected to shrink classes.
- High-dimensional data: with many attributes, such as location traces or purchase histories, reaching k destroys most utility.
- Wrong quasi-identifier set: an attribute that seemed harmless may be available to the attacker and break the guarantee.
Under the GDPR, a k-anonymized dataset is often still pseudonymous personal data rather than anonymous data, because residual risk remains. Practitioners therefore combine k-anonymity with access controls, data use agreements and, where feasible, stronger models.
In plain words
Picture a crowd photo where every face is blurred, but people are still described by age, neighborhood and gender. If only one person in the photo is a 37-year-old man from a certain street, the blur does not help. k-anonymity makes sure every description fits at least k people, so nobody stands alone.
It does this by making details less precise, such as saying thirties instead of 37. The catch is that if everyone in a group shares the same secret, the secret still leaks, even though no single person is pointed out.
A real-world example
A regional hospital network wants to share five years of emergency admissions with a university research team. The privacy engineer treats age, sex, three-digit ZIP prefix and admission month as quasi-identifiers and sets a target of k = 5.
After generalizing ages into five-year bands and admission dates into quarters, about 2 percent of records still fall into classes smaller than five, mostly very old patients in rural areas, and these are suppressed. A check then reveals classes where every record has the same rare diagnosis, so the team adds an l-diversity requirement of 3 for the diagnosis column. The released file supports the planned analysis of seasonal admission trends, and the data use agreement prohibits linkage with other datasets.