Content area
Differential privacy (DP) has emerged as the de facto standard for releasing query results over private data. A considerable number of DP mechanisms have been developed to address various fundamental challenges, including mean and median estimation, releasing graph statistics, and answering SQL queries. These works aim to provide results with high utility, i.e. high accuracy, while ensuring DP protection. Some of these approaches have achieved near-optimal performance, meaning their errors closely approach the established DP lower bounds. Despite the advancements of current DP mechanisms in terms of utility, the practical adoption of DP remains relatively limited. This thesis seeks to enhance the practicality of DP to better align with real-world needs.
Firstly, we noticed that current DP mechanisms only provide a noisy query answer without indicating the potential error induced by this noisy result, which constrains further meaningful analysis. To fix this issue, we propose a series of differentially private confidence interval (CI) techniques that are (1) differentially private; (2) correct, i.e., the interval contains the true query answer with the specified confidence level; and (3) have good utility guarantee. Our techniques are applicable across a diverse range of problems, from basic statistical analyses to complex conjunctive queries.
Secondly, the standard DP model provides uniform privacy protection for all users, which may not be desirable in real applications since users may have different privacy concerns. So we study the personalized differential privacy (PDP) model, where each user may have a different privacy parameter. Within this framework, we present the personalized truncation mechanism which is the first PDP mechanism with an explicit utility guarantee. This mechanism is designed to accommodate a broad class of select-join-aggregate (SJA) queries over relational databases, even under foreign-key constraints.
Finally, in real-world contexts, users often face challenges in trusting service providers. Consequently, a common approach is that each user privatizes their data by themselves before sending it to an untrusted data analyzer, which is known as the local model of DP. We further extend our study of personalized privacy into the local DP model by developing advanced algorithms for sum estimation.