论文标题
步行到隐藏：通过网络中的随机消息交换的隐私放大
Walking to Hide: Privacy Amplification via Random Message Exchanges in Network
论文作者
论文摘要
* Shuffle模型 *是放大差异隐私 *本地模型 *的隐私保证的强大工具。与在本地模型中保证隐私的完全分散的方式相反，洗牌模型需要一个中心值得信赖的洗牌者。为了避免这种中心调整，Liew等人的最新工作。 （2022）通过在客户构成的通信网络上随机步行，以分散的方式提出了以分散的方式改组本地随机数据。因此，即使是无限长的随机步行，其提供的隐私放大限制了它提供的限制取决于基础通信网络的拓扑。它与洗牌模型的最新隐私放大不匹配（Feldman等，2021）。 在这项工作中，我们证明了〜$ n $客户端的数据的输出，每个数据都受到$ε_0$ - 局部随机化的扰动，并通过随机步行和对数步骤进行随机步行，为$（{o}（（1- e^ - e^{ - ε_0}） o（δ））$ - 差异私有。重要的是，这种结合独立于通信网络的拓扑，渐近地缩小了网络洗牌模型的隐私放大界限（Liew等，2022）和洗牌模型（Feldman等，2021）。我们的证明是基于对洗牌模型的减少，以及对有限长度随机步行的分布的分析。在此基础上，我们进一步表明，如果每个客户都以概率〜$ p $独立采样，则可以将网络洗牌模型的隐私保证进一步提高到$（{o}（（1- e^{ - e^{ - ε_0}）\ sqrt {p（e^^{e^{ε_0} / n）\ ln（e^{^{ε_0} / n）\ ln（1 /δ）重要的是，还以完全分散的方式进行子采样，而不需要受信任的中央实体。与先前工作中的相关界限相比，我们的界限更强。
The *shuffle model* is a powerful tool to amplify the privacy guarantees of the *local model* of differential privacy. In contrast to the fully decentralized manner of guaranteeing privacy in the local model, the shuffle model requires a central, trusted shuffler. To avoid this central shuffler, recent work of Liew et al. (2022) proposes shuffling locally randomized data in a decentralized manner, via random walks on the communication network constituted by the clients. The privacy amplification bound it thus provides depends on the topology of the underlying communication network, even for infinitely long random walks. It does not match the state-of-the-art privacy amplification bound for the shuffle model (Feldman et al., 2021). In this work, we prove that the output of~$n$ clients' data, each perturbed by an $ε_0$-local randomizer, and shuffled by random walks with a logarithmic number of steps, is $( {O} ( (1 - e^{-ε_0} ) \sqrt{ ( e^{ε_0} / n ) \ln (1 / δ) } ), O(δ) )$-differentially private. Importantly, this bound is independent of the topology of the communication network, and asymptotically closes the gap between the privacy amplification bounds for the network shuffle model (Liew et al., 2022) and the shuffle model (Feldman et al., 2021). Our proof is based on a reduction to the shuffle model, and an analysis of the distribution of random walks of finite length. Building on this, we further show that if each client is sampled independently with probability~$p$, the privacy guarantee of the network shuffle model can be further improved to $( {O} ( (1 - e^{-ε_0} ) \sqrt{p ( e^{ε_0} / n ) \ln (1 / δ) } ) , O(δ) )$. Importantly, the subsampling is also performed in a fully decentralized manner that does not require a trusted central entity; compared with related bounds in prior work, our bound is stronger.
