t-Closeness

The core mathematical foundation of t-closeness uses the Earth Mover's Distance to quantify the difference between two distributions. EMD measures the minimum amount of work required to transform one distribution into another by moving probability mass. For numerical attributes, this considers the ordered distance between values; for categorical attributes, it requires a defined semantic distance hierarchy. The equivalence class is considered t-close if the EMD between its sensitive attribute distribution and the global distribution is less than or equal to the threshold t.

t-Closeness directly addresses the skewness attack, a vulnerability where l-Diversity fails. If an equivalence class has l-distinct values but their overall distribution is significantly skewed relative to the global dataset, an attacker can infer probabilistic information about an individual. For example, if 99% of the global population tests negative for a disease but an l-diverse group has 50% positive, the attacker gains significant inferential power. t-Closeness constrains this distributional divergence.

The implementation of t-closeness differs by attribute type:

• Numerical Attributes: EMD is calculated using the ordered distance between values. The distribution is treated as a histogram, and the cost of moving mass between buckets is proportional to the difference in their values.
• Categorical Attributes: Requires a semantic distance hierarchy (e.g., a taxonomy tree) to define the cost of transforming one category into another. Without this hierarchy, EMD defaults to treating all distinct categories as equidistant, which may not reflect real-world semantics.

While providing stronger privacy than k-Anonymity and l-Diversity, t-Closeness introduces significant trade-offs:

• Information Loss: Enforcing tight distributional constraints across all equivalence classes can severely degrade data utility, especially for granular analyses.
• Computational Complexity: Calculating and optimizing EMD across multiple quasi-identifier groupings is NP-hard, making it impractical for high-dimensional datasets without heuristic approximations.
• Threshold Sensitivity: Selecting an appropriate t value is non-trivial. A value too low destroys utility; a value too high fails to prevent inference.

t-Closeness forms the third tier in the evolution of syntactic privacy models:

• k-Anonymity: Prevents record linkage (singling out an individual) by ensuring each QID group has at least k members.
• l-Diversity: Prevents attribute linkage (homogeneity attacks) by requiring l well-represented sensitive values per group.
• t-Closeness: Prevents distributional inference (skewness attacks) by bounding the distance between group-level and global sensitive attribute distributions. It is the only model of the three that explicitly limits probabilistic knowledge gain.

The defining constraint of t-closeness is formalized as: D[P, Q] ≤ t, where P is the distribution of the sensitive attribute within any equivalence class, Q is the distribution of that attribute across the entire dataset, and D is the distance metric (typically EMD). This ensures that an observer learns nothing more about an individual's sensitive attribute than what the global population distribution already reveals, effectively bounding the maximum information gain an adversary can achieve.

The foundational privacy model requiring each record to be indistinguishable from at least k-1 other records with respect to quasi-identifiers. While it prevents singling out individuals, it remains vulnerable to homogeneity attacks where all k records share the same sensitive value, and background knowledge attacks where an adversary can narrow possibilities using external information. t-Closeness directly addresses these limitations by constraining the distribution of sensitive attributes.

An extension of k-anonymity requiring each equivalence class to contain at least l well-represented values for sensitive attributes. Key variants include:

• Distinct l-diversity: At least l distinct sensitive values per class
• Entropy l-diversity: Entropy of sensitive values exceeds log(l)
• Recursive (c,l)-diversity: Most frequent value constrained below threshold

While stronger than k-anonymity, l-diversity still fails against skewness attacks where the overall dataset distribution differs from equivalence class distributions—the precise gap t-closeness fills.

A mathematical framework providing provable privacy guarantees by injecting calibrated noise into query results. Unlike syntactic models like t-closeness that transform data, differential privacy operates at the query interface level, ensuring the output distribution is nearly identical whether or not any single individual is included. The privacy loss is quantified by the epsilon budget, where lower epsilon values provide stronger guarantees at the cost of reduced utility. While t-closeness protects published datasets, differential privacy protects interactive queries.

A set of non-sensitive attributes that, when combined with external data, can uniquely or nearly uniquely identify an individual. Common QIDs include:

• Demographics: Age, gender, ZIP code
• Temporal markers: Admission date, discharge date
• Geographic indicators: Census tract, county

Identifying QIDs is the critical first step in applying t-closeness, as these attributes define the equivalence classes whose sensitive attribute distributions must be constrained within threshold t of the overall distribution.

The distance metric most commonly used to implement t-closeness, measuring the minimum work required to transform one distribution into another. For numerical attributes, EMD considers the ordered distance between values, making it sensitive to semantic closeness. For categorical attributes, EMD uses a hierarchy-based distance where related values (e.g., 'flu' and 'bronchitis') have smaller distances than unrelated ones (e.g., 'flu' and 'fracture'). The threshold t represents the maximum allowable EMD between any equivalence class distribution and the global distribution.

The probability that an adversary can successfully link de-identified records back to specific individuals using auxiliary information. Risk assessment methodologies include:

• Prosecutor risk: Likelihood a specific known individual is in the dataset
• Journalist risk: Probability of identifying any single record
• Marketer risk: Fraction of records identifiable at scale

t-Closeness reduces re-identification risk by ensuring that even if an adversary identifies an individual's equivalence class, the sensitive attribute distribution within that class mirrors the population, limiting information gain.