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

Recent work of Erlingsson, Feldman, Mironov, Raghunathan, Talwar, and Thakurta [EFMRTT19] demonstratesthat random shuffling amplifies differential privacy guarantees of locally randomized data. Such amplification impliessubstantially 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 $\epsilon_0$-differentially private local randomizers results in an $(O((1-e^{-\epsilon_0})\sqrt{\frac{e^{\epsilon_0}\log(1/\delta)}{n}}), \delta)$-differentially private algorithm. This significantly improves over previous work and achieves the asymptotically optimal dependence in $\epsilon_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 $\epsilon$ and we show that it gets to within a small constant factor of the optimal bound. It also naturally extends to an empirical method to provide bounds for Renyi differential privacy in the shuffle model.