The Composition Theorem for Differential Privacy

Peter Kairouz; Sewoong Oh; Pramod Viswanath

Source-linked AI summary

The Composition Theorem for Differential Privacy

Peter Kairouz, Sewoong Oh, Pramod Viswanath

arXiv:1311.0776v4Nov 4, 2013cs.DScs.CRcs.IT

TL;DR

Sequential composition raises the question of how overall privacy degrades with the number and privacy levels of repeated mechanisms. The paper answers it using hypothesis testing and data-processing inequalities, obtaining an exact, attainable composition guarantee that improves prior results and supports applications including multi-party computation.

Problem
The paper asks how privacy degrades under k-fold adaptive composition when each interactive query satisfies differential privacy guarantees.
Method
The paper interprets differential privacy through binary hypothesis testing and uses data-processing inequalities to analyze composition.
Results
The paper exactly characterizes the privacy guarantee under k-fold composition and constructs nonadaptive mechanisms that attain it, strictly improving the state of the art by a logarithmic factor.
Takeaways & Limitations
The composition theorem can strengthen existing results in differential privacy applications, including noise addition and secure multi-party computation.
Takeaways & Limitations
The multi-party computation application assumes independent private binary data across parties; without independence, parties can learn about one another.

Abstract

from arXiv · show

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.

1 Introduction

The paper characterizes how privacy degrades under repeated adaptive queries, improving prior composition guarantees through an exact bound and matching mechanisms. Its hypothesis-testing interpretation and data-processing inequalities also yield strengthened applications and results for noise mechanisms and secure multi-party computation.

Motivation: Sequential composition asks how privacy degrades when multiple interactive queries each satisfy differential privacy guarantees.A routine bound gives (kε, kδ)-differential privacy, while prior work provides a tighter adaptive-composition guarantee.
Main result: The paper gives an exact characterization of privacy under k-fold composition and constructs nonadaptive mechanisms that attain the guarantee.The result applies to any k-fold adaptive composition of (ε, δ)-differentially private mechanisms.
Main result: The new composition result strictly improves the state of the art by a logarithmic factor, especially when ε and δ are both small.The approximation for the new privacy parameters is reported as smaller than the existing guarantee by a logarithmic factor.
Method: The operational interpretation views differential privacy through false-alarm and missed-detection guarantees in binary hypothesis testing.This perspective provides the logic for the proof and supports generalizations such as heterogeneous compositions.
Method: Hypothesis-testing data-processing inequalities produce strong technical results underlying the composition analysis.The paper emphasizes both a natural data-processing inequality and its strong converse.
Applications: The theorem strengthens existing conclusions in noise addition, related differential privacy results, and secure multi-party computation.The paper also shows that Gaussian noise is not unique in achieving the same utility as measured by noise variance, and proves randomized response optimal for secure multi-party computation.

2 Differential Privacy as Hypothesis Testing

The paper reformulates differential privacy as a binary hypothesis-testing constraint on false alarms and missed detections. This yields a graphical privacy region, an equivalent characterization, and data-processing results for comparing mechanisms.

Operational interpretation: Differential privacy can be interpreted as constraints on false-alarm and missed-detection probabilities when distinguishing two neighboring databases.The operational view makes it impossible to obtain both small false-alarm and missed-detection probabilities from differentially private data.
Privacy region: The privacy region R(ε, δ) consists of error-probability pairs satisfying PFA + e^εPMD ≥ 1 − δ and e^εPFA + PMD ≥ 1 − δ.The region is represented graphically and is symmetric around PFA + PMD = 1.
Privacy region: The privacy region includes error pairs generated by randomized or soft hypothesis-testing decisions through convexification.A decision rule may accept the null hypothesis with an internal probability depending on the output.
Characterization: A mechanism is (ε, δ)-differentially private if and only if its privacy region is contained in R(ε, δ).This provides a necessary and sufficient condition in the hypothesis-testing representation.
Data processing: If mechanism M dominates M′ through the Markov chain D–X–Y, then R(M′, D1, D2) ⊆ R(M, D1, D2).Post-processing cannot enlarge the privacy region relative to the original mechanism.
Data processing: Conversely, privacy-region inclusion implies a stochastic transformation that further privatizes the output while preserving its conditional marginal distributions.This establishes a mechanism-comparison interpretation for the region inclusion.

3 Composition of Differentially Private Mechanisms

This section characterizes privacy degradation under k-fold adaptive composition, proving an exact tight privacy region and a simpler outer bound that improves prior guarantees. The analysis uses hypothesis testing and extends to heterogeneous mechanisms.

