Differentially Private Consistent Release of Counting Queries
TL;DR
This work studies the problem of releasing counting-query outputs through a stochastic mechanism that is both consistent and \((\epsilon,\delta)\)-differentially private and derives upper and lower bounds on the optimal achievable performance based on convex mixing and spectral perturbation.
Abstract
We study the problem of releasing counting-query outputs through a stochastic mechanism that is both consistent and \((\epsilon,\delta)\)-differentially private. Consistency requires the released value to lie within the feasible range of the query, while utility is measured by the worst-case probability of error. We first derive a closed-form expression for the minimum achievable error probability and obtain an explicit optimal mechanism. By exploiting the active differential privacy constraints satisfied by this mechanism, we then characterize the entire class of optimal mechanisms via a propagation argument, identifying the structural properties shared by all optimizers. We next extend the framework to the setting in which the privacy mechanism is cascaded with an arbitrary fixed stochastic transformation representing a predetermined portion of the communication medium between the source and the destination. We first establish necessary and sufficient conditions under which this partial fixation of the medium incurs no loss in utility. We then derive upper and lower bounds on the optimal achievable performance based on convex mixing and spectral perturbation. Finally, we apply the theory to (M)-ary phase-shift keying (PSK) transmission over an additive white Gaussian noise (AWGN) channel and show that uncoded transmission is effectively optimal in the high-privacy regime.