Optimum Noise Mechanism for Differentially Private Queries in Discrete Finite Sets

In this paper, we provide an optimal additive noise mechanism for database queries with discrete answers on a finite support. The noise provides the minimum error rate for a given $(\epsilon,\delta)$ pair. Popular schemes apply random additive noise with infinite support and then clamp the resulting query response to the desired range. Clamping, unfortunately, compromises the privacy guarantees. Using modulo addition, rather than clamping, we show that, for any $(\epsilon,\delta)$ pair, the optimum additive noise distribution can be obtained by solving a mixed integer linear program (MILP). Having introduced our optimal noise design formulation, we derive closed form solutions for the optimal noise probability mass function (PMF) and the probability of error for two special cases. In our performance studies, we show that the proposed optimal mechanism outperforms state of the art for a given probability of error and for any budget $\epsilon >0$.