Composition experiment: The composition experiment studies how privacy guarantees degrade when an adversary accesses neighboring databases repeatedly through differentially private mechanisms.The adversary’s view consists of the mechanisms’ outputs and its internal randomness, with independent mechanism randomness across accesses.
Prior guarantees: The standard composition guarantee is (kε, kδ)-differential privacy, while prior work obtained a smaller ε by allowing additional δ slack.The earlier bound is O(kε^2 + kε^2 log(1/˜δ), ε log(ε/˜δ)) in the stated regime and is significantly smaller than kε.
Optimal privacy region: The exact bound is tight because an explicit sequence of mechanisms achieves the same privacy region under composition, even without adaptivity.This establishes a matching worst-case privacy degradation and resolves the previously open optimality question.
Optimal privacy region: Theorem 3.3 exactly characterizes the privacy region under k-fold adaptive composition as the intersection of regions with parameters ((k − 2i)ε, 1 − (1 − δ)^k(1 − δ_i)).The bound applies for i = 0, 1, . . . , ⌊k/2⌋ and is expressed as an intersection over those indices.
Proof strategy and illustrations: The optimality proof interprets differential privacy through false-alarm and missed-detection guarantees in binary hypothesis testing and uses new analysis tools.Figure 2 illustrates degradation as k increases, while Figure 3 compares the privacy guarantees from Theorems 3.1, 3.2, and 3.3 for 30-fold composition.
Simplified and heterogeneous bounds: Theorem 3.4 gives a simpler outer bound that improves prior composition guarantees, especially for large k, while reducing approximate-privacy degradation from kδ + ˜δ to 1 − (1 − δ)^k(1 − ˜δ).The paper also extends the analysis to heterogeneous mechanisms, where the εℓ terms combine through summation.

4 Applications of the Optimal Composition Theorem

The optimal composition theorem yields concrete privacy and utility improvements for noise-adding mechanisms. Under composition, Gaussian, Laplacian, staircase, and geometric mechanisms can attain strong guarantees, with geometric noise exactly achieving the optimal privacy region for counting queries.

Choosing ε0 = ε/(2k log(e + ε/δ)) and δ0 = δ/2k suffices to ensure overall (ε, δ)-differential privacy for k composed mechanisms.
A variance condition improves utility for noise-adding mechanisms when ε = Θ(δ), including improved utility for graph cut queries.
Gaussian noise achieves the same privacy under composition with a log(1/δ) smaller variance when δ = Θ(ε) than the prior sufficient bound.
Laplacian and staircase mechanisms can achieve the same composed privacy level with the same variance as Gaussian mechanisms.
For sensitivity-one counting queries, geometric noise achieves the largest privacy region under k-fold composition universally for every neighboring database pair.

5 Applications of the Operational Interpretation to Private Multi-Party Computation

The paper applies its hypothesis-testing interpretation of differential privacy to secure multi-party computation. It proves that randomized response is universally optimal for accuracy under broad privacy, function, cost, and interaction settings.

Each party randomizes and publishes its own bit, while parties and the central observer separately optimize their decision rules.
The optimality result covers arbitrary functions, heterogeneous privacy constraints, all cost metrics, and both average and worst-case accuracy.
The optimality is simultaneous for every party and the central observer, separating optimal data release from optimal decision making.
Randomized response dominates every other (εi, δi)-differentially private mechanism in the local multi-party setting, including interactive protocols.
Independent private bits are required because dependence could let parties learn about one another without revealing additional information.
Randomized response is optimal because it achieves the largest hypothesis-testing region allowed by the privacy constraints.

6 Proof of Theorem 3.3

The proof establishes exact privacy degradation by constructing a simple mechanism that dominates all (ε, δ)-differentially private mechanisms and analyzing its composition. Converse and achievability together show that the resulting privacy region is exact, including for adaptive composition.

The proposed mechanism dominates every (ε, δ)-differentially private mechanism.
Its outputs depend only on the hypothesis, not on the database or query, while retaining the single-access privacy region R(ε, δ).
The k-fold composition has explicitly characterized product distributions and a privacy region indexed by ε_i = (k − 2i)ε.
The constructed nonadaptive sequence achieves the bound, proving both converse and achievability and therefore exact characterization.
6.2 Converse: The proof uses a simulated composition experiment, Markov-chain factorization, and differential-privacy data processing to bound arbitrary adaptive mechanisms by the proposed sequence.
6.2 Converse: A Bayesian-network argument gives the same conditional-independence relation because the mechanism outputs d-separate the hypothesis from the rest of the network.

7 Proof of Theorem 3.4

The proof derives an outer bound on the privacy region of the composed canonical mechanism by separating pure-privacy and approximate-privacy effects. A tail-bound analysis then yields the stated k-fold differential-privacy guarantee.

The proof computes the privacy region from the joint PMFs of k independent copies of the canonical null and alternative outputs.
The analysis partitions outcomes according to whether either composed PMF is zero, separating the effects of (ε, 0)- and (0, δ)-differential privacy.
The zero-probability region contributes the shift 1 − (1 − δ)^k to the privacy bound.
A Chernoff-type tail-bound argument upper-bounds the remaining likelihood-ratio contribution using a moment-generating-function estimate.
The resulting composition guarantee is (ε̃, 1 − (1 − δ)^k(1 − δ̃))-differential privacy.

8 Proof of Theorem 3.5

This proof extends the preceding outer-bound argument while retaining dependence on the composition-step index. It applies the same tail-bound strategy to obtain the corresponding k-fold privacy guarantee.

