A Privacy Score for Anonymous Databases

Abstract

In this thesis, we present a quantitative measure called the Database Privacy Score to assess the level of privacy in an anonymous database. Individuals in an anonymous database are still at risk of having personal information uncovered about them in a linkage attack. A privacy score is assigned to each individual in the database, measuring the risk of an adversary gaining new knowledge about them in a linkage attack. This requires looking at a set of attributes K and determining which additional attributes can be inferred from knowing K. This is where the bulk of the computational work occurs, and we present algorithms for computing this. C++ source code is included in the Appendix for all computations involved in computing the Database Privacy Score. We also show that under certain assumptions, applying k-anonymity to a database cannot worsen the privacy score, although there is no guarantee that it will improve the score. We also look at privacy from a topological perspective, and propose a solution for removing inferences that come from topological holes in the Dowker Complex representing our database.