Optimum Noise Mechanism for Differentially Private Queries in Discrete Finite Sets

Most published work on differential privacy (DP) focuses exclusively on meeting privacy constraints, by adding to the query noise with a pre-specified parametric distribution model, typically with one or two degrees of freedom. The accuracy of the response and its utility to the intended use are frequently overlooked. Considering that several database queries are categorical in nature (e.g., a label, a ranking, etc.), or can be quantized, the parameters that define the randomized mechanism's distribution are finite. Thus, it is reasonable to search through numerical optimization for the probability masses that meet the privacy constraints while minimizing the query distortion. Considering the modulo summation of random noise as the DP mechanism, the goal of this paper is to introduce a tractable framework to design the optimum noise probability mass function (PMF) for database queries with a discrete and finite set, optimizing with an expected distortion metric for a given $(\epsilon,\delta)$. We first show that the optimum PMF can be obtained by solving a mixed integer linear program (MILP). Then, we derive closed-form solutions for the optimum PMF that minimize the probability of error for two special cases. We show numerically that the proposed optimal mechanisms significantly outperform the state-of-the-art.