Differential privacy via wavelet transforms

By Xiaokui Xiao, Guozhang Wang, Johannes Gehrke. 2009

564 citations recorded by the source corpus.

Privacy preserving data publishing has attracted considerable research interest in recent years. Among the existing solutions, ∈-differential privacy provides one of the strongest privacy guarantees. Existing data publishing methods that achieve ∈-differential privacy, however, offer little data utility. In particular, if the output dataset is used to answer count queries, the noise in the query answers can be proportional to the number of tuples in the data, which renders the results useless. In this paper, we develop a data publishing technique that ensures ∈-differential privacy while providing accurate answers for range-count queries, i.e., count queries where the predicate on each attribute is a range. The core of our solution is a framework that applies wavelet transforms on the data before adding noise to it. We present instantiations of the proposed framework for both ordinal and nominal data, and we provide a theoretical analysis on their privacy and utility guarantees. In an extensive experimental study on both real and synthetic data, we show the effectiveness and efficiency of our solution.

Subfields: Artificial Intelligence, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Privacy & Security

Citations in the corpus

Marginal Release Under Local Differential Privacy (2017, methodology): “A variant is to apply this release to a transformation of the data, such as a wavelet or Fourier transform [37, 3].”
Differential Privacy Preservation for Deep Auto-Encoders: an Application of Human Behavior Prediction (2016, background): “…in some particular analysis tasks, e.g., collaborative recommendation (McSherry and Mironov 2009), logistic regression (Chaudhuri and Monteleoni 2008), publishing contingency tables (Xiao, Wang, and Gehrke 2010), and spectral graph analysis (Wang, Wu, and Wu 2013) in social network analysis.”
Functional Mechanism: Regression Analysis under Differential Privacy (2012, background): “In particular, Hay et al. [13], Li et al. [17], Xiao et al. [30], and Cormode et al. [6] present methods for minimizing the worst-case error of a given set of count queries; Barak et al. [2] and Ding et al. [8] consider the publication of data cubes; Xu et al. [31] and Li et al. [18] focus on…”
A Simple and Practical Algorithm for Differentially Private Data Release (2010, methodology): “In Section 3.1 we turn to an empirical comparison of our algorithm with [18] and additional related work on range queries [25, 17, 18, 19, 20, 21].”
Real-time aggregate monitoring with differential privacy (2012, background): “Most existing works on differentially private data release deal with one-time release of static data [4, 7, 13, 14, 15, 16].”
Application of Local Differential Privacy to Collection of Indoor Positioning Data (2018, background): “The ﬁrst one is ofﬂine setting where a statistical summary, such as histograms or a set of synthetic data that mimic the original data, is released for public use [5], [17], [21], [34].”
The optimal mechanism in differential privacy (2012, unknown): “, [10], [11], [12], [13], [14], [5], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30], [31], [32], [33], [34], [35], [36], [37], [38], [39], [40], [41], [42], [43], [44], [45], [46].”
Differential Privacy Techniques for Cyber Physical Systems: A Survey (2018, background): “transformation-based approaches working over principle of transformation of actual correlated data to independent data while maintaining key information have also been proposed by researchers in [72], [74], [102]–[104].”
Adaptive Laplace Mechanism: Differential Privacy Preservation in Deep Learning (2017, background): “, data collection [19], spatiotemporal correlations [20, 21], data streams [22], stochastic gradient descents [23], recommendation [7], regression [6], online learning [24], publishing contingency tables [25], and spectral graph analysis [26].”
PrivateSQL: A Differentially Private SQL Query Engine (2019, background): “, histograms, CDFs, marginals on a single table) [7,20,34,35,37,40], sub-graph queries (e.”
Optimal private halfspace counting via discrepancy (2012, methodology): “For interval queries, the work of Blum, Ligett, and Roth was subsequently improved by Xiao, Wang, and Gehrke [32] (in the regime where database size and universe size are comparable), who gave a polylogarithmic noise upper bound via the wavelet transform.”
Optimizing linear counting queries under differential privacy (2009, methodology): “We begin by analyzing two techniques proposed recently [17, 11].”
Differentially private histogram publication (2012, methodology): “[8] develop a wavelet-based approach that can handle multi-dimensional datasets, and it achieves a noise variance bound of O(log n), where d is the dimensionality of the data set.”
Cryptϵ: Crypto-Assisted Differential Privacy on Untrusted Servers (2019, unknown): “Interesting work has been done in both theCDPmodel [8, 22, 30, 33, 34, 39, 54– 56, 58, 70, 71, 75, 85, 89, 90, 100–102, 104, 105, 107] and the LDP model [13, 32, 42, 44, 91, 95–97, 108].”