Optimized Budget Selection For Local Differential Privacy

In recent years, local differential privacy (LDP) has emerged as a popular privacystandard and received significant attention from academia and the industry. Thereis increasing interest in its deployment in industrial applications, smart homes, andsmart cities. A pivotal problem in LDP is how to select the value of the privacybudget parameter ε, which controls the tradeoff between the strength of privacyprotection and utility loss.In this dissertation, we propose Optimus, a utility-driven and optimization-basedapproach for ε budget selection in LDP. Given a utility constraint, Optimus formulatesthe problem of budget selection as an optimization problem and contains fivesolution methods for finding the minimal ε that satisfies the given constraint. We experimentallyevaluate the five solution methods in Optimus using five popular LDPprotocols, two datasets, and varying utility constraints. We find that the ε budgetsselected by the different methods are consistent, which is important considering thatLDP is randomized and the optimization process is heuristic. Furthermore, we performcomparative analyses regarding the methods’ efficiency and hyperparametersto assist in their future use. To the best of our knowledge, Optimus is the firstwork to provide a quantitative and algorithmic approach to solving the challenge ofε budget selection in LDP.Beside Optimus which is a general approach for utility-driven budget selection in LDP, we also consider the capacity planning problem specifically, as a practicalapplication in smart homes. Since, the main premise of LDP is that data is perturbedto protect privacy, therefore consumption statistics estimated via LDP are inherentlynoisy. When noisy estimates are used for capacity planning, they can lead to falsepositives (false claims of capacity exceedance) or false negatives (actual exceedancesare neglected).To address these concerns, we propose a system called CAPRI for capacity planningand optimized budget selection in smart city applications under LDP. Based ona specified set of conditions (e.g., number of clients, possible consumption values,LDP protocol) and constraints (e.g., false positive probability should be below 0.01),CAPRI is able to determine the ε privacy budget which simultaneously satisfies thedesired constraints and maximizes clients’ privacy. To do so, CAPRI proposes anoptimization-based problem formulation and a search-based solution which relies onLDP simulations. We experimentally validate and demonstrate the effectiveness ofCAPRI using real-world and synthetic datasets, three popular LDP protocols, andvarious constraints and conditions.