The Composition Theorem for Differential Privacy

2013/11/04 by Peter Kairouz, Sewoong Oh, Kairouz, Peter +3 · 53 citations
Computer Science · Mathematics · #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.CR #cs.DS #cs.IT #math.IT

paper · pdf · doi:10.48550/arxiv.1311.0776

32 pages 4 figures, Added a new section on private multi-party computation

arxiv created 2015/12/06 · arxiv updated 2015/12/08

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 by

• DPSR: Differentially Private Sparse Reconstruction via Multi-Stage Denoising for Recommender Systems
• SUP: An Inferable Private Multiple Testing Framework with Super Uniformity
• Infinitely divisible privacy and beyond I: resolution of the s²=2k conjecture
• Differential privacy from axioms
• Beyond Membership: Limitations of Add/Remove Adjacency in Differential Privacy
• Setting ε is not the Issue in Differential Privacy
• PrivacyGuard: A Modular Framework for Privacy Auditing in Machine Learning
• Mitigating Privacy-Utility Trade-off in Decentralized Federated Learning via f-Differential Privacy
• Gaussian Certified Unlearning in High Dimensions: A Hypothesis Testing Approach
• An information theorist's tour of differential privacy
• Locally Optimal Private Sampling: Beyond the Global Minimax
• Cocoon: A System Architecture for Differentially Private Training with Correlated Noises
• No Prior, No Leakage: Revisiting Reconstruction Attacks in Trained Neural Networks
• RAG Security and Privacy: Formalizing the Threat Model and Attack Surface
• SynBench: A Benchmark for Differentially Private Text Generation
• Membership Inference Attacks on Recommender System: A Survey
• Sequentially Auditing Differential Privacy
• PLRV-O: Advancing Differentially Private Deep Learning via Privacy Loss Random Variable Optimization
• Managing Correlations in Data and Privacy Demand
• Augmented Shuffle Differential Privacy Protocols for Large-Domain Categorical and Key-Value Data
• Differentially Private Federated Quantum Learning via Quantum Noise
• Auditing Approximate Machine Unlearning for Differentially Private Models
• An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noise
• Privacy Disclosure of Similarity Rank in Speech and Language Processing
• RecPS: Privacy Risk Scoring for Recommender Systems
• Auditing Apple's DifferentialPrivacy.framework: Implementation Bugs, Misconfigurations, and Practical Risks
• Frequency Estimation of Correlated Multi-attribute Data under Local Differential Privacy
• Differential Privacy in Kernelized Contextual Bandits via Random Projections
• Interpreting Differential Privacy in Terms of Disclosure Risk
• A Unified Framework for Adversary-Aware Differential Privacy Bounds
• Unifying Re-Identification, Attribute Inference, and Data Reconstruction Risks in Differential Privacy
• StraightDP: Geometry-Aware Differential Privacy for Rectified-Flow Transformers
• UniAud: A Unified Auditing Framework for High Auditing Power and Utility with One Training Run
• Convergent Privacy Framework for Multi-layer GNNs through Contractive Message Passing
• A Novel Approach to Differential Privacy with Alpha Divergence
• The Hitchhiker's Guide to Efficient, End-to-End, and Tight DP Auditing
• Decentralized Optimization with Amplified Privacy via Efficient Communication
• Residual-PAC Privacy: Automatic Privacy Control Beyond the Gaussian Barrier
• Synthetic Tabular Data: Methods, Attacks and Defenses
• Trade-offs in Data Memorization via Strong Data Processing Inequalities
• Private Rate-Constrained Optimization with Applications to Fair Learning
• Faster Rates for Private Adversarial Bandits
• Optimal Piecewise-based Mechanism for Collecting Bounded Numerical Data under Local Differential Privacy
• Lower Bounds on the MMSE of Adversarially Inferring Sensitive Features
• Source Anonymity for Private Random Walk Decentralized Learning
• Optimal Regret of Bernoulli Bandits under Global Differential Privacy
• MAPLE: Metadata Augmented Private Language Evolution
• Understanding Disclosure Risk in Differential Privacy with Applications to Noise Calibration and Auditing (Extended Version)
• Optimal Quantum Differential Privacy via Fisher Information Spectral Analysis
• Density-Aware Noise Mechanisms for Differential Privacy on Riemannian Manifolds via Conformal Transformation
• DP-MemView: A Memory Interface for Attribute-Level Transcript Privacy in Long-Term LLM Agents
• MCMC for Bayesian estimation of Differential Privacy from Membership Inference Attacks
• Decomposition-Based Optimal Bounds for Privacy Amplification via Shuffling

Related

• Concurrent Composition of Differential Privacy
• Composition Theorems for Interactive Differential Privacy
• Analytic Theory to Differential Privacy
• Privacy and Utility Tradeoff in Approximate Differential Privacy
• The Algorithmic Foundations of Differential Privacy