Optimal Noise Adding Mechanisms for Approximate Differential Privacy

• Published in: IEEE transactions on information theory 2016-02, Vol.62 (2), p.952-969
• Main Authors: Quan Geng, Viswanath, Pramod
• Format: Article
• Language: English
• Subjects: Approximation; Cost function; Cryptography; Data privacy; Laplace equations; Noise; Optimization; Privacy; Query processing; randomized algorithm; Sensitivity; Utilities
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2015.2504972

We study the (nearly) optimal mechanisms in (ϵ, δ)-differential privacy for integer-valued query functions and vector-valued (histogram-like) query functions under a utility-maximization/cost-minimization framework. Within the classes of mechanisms oblivious of the database and the queries beyond the global sensitivity, we characterize the tradeoff between ϵ and δ in utility and privacy analysis for histogram-like query functions, and show that the (ϵ, δ)-differential privacy is a framework not much more general than the (ϵ, 0)-differential privacy and (ϵ, δ)-differential privacy in the context of ℓ 1 and ℓ 2 cost functions, i.e., minimum expected noise magnitude and noise power. In the same context of ℓ 1 and ℓ 2 cost functions, we show the near-optimality of uniform noise mechanism and discrete Laplacian mechanism in the high privacy regime (as (ϵ, δ) → (0, 0)). We conclude that in (ϵ, δ)-differential privacy, the optimal noise magnitude and the noise power are Θ(min((1/ϵ), (1/δ))) and Θ(min((1/ϵ 2 ), (1/δ 2 ))), respectively, in the high privacy regime.