Source-linked AI summary
Privacy via the Johnson-Lindenstrauss Transform
Krishnaram Kenthapadi, Aleksandra Korolova, Ilya Mironov, Nina Mishra
TL;DR
The paper asks whether a data collector can publish user information that supports third-party distance estimation without revealing private attributes. It projects binary user representations into a lower-dimensional space, adds Gaussian noise, and establishes privacy and distance-recovery guarantees. The approach offers a privacy-preserving way to support distance computations, but its protections do not cover persistent trends formed by correlated attributes and do not fit applications where proximity itself is sensitive.
Problem
The paper studies how to enable third parties to estimate distances between users for data mining without compromising users’ private attributes.
Method
The method publishes lower-dimensional user sketches produced by a random Johnson-Lindenstrauss projection followed by Gaussian noise, with distances recovered from the perturbed sketches.
Results
The perturbed sketches preserve differential privacy, preserve squared Euclidean distance in expectation, and preserve distances with high probability up to Johnson-Lindenstrauss factors plus a noise-dependent additive term.
Takeaways & Limitations
The work demonstrates that privacy-preserving publication can support third-party distance computations and compares favorably with direct distance perturbation for potential segmentation and nearest-neighbor applications.
Takeaways & Limitations
The guarantees cover a constant number of attributes, not persistent trends from correlated attributes, and the method does not apply when proximity to a particular user is itself sensitive.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper asks whether third parties can estimate distances between users from published data without compromising private attributes. It proposes privacy-preserving sketches and compares them with alternative perturbation methods while identifying a scope limitation.
- The central problem is enabling third-party distance estimation over users’ bit vectors without allowing inference of private attributes.
- Existing anonymization and random-projection approaches lacked rigorous privacy guarantees or were vulnerable to concrete attacks.
- The proposed method applies a random Johnson-Lindenstrauss transform and Gaussian noise to produce sketches that preserve differential privacy and support distance recovery.
- Squared Euclidean distances are preserved in expectation, while high-probability error includes Johnson-Lindenstrauss distortion plus a noise-dependent additive factor.
- Compared with direct noise on the user-distance matrix, projection-based privacy requires lower noise variance when maximal user-vector weight is much smaller than the number of users.
- For fixed k, both projection and randomized-response methods are inaccurate for nearby points, whereas randomized response excels for far-apart pairs and projection methods for medium distances.
- The method does not apply when proximity to a particular user is itself sensitive information.
2 Preliminaries
The paper models users as binary attribute vectors and evaluates utility through private recovery of pairwise Euclidean distances. Its privacy framework uses differential privacy, while Johnson-Lindenstrauss embeddings provide the dimensionality-reduction basis.
- Each user is represented by a binary vector whose dimensions encode attributes, with attribute meanings assumed nonsensitive or separately privatized.
- The formal goal is to publish user-profile sketches that preserve privacy while enabling third parties to estimate pairwise distances.
- Utility is defined as whether a third party can recover pairwise Euclidean distances using only transformed privacy-preserving profiles.
- Differential privacy compares outputs on datasets differing in one user’s one attribute and limits inference of that attribute from published information.
- Normal noise supports the more lenient (ε, δ)-differential privacy guarantee, while Laplace noise is typically used for (ε, 0)-differential privacy.
- The Johnson-Lindenstrauss Lemma provides embeddings into R^k that preserve all pairwise distances within a 1 ± λ_JL factor.
3 Construction and Usage of Privacy-Preserving Projections
The construction publishes a lower-dimensional noisy sketch and a projection matrix, then recovers distances from the sketches. Its design balances projection distortion against noise while selecting the projection for distance preservation and low sensitivity.
- The mechanism has two components: transforming each user profile into a privacy-preserving sketch and recovering distances from the transformed sketches.
- The published transformation is reusable, so subsequent operations on the released data do not consume additional privacy budget or pose additional privacy risk.
- PrivateProjection first maps the n × d user representation into a much lower k-dimensional space while approximately preserving pairwise distances.
- The algorithm publishes a random projection matrix P and a privacy-preserving n × k matrix Z formed by adding noise to the projected representation.
- For fixed privacy, smaller k increases dimensionality-reduction distortion, whereas larger k increases distortion from added noise.
- The Gaussian noise variance is chosen from the desired (ε, δ) guarantee and the projection matrix’s ℓ2 sensitivity.
- Projection matrices are selected to preserve ℓ2 distances and minimize the noise required for privacy, favoring low ℓ2 sensitivity.
3. Each entry of the matrix is chosen independently to be +
The mechanism projects user vectors into a lower-dimensional space, adds Gaussian noise calibrated to projection sensitivity and privacy parameters, and recovers approximate pairwise distances from the published sketches.
- Noise calibration: Each noise entry is independently drawn from a Normal distribution with mean 0 and variance σ2.The noise variance depends on the projection’s ℓ2-sensitivity and the privacy parameters ǫ and δ.
- Distance recovery: The squared-distance recovery algorithm subtracts the expected Gaussian-noise distortion, 2kσ2, from the transformed squared distance.The correction accounts for systematic positive distortion introduced by noise.
- Mechanism: The projection-and-noise mechanism publishes lower-dimensional user sketches while supporting privacy-preserving distance estimation.Distances are recovered from the transformed representations rather than the original user vectors.
- Privacy guarantees: Choosing σ according to the projection sensitivity yields (ǫ, δ)-differential privacy for changes to an individual attribute.The guarantee also applies when input values lie in [0, 1], not only when they are Boolean.
- Privacy guarantees: The privacy proof relies on bounding the effect of a one-attribute change through the projection matrix’s ℓ2-sensitivity.Gaussian spherical symmetry reduces the geometric argument to a single differing coordinate.
- Privacy guarantees: The privacy–utility relationship can be read from feasible ǫ, δ curves for a fixed σ; for (ǫ, δ)=(1, 0.1), σ is approximately 1.0.The figure supports selecting either privacy parameters for a fixed noise level or a noise level for fixed privacy parameters.
- Utility guarantees: The noise scale can be chosen independently of the projection realization, enabling utility guarantees for Gaussian projection matrices.The paper analyzes unbiased distance estimates, their variance, and deviation bounds for Gaussian projections.
2. Variance of dist2
The paper decomposes the perturbed squared-distance estimator into projection and noise terms, then derives its variance, deviation bounds, and the unresolved challenge of choosing the projection dimension.
- Deviation bounds: Deviation bounds hold with probability 1−(δJL+δχ2+δN), combining projection, chi-squared, and Gaussian-noise failure events.A union bound combines the component-wise bounds.
- Estimator decomposition: The squared-distance estimator is expressed as a sum of three random variables representing projection, interaction, and noise contributions.This decomposition supports the subsequent variance calculation.
- Estimator decomposition: The projected difference (x−y)P is Gaussian with covariance determined by the original squared distance and target dimension k.For vectors at Euclidean distance r, the projection follows N_k(0, r2/k).
- Variance analysis: The estimator’s variance is obtained by expanding Var(Z1 + Z2 + Z3) and evaluating the resulting second moments.The calculation uses the zero means and independence properties of the Gaussian terms.
- Variance analysis: Independence between the projected difference and Gaussian noise allows pairwise-product expectations to be evaluated separately.The analysis assumes σ is chosen independently of the projection matrix P.
- Optimal projection dimension: The optimal target dimension k remains an open question because the best choice depends on expected distances, noise, and the desired failure probability.The paper gives analytic optimization approaches but identifies dimension selection as unresolved in general.
- Optimal projection dimension: For fixed noise, analytic approaches imply that the optimal k depends on expected distance and scales inversely with σ2.The paper also suggests using different optimized projections for different distance ranges.
4 Alternative Approaches
The paper compares direct noise addition and randomized response with privacy-preserving projection for releasing pairwise distances. NoiseAddition perturbs the distance matrix directly, while randomized response perturbs user vectors and corrects the resulting distortion.
- Direct Noise Addition: NoiseAddition releases a strictly upper triangular matrix of noisy pairwise squared distances by adding calibrated Gaussian noise to the true distances.The matrix is published for later recovery of any desired pairwise distance.
- Direct Noise Addition: The NoiseAddition estimator has variance σ^2, and that variance grows linearly with the number of users n.This reflects the mechanism’s direct perturbation of the pairwise-distance matrix.
- Comparison with PrivateProjection: PrivateProjection has lower estimator variance than NoiseAddition when the maximal user-vector weight is much smaller than the number of users.The comparison is expressed as µσ_PP^2 = o(n).
- Randomized Response: Randomized response flips each vector bit with probability p, then estimates original squared distances from the perturbed vectors.The estimator corrects the systematic distortion caused by flipping bits.
- Randomized Response: Randomized response preserves (ε, 0)-differential privacy under its flip-probability condition and yields an unbiased, concentrated squared-distance estimate.The expected perturbed distance is adjusted to estimate the original distance.
- Comparison of PrivateProjection and RandomizedResponse: PrivateProjection is more accurate for smaller squared distances, whereas RandomizedResponse is preferable for larger squared distances.The exact boundary depends on privacy parameters and failure probabilities.
5 Discussion
The released sketches support clustering and nearest-neighbor tasks while exposing only specified transformed data, but their utility and privacy protections have important boundaries.
- Published information: The published information consists of attribute meanings, the Johnson-Lindenstrauss matrix, and each user’s perturbed sketch with userID.These are the items the paper identifies as safe to publish, assuming attribute meanings are not sensitive.
- Applications: Perturbed sketches can support user segmentation and nearest-neighbor search when third parties have suitable additional information.The paper gives clustering and similarity-based recommendation examples for these uses.
- Utility limitations: Sketch dimensions are uninterpretable, so selecting users by a particular attribute requires projecting that attribute and comparing distances in a range where both methods perform poorly.This creates a concrete utility limitation for attribute-based selection.
- Utility limitations: Equal weighting of all attributes may be undesirable, while using multiple weighted projections consumes additional privacy budget and requires preventing third-party collusion.The limitation applies when third parties want to prioritize similarity on selected attributes.
- Utility limitations: The sketches provide a static snapshot, and updates as user information changes require additional privacy budget.The paper identifies dynamic data sharing as a broader challenge for privacy-preserving data sharing.
- Privacy limitations: The guarantees cover a constant number of attributes but not persistent trends arising from correlated or representative attributes.The paper notes that coarser attribute categories may sometimes be more appropriate.
- Privacy limitations: The method is not relevant when identifying that two users are similar is itself a privacy violation.Its scope assumes that third parties may perform distance computations and clustering.
6 Related Work
Related work includes random-projection release, differential-privacy algorithms, and query-based access, with different privacy and utility trade-offs from this approach.
- Random projection: Prior random-projection work preserved analytic properties such as inner products and Euclidean distances but did not use an operational differential-privacy definition.The cited approach used a projection matrix drawn from a distribution unknown to the adversary.
- Randomized response: Randomized response offers slightly better privacy, whereas the present method preserves small distances more effectively.The comparison favors the present method for applications interested in nearby users.
- Differentially private computation: Trusted-administrator methods can privately produce k-Means cluster centers, but they pursue a different goal from publishing user sketches.The paper also contrasts these methods with releasing data for third-party distance computations.
- Query-based access: Black-box perturbed queries avoid publishing data but burden the first-party provider and consume privacy budget with each query.This is presented as an alternative direction for interacting with private data.
7 Conclusion and Future Work
The paper presents perturbed lower-dimensional sketches as a viable way to enable private distance computations, while identifying broader data-sharing needs beyond this capability.
- Conclusion: Projecting users into a lower-dimensional space limits noise per user while preserving distances sufficiently for distance computations.The paper presents this as the key insight behind its privacy-preserving sketches.
- Conclusion: The method is preferable for potential user segmentation and nearest-neighbor search compared with directly perturbing pairwise distances or user attributes.This comparison is stated as part of the paper’s conclusion.
- Future work: Future work includes supporting other data-mining primitives and dynamically changing data.The paper describes privacy-preserving sharing as broader than enabling distance computations.
A Appendix
The appendix develops probabilistic bounds used in the analysis, including chi-squared tail bounds, Gaussian-noise relations, and conditions under which one bound is stronger.
- Probabilistic bounds: The appendix uses a chi-squared distribution with k degrees of freedom to analyze relevant random quantities.It states the distributional setting before applying tail bounds.
- Probabilistic bounds: A Laurent–Massart chi-squared tail bound is combined with a union bound over n independent variables.This establishes a bound across the collection of variables.
- Bound comparison: The appendix expresses tail probabilities through the standard Normal CDF Φ for one of the bound derivations.It presents this as an alternative formulation of the tail analysis.
- Bound comparison: The appendix compares two bounds and states that the second is stronger when x ≥0.8σ.The condition is repeated in the appendix’s result statements.
- Gaussian analysis: For an arbitrary distribution X over R^k and independent Gaussian noise Y ∼ N^k(0, σ^2), the analysis uses Gaussian scaling and additivity.The appendix explicitly introduces the variables and the Gaussian property used in the proof.