论文标题
藏在克隆中：通过改组来简单而几乎最佳的隐私放大分析
Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling
论文作者
论文摘要
Erlingsson，Feldman，Mironov，Raghunathan，Talwar和Thakurta [EFMRTT19]的最新工作表明，随机洗牌放大了局部随机数据的差异隐私保证。这种扩增意味着对数据匿名贡献数据的系统（Bemmrlrkts17）的系统具有更大的隐私保证，并引起了人们对隐私的洗牌模型的重大兴趣[CSUZZ19; EFMRTT19]。 我们表明，输入到$ \ varepsilon_0 $ -diffient的本地局部随机化器输入的$ n $数据记录的随机改组会导致$（（（1-e^{ - \ \ varepsilon_0}）\ sqrt {\ sqrt {\ frac {\ frac { Δ）$ - 差异私有算法。这对以前的工作有了显着改善，并在$ \ varepsilon_0 $中实现了渐近的最佳依赖性。我们的结果是基于一种比以前的工作更简单的新方法，并扩展到近似差异隐私，并具有几乎相同的保证。重要的是，我们的工作还产生了一种算法，用于在产生的$ \ varepsilon $和$δ$以及rényi差异隐私保证上得出更紧密的界限。我们以数字显示我们的算法达到最佳结合的小恒定因子。作为我们分析的直接推论，我们得出了一种简单而几乎最佳的算法，以用于隐私的洗牌模型中的频率估计。我们还观察到，我们的结果意味着对无需替代的噪声随机梯度下降的首次渐近最佳隐私分析。
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})\sqrt{\frac{e^{\varepsilon_0}\log(1/δ)}{n}}), δ)$-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. Importantly, our work also yields an algorithm for deriving tighter bounds on the resulting $\varepsilon$ and $δ$ 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.
