Abstract
The shuffle model of Differential Privacy (DP) has gained significant attention in privacy-preserving data analysis due to its remarkable tradeoff between privacy and utility. It is characterized by adding a shuffling procedure after each user's locally differentially private perturbation, which leads to a privacy amplification effect. Most studies in the shuffle DP focus on proving a tighter privacy guarantee of privacy amplification. However, current results assume that the local privacy budget $\epsilon_0$ is within a limited range. In this work, we present the first asymptotically optimal analysis of Renyi Differential Privacy (RDP) in the shuffle model without constraints on $\epsilon_0$. We introduce hypothesis testing for privacy amplification through shuffling, offering a distinct analysis technique and a tighter upper bound. Furthermore, we propose a DP-SGD algorithm based on RDP. Experiments demonstrate that our approach outperforms existing methods significantly at the same privacy level.
Introduction: The Shuffle Model
In the landscape of data privacy, a persistent tension exists between Local Differential Privacy (LDP) and Central Differential Privacy (DP). While LDP ensures that users do not need to trust a central server, it often results in significant utility degradation. Central DP offers superior utility but requires a fully trusted aggregator to handle raw data.
The shuffle model serves as an effective middle ground. As illustrated in Figure 1, users first apply local DP to their data. These perturbed responses are then processed by an anonymous shuffler before reaching the aggregator. This shuffling step provides a "privacy amplification" effect, making it mathematically harder for the server to link specific responses back to individual users.
Bridging the Gap in Privacy Amplification
Despite the advantages of the shuffle model, existing theoretical proofs for privacy amplification have been constrained. Previous bounds often required the initial local noise ($\epsilon_0$) to be very small or left a significant gap between the proven upper bounds and the theoretical lower bounds.
This paper addresses these limitations by reframing the shuffling process as a statistical hypothesis testing problem—specifically, measuring the distance between multinomial distributions. By leveraging the $f$-DP framework, the authors treat privacy as the difficulty of distinguishing whether a specific user's data was $x$ or $x'$. This technique allows for much more precise calculations than traditional concentration inequalities like Chernoff bounds.
Asymptotically Optimal Bounds
A core contribution of this work is the derivation of a new RDP bound: $O(2e^{\epsilon_0} \lambda / n)$. Crucially, this bound is asymptotically optimal and holds for any value of $\epsilon_0$, removing the restrictive assumptions of prior research. As shown in the comparison table below, this new bound is significantly tighter than previous results from Erlingsson et al. (2019), Girgis et al. (2021), and Feldman et al. (2022/2023).
Experimental Validation: DP-SGD
The researchers applied these tighter bounds to the Differentially Private Stochastic Gradient Descent (DP-SGD) algorithm. By utilizing a more accurate "privacy accountant," the algorithm can achieve higher utility for the same formal privacy budget.
In experiments using the MNIST dataset, the proposed method achieved a training accuracy of 96.41%, compared to a non-private baseline of 98.18%. This performance significantly exceeds that of previous shuffle-model methods, demonstrating that tighter theoretical bounds lead directly to more effective machine learning models in practice.
Conclusion
By providing the first asymptotically optimal analysis of RDP in the shuffle model without constraints on the local privacy budget, this work significantly advances the state-of-the-art in privacy-preserving data analysis. The introduction of hypothesis testing techniques not only yields tighter bounds but also provides a robust framework for future research into complex data analysis tasks beyond simple aggregation.
Summary updated