Optimizing Linear Query Release under Pointwise Maximal Leakage

Sammanfattning

The widespread collection and analysis of personal data necessitate robust privacy protections to prevent unauthorized disclosure of sensitive information. This thesis investigates the privacy guarantees of answering linear queries using the Laplace mechanism, with a focus on the pointwise maximal leakage (PML) framework as a novel privacy metric. Unlike traditional differential privacy (DP), pointwise maximal leakage leverages prior distributional knowledge to quantify information leakage more precisely, offering a promising approach to balance privacy and data utility. We derive a tight PML bound for linear queries, demonstrating that it is strictly tighter than the DP bound when prior knowledge is incorporated, thus enabling reduced noise levels for equivalent privacy guarantees. For computational efficiency, we develop simplified upper bounds, which reduce complexity in computation from exponential to polynomial in the number of data classes. Additionally, we propose the PML-adapted Laplace mechanism (PALM), which optimizes noise scales for individual queries within a workload to enhance utility, particularly for queries with varying scales. Empirical evaluations on the UCI Adult dataset compare DP, PML, and PALM across random and fixed query workloads, showing that PML and PALM consistently outperform DP in terms of utility, with the PML-adapted Laplace mechanism achieving significant improvements in workloads with scale disparities. These findings highlight the potential of PML-based mechanisms for privacy-preserving data analysis in applications such as census data processing and healthcare statistics.