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}上找到。

0
下载
关闭预览

相关内容

【NeurIPS2021】多模态虚拟点三维检测
专知会员服务
18+阅读 · 2021年11月16日
专知会员服务
123+阅读 · 2020年9月8日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Pytorch多模态框架MMF
专知
49+阅读 · 2020年6月20日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
使用随机森林分类器预测森林火灾规模
论智
13+阅读 · 2018年5月15日
国家自然科学基金
4+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
2+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
VIP会员
相关资讯
相关基金
国家自然科学基金
4+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
2+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员