Privacy via the Johnson-Lindenstrauss Transform

Krishnaram Kenthapadi, Aleksandra Korolova, Ilya Mironov, Nina Mishra

Abstract

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.

Introduction

Data collectors, such as hospitals, social networks, and financial institutions, often possess high-dimensional datasets that could provide immense value to third-party researchers. However, the tension between data utility and individual privacy remains a significant barrier. Traditional anonymization techniques, such as removing personally identifiable information (PII), are frequently vulnerable to re-identification attacks.

This paper addresses a specific, vital use case: enabling a third party to calculate the similarity (Euclidean distance) between users without exposing their raw private attributes. The authors propose a framework that balances the rigorous requirements of differential privacy with the practical needs of distance-based data mining tasks like clustering and nearest-neighbor search.

The PrivateProjection Mechanism

The authors introduce a two-step pipeline called PrivateProjection to transform sensitive bit vectors into private, low-dimensional sketches:

  1. Dimensionality Reduction: Each user's data (a high-dimensional bit vector) is projected into a lower-dimensional space using a random Johnson-Lindenstrauss (JL) transform. This transform is known for its ability to "squash" data while approximately preserving the Euclidean distances between points.
  2. Noise Addition: To satisfy formal privacy guarantees, the algorithm adds Gaussian noise to every entry of the resulting lower-dimensional representation.

The core innovation of this approach lies in the analysis of the $l_2$-sensitivity of the projection matrix. Because the JL transform is a linear projection, the authors prove that the amount of noise required to achieve $(\epsilon, \delta)$-differential privacy depends on the properties of the projection matrix rather than the original high dimensionality of the data.

To ensure the data remains useful, the authors provide a companion algorithm, RecoverDistancePP. This allows a third party to take the noisy sketches and produce an unbiased estimate of the original squared Euclidean distance by applying a specific "discount" factor related to the noise variance.

Key Insights and Theoretical Results

Privacy-Utility Trade-offs

A primary finding of the research is that privacy is effectively "cheaper" in lower dimensions. By projecting data into a lower-dimensional space before adding noise, the "privacy budget" is spent more efficiently. Surprisingly, the sensitivity—and thus the required noise—is independent of the original dimension $d$ of the data, depending instead on the sensitivity of the projection matrix $P$.

Accuracy in the "Medium Distance" Range

The authors compare PrivateProjection to other methods like Randomized Response (which involves flipping bits in the original vector). While Randomized Response can be effective for very large distances, PrivateProjection is significantly more accurate for "medium" distances. This is the specific range where most clustering and nearest-neighbor algorithms operate, making the proposed method particularly suited for standard data mining applications.

Formal Utility Bounds

The paper derives a rigorous variance bound for the distance estimator: $$Var[dist^2_{PP}] = 2r^4/k + 8\sigma^2r^2 + 8\sigma^4k$$ This formula allows practitioners to calculate the expected error based on their choice of target dimension ($k$) and noise level ($\sigma$). The authors demonstrate that PrivateProjection outperforms simply adding noise to a distance matrix in scenarios where the number of active attributes per user is small relative to the total population.

Limitations and Considerations

While the method provides a robust framework for private distance estimation, several limitations remain:

  • Static Data Constraints: The current method is designed for a single snapshot of data. Updating a user's sketch as their attributes change would consume more of the privacy budget.
  • Loss of Interpretability: Once data is projected and noise is added, individual dimensions lose their original meaning. Third parties can determine if users are similar, but they cannot query specific attributes (e.g., demographic information).
  • Attribute Weighting: The model treats all attributes as equally important. Allowing for weighted distances would require more complex mechanisms that might degrade the privacy guarantee.
  • Sensitivity of Proximity: The authors note that this method is not intended for applications where the mere fact that two users are "close" is considered sensitive information.

Conclusion

This work demonstrates that privacy-preserving distance computation is an achievable goal through the combination of dimensionality reduction and calibrated noise. By leveraging the properties of the Johnson-Lindenstrauss transform, PrivateProjection offers a mathematically sound way to share data for complex mining tasks while maintaining the rigorous standards of differential privacy.

Summary updated

Abstract

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.
BibTeX
@article{kenthapadi2013privacy,
  author = {Krishnaram Kenthapadi and Aleksandra Korolova and Ilya Mironov and Nina Mishra},
  title = {{Privacy via the Johnson-Lindenstrauss Transform}},
  journal = {J. Priv. Confidentiality},
  year = {2013},
  doi = {10.29012/jpc.v5i1.625},
}
Figure