Abstract
Local Differential Privacy (LDP) is a robust standard for privacy-preserving data collection, yet it often suffers from a significant utility-privacy trade-off. This paper introduces a framework to achieve "privacy for free" by aggregating data that users have already shared across multiple services using LDP. By combining these multiple noisy reports through Bayesian inference and Expectation-Maximization, the authors estimate population means and distributions with significantly higher accuracy than any single service, all without requiring users to expend additional privacy budget.
Introduction: The "Noisy Waste" Opportunity
Local Differential Privacy (LDP) allows service providers to collect sensitive user data (e.g., age, income) by having users perturb their information with noise before transmission. While effective for privacy, this noise degrades statistical utility. Traditionally, LDP research focuses on a single-service scenario. However, in the modern digital ecosystem, users frequently share similar attributes across various platforms like LinkedIn, GitHub, and Skype.
The authors identify that a new data collector can leverage these existing "noisy" reports to reconstruct a clearer signal. This "privacy for free" paradigm avoids asking users for new data, which would otherwise deplete their privacy budget ($\epsilon$) or increase privacy risks.
Methodology: Aggregating Multi-Service Data
The paper proposes a three-stage architecture to aggregate perturbed data from $m$ services, as illustrated below.
Three primary methods are introduced to process this data:
- Unbiased Averaging (UA): This method mathematically "unbiases" results from mechanisms like Square Wave, allowing for simple averaging across services.
- User-level Weighted Averaging (UWA): For mean estimation, UWA employs Bayesian updating to estimate the posterior distribution of a user's true value. It assigns optimal weights to reports based on their specific LDP mechanism and privacy budget to minimize overall variance.
- User-level Likelihood Estimation (ULE): For distribution estimation, ULE treats a user's collection of reports as a single observation vector and uses an Expectation-Maximization (EM) algorithm to find the most likely global distribution.
Experimental Evaluation
The framework was evaluated on both synthetic (Beta and Beta+Sin distributions) and real-world datasets, including the NYC Taxi dataset (1M+ records), San Francisco retirement compensation data, and Taobao advertising click records.
Key Results
- Accuracy Gains: UWA improved mean estimation accuracy (MSE) by 53.3% to 85.0% over the best single service.
- Distribution Recovery: ULE outperformed standard LDP mechanisms by 21.1% to 81.0% in terms of Jensen-Shannon divergence.
- Scalability and Efficiency: As the number of services increases, estimation error consistently drops. Aggregating four services with $\epsilon=0.1$ each (total $\epsilon=0.4$) proved more accurate than a single service using a riskier $\epsilon=0.5$.
Discussion and Future Work
The core insight is "Information Synergy": correlating multiple noisy reports from the same original value allows an aggregator to cancel out significant noise. The framework is mechanism-agnostic, supporting any LDP method with a known probability density function.
However, challenges remain. The ULE method is computationally intensive for very large user bases, requiring complex matrix partitioning. Furthermore, the framework relies on the ability to link user identities across services. Future research will explore aggregating dynamic data that changes over time, such as location or telemetry.
Summary updated