The complexity of computing the optimal composition of differential privacy

DOI10.1007/978-3-662-49096-9_7MaRDI QIDQ2796124zbMATH OpenOpenAlexFDO

Authors Jack Murtagh, Salil Vadhan

Publication date 23 March 2016

Published in Theory of Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.03113

zbMATH Keywords

computational complexityapproximation algorithmscompositiondifferential privacy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

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 $(epsilo{n}_1,delt{a}_1),ldots,(epsilo{n}_k,delt{a}_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).

Recommendations

• The complexity of computing the optimal composition of differential privacy
• Concurrent composition of differential privacy
• The algorithmic foundations of differential privacy
• Answering n^2+o(1) counting queries with differential privacy is hard
• Differentially private combinatorial optimization

Cites work

• Approximate counting by dynamic programming
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• Randomized response: a survey technique for eliminating evasive answer bias
• The Composition Theorem for Differential Privacy
• The algorithmic foundations of differential privacy
• The complexity of computing the optimal composition of differential privacy
• Theory of Cryptography

Cited in

(21)

• scientific article; zbMATH DE number 7164746 (Why is no real title available?)
• PAC privacy: automatic privacy measurement and control of data processing
• The complexity of computing the optimal composition of differential privacy
• Asymmetric Distances for Approximate Differential Privacy
• Gaussian differentially private robust mean estimation and inference
• Foundations of Differentially Oblivious Algorithms
• Bounding, concentrating, and truncating: unifying privacy loss composition for data analytics
• Fingerprinting codes and the price of approximate differential privacy
• Separating computational and statistical differential privacy in the client-server model
• Federated learning on Riemannian manifolds with differential privacy
• A theory of composition for differential obliviousness
• The complexity of verifying loop-free programs as differentially private
• Concentrated differential privacy: simplifications, extensions, and lower bounds
• Differential privacy: getting more for less
• The complexity of differential privacy
• A novel adaptive differential privacy algorithm for empirical risk minimization
• Optimal differentially private learning of thresholds and quasi-concave optimization
• Advanced composition theorems for differential obliviousness
• Concurrent composition of differential privacy
• Beyond Differential Privacy: Composition Theorems and Relational Logic for f-divergences between Probabilistic Programs
• PT-ADP: a personalized privacy-preserving federated learning scheme based on transaction mechanism

Describes a project that uses

Uses Software

• Dataverse

This page was built for publication: The complexity of computing the optimal composition of differential privacy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2796124)