Optimal Noise Adding Mechanisms for Approximate Differential Privacy
2016
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.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI