Differential Privacy Beyond The Central Model

A differentially private algorithm adds randomness to its computations to ensure that its output reveals little about its input. This careful decoupling of output and input provides privacy for users that contribute input data, but the nature of this privacy depends on the model of differential privacy used. In the most common model, a differentially private algorithm receives a raw database and must produce a differentially private output. This privacy guarantee requires several assumptions. There must exist a secure way of sending the data to the algorithm; the algorithm must maintain a secure state while carrying out its computations; and data contributors must trust the algorithm operator to responsibly steward their raw data in the future. When these three assumptions hold, differential privacy offers both meaningful utility and privacy. In this dissertation, we study what is possible when these assumptions fail. Pan-privacy weakens the first two assumptions and removes the third. Local differential privacy removes all three. Unfortunately, this flexibility comes at a cost. Pan-privacy often introduces more random noise, and local differential privacy adds more noise still. This reduces utility in the forms of worse accuracy and higher sample complexity. Motivated by this trade-off between privacy and utility, it is important to understand the relative powers of these models. We approach this question in two ways. The first part of this dissertation focuses on connections between different models: we show that in some settings, it is possible to convert algorithms in one model to algorithms in another. The second part of this dissertation complements these connections with separations: we construct problems where algorithms in different models must obtain different performance guarantees