Concurrent Composition Theorems for Differential Privacy

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 R\`enyi DP (which we also claimed in an earlier version of this paper, but with an incorrect proof). Lyu leaves the general case of $f$-DP as an open problem, which we solve in this paper.