Mathematical foundations of differential privacy

Abstract

Sensitive personal data collected about us has the potential to give great insight into human behaviour, but it remains a challenge to publish such information while guaranteeing (i) individuals’ privacy and (ii) data utility. This problem has received much attention in the computer science research community in recent decades. Since 2006, differential privacy has emerged as a popular paradigm to measure the privacy of sensitive data publications. In this thesis we explore the mathematical foundations of differential privacy, with a particular focus on the tradeoff of privacy and utility. After reviewing the history of the right to privacy and the literature on differential privacy, we present the cornerstone of our research: a single, unifying rigorous mathematical framework for differential privacy. The abstract approach taken allows for a wide variety of data types, query types and sanitisation methods to be handled in the one framework. This also allows us to prove results in generality. We take a special focus on 1-dimensional mechanisms, and their use in creating more general n-dimensional mechanisms. The versatility of this unifying framework is demonstrated when we apply it to the special case of categorical data. This also leads us to examine the polytope of differentially private mechanisms, and later to applying the differential privacy protocol to the randomised response technique, a privacy technique first proposed in 1965. We also examine the randomised response technique beyond differential privacy, and how efficiencies can be gained over previous methods. Throughout this thesis, a special focus is maintained on the privacy/utility tradeoff, and particularly on optimal mechanisms. We present error bounds on differentially private mechanisms, and derive the optimal mechanism for the max-mean error function. By examining the extreme points of the differential privacy polytope, we allow for the determination of the optimal mechanism for more general linear error functions. An optimal randomised response mechanism which satisfies differential privacy is also presented.