Google Research

Optimal Noise Adding Mechanisms for Approximate Differential Privacy

IEEE Transactions on Information Theory, vol. 62 (2016), pp. 952-969

Abstract

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.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work