×

Optimal data-independent noise for differential privacy. (English) Zbl 1320.68065

Summary: \({\varepsilon}\)-differential privacy is a property that seeks to characterize privacy in data sets. It is formulated as a query-response method, and computationally achieved by output perturbation. Several noise-addition methods to implement such output perturbation have been proposed in the literature. We focus on data-independent noise, that is, noise whose distribution is constant across data sets. Our goal is to find the optimal data-independent noise distribution to achieve \({\varepsilon}\)-differential privacy. We propose a general optimality criterion based on the concentration of the probability mass of the noise distribution around zero, and we show that any noise optimal under this criterion must be optimal under any other sensible criterion. We also show that the Laplace distribution, commonly used for noise in \({\varepsilon}\)-differential privacy, is not optimal, and we build the optimal data-independent noise distribution. We compare the Laplace and the optimal data-independent noise distributions. For univariate query functions, both introduce a similar level of distortion; for multivariate query functions, optimal data-independent noise offers responses with substantially better data quality.

MSC:

68P15 Database theory
68P25 Data encryption (aspects in computer science)
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

Software:

PrivateLR; SuLQ
PDFBibTeX XMLCite
Full Text: DOI

References:

[8] Dwork, C.; Smith, A., Differential privacy for statistics: what we know and what we want to learn, Journal of Privacy and Confidentiality, 1, 2, 135-154 (2009)
[10] Dwork, C., A firm foundation for private data analysis, Communications of the ACM, 54, 86-95 (2011)
[11] Hundepool, A.; Domingo-Ferrer, J.; Franconi, L.; Giessing, S.; Schulte Nordholt, E.; Spicer, K.; de Wolf, P.-P., Statistical Disclosure Control (2012), Wiley
[16] Nissim, K.; Raskhodnikova, S.; Smith, A., Smooth sensitivity and sampling in private data analysis, (Johnson, D. S.; Feige, U., 39th ACM Symposium on Theory of Computing - STOC 2007 (2007), ACM), 75-84 · Zbl 1232.68039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.