The Complexity of Computing the Optimal Composition of Differential Privacy

By Jack Murtagh, Salil P. Vadhan. 2015

142 citations recorded by the source corpus.

In the study of differential privacy, composition theorems starting with the original paper of Dwork, McSherry, Nissim, and Smith TCC'06 bound the degradation of privacy when composing several differentially private algorithms. Kairouz, Oh, and Viswanath ICML'15 showed how to compute the optimal bound for composing k arbitrary $$\epsilon ,\delta $$-differentially private algorithms. We characterize the optimal composition for the more general case of k arbitrary $$\epsilon _{1},\delta _{1},\ldots ,\epsilon _{k},\delta _{k}$$-differentially private algorithms where the privacy parameters may for each algorithm in the composition. We show that computing the optimal composition in general is #P-complete. Since computing optimal composition exactly is infeasible unless FP=#P, we give an approximation algorithm that computes the composition to arbitrary accuracy in polynomial time. The algorithm is a modification of Dyer's dynamic programming approach to approximately counting solutions to knapsack problems STOC'03.

Subfields: Artificial Intelligence, Information Systems, Statistical Learning Theory, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Statistical Learning Theory

In Privacy & Security

Citations in the corpus

Subsampled Rényi Differential Privacy and Analytical Moments Accountant (2018, background): “Unfortunately, the resulting optimal composition bound is quite complex to state exactly, and indeed is even #P-complete to compute exactly when composing mechanisms with diﬀerent ( (cid:15) i , δ i ) parameters (Murtagh & Vadhan, 2016).”
Rényi Differential Privacy (2017, background): “Murtagh and Vadhan [8] demonstrate that generalizing this result to composition of heterogeneous mechanisms (i.e., satisfying (ǫi, δi)-DP for different ǫi’s) is #P-hard; they describe a PTAS for an approximate solution.”
The Complexity of Differential Privacy (2017, background): “Unfortunately, the resulting optimal composition bound is quite complex, and indeed is even #P-complete to compute exactly when composing mechanisms with different (εi, δi) parameters [82].”
Composable and versatile privacy via truncated CDP (2018, result): “This stands in sharp contrast to the situation with approximate DP, for which computing optimal composition bounds is computationally intractable (#P-hard) [20].”
Deep Learning with Gaussian Differential Privacy (2019, unknown): “#P hard to compute the privacy bounds from their composition theorem [42].”
Differential Privacy Techniques for Cyber Physical Systems: A Survey (2018, methodology): “However, existing methods of deciding privacy budget using composition theorem are not optimal [334].”