Introduction
Collecting sensitive user data often involves a difficult trade-off between individual privacy and statistical utility. Traditional Differential Privacy (DP) models typically fall into two categories: Local DP (LDP), which provides high privacy but low accuracy due to noise added at the source, and Central DP, which offers high accuracy but requires absolute trust in a central server.
The Shuffle Model has emerged as a promising middle ground, using an anonymizing shuffler to bridge the gap. However, existing shuffle models often impose a uniform privacy level on all users. This "one-size-fits-all" approach fails to account for diverse user preferences—where some users may demand strict privacy while others are willing to share more accurate data. This paper introduces a framework for agnostic segmented privacy, allowing users to choose their own privacy levels without revealing those choices to the data collector.
Problem Statement: The Privacy-Utility Gap
In standard shuffle models, the privacy level is fixed. If the level is too low, conservative users may opt out; if too high, the data becomes too noisy for liberal users' contributions to be meaningful.
A major challenge in allowing user-defined privacy levels is that the choice of a privacy setting can itself be sensitive information. For instance, a user selecting a "high privacy" setting might inadvertently signal specific demographic or behavioral traits. The authors address this by ensuring that the server remains "agnostic" to individual privacy choices while still optimizing for overall utility.
The Proposed Framework
The authors propose a three-step framework designed to maintain anonymity for both the data and the privacy preferences.
1. Privacy Level Aggregation
Users first communicate their chosen privacy level ($\epsilon_i$) to the shuffler. The shuffler anonymizes these choices and provides the server with a shuffled histogram. This allows the server to know the distribution of privacy preferences (e.g., how many users chose "conservative" vs. "liberal") without knowing which specific user made which choice.
2. Parameter Optimization
Using the aggregated histogram, the server calculates the optimal protocol parameters. This includes determining the number of "blanket messages" ($m$)—dummy data points that act as noise—and sampling rates required to minimize the total Mean Squared Error (MSE).
3. Data Aggregation
Finally, users send their actual data ($x_i$), randomized via a Poisson Randomizer, along with the calculated blanket messages. The shuffler mixes these messages, ensuring that the server receives a sanitized, aggregated dataset.
Evaluation and Results
The framework was evaluated using the MSNBC Dataset (real-world page visit data) and a Synthetic Set-Valued Dataset to test scalability. The results demonstrate a significant improvement over existing methods:
- 50% Error Reduction: By allowing for segmented privacy rather than a uniform "worst-case" privacy setting, the model reduced estimation error (MSE) by approximately half.
- Multi-Message Advantage: The multi-message approach proved superior to single-message shuffle protocols, as it allows users to send multiple randomized fragments, significantly improving accuracy.
- Minimal Overhead: The study found that the optimal number of blanket messages ($m$) is typically low (often less than 4), keeping communication costs manageable for user devices.
Conclusion and Future Directions
The "agnostic segmented" approach proves that protecting the choice of privacy is as critical as protecting the data itself. By leveraging liberal users' data to provide a "blanket" of protection for conservative users, the framework achieves a superior privacy-utility balance.
While the current work focuses on set-valued data, future research could extend these techniques to real-valued gradients in federated learning. Additionally, while the communication is efficient, the server-side optimization currently involves complex numerical searches that could be further streamlined for real-time applications.
Summary updated