Optimal noise adding mechanisms for approximate differential privacy

We study the (nearly) optimal mechanisms in (∈, δ)-differential privacy for integer-valued query functions and vector-valued (histogram-like) query functions under a utilitymaximization/ 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 (0, δ)-differential privacy in the context of ℓ¹ and ℓ² cost functions, i.e., minimum expected noise magnitude and noise power. In the same context of ℓ¹ and ℓ² 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/∈²), (1/δ²))), respectively, in the high privacy regime.