T-Closeness
T-Closeness is the privacy model requiring that the distribution of sensitive attribute values within each equivalence class be close to the distribution in the overall dataset — measured by a distance metric not exceeding threshold t, addressing both the homogeneity attack (defeated by l-diversity) and the skewness attack where the distribution within a group reveals information even when values are diverse.
What Is T-Closeness?
- Definition: A dataset satisfies t-closeness if the distance between the distribution of a sensitive attribute in any equivalence class and the distribution in the overall dataset is no more than threshold t.
- Distance Metric: Typically uses Earth Mover's Distance (EMD), which measures the minimum "work" needed to transform one distribution into another.
- Key Paper: Li, Li, and Venkatasubramanian (2007), "T-Closeness: Privacy Beyond K-Anonymity and L-Diversity."
- Hierarchy: t-Closeness implies l-diversity implies k-anonymity — each model is strictly stronger than the previous.
Why T-Closeness Matters
- Skewness Attack Prevention: Even l-diverse groups can have skewed sensitive value distributions — if 90% of a group has "cancer" vs. 10% in the population, the disease is highly likely.
- Distributional Privacy: Ensures that membership in an equivalence class reveals minimal probabilistic information about sensitive attributes.
- Strongest Statistical Guarantee: Among the k-anonymity family of models, t-closeness provides the strongest privacy protection.
- Information-Theoretic Foundation: The distance threshold t directly bounds the information gain from group membership.
The Problem T-Closeness Solves
| Scenario | Group Distribution | Population Distribution | Privacy |
|---|---|---|---|
| L-Diverse but Skewed | Cancer: 80%, Flu: 10%, Cold: 10% | Cancer: 10%, Flu: 45%, Cold: 45% | ✗ Group membership strongly suggests cancer |
| T-Close | Cancer: 12%, Flu: 43%, Cold: 45% | Cancer: 10%, Flu: 45%, Cold: 45% | ✓ Group is similar to population |
How T-Closeness Works
| Component | Description | Implementation |
|---|---|---|
| Equivalence Class | Group of records sharing quasi-identifiers | Grouped by generalized attributes |
| Class Distribution | Frequency of sensitive values within group | Count sensitive values per group |
| Overall Distribution | Frequency of sensitive values in full dataset | Count sensitive values globally |
| EMD Calculation | Distance between class and overall distributions | Earth Mover's Distance computation |
| Threshold Check | Verify EMD ≤ t for every equivalence class | Reject or modify groups exceeding t |
Earth Mover's Distance (EMD)
- Intuition: The minimum cost of transforming one distribution into another by "moving earth" (probability mass).
- Numerical Attributes: EMD accounts for the ordered nature of values (age 30 is closer to 35 than to 80).
- Categorical Attributes: EMD treats all categories as equidistant.
- Normalized: EMD is normalized to [0, 1] range for threshold comparison.
Limitations
- Utility Impact: Strict t thresholds can severely reduce data utility through heavy generalization.
- Parameter Selection: Choosing appropriate t is application-dependent with no universal guideline.
- Computational Cost: EMD computation and achieving t-closeness are more expensive than k-anonymity or l-diversity.
- Diminishing Returns: Very low t values may provide negligible additional protection over moderate values.
- Modern Alternative: Differential privacy provides stronger, composable guarantees without the group-based framework.
T-Closeness is the strongest member of the k-anonymity family of privacy models — closing the distributional loopholes in k-anonymity and l-diversity by ensuring that group membership reveals minimal information about sensitive attributes, providing near-population-level uncertainty for any identified individual.