We initiate a study of the composition properties of interactive differentially private mechanisms. An interactive differentially private mechanism is an algorithm that allows an analyst to adaptively ask queries about a sensitive dataset, with the property that an adversarial analyst's view of the interaction is approximately the same regardless of whether or not any individual's data is in the dataset. Previous studies of composition of differential privacy have focused on non-interactive algorithms, but interactive mechanisms are needed to capture many of the intended applications of differential privacy and a number of the important differentially private primitives. We focus on concurrent composition, where an adversary can arbitrarily interleave its queries to several differentially private mechanisms, which may be feasible when differentially private query systems are deployed in practice. We prove that when the interactive mechanisms being composed are pure differentially private, their concurrent composition achieves privacy parameters (with respect to pure or approximate differential privacy) that match the (optimal) composition theorem for noninteractive differential privacy. We also prove a composition theorem for interactive mechanisms that satisfy approximate differential privacy. That bound is weaker than even the basic (suboptimal) composition theorem for noninteractive differential privacy, and we leave closing the gap as a direction for future research, along with understanding concurrent composition for other variants of differential privacy.


翻译:我们开始研究不同私人互动机制的构成特性。 互动式的私人机制是一种允许分析师对敏感数据集进行适应性查询的算法,其属性是,对立分析师对互动的看法大致相同,而不论个人的数据是否在数据集中。 以前对不同隐私构成的研究侧重于非互动式算法,但需要互动机制来捕捉不同隐私和一些重要差异性私人原始体的许多预期应用。我们侧重于同时构成,即对手可以任意将其查询与若干差异性私营机制互交,而当实际采用差异性私人查询系统时,这种机制可能是可行的。我们证明,当互动机制的构成是纯粹的私人机制时,其同时构成就达到了隐私参数(纯或近似差异性隐私),与非互动性差异性隐私的(最优)组成原理相匹配。 我们还证明,满足大致差异性隐私的互动机制的构成是构成的构成。 我们的界限比基本(次偏差)的私人机制更弱,在使用非互动性隐私结构时,我们将缩小差距的构成作为非互动性隐私的另一种理解。

0
下载
关闭预览

相关内容

IFIP TC13 Conference on Human-Computer Interaction是人机交互领域的研究者和实践者展示其工作的重要平台。多年来,这些会议吸引了来自几个国家和文化的研究人员。官网链接:http://interact2019.org/
最新《Transformers模型》教程,64页ppt
专知会员服务
305+阅读 · 2020年11月26日
如何撰写好你的博士论文?CMU-Priya博士这30页ppt为你指点
专知会员服务
55+阅读 · 2020年10月30日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
3+阅读 · 2017年10月27日
Arxiv
0+阅读 · 2021年11月8日
Arxiv
0+阅读 · 2021年11月7日
Arxiv
0+阅读 · 2021年11月3日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
3+阅读 · 2017年10月27日
Top
微信扫码咨询专知VIP会员