An interactive mechanism is an algorithm that stores a data set and answers adaptively chosen queries to it. The mechanism is called differentially private, if any adversary cannot distinguish whether a specific individual is in the data set by interacting with the mechanism. We study composition properties of differential privacy in concurrent compositions. In this setting, an adversary interacts with k interactive mechanisms in parallel and can interleave its queries to the mechanisms arbitrarily. Previously, [Vadhan and Wang, TCC 2021] proved an optimal concurrent composition theorem for pure-differential privacy. We significantly generalize and extend their results. Namely, we prove optimal parallel composition properties for several major notions of differential privacy in the literature, including approximate DP, R\'enyi DP, and zero-concentrated DP. Our results demonstrate that the adversary gains no advantage by interleaving its queries to independently running mechanisms. Hence, interactivity is a feature that differential privacy grants us for free.
翻译：互动机制是一种算法,它存储一个数据集,并回答自定选择的询问。 如果任何对手无法通过与机制互动来区分某个特定个人是否在数据集中的话,这个机制被称为“有差别的私人”机制。 我们研究不同隐私在同时构成中的构成特性。 在这种环境下,对手与 k 互动机制平行互动,可以任意将其询问与机制联系起来。 以前, [瓦德汉和王, TCC 2021] 证明是纯区分隐私的最佳同时构成。 我们大大地概括和扩展了它们的结果。 也就是说,我们对文献中若干差异隐私的主要概念,包括近似DP、 R\'enyi DP 和零集中的DP, 证明是最佳的平行构成特性。 我们的结果表明,对立机制进行独立运行的查询不会带来优势。 因此,互动是一个差异隐私的特征,可以让我们免费获得。
相关内容
微信扫码咨询专知VIP会员