Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2401.04306 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916085348958208 |
|---|---|
| author | Chen, E Cao, Yang Ge, Yifei |
| author_facet | Chen, E Cao, Yang Ge, Yifei |
| contents | 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(ε_0/\sqrt{n})$ (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 $ε_0$ 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 Renyi 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_04306 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Renyi Differential Privacy in the Shuffle Model: Enhanced Amplification Bounds Chen, E Cao, Yang Ge, Yifei Combinatorics 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(ε_0/\sqrt{n})$ (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 $ε_0$ 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 Renyi 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. |
| title | Renyi Differential Privacy in the Shuffle Model: Enhanced Amplification Bounds |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.04306 |