Privacy risk diagnosis: Mining l-diversity

Abstract

Most of the recent efforts addressing the issue of data privacy have focused on devising algorithms for anonymization and diversification. Our objective is upstream of these works: we are concerned with the diagnosis of privacy risk and more specifically in this paper with l-diversity. We show that diagnosing l-diversity for various definitions of the concept is a knowledge discovery problem that can be mapped to the framework proposed by Mannila and Toivonen. The problem can therefore be solved with level-wise algorithms such as the apriori algorithm. We introduce and prove the necessary monotonicity property with respect to subset operator on attributes set for several instantiations of the l-diversity principle. We present and evaluate an algorithm based on the apriori algorithm. This algorithm computes, for instance, "maximum sets of attributes that can safely be published without jeopardizing sensitive attributes", even if they were quasi-identifiers available from external sources, and "minimum subsets of attributes which jeopardize anonymity". © 2009 Springer Berlin Heidelberg.