Schrödinger Mechanisms: Optimal Differential Privacy Mechanisms for Small Sensitivity
Wael Alghamdi, Shahab Asoodeh, Flávio P. Calmon, Juan Felipe Gomez, Oliver Kosut, Lalitha Sankar · 2023
We consider the problem of designing optimal differential privacy mechanisms with a favorable privacy-utility tradeoff in the limit of a large number n of compositions (i.e., sequential queries). Here, utility is measured by the average distance between the mechanism's input and output, evaluated by a cost function c. We show that if n is sufficiently large and the sensitivities of all queries are small, then the optimal additive noise mechanism has probability density function fully characterized by the ground-state eigenfunction of the Schrödinger operator with potential c. This leads to a family of optimal mechanisms, dubbed the Schrödinger mechanisms, depending on the choice of the cost function. Instantiating this result, we demonstrate that for c(x) = x2the Gaussian mechanism is optimal, and for c(x) = |x|, the optimal mechanism is obtained by the Airy function, thereby leading to the Airy mechanism.