Differential Privacy for Geometric Data

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Differential Privacy for Geometric Data"

By

Miss Yuting LIANG


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 
neighbors 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:                   Tuesday, 10 June 2025

Time:                   10:00am - 12:00noon

Venue:                  Room 3494
                        Lifts 25/26

Chairman:               Prof. Jianfeng CAI (MATH)

Committee Members:      Prof. Ke YI (Supervisor)
                        Dr. Sunil ARYA
                        Prof. Siu-Wing CHENG
                        Dr. Sisi JIAN (CIVL)
                        Prof. Haibo HU (PolyU)