You are looking at a specific version 20151030:193332 of this paper. See the latest version.

Paper 2015/1057

The Complexity of Computing the Optimal Composition of Differential Privacy

Jack Murtagh, Salil Vadhan

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 (epsilon,delta)-differentially private algorithms. We characterize the optimal composition for the more general case of k arbitrary (epsilon_1, delta_1),...,(epsilon_k, delta_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).

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in TCC 2016
Keywords
differential privacycompositioncomputational complexityapproximation algorithms
Contact author(s)
jmurtagh @ seas harvard edu
salil @ seas harvard edu
History
2015-10-30: received
Short URL
https://ia.cr/2015/1057
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.