We study the concurrent composition properties of interactive differentially private mechanisms, whereby an adversary can arbitrarily interleave its queries to the different mechanisms. We prove that all composition theorems for non-interactive differentially private mechanisms extend to the concurrent composition of interactive differentially private mechanisms, whenever differential privacy is measured using the hypothesis testing framework of $f$-DP, which captures standard $(\eps,\delta)$-DP as a special case. We prove the concurrent composition theorem by showing that every interactive $f$-DP mechanism can be simulated by interactive post-processing of a non-interactive $f$-DP mechanism. In concurrent and independent work, Lyu~\cite{lyu2022composition} proves a similar result to ours for $(\eps,\delta)$-DP, as well as a concurrent composition theorem for R\'enyi DP. We also provide a simple proof of Lyu's concurrent composition theorem for R\'enyi DP. Lyu leaves the general case of $f$-DP as an open problem, which we solve in this paper.


翻译:差分隐私的并发组合定理 翻译后的摘要: 本文研究交互式差分隐私机制的并发组合特性,其中对手可以任意交替查询不同的机制。我们证明了所有非交互式差分隐私机制的组合定理都可以扩展到交互式差分隐私机制的并发组合,只要使用 $f$-DP 的假设测试框架来衡量差分隐私,该框架捕获标准的 $(\epsilon, \delta)$-DP 作为一个特例。我们通过展示每个交互式 $f$-DP 机制都可以被一个非交互式 $f$-DP 机制的交互式后处理所模拟来证明了并发组合定理。在独立的并发工作中,Lyu~\cite{lyu2022composition}证明了类似于我们的并发组合定理的 $(\epsilon, \delta)$-DP 的结果,以及 R\'enyi-DP 的并发组合定理。我们还为 R\'enyi-DP 的 Lyu 并发组合定理提供了一个简单的证明。Lyu 将 $f$-DP 的一般情况作为一个未解决的问题,我们在本文中解决了这个问题。

0
下载
关闭预览

相关内容

专知会员服务
88+阅读 · 2021年6月29日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
【ICML2020】统一预训练伪掩码语言模型
专知会员服务
25+阅读 · 2020年7月23日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Zero-Shot Learning相关资源大列表
专知
52+阅读 · 2019年1月1日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年5月17日
VIP会员
相关VIP内容
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Zero-Shot Learning相关资源大列表
专知
52+阅读 · 2019年1月1日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员