Rényi Differential Privacy in the Shuffle Model: Enhanced Amplification Bounds

E Chen, Yang Cao, Yifei Ge

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, meaning that the privacy guarantee of a small level of noise, say ϵ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</inf> , 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 ϵ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</inf> is 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 ϵ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</inf> . 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.
BibTeX
@misc{chen2024renyi,
  author = {E Chen and Yang Cao and Yifei Ge},
  title = {{Rényi Differential Privacy in the Shuffle Model: Enhanced Amplification Bounds}},
  year = {2024},
  eprint = {2401.04306},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2401.04306},
  howpublished = {arXiv},
}

Loading related content...

Figure