The proof follows Theorem 3.4 while explicitly retaining dependence on ℓ, the index of the composition step.
The canonical outputs use ε_ℓ and δ_ℓ in their null and alternative distributions at composition step ℓ.
As before, the proof focuses on an outer bound and uses a Chernoff-type tail argument for the remaining likelihood-ratio term.
Substitution of the selected parameters yields the desired k-fold composition bound.

9 Proofs

The proofs connect differential privacy with hypothesis-testing error regions and establish that post-processing cannot enlarge the privacy region. Randomized decision rules reduce to convex combinations of hard-threshold rules.

If one mechanism’s output can be post-processed through a Markov chain to simulate another, the latter’s privacy region is contained in the former’s.
Differential privacy is operationally equivalent to constraints on false-alarm and missed-detection probabilities for every rejection region.
An arbitrary randomized decision rule is represented by ordered acceptance probabilities over a partition of the output space.
Every such decision rule yields a convex combination of privacy-region points from hard-threshold rules.

A Examples illustrating the strengths of graphical representation of differential privacy

The paper uses a graphical privacy-region representation to establish equivalent privacy guarantees and derive bounds on total variation distance.

A mechanism satisfying (ε, δ)-differential privacy also satisfies every (ε̃, δ̃) guarantee whose privacy region contains the original one.The proof uses the inclusions R(M) ⊆ R(ε, δ) ⊆ R(ε̃, δ̃).
The graphical representation shows that total variation distance cannot exceed the stated privacy-region boundary.
Total variation distance between outputs on neighboring databases is bounded by 1 − 2(1 − δ)/(1 + e^ε).
The same total variation bound can be written as δ + (1 − δ)(e^ε − 1)/(e^ε + 1).The paper obtains this expression by treating a set S as the rejection region in its hypothesis-testing formulation.

B Analysis of the Gaussian mechanism in Theorem 4.3

The Gaussian-mechanism analysis studies the smallest noise variance ensuring (ε, δ)-differential privacy after k-fold composition. It derives an order bound and identifies the exact composition region as optimal for Gaussian mechanisms.

The analysis asks how small Gaussian noise variance can be while preserving (ε, δ)-differential privacy under k-fold composition.It considers neighboring databases whose query answers differ by ∆ in every coordinate.
The composed Gaussian outputs are modeled by product densities centered at 0 and ∆1_k, with common variance σ^2.The privacy analysis uses the log-likelihood ratio Z between these two product distributions.
The proof bounds the moment generating function of the privacy loss variable Z and substitutes a specific λ to obtain a composition guarantee.
σ^2 = O((k∆^2/ε^2) log(e + (ε/δ))) suffices for (ε, δ)-differential privacy under k-fold composition.The sufficient conditions include σ^2 ≥ (4k∆^2/ε^2) log(e + (ε/δ)) and σ^2 ≥ k∆^2/(4ε).
For Gaussian mechanisms, the k-fold composition privacy region is exactly the optimal region described by the paper’s composition theorem.This region is also stated to be the largest possible for (ε, 0)-differentially private mechanisms.

C.1 Cut queries of a graph and variance queries of a matrix

The paper applies its tight composition theorem to improve privacy–utility tradeoffs for graph cut queries and matrix variance queries, reducing the noise required by prior analyses.

Cut queries of a graph: The original Johnson–Lindenstrauss mechanism achieved the best known tradeoff between additive error τ₀ and privacy ε among several state-of-the-art mechanisms.The comparison includes Laplace noise, the Exponential mechanism, Multiplicative Weights, and Iterative Database Construction.
Cut queries of a graph: When ε = Θ(δ), the new cut-query bound is smaller than the prior bound by a square-root logarithmic factor.
Variance queries of a matrix: The same composition improvement is applied to a differentially private covariance mechanism for matrix variance queries.Neighboring matrices differ in one row by Euclidean distance at most one.
Cut queries of a graph: The mechanism sanitizes a graph Laplacian and answers cut queries using the sanitized matrix and the indicator vector of the queried set.Its approximation guarantee uses multiplicative error η and additive error τ.
Cut queries of a graph: Theorem 3.4 improves the Johnson–Lindenstrauss analysis by permitting larger per-row privacy ε₀ and therefore smaller noise w.
Cut queries of a graph: The resulting noise bound is w ≤ 4√(r log(e + 2ε/δ) log(4r/δ))/ε, yielding the improved error bound in (32).The analogous proof applies to matrix variance queries.

D Proof of Theorem 5.1

The proof shows that any differentially private protocol transcript can be simulated from randomized-response outputs. An induction over stochastic transformations establishes the required distributional equality.

Theorem D.1 states that every protocol transcript can be generated through a stochastic transformation of the parties’ randomized-response outputs.
The proof proceeds by induction over transformations that take randomized responses for an initial block of bits and retain the remaining original bits.
The base case uses Bayes’ rule, differential privacy, and a reverse data processing inequality to simulate the transcript from the first randomized response.
The induction step constructs successive stochastic transformations that replace each remaining original bit with its randomized-response output.
Induction yields the final simulation equality and proves Theorem D.1.