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

We consider privacy-preserving data analysis in the local model of differential privacy augmented with a shuffler. In this model, each user sends a locally differentially private report and these reports are then anonymized and randomly shuffled. Systems based on this model were first proposed in [BEMMRLRKTS17]. The authors of [EFMRTT19] showed that random shuffling of inputs to locally private protocols amplifies the privacy guarantee. Thus, when the collection of anonymized reports is viewed in the central model, the privacy guarantees are substantially stronger than the original local privacy guarantees. A similar result was shown for the binary randomized response by Cheu, Smith, Ullman, Zeber, and Zhilyaev [CSUZZ19] who also formalized a related shuffle model of privacy. The analysis in [EFMRTT19] relies on a more general result referred to as privacy amplification by shuffling. This result shows that privacy is amplified when the inputs are shuffled before applying local randomizers and holds even when local randomizers are chosen sequentially and adaptively. Allowing adaptive choice of local randomizers is necessary for analyzing iterative optimization algorithms such as stochastic gradient descent.