Models and algorithms for data privacy
Rajeev Motwani, Krishnaram Kenthapadi · 2006
Over the last twenty years, there has been a tremendous growth in the amount of private data that can be collected and analyzed digitally. On the one hand, this has led to the development of data mining tools that aim to infer useful trends from this data. But, on the other hand, easy access to personal data poses a threat to individual privacy. In this thesis, we provide models and algorithms for protecting the privacy of individuals in such large data sets while still allowing users to mine useful trends and statistics. We focus on two frameworks for protecting privacy in statistical databases. The first part of the thesis focuses on the interactive framework, in which the user (researcher) queries the database through a privacy mechanism, which may deny the query or alter the answer in order to ensure privacy. We first consider the online query auditing problem: given a sequence of queries about the data, their corresponding answers and given a new query, deny the answer if privacy can be breached or give the true answer otherwise. We uncover the fundamental problem that query denials leak information and introduce the simulatable auditing model to overcome this problem. We also describe a probabilistic notion of (partial) compromise, in order to overcome the known limitations of the existing privacy definition. We then present simulatable auditing algorithms under both these definitions. The second problem we consider is output perturbation, in which the database administrator computes exact answer to the query and then outputs a perturbed answer as the response to the query. Inspired by the desire to enable individuals to retain control over their information, we provide a fault-tolerant distributed implementation of output perturbation schemes, thereby eliminating the need for a trusted database administrator. The second part of the thesis focuses on the non-interactive framework and considers two anonymization methods for publishing data. We present approximation algorithms for anonymizing databases under the k-Anonymity model. Then we propose a new method for anonymizing data records, where the data records are clustered and then cluster centers are published, and provide approximation algorithms.