Rényi Differential Privacy in the Shuffle Model: Enhanced Amplification Bounds
E Chen, Yang Cao, Yifei Ge · 2024
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, meaning that the privacy guarantee of a small level of noise, say ϵ0, can be enhanced to $O\left( {{\varepsilon _0}/\sqrt n } \right)$ (the smaller, the more private) after shuffling all n users’ perturbed data. Most studies in the shuffle DP focus on proving a tighter privacy guarantee of privacy amplification. However, the current results assume that the local privacy budget ϵ0is within a limited range. In addition, there remains a gap between the tightest lower bound and the known upper bound of the privacy amplification. In this work, we push forward the state-of-the-art by making the following contributions. Firstly, we present the first asymptotically optimal analysis of Ŕenyi Differential Privacy (RDP) in the shuffle model without constraints on ϵ0. Secondly, 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.