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})\sqrt{\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].

随机洗牌可显著提高局部随机化数据的差分隐私保证，我们提出了一种基于新方法的差分隐私算法，其具有渐近最优的依赖性，应用于洗牌模型中的频率估计，是简单且近乎最优的算法。

躲藏在克隆之中：洗牌隐私扩增的简单且几乎最优分析