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.