Concurrent Composition Theorems for all Standard Variants of Differential Privacy

          @misc{ scivideos_22920,
            doi = {},
            url = {https://old.simons.berkeley.edu/talks/concurrent-composition-theorems-all-standard-variants-differential-privacy},
            author = {},
            keywords = {},
            language = {en},
            title = {Concurrent Composition Theorems for all Standard Variants of Differential Privacy},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2022},
            month = {nov},
            note = {22920 see, \url{https://scivideos.org/simons-institute/22920}}
          }
          

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 for all standard variants of differential privacy including $(\eps,\delta)$-DP with $\delta>0$, R\`enyi DP, and $f$-DP, thus answering the open question by \cite{vadhan2021concurrent}. For $f$-DP, which captures $(\eps,\delta)$-DP as a special case, we prove the concurrent composition theorems by showing that every interactive $f$-DP mechanism can be simulated by interactive post-processing of a non-interactive $f$-DP mechanism. For R\`enyi DP, we use a different approach by showing the optimal adversary against the concurrent composition can be decomposed as a product of the optimal adversaries against each interactive mechanism.