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.
Introduction
In privacy-preserving machine learning, practitioners typically choose between two trust models. The Centralized Differential Privacy (DP) model offers high utility but requires a trusted central server to aggregate raw data. Conversely, the Local Differential Privacy (LDP) model requires no trust in a central entity, as users perturb their data locally. However, LDP often results in poor utility because the cumulative noise scales significantly with the number of participants $n$, often by a factor of $\sqrt{n}$.
This paper bridges this gap by introducing Network Differential Privacy (Network DP). The authors demonstrate that in a fully decentralized, peer-to-peer network, the act of passing information between nodes naturally amplifies privacy. This allows decentralized systems to achieve the high utility of centralized models without the need for a trusted coordinator.
Methodology: Network DP and Token Passing
Network DP relaxes the standard LDP assumption by considering a "local view" of the system. Instead of an omniscient adversary, it assumes a curious user only observes messages they directly send or receive.
The authors evaluate this through a token-passing model. A "token"—representing a running sum, histogram, or model weights—is passed sequentially between users. Each user updates the token with their local data, adds noise, and forwards it.
Algorithm for Decentralized Summation
The study focuses on two topologies: a directed ring and a complete graph. In the complete graph, the token follows a random walk, which acts as a natural shuffler, hiding individual contributions within the aggregate.
Key Insights
- Decentralization as a Privacy Feature: The sequential nature of peer-to-peer communication inherently obscures individual data points. The lack of a central server is proved to be a privacy feature, not just a scalability one.
- The Power of Local Views: Restricting the threat model to what a single node observes allows for mathematically tighter privacy bounds compared to a "god's-eye" view of the network.
- Random Walks as Shufflers: On complete graphs, the randomness of the token's path ensures that individual contributions are "hidden in the crowd," similar to cryptographic shuffling protocols.
Results and Evaluation
The authors prove that Network DP achieves an $O(1/\sqrt{n})$ privacy improvement over LDP for basic tasks like summation. For machine learning tasks using Stochastic Gradient Descent (SGD), the improvement is $O(\ln n / \sqrt{n})$.
Empirical Performance
Experiments on the UCI Housing dataset for logistic regression show that while LDP fails to converge under strict privacy budgets (e.g., $\epsilon = 1$), Network DP successfully trains the model, nearly matching the accuracy of the centralized baseline.
As shown in the figures above, the theoretical privacy loss for Network DP decreases as the network size $n$ increases, whereas standard LDP loss increases. Empirical simulations further confirm that the actual privacy loss is often even lower than the theoretical upper bounds, showing effectiveness even for small networks ($n \ge 20$).
Conclusion and Future Work
Network DP demonstrates that full decentralization provides formal privacy gains. While the current work focuses on ring and complete topologies, future research will explore arbitrary network graphs using graph theory concepts like hitting times and apply these principles to more complex "gossip" protocols where nodes average models with neighbors simultaneously.
Summary updated