论文标题
交互式差异隐私的组成定理
Composition Theorems for Interactive Differential Privacy
论文作者
论文摘要
交互式机制是一种存储数据集并回答自适应查询的算法。如果任何对手无法通过与机制相互作用来区分数据集中的特定人，则该机制称为私有。我们研究并发组成中差异隐私的组成特性。在这种情况下，对手并行与K交互作用机制相互作用，并可以任意将其查询与机制交织在一起。以前，Vadhan和Wang [2021]证明了纯差异隐私的最佳并发组成定理。我们显着概括并扩大他们的结果。也就是说，我们证明了文献中几种主要差异隐私概念的最佳平行组成特性，包括近似DP，RényiDP和零浓缩的DP。我们的结果表明，对手通过将其查询与独立运行机制交织在一起，从而获得了任何优势。因此，互动性是差异隐私免费赋予我们的功能。 Vadhan和Zhang [2022]同时独立地独立于我们的工作，证明了F-DP的最佳并发组成定理[Dong等，2022]，这意味着我们对大约DP情况的结果。
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 [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ényi 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. Concurrently and independently of our work, Vadhan and Zhang [2022] proved an optimal concurrent composition theorem for f-DP [Dong et al., 2022], which implies our result for the approximate DP case.
