In decentralized settings, the shuffle model of differential privacy has emerged as a promising alternative to the classical local model. Analyzing privacy amplification via shuffling is a critical component in both single-message and multi-message shuffle protocols. However, current methods used in these two areas are distinct and specific, making them less convenient for protocol designers and practitioners. In this work, we introduce variation-ratio reduction as a unified framework for privacy amplification analyses in the shuffle model. This framework utilizes total variation bounds of local messages and probability ratio bounds of other users' blanket messages, converting them to indistinguishable levels. Our results indicate that the framework yields tighter bounds for both single-message and multi-message encoders (e.g., with local DP, local metric DP, or general multi-message randomizers). Specifically, for a broad range of local randomizers having extremal probability design, our amplification bounds are precisely tight. We also demonstrate that variation-ratio reduction is well-suited for parallel composition in the shuffle model and results in stricter privacy accounting for common sampling-based local randomizers. Our experimental findings show that, compared to existing amplification bounds, our numerical amplification bounds can save up to $30\%$ of the budget for single-message protocols, $75\%$ of the budget for multi-message protocols, and $75\%$-$95\%$ of the budget for parallel composition. Additionally, our implementation for numerical amplification bounds has only $\tilde{O}(n)$ complexity and is highly efficient in practice, taking just $2$ minutes for $n=10^8$ users. The code for our implementation can be found at \url{https://github.com/wangsw/PrivacyAmplification}.
翻译:在分散设置中,差分隐私的洗牌模型已成为传统本地模型的一种有前途的替代方案。分析通过洗牌进行隐私扩增是单消息和多消息洗牌协议的关键组成部分。然而,目前用于这两个领域的方法是不同和具体的,这使得它们对于协议设计人员和从业人员来说更不方便。在这项工作中,我们引入变率降低作为隐私扩增分析中洗牌模型的统一框架。该框架利用本地消息的总体差分界限和其他用户毯子消息的概率比限制,将它们转换为不可区分的水平。我们的结果表明,该框架针对单消息和多消息编码器(例如,具有本地DP、本地度量DP或一般多消息随机器的本地随机性)产生更紧密的界限。具体而言,对于具有极端概率设计的广泛本地随机器范围,我们的扩增界限是完全紧密的。我们还表明,变率降低适合于洗牌模型的并行组合,并导致对于常见的基于采样的本地随机器更严格的隐私会计。我们的实验结果显示,与现有的扩增限制相比,我们的数值扩增限制可以节省单消息协议的预算高达30%,多消息协议的预算高达75%,并且可以节省并行组合的预算高达75%—95%。此外,我们的数值扩增界限实现仅具有$\tilde{O}(n)$复杂度,在实践中效率极高,对于n=10^8个用户我们只需要2分钟。我们实现的代码可在\url{https://github.com/wangsw/PrivacyAmplification}上找到。