Privacy via the Johnson-Lindenstrauss Transform

By Krishnaram Kenthapadi, Aleksandra Korolova, Ilya Mironov, Nina Mishra. 2012

154 citations recorded by the source corpus.

Suppose that party A collects private information about its users, where each user's data is represented as a bit vector. Suppose that party B has a proprietary data mining algorithm that requires estimating the distance between users, such as clustering or nearest neighbors. We ask if it is possible for party A to publish some information about each user so that B can estimate the distance between users without being able to infer any private bit of a user. Our method involves projecting each user's representation into a random, lower-dimensional space via a sparse Johnson-Lindenstrauss transform and then adding Gaussian noise to each entry of the lower-dimensional representation. We show that the method preserves differential privacy---where the more privacy is desired, the larger the variance of the Gaussian noise. Further, we show how to approximate the true distances between users via only the lower-dimensional, perturbed data. Finally, we consider other perturbation methods such as randomized response and draw comparisons to sketch-based methods. While the goal of releasing user-specific data to third parties is more broad than preserving distances, this work shows that distance computations with privacy is an achievable goal.

Subfields: Artificial Intelligence, Computer Science Applications, Sociology and Political Science, 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 Computer Science Applications

In Sociology and Political Science

In Privacy & Security

Citations in the corpus

Learning Privately over Distributed Features: An ADMM Sharing Approach (2019, methodology): “A few recent studies [8, 9, 10, 11, 12, 13, 14] have revisited vertically partitioned features under the setting of distributed learning, which is motivated by the increase in feature dimensionality as well as the opportunity of cooperation between multiple parties that may hold different aspects of”
Differentially-Private "Draw and Discard" Machine Learning (2018, methodology): “In that case, the variance of the Gaussian noise would need to be calibrated according to Lemma 1 from [30] or Theorem A.1 of [15].”
Local, Private, Efficient Protocols for Succinct Histograms (2015, background): “Running many copies of the protocol for unique heavy hitters in parallel, we can recover the list of heavy hitters.”
RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response (2014, background): “Usage of various dimensionality reduction techniques in order to improve the privacy properties of algorithms while retaining utility is also fairly common [20, 17, 1, 22].”
Preserving privacy between features in distributed estimation (2017, methodology): “Theorem 1 (Adapted from Kenthapadi et al. (2013)) .”
Random Projections, Graph Sparsification, and Differential Privacy (2013, background): “Since then, many sanitizers for preserving DP have been proposed in the literature, including the Exponential sanitizer [4, 23, 27], the Multiplicative Update sanitizer [16–19], the Median sanitizer [30], the Boosting sanitizer [10], and the Random Projection sanitizer [25].”
Interpretable and Differentially Private Predictions (2019, methodology): “…to use random projections to better deal with privacy and accuracy trade-off : We propose to adopt the Johnson-Lindenstrauss transform , a.k.a., random projection (Kenthapadi et al. 2013), to decrease the dimensionality of each LLM and then privatize the resulting lower dimensional quantities.”
Uplink Communication Efficient Differentially Private Sparse Optimization With Feature-Wise Distributed Data (2018, background): “(Heinze-Deml, McWilliams, and Meinshausen 2017) proposes to add privacy protection during preprocessing by communicating perturbed sketched features (Kenthapadi et al. 2013).”
Efficient Differentially Private F0 Linear Sketching (2020, methodology): “∗ The space usage of [26] is measured in terms of real numbers; it is unclear how much space a private, discrete implementation would need.”
A Survey on Differential Privacy for Unstructured Data Content (2022, methodology): “The widely used dimensionality reduction method of the Johnson-Lindenstrauss transform has been proved to preserve DP in [6, 54].”