Differential Privacy for Geometric Data

Abstract

Differential Privacy (DP) is the de facto privacy model for protecting personal information; it has received extensive attention from the privacy research community, and many useful tools have been developed. Roughly speaking, DP requires an algorithm to produce similar outputs on all pairs of input datasets differing by one record, and does not differentiate based on the actual distance between the differing records. This requirement is too strong for data that reside in a metric space with a large (or even unbounded) diameter. An alternative privacy definition which can be seen as an extension of DP to metric spaces is known as Geo-Privacy (GP); it offers a guarantee similar to DP except that it allows the guarantee to be dependent on the distance between each pair of inputs. However, unlike DP, GP is much less studied and previous tools for GP privatization had been limited.

In this thesis, we develop new tools with supporting theory for GP privatization. We first introduce a generalized definition for Geo-Privacy, which fully captures standard DP as a special case. Then, we generalize the Smooth Sensitivity framework for DP to GP equipped with an arbitrary metric. Next, we present our Concentrated Geo-Privacy (CGP) definition, a closely related alternative to GP which offers better composability. Finally, we present our adaptive budgeting framework, where we also generalize privacy filters from DP to GP. To verify the applicability and utility of our frameworks, we discuss several applications: one-way, two-way threshold functions and general range counting, Gaussian KDE estimation, k nearest neighbours and the convex hull query. We provide theoretical analyses and experimental evaluation to demonstrate improved utility over the previous basic mechanism for GP privatization.

Date of Award	2025
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology
Supervisor	Ke YI (Supervisor)