The Composition Theorem for Differential Privacy

DOI10.1109/TIT.2017.2685505MaRDI QIDQ4682988zbMATH OpenOpenAlexFDO

Authors Peter Kairouz, Sewoong Oh, P. Viswanath

Publication date 19 September 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Authentication, digital signatures and secret sharing (94A62)

Abstract: Sequential querying of differentially private mechanisms degrades the overall privacy level. In this paper, we answer the fundamental question of characterizing the level of overall privacy degradation as a function of the number of queries and the privacy levels maintained by each privatization mechanism. Our solution is complete: we prove an upper bound on the overall privacy level and construct a sequence of privatization mechanisms that achieves this bound. The key innovation is the introduction of an operational interpretation of differential privacy (involving hypothesis testing) and the use of new data processing inequalities. Our result improves over the state-of-the-art, and has immediate applications in several problems studied in the literature including differentially private multi-party computation.

Cited in

(20)

• Confidentiality and differential privacy in the dissemination of frequency tables
• Locally differentially private item-based collaborative filtering
• The complexity of computing the optimal composition of differential privacy
• Concentrated differential privacy: simplifications, extensions, and lower bounds
• Differentially Private Distributed Learning
• The complexity of computing the optimal composition of differential privacy
• Comment
• The complexity of differential privacy
• A novel adaptive differential privacy algorithm for empirical risk minimization
• Beyond Differential Privacy: Composition Theorems and Relational Logic for f-divergences between Probabilistic Programs
• Differential privacy in constant function market makers
• Discrimination of quantum states under locality constraints in the many-copy setting
• Distribution-invariant differential privacy
• Canonical noise distributions and private hypothesis tests
• Total variation distance privacy: accurately measuring inference attacks and improving utility
• Optimal differentially private learning of thresholds and quasi-concave optimization
• Privacy-preserving Frank-Wolfe on shuffle model
• Bounding, concentrating, and truncating: unifying privacy loss composition for data analytics
• Differentially private Assouad, Fano, and Le Cam
• Federated learning on Riemannian manifolds with differential privacy

This page was built for publication: The Composition Theorem for Differential Privacy

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