On Randomization, Public Information and the Curse of Dimensionality

A key method for privacy preserving data mining is that of randomization. Unlike k-anonymity, this technique does not include public information in the underlying assumptions. In this paper, we provide a first comprehensive analysis of the randomization method in the presence of public information. We define a quantification of the randomization method which we refer to as k-randomization of the data. The inclusion of public information in the theoretical analysis of the randomization method results in a number of interesting and insightful conclusions. These conclusions expose some vulnerabilities of the randomization method. We show that the randomization method is unable to effectively achieve privacy in the high dimensional case. We theoretically quantify the degree of randomization required to guarantee privacy as a function of the underlying data dimensionality. Furthermore, we show that the randomization method is susceptible to many natural properties of real data sets such as clusters or outliers. Finally, we show that the use of public information makes the choice of perturbing distribution very critical in a number of subtle ways. Our analysis shows that the inclusion of public information in the analysis makes the goal of privacy preservation more elusive than previously thought for the randomization method.