Recent work of Erlingsson, Feldman, Mironov, Raghunathan, Talwar, and Thakurta [EFMRTT19] demonstrates that random shuffling of input data amplifies differential privacy guarantees  . Such amplification leads to substantially stronger privacy guarantees for systems in which data is contributed anonymously [BEMMRLRKTS17] and for the analysis of noisy stochastic gradient descent  . We show that an \varepsilon_0-locally differentially private algorithm, under shuffling with n users, amplifies to a (\Theta ((1-e^{-\varepsilon_0})\frac{e^{\varepsilon_0\log(1/\delta)}{n}}), \delta) -central differential privacy guarantee . This significantly improves over previous work and achieves the asymptotically optimal dependence on \varepsilon_0. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees. Our work also yields an empirical method to derive tighter bounds on the central \varepsilon and we show that it gets to within a small constant factor of the correct bound. As a direct corollary of our analysis  we derive a simple and asymptotically optimal algorithm for discrete distribution estimation in the shuffle model of privacy CSUZZ19 .
Recent work of Erlingsson, Feldman, Mironov, Raghunathan, Talwar, and Thakurta [EFMRTT19] demonstrates that random shuffling amplifies differential privacy guarantees of locally randomized data . Such amplification implies substantially stronger privacy guarantees for systems in which data is contributed anonymously [BEMMRLRKTS17] and has lead to significant interest in the shuffle model of privacy CSUZZ19,EFMRTT19 . We show that random shuffling of n data records that are input to \varepsilon_0-differentially private local randomizers results in an (O ((1-e^{-\varepsilon_0})\frac{e^{\varepsilon_0\log(1/\delta)}{n}}), \delta) -differentially private algorithm . This significantly improves over previous work and achieves the asymptotically optimal dependence in \varepsilon_0. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees. Our work also yields an empirical method to derive tighter bounds the resulting \varepsilon and we show that it gets to within a small constant factor of the optimal bound. As a direct corollary of our analysis , we derive a simple and asymptotically optimal algorithm for discrete distribution estimation in the shuffle model of privacy . We also observe that our result implies the first asymptotically optimal privacy analysis of noisy stochastic gradient descent that applies to sampling without replacement .
D
of input data
A
of locally randomized data
R
leads to
implies
R
for the analysis of noisy stochastic gradient descent
has lead to significant interest in the shuffle model of privacy
A
CSUZZ19,EFMRTT19
R
an \varepsilon_0-locally differentially private algorithm, under shuffling with n users, amplifies to a (\Theta
random shuffling of n data records that are input to \varepsilon_0-differentially private local randomizers results in an (O
R
-central differential privacy guarantee
-differentially private algorithm
R
on
in
R
on the central
the resulting
R
correct
optimal
A
,
R
CSUZZ19
. We also observe that our result implies the first asymptotically optimal privacy analysis of noisy stochastic gradient descent that applies to sampling without replacement