Optimal Noise Adding Mechanisms for Approximate Differential Privacy

DOI10.1109/TIT.2015.2504972MaRDI QIDQ2977016zbMATH OpenOpenAlexFDO

Authors Quan Geng, P. Viswanath

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.1330

Mathematics Subject Classification ID

Authentication, digital signatures and secret sharing (94A62)

Abstract: We study the (nearly) optimal mechanisms in $(epsilon,delta)$-approximate differential privacy for integer-valued query functions and vector-valued (histogram-like) query functions under a utility-maximization/cost-minimization framework. We characterize the tradeoff between $epsilon$ and $delta$ in utility and privacy analysis for histogram-like query functions ($el{l}^1$ sensitivity), and show that the $(epsilon,delta)$-differential privacy is a framework not much more general than the $(epsilon,0)$-differential privacy and $(0,delta)$-differential privacy in the context of $el{l}^1$ and $el{l}^2$ cost functions, i.e., minimum expected noise magnitude and noise power. In the same context of $el{l}^1$ and $el{l}^2$ cost functions, we show the near-optimality of uniform noise mechanism and discrete Laplacian mechanism in the high privacy regime (as $(epsilon,delta)o(0,0)$). We conclude that in $(epsilon,delta)$-differential privacy, the optimal noise magnitude and noise power are $Theta(min(frac1epsilon,frac1delta))$ and $Theta(min(frac1epsilo{n}^2,frac1delt{a}^2))$, respectively, in the high privacy regime.

Cited in

(6)

• Assessing the effectiveness of the noise addition method of preserving confidentiality in the multivariate normal case
• An optimal (, )-differentially private learning of distributed deep fuzzy models
• Bounded privacy-utility monotonicity indicating bounded tradeoff of differential privacy mechanisms
• PAC privacy: automatic privacy measurement and control of data processing
• Infinitely divisible noise in the low privacy regime
• Mathematical comparison of classical and quantum mechanisms in optimization under local differential privacy

This page was built for publication: Optimal Noise Adding Mechanisms for Approximate Differential Privacy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977016)