t-Closeness: Privacy Beyond k-Anonymity and l-Diversity

TLDR

k‑anonymity requires each equivalence class to contain at least k records, but it cannot prevent attribute disclosure, leading to the proposal of l‑diversity, which demands at least l well‑represented values for each sensitive attribute. The paper demonstrates the limitations of l‑diversity and introduces t‑closeness as a new privacy notion. t‑closeness requires that the distribution of a sensitive attribute in any equivalence class be within a threshold t of the overall distribution, measured using the earth‑mover distance, and the authors illustrate its advantages with examples and experiments. The study finds that l‑diversity is neither necessary nor sufficient to prevent attribute disclosure.

Abstract

The k-anonymity privacy requirement for publishing microdata requires that each equivalence class (i.e., a set of records that are indistinguishable from each other with respect to certain "identifying" attributes) contains at least k records. Recently, several authors have recognized that k-anonymity cannot prevent attribute disclosure. The notion of l-diversity has been proposed to address this; l-diversity requires that each equivalence class has at least l well-represented values for each sensitive attribute. In this paper we show that l-diversity has a number of limitations. In particular, it is neither necessary nor sufficient to prevent attribute disclosure. We propose a novel privacy notion called t-closeness, which requires that the distribution of a sensitive attribute in any equivalence class is close to the distribution of the attribute in the overall table (i.e., the distance between the two distributions should be no more than a threshold t). We choose to use the earth mover distance measure for our t-closeness requirement. We discuss the rationale for t-closeness and illustrate its advantages through examples and experiments.