L-Diversity
L-Diversity is the privacy model that extends k-anonymity by requiring each equivalence class to contain at least l "well-represented" values for sensitive attributes — addressing the homogeneity attack where all records in a k-anonymous group share the same sensitive value, ensuring that an attacker who identifies an individual's equivalence class still faces meaningful uncertainty about their sensitive attribute.
What Is L-Diversity?
- Definition: A dataset satisfies l-diversity if every equivalence class (group of records sharing quasi-identifier values) contains at least l distinct values for each sensitive attribute.
- Core Improvement: Adds diversity of sensitive values within each group, preventing the homogeneity attack that defeats k-anonymity.
- Key Paper: Machanavajjhala et al. (2007), "L-Diversity: Privacy Beyond K-Anonymity."
- Relationship: Strictly stronger than k-anonymity — l-diversity implies k-anonymity with k ≥ l, but not vice versa.
Why L-Diversity Matters
- Addresses Homogeneity: Prevents the case where all records in a group share the same sensitive value (e.g., all have "HIV+"), which leaks sensitive information despite k-anonymity.
- Stronger Privacy: Even if an attacker identifies someone's equivalence class, they face uncertainty about the sensitive attribute.
- Practical Improvement: Many real datasets have clusters with similar sensitive values that k-anonymity alone doesn't protect.
- Building Block: Provides additional privacy on top of k-anonymity without dramatically different implementation.
The Problem L-Diversity Solves
| 3-Anonymous Group | Disease | Privacy |
|---|---|---|
| Age 20-30, ZIP 021 | Cancer | ✗ All same — attacker knows diagnosis |
| Age 20-30, ZIP 021 | Cancer | ✗ (homogeneity attack) |
| Age 20-30, ZIP 021 | Cancer | ✗ |
| 3-Diverse Group | Disease | Privacy |
|---|---|---|
| Age 20-30, ZIP 021 | Cancer | ✓ Three different values |
| Age 20-30, ZIP 021 | Flu | ✓ (l=3 diversity) |
| Age 20-30, ZIP 021 | Diabetes | ✓ |
Variants of L-Diversity
| Variant | Requirement | Strength |
|---|---|---|
| Distinct | At least l different sensitive values per group | Basic — minimum requirement |
| Entropy | Entropy of sensitive values ≥ log(l) | Stronger — prevents skewed distributions |
| Recursive (c,l) | Most frequent value appears < c × least frequent | Strongest — limits any value from dominating |
How to Achieve L-Diversity
- Further Generalization: Merge equivalence classes that lack diversity until each group meets the l threshold.
- Anatomization: Separate quasi-identifiers from sensitive attributes into linked tables.
- Record Suppression: Remove records from homogeneous groups to ensure diversity.
- Redistribution: Reassign records between groups to balance sensitive value diversity.
Limitations
- Semantic Similarity: Two "diverse" values may be semantically similar (e.g., "stomach cancer" and "colon cancer" are both cancer).
- Attribute Disclosure: Even with l diverse values, skewed distributions can leak information probabilistically.
- High-Cardinality: Difficult to achieve when sensitive attributes have few possible values.
- Addressed by: T-Closeness, which requires the distribution of sensitive values in each group to be close to the overall distribution.
L-Diversity is an essential advancement in data anonymization — providing the diversity guarantees that k-anonymity lacks by ensuring that knowledge of an individual's quasi-identifier group still leaves meaningful uncertainty about their sensitive attributes.