Privacy Amplification by Decentralization

Edwige Cyffers, Aurélien Bellet

Abstract

Analyzing data owned by several parties while achieving a good trade-off between utility and privacy is a key challenge in federated learning and analytics. In this work, we introduce a novel relaxation of local differential privacy (LDP) that naturally arises in fully decentralized algorithms, i.e., when participants exchange information by communicating along the edges of a network graph without a central coordinator. This relaxation, which we call Network Differential Privacy (Network DP), captures the fact that users have only a local view of the system. To show the relevance of Network DP, we study a decentralized model of computation where a token performs a walk on the network graph and is updated sequentially by the party who receives it. For tasks such as real summation, histogram computation, and optimization with gradient descent, we propose simple algorithms on ring and complete topologies. We prove that the privacy-utility trade-offs of our algorithms under Network DP significantly improve upon what is achievable under LDP, and often match the utility of the trusted curator model. Our results show for the first time that formal privacy gains can be obtained from full decentralization.

Introduction

In the world of Federated Learning (FL), practitioners often face a "trust vs. utility" deadlock. The Centralized Model offers high utility by adding noise once at a central server, but requires absolute trust in that server. Conversely, Local Differential Privacy (LDP) requires no trust but necessitates adding massive noise locally, which degrades accuracy as the number of users ($n$) increases.

This paper introduces Network Differential Privacy (Network DP), a framework demonstrating that decentralized algorithms—where users communicate only with neighbors—naturally provide stronger privacy than standard LDP. By leveraging the restricted "local view" of participants in a graph, we can achieve the utility of a trusted curator without needing one.

Methodology

The authors study a token-based computation model where a "token" (e.g., a partial sum or model weights) traverses a network. Each user receives the token, updates it with their private data, adds noise, and passes it on. Two primary topologies are analyzed: a deterministic Ring and a Complete Graph (random walk).

Algorithm for private histogram computation on a ring topology using a token-based walk.

The core innovation is showing that these walks act as a "privacy amplifier." Because the token passes through many users before reaching a potential adversary, the adversary cannot easily distinguish a specific user's contribution from the aggregated, noisy contributions of others. Theoretical findings were validated using synthetic data for summation and histogram tasks, and the UCI Housing Dataset for training decentralized logistic regression models via Stochastic Gradient Descent (SGD).

Key Insights and Results

The primary insight is that decentralization acts as a natural "shuffler." In standard LDP, an adversary is assumed to see everything shared. In Network DP, an adversary only sees messages they personally receive. This restriction provides a significant privacy "bonus."

Theoretical and Empirical Gains

For summation and histograms, Network DP achieves a privacy gain of $O(1/\sqrt{n})$ over LDP. For decentralized SGD, the amplification is $O(\ln n / \sqrt{n})$.

Theoretical and empirical privacy loss comparison between Local DP (LDP) and Network DP (NDP) as a function of network size $n$.

As shown in Figure 1, the theoretical bounds for Network DP (NDP) decrease as $n$ grows, whereas standard LDP bounds remain constant or even increase. Empirical results confirm these gains: in experiments with 2,000 users, Network DP-SGD nearly matched the performance of a centralized model, while the standard LDP approach often failed to converge or produced highly inaccurate models due to excessive noise.

Discussion and Future Work

While a simple ring is vulnerable to collusion between neighbors, random walks on complete graphs are robust, maintaining privacy gains even if a constant fraction of the network colludes. However, several challenges remain:

  • Topology Constraints: Most proofs focus on rings and complete graphs; extending these to arbitrary graph topologies (like small-world networks) is a major next step.
  • Assumptions: Current analysis for complete graphs assumes an adversary doesn't know exactly who sent the token. Lifting this "hidden path" assumption requires more complex analysis.
  • Synchronicity: The model assumes a single sequential token. Future work could explore asynchronous "gossip" protocols where multiple messages circulate simultaneously.

Summary updated

Abstract

Analyzing data owned by several parties while achieving a good trade-off between utility and privacy is a key challenge in federated learning and analytics. In this work, we introduce a novel relaxation of local differential privacy (LDP) that naturally arises in fully decentralized algorithms, i.e., when participants exchange information by communicating along the edges of a network graph without central coordinator. This relaxation, that we call network DP, captures the fact that users have only a local view of the system. To show the relevance of network DP, we study a decentralized model of computation where a token performs a walk on the network graph and is updated sequentially by the party who receives it. For tasks such as real summation, histogram computation and optimization with gradient descent, we propose simple algorithms on ring and complete topologies. We prove that the privacy-utility trade-offs of our algorithms under network DP significantly improve upon what is achievable under LDP, and often match the utility of the trusted curator model. Our results show for the first time that formal privacy gains can be obtained from full decentralization. We also provide experiments to illustrate the improved utility of our approach for decentralized training with stochastic gradient descent.
BibTeX
@inproceedings{cyffers2022privacy,
  author = {Edwige Cyffers and Aurélien Bellet},
  title = {{Privacy Amplification by Decentralization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=GHCHAHqQqZH},
}
Figure