SoK: Chasing Accuracy and Privacy, and Catching Both in Differentially Private Histogram Publication

Abstract

Histograms and synthetic data are of key importance in data analysis. However, researchers have shown that even aggregated data such as histograms, containing no obvious sensitive attributes, can result in privacy leakage. To enable data analysis, a strong notion of privacy is required to avoid risking unintended privacy violations. Such a strong notion of privacy is differential privacy, a statistical notion of privacy that makes privacy leakage quantifiable. The caveat regarding differential privacy is that while it has strong guarantees for privacy, privacy comes at a cost of accuracy. Despite this trade off being a central and important issue in the adoption of differential privacy, there exists a gap in the literature regarding providing an understanding of the trade off and how to address it appropriately. Through a systematic literature review (SLR), we investigate the state-of-the-art within accuracy improving differentially private algorithms for histogram and synthetic data publishing. Our contribution is two-fold: 1) we identify trends and connections in the contributions to the field of differential privacy for histograms and synthetic data and 2) we provide an understanding of the privacy/accuracy trade off challenge by crystallizing different dimensions to accuracy improvement. Accordingly, we position and visualize the ideas in relation to each other and external work, and deconstruct each algorithm to examine the building blocks separately with the aim of pinpointing which dimension of accuracy improvement each technique/approach is targeting. Hence, this systematization of knowledge (SoK) provides an understanding of in which dimensions and how accuracy improvement can be pursued without sacrificing privacy.

References in corpus (13)

• A simple and practical algorithm for differentially private data release
• Quantifying Differential Privacy under Temporal Correlations
• Comparative Study of Differentially Private Data Synthesis Methods
• Impact of Prior Knowledge and Data Correlation on Privacy Leakage: A Unified Analysis
• Efficient Lipschitz Extensions for High-Dimensional Graph Statistics and Node Private Degree Distributions
• Adaptively Sharing Time-Series with Differential Privacy
• Differentially Private Identity and Closeness Testing of Discrete Distributions
• Towards Differentially Private Truth Discovery for Crowd Sensing Systems
• The Application of Differential Privacy for Rank Aggregation: Privacy and Accuracy
• Constrained Differential Privacy for Count Data
• End-to-End Differentially-Private Parameter Tuning in Spatial Histograms
• Privacy-Preserving Synthetic Datasets Over Weakly Constrained Domains
• More Flexible Differential Privacy: The Application of Piecewise Mixture Distributions in Query Release