The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy

By Jeremiah Blocki, Avrim Blum, Anupam Datta, Or Sheffet. 2012

262 citations recorded by the source corpus.

This paper proves that an "old dog", namely - the classical Johnson-Lindenstrauss transform, "performs new tricks" - it gives a novel way of preserving differential privacy. We show that if we take two databases, D and D', such that (i) D'-D is a rank-1 matrix of bounded norm and (ii) all singular values of D and D' are sufficiently large, then multiplying either D or D' with a vector of iid normal Gaussians yields two statistically close distributions in the sense of differential privacy. Furthermore, a small, deterministic and public alteration of the input is enough to assert that all singular values of D are large. We apply the Johnson-Lindenstrauss transform to the task of approximating cut-queries: the number of edges crossing a (S, S)-cut in a graph. We show that the JL transform allows us to publish a sanitized graph that preserves edge differential privacy (where two graphs are neighbors if they differ on a single edge) while adding only O(|S|ϵ) random noise to any given query (w.h.p). Comparing the additive noise of our algorithm to existing algorithms for answering cut-queries in a differentially private manner, we outperform all others on small cuts (|S| = o(n)). We also apply our technique to the task of estimating the variance of a given matrix in any given direction. The JL transform allows us to publish a sanitized covariance matrix that preserves differential privacy w.r.t bounded changes (each row in the matrix can change by at most a norm-1 vector) while adding random noise of magnitude independent of the size of the matrix (w.h.p). In contrast, existing algorithms introduce an error which depends on the matrix dimensions.

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

Extremal Mechanisms for Local Differential Privacy (2014, methodology): “The typical recipe is to propose a differentially private mechanism inspired by [11, 13, 26, 20], and then establish its near-optimality by comparing the achievable utility to a converse, for example in principal component analysis [8, 5, 19, 24], linear queries [21, 18], logistic regression [7] and”
Privacy via the Johnson-Lindenstrauss Transform (2012, neutral): “[4] and Hsu et al.”
Interpretable and Differentially Private Predictions (2019, methodology): “Random projections have previously been used to ensure DP (Blocki et al. 2012).”
On significance of the least significant bits for differential privacy (2012, background): “More importantly, some (or even substantial) amount of additive noise is not by itself a guarantee of diﬀerential privacy.”
Random Projections, Graph Sparsification, and Differential Privacy (2013, background): “[3] (BBDS) can be adapted to preserve DP for answering cut-queries on sparse graphs, with an asymptotically efficient sanitizer than BBDS.”
LOCO: Distributing Ridge Regression with Random Projections (2014, result): “Here we collect supplementary technical details, empirical results and discussion which support the results presented in the main text.”
Efficient Differentially Private F0 Linear Sketching (2020, background): “[8] prove that the Johnson-Lindenstrauss transform is in fact differentially private, when keeping the sketch matrix secret.”
On differentially private low rank approximation (2013, methodology): “While their work used input perturbation to achieve privacy, in this work we suggest alternate ways to compute a diﬀerentially private approximation to this objective.”
Secure Deep Graph Generation with Link Differential Privacy (2020, methodology): “For graph structured data, two types of privacy constraints can be applied, i.e., node-DP [Kasiviswanathan et al., 2013] and edge-DP [Blocki et al., 2012], which define two neighboring graphs to differ by at most one node or edge.”