Segmented Private Data Aggregation in the Multi-message Shuffle Model

Shaowei Wang, Ruilin Yang, Sufen Zeng, Kaiqi Yu, Rundong Mei, Shaozheng Huang, Wei Yang

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.

Table of notations used in the protocol.

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.

The three-step framework for agnostic segmented private data aggregation.

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

Abstract

The shuffle model of differential privacy (DP) offers compelling privacy-utility trade-offs in decentralized settings (e.g., internet of things, mobile edge networks). Particularly, the multi-message shuffle model, where each user may contribute multiple messages, has shown that accuracy can approach that of the central model of DP. However, existing studies typically assume a uniform privacy protection level for all users, which may deter conservative users from participating and prevent liberal users from contributing more information, thereby reducing the overall data utility, such as the accuracy of aggregated statistics. In this work, we pioneer the study of segmented private data aggregation within the multi-message shuffle model of DP, introducing flexible privacy protection for users and enhanced utility for the aggregation server. Our framework not only protects users' data but also anonymizes their privacy level choices to prevent potential data leakage from these choices. To optimize the privacy-utility-communication trade-offs, we explore approximately optimal configurations for the number of blanket messages and conduct almost tight privacy amplification analyses within the shuffle model. Through extensive experiments, we demonstrate that our segmented multi-message shuffle framework achieves a reduction of about 50\% in estimation error compared to existing approaches, significantly enhancing both privacy and utility.
BibTeX
@misc{wang2024segmented,
  author = {Shaowei Wang and Ruilin Yang and Sufen Zeng and Kaiqi Yu and Rundong Mei and Shaozheng Huang and Wei Yang},
  title = {{Segmented Private Data Aggregation in the Multi-message Shuffle Model}},
  year = {2024},
  eprint = {2407.19639},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.19639},
}
Figure