Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling

By Vitaly Feldman, Audra McMillan, Kunal Talwar. 2020

198 citations recorded by the source corpus.

Recent work of Erlingsson, Feldman, Mironov, Raghunathan, Talwar, and Thakurta [1] demonstrates that random shuffling amplifies differential privacy guarantees of locally randomized data. Such amplification implies substan-tially stronger privacy guarantees for systems in which data is contributed anonymously [2] and has lead to significant interest in the shuffle model of privacy [3], [1]. We give a characterization of the privacy guarantee of the random shuffling of $\mathbf{n}$ data records input to epsilon-differentially private local randomizers that significantly im-proves over previous work and achieves the asymptotically optimal dependence in epsilon. 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. Importantly, our work also yields an algorithm for deriving tighter bounds on the resulting epsilon and delta as well as Rényi differential privacy guarantees. We show numerically that our algorithm gets to within a small constant factor of the optimal bound. As a direct corollary of our analysis we derive a simple and nearly optimal algorithm for frequency 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.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Electrical and Electronic Engineering

Citations in the corpus

Practical and Private (Deep) Learning without Sampling or Shuffling (2021, methodology): “3A similar argument holds for amplification by shuffling [23, 30], when the data are uniformly shuffled at the beginning of every epoch.”
Privacy Amplification by Decentralization (2020, methodology): “We can obtain a similar result for histograms by bounding the privacy loss incurred for each cycle by using ampliﬁcation by shuﬄing (Erlingsson et al., 2019; Balle et al., 2019b; Feldman et al., 2020), similar to what we did for the ring topology (Section 3.2).”
How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy (2023, background): “Recent studies suggest that shuffling can also amplify privacy (Erlingsson et al., 2019; Feldman et al., 2022), but the best known amplification guarantees are weaker than what one would achieve via sampling.”
Lossless Compression of Efficient Private Local Randomizers (2021, methodology): “The ε > 1 regime has become particularly important since the introduction of the privacy amplification techniques based on anonymization and shuffling of LDP reports (Bittau et al., 2017; Erlingsson et al., 2019; Cheu et al., 2019; Balle et al., 2019; Feldman et al., 2020).”
Differentially Private Histograms in the Shuffle Model from Fake Users (2021, methodology): “The privacy amplification lemma from [15] lets us analyze the case where k = 0.”