l-Diversity

The simplest form of l-diversity requiring each equivalence class to contain at least l distinct values for the sensitive attribute.

• Guarantee: An adversary cannot pinpoint the exact sensitive value, only narrow it down to one of at least l possibilities.
• Limitation: Vulnerable to probabilistic inference attacks if one value appears far more frequently than others, even if l distinct values exist.
• Example: In a medical dataset, if an equivalence class contains 'HIV', 'Cancer', and 'Flu', but 'HIV' appears in 95% of records, the distinct requirement is met but privacy is weak.

A stronger variant requiring the entropy of the sensitive attribute distribution in each equivalence class to be at least log(l).

• Mechanism: Entropy measures the uncertainty of a distribution. Higher entropy means more uniform distribution of values.
• Advantage: Protects against skewness attacks where one sensitive value dominates, unlike distinct l-diversity.
• Formula: For a class with sensitive values s1, s2, ..., sm and probabilities p1, p2, ..., pm, entropy H = -Σ pi × log(pi) must exceed log(l).
• Trade-off: More computationally intensive to verify and enforce than distinct l-diversity.

Ensures that the most frequent sensitive value in an equivalence class does not appear too often relative to the less frequent values.

• Constraint: The frequency of the most common value must be less than c times the sum of frequencies of the least common values.
• Parameter c: A user-defined constant, typically between 1 and 3, controlling the strictness of the balance requirement.
• Protection: Defends against homogeneity attacks by capping the dominance of any single sensitive attribute value.
• Use Case: Ideal when certain sensitive values are inherently rare but highly sensitive, preventing their concentration in small groups.

Addresses the scenario where an adversary can positively identify an individual's sensitive attribute with high confidence, even without exact certainty.

• Problem: In k-anonymity, if all k records in an equivalence class share the same sensitive value, the adversary knows the individual's sensitive attribute with 100% certainty.
• l-Diversity Solution: By ensuring at least l well-represented values, the adversary's confidence is capped at 1/l for any single guess.
• Real-World Impact: Critical for attributes like HIV status, genetic markers, or financial fraud flags where any probabilistic leak is unacceptable.
• Threshold Selection: l is typically set between 3 and 10, balancing privacy with data utility.

Despite its improvements over k-anonymity, l-diversity has known vulnerabilities that led to stronger models like t-closeness.

• Similarity Attacks: When sensitive values in an equivalence class are semantically similar (e.g., all are stomach-related diseases), the adversary still learns sensitive information.
• Skewness Attacks: Distinct l-diversity fails when the overall dataset distribution is skewed and this skew is reflected in equivalence classes.
• Background Knowledge Attacks: Adversaries with external knowledge about an individual may still infer sensitive values even with diversity.
• Utility Trade-off: Enforcing l-diversity on high-dimensional data can require excessive generalization, destroying analytical value.

l-Diversity is typically enforced during the generalization and suppression phase of a de-identification pipeline.

• Process: Quasi-identifiers are generalized (e.g., age 34 → age range 30-40) until each resulting equivalence class satisfies the chosen l-diversity variant.
• Algorithms: Common approaches include Mondrian multidimensional partitioning and top-down specialization adapted for l-diversity constraints.
• Integration: Often combined with k-anonymity as a baseline, then l-diversity is applied as an additional filter on the anonymized groups.
• Tools: Libraries like ARX Data Anonymization Tool support configurable l-diversity models for production pipelines.

A set of non-sensitive attributes that, when combined with external data, can uniquely or nearly uniquely identify an individual. Common QIDs include date of birth, ZIP code, and gender. The l-diversity model operates by grouping records into equivalence classes based on generalized QID values, then ensuring each class contains at least l well-represented sensitive values. Identifying and selecting appropriate QIDs is the critical first step in any anonymization pipeline.

A structured taxonomy organizing attribute values from specific to general, used to achieve k-anonymity and l-diversity. For example, a ZIP code 90210 might be generalized to 9021*, then 902, then California. By replacing precise QID values with broader categories, records naturally group into equivalence classes. The challenge is balancing information loss against privacy protection—over-generalization destroys analytical utility while under-generalization fails privacy requirements.

The complete removal of an entire column or attribute from a dataset when it poses unacceptable re-identification risk. In l-diversity implementations, suppression may be applied to outlier records that cannot be grouped into equivalence classes meeting the l-diversity threshold without excessive generalization. This creates a trade-off: suppressed records reduce dataset completeness but prevent the minimal group size violations that would otherwise compromise the privacy model.