The optimal mechanism in differential privacy

Differential privacy is a framework to quantify to what extent individual privacy in a statistical database is preserved while releasing useful aggregate information about the database. This dissertation studies the fundamental trade-off between privacy and utility in differential privacy in the most basic problem settings. We first derive the optimal (epsilon)-differentially private mechanism for single real-valued query function under a very general utility-maximization (or cost-minimization) framework. The class of noise probability distributions in the optimal mechanism has staircase-shaped probability density functions which are symmetric (around the origin), monotonically decreasing and geometrically decaying. The staircase mechanism can be viewed as a geometric mixture of uniform probability distributions, providing a simple algorithmic description for the mechanism. Furthermore, the staircase mechanism naturally generalizes to discrete query output settings as well as more abstract settings. We explicitly derive the parameter of the optimal staircase mechanism for ell_1 and ell_2 cost functions. Comparing the optimal performances with those of the usual Laplacian mechanism, we show that in the high privacy regime (epsilon is small), the Laplacian mechanism is asymptotically optimal as epsilon to 0; in the low privacy regime (epsilon is large), the minimum magnitude and second moment of noise are Theta(Delta e^{-epsilon/2) and Theta(Delta^2 e^{-{2\epsilon}/{3}) as epsilon to +infinity, respectively, while the corresponding figures when using the Laplacian mechanism are {Delta}/{epsilon} and {2\Delta^2}/{\epsilon^2}, where Delta is the sensitivity of the query function. We conclude that the gains of the staircase mechanism are more pronounced in the low privacy regime. We also show the optimality of the staircase mechanism for epsilon- differentially privacy in the multiple dimensional setting where the query output has multiple components, e.g., histogram query function. We prove that when the dimension is two, for the ell^1 cost function, the noise probability distribution in the optimal mechanism has a multiple dimensional staircase-shaped probability density function. We explicitly derive the parameter of the optimal two-dimensional staircase mechanism, and study the asymptotical performance of optimal mechanism in the high and low privacy regimes. Comparing the optimal performances with those of the usual Laplacian mechanism, we show that in the high privacy regime (epsilon is small), the Laplacian mechanism is asymptotically optimal as epsilon to 0; in the low privacy regime (epsilon is large), the optimal cost is Theta(e^{-{epsilon}/{3}), while the cost of the Laplacian mechanism is {2\Delta}/{\epsilon}. We conclude that the gains of the staircase mechanism are more pronounced in the low privacy regime. Lastly, we study the optimal mechanisms in (epsilon, delta)-differential privacy for integer-valued query functions under a utility-maximization/cost-minimization framework. We show that the…