# Composition of privacy mechanisms

This is the third post of my data privacy series. Please refer to the first post for the definition of differential privacy and the second post for privacy mechanism.

## Robustness of differential privacy versus processing

If a mechanism is -differential private to begin with, then further operation on is still -differential private.

##### Proof:

Let’s assume the operation applying on the output of is stochastic as deterministic operation is just a special case. Then, we have

(1) where and are “adjacent” data sets and is due to the fact that is -differential private. Therefore, is -differential private.

Actually, the above property should be apparent from the beginning. Because if this is not satisfied, the definition of privacy is meaningless since the “private” information could disclose unauthorized information simply through some malicious processing.

On the other hand, if multiple mechanisms are sequentially explored, we expect that the privacy of the overall mechanism (as a sequential combination of the multiple access) should reduce. We have this very simple lemma as follows.

### Lemma (Sequential Composition):

If we have two mechanisms and are – and -differential private, respectively, the overall mechanism is -differential private provided that the two mechanisms are independent.

##### Proof:

(2) where and are “adjacent” data sets.

One can of course generalize the above lemma to combination of many mechanisms by applying it repeatedly.

We can also compose multiple mechanisms in parallel where each member mechanism can only access a disjoint portion of the data set. Then, we have the following lemma.

### Lemma (Parallel Composition):

If we have two mechanisms and applying on disjoint subsets of a data set and and are -differential private, then the overall mechanism is -differential private provided that the member mechanisms are independent.

##### Proof:

Let and are “adjacent” data sets. Since they are adjacent, we cannot have both and . Without loss of generality, assume and . Then,

(3) Again, the parallel composition lemma can obviously be generalized to the case with more than two member mechanisms.

### Example 1 (Disclosing gender population sizes of a group):

Consider that we have a data set containing only the gender attribute and we disclose the population sizes of each gender. To ensure the data set is differentially private, one can add laplacian noise to each population size before disclosing. Let and denote the mechanism of outputing the population for the males and females, respectively. If each mechanism is -differential private, the combined mechanism is also -differential private. Note that we have parallel composition here since the gender populations are disjoint.

### Example 2 (Disclosing disease population sizes of a group):

Consider a similar setting as the previous example but we try to disclose the population sizes of a number of diseases, e.g., AIDS, SARS, lung cancer, etc. Again, we add laplacian noise to each population size before disclosing such that each disclosing mechanism is -differentially private. Let say we consider different diseases here and we will disclose the population size for each of them. The overall mechanism in this case will be -differentially private instead of -differentially private. Note that we have sequential composition here rather than parallel composition since the diseases populations are generally not disjoint (e.g., one can have both AIDS and lung cancer).