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 的一般情况作为一个未解决的问题,我们在本文中解决了这个问题。