Concurrent Composition Theorems for Differential Privacy

DOI10.1145/3564246.3585241MaRDI QIDQ6405259zbMATH OpenOpenAlexFDO

Authors Salil Vadhan, Wanrong Zhang

Publication date 17 July 2022

Full work available at URL https://doi.org/10.1145/3564246.3585241

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: 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.

Cited in

(2)

• Advanced composition theorems for differential obliviousness
• Securing dynamic data: a primer on differentially private data structures (invited talk)

This page was built for publication: Concurrent Composition Theorems for Differential Privacy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405259)