Smooth Sensitivity for Geo-Privacy

Suppose each user i holds a private value x i in some metric space (U, dist), and an untrusted data analyst wishes to compute i f (x i ) for some function f : U → R by asking each user to send in a privatized f (x i ). This is a fundamental problem in privacy-preserving population analytics, and the local model of differential privacy (LDP) is the predominant model under which the problem has been studied. However, LDP requires any two different x i , x ′ i to be ε-distinguishable, which can be overly strong for geometric/numerical data. On the other hand, Geo-Privacy (GP) stipulates that the level of distinguishability be proportional to dist(x i , x ′ i ), providing an attractive alternative notion of personal data privacy in a metric space. However, existing GP mechanisms for this problem, which add a uniform noise to either x i or f (x i ), are not satisfactory. In this paper, we generalize the smooth sensitivity framework from Differential Privacy to Geo-Privacy, which allows us to add noise tailored to the hardness of the given instance. We provide definitions, mechanisms, and a generic procedure for computing the smooth sensitivity under GP equipped with a general metric. Then we present three applications: oneway and two-way threshold functions, and Gaussian kernel density estimation, to demonstrate the applicability and utility of our smooth sensitivity framework.