Three composition theorems for differential privacy

This is a brief post, bringing together three composition theorems for differential privacy.

The composition of an ε1-differentially private algorithm and an ε2-differentially private algorithm is an (ε1+ε2)-differentially private algorithm.

The composition of an (ε1, δ1)-differentially private algorithm and an (ε2, δ2)-differentially private algorithm is an (ε1+ε2, δ1+δ2)-differentially private algorithm.

The composition of an (α, ε1)-Rényi differentially private algorithm and an (α, ε2)-Rényi differentially private algorithm is an (α, ε1+ε2)-Rényi differentially private algorithm.

The three composition rules can be summarized briefly as follows: ε1 ∘ ε2 → (ε1 + ε2) (ε1, δ1) ∘ (ε2, δ2) → (ε1+ε2, δ1+δ2) (α, ε1) ∘ (α, ε2) → (α, ε1+ε2) What is the significance of these composition theorems? In short, ε-differential privacy and Rényi differential privacy compose as one would hope, but (ε, δ)-differential privacy does not.

The first form of differential privacy proposed was ε-differential privacy.

It is relatively easy to interpret, composes nicely, but can be too rigid.

If you have Gaussian noise, for example, you are lead naturally to (ε, δ)-differential privacy.

The δ term is hard to interpret.

Roughly speaking you could think  it as the probability that ε-differential privacy fails to hold.

Unfortunately with (ε, δ)-differential privacy the epsilons add and so do the deltas.

We would prefer that δ didn’t grow with composition.

Rényi differential privacy is a generalization of ε-differential privacy that uses a family of information measures indexed by α to measure the impact of a single row being or not being in a database.

The case of α = ∞ corresponds to ε-differential privacy, but finite values of α tend to be less pessimistic.

The nice thing about the composition theorem for Rényi differential privacy is that the α parameter doesn’t change, unlike the δ parameter in (ε, δ)-differential privacy.


Leave a Reply