The Complexity of Computing the Optimal Composition of Differential Privacy
View/ Open
Published Version
https://doi.org/10.1007/978-3-662-49096-9_7Metadata
Show full item recordCitation
Murtagh, Jack, and Salil Vadhan. 2015. “The Complexity of Computing the Optimal Composition of Differential Privacy.” Lecture Notes in Computer Science (December 19): 157–175. doi:10.1007/978-3-662-49096-9_7.Abstract
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 ( , δ)- differentially private algorithms. We characterize the optimal composition for the more general case of k arbitrary ( 1, δ1), . . . ,( k, δk)-differentially private algorithms where the privacy parameters may differ 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).Other Sources
https://arxiv.org/abs/1507.03113Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAACitable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:28237450
Collections
- FAS Scholarly Articles [18292]
Contact administrator regarding this item (to report mistakes or request changes)