TY - JOUR
T1 - Optimal noise adding mechanisms for approximate differential privacy
AU - Geng, Quan
AU - Viswanath, Pramod
N1 - Funding Information:
This work was supported in part by the National Science Foundation under Grant CCF-1422278 and in part by the University of Illinois at Urbana-Champaign. This paper was presented at the 2013 Workshop on Big Data and Differential Privacy, Simons Institute for Theory of Computing. The authors would like to thank the associate editor Dr. Adam Smith and the anonymous reviewers for their insightful comments and suggestions, which help us improve the presentation of this work.
Publisher Copyright:
© 2015 IEEE.
PY - 2016/2/1
Y1 - 2016/2/1
N2 - 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 ℓ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.
AB - 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 ℓ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.
KW - Data privacy
KW - Randomized algorithm
UR - http://www.scopus.com/inward/record.url?scp=84959420145&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84959420145&partnerID=8YFLogxK
U2 - 10.1109/TIT.2015.2504972
DO - 10.1109/TIT.2015.2504972
M3 - Article
AN - SCOPUS:84959420145
SN - 0018-9448
VL - 62
SP - 952
EP - 969
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 2
M1 - 2504972
ER -