Exploring Models for Implementing Differential Privacy

Abstract

Researchers across many fields use statistical analysis on collected data to make decisions and inform policy. However, datasets collected from individuals may contain sensitive information. Ideally, we want to perform analysis that allows us to learn about the population as whole while keeping information private on an individual level. Formally, we use differential privacy to quantify the privacy loss associated with our analyses. In this thesis, we consider different models for differential privacy and construct private algorithms to solve common problems. We first consider a discrete setting where all computations are performed on rational numbers to more accurately simulate what is possible to implement on a real computer (i.e. not using real numbers). In this setting, we construct differentially private algorithms for releasing histograms that are both efficient and optimally accurate. The rest of the thesis considers a distributed setting where users hold their own data. We explore the shuffle model where users perform local computation on their data before sending messages ``anonymously'' to an untrusted analyzer. We construct differentially private algorithms in the shuffle model for releasing histograms, counting the number of distinct elements and uniformity testing. Finally, we consider the setting where malicious users interact with a semi-honest server. We give a candidate construction for solving secure multi-party computation in the client-server model with efficient clients under the LWE assumption and the existence of NIZKs. This would allow us to run differential private algorithms from the central model in a distributed setting.