4
$\begingroup$

I know that if there are $n$ functions $M_1, M_2, \cdots, M_n$ computed on disjoint subsets of the private database whose privacy guarantees are $\epsilon_1, \cdots ,\epsilon_n$ differential privacy, respectively, then any function $g$ of them: $g(M_1, \dots,M_n)$ is $$(\max_i \epsilon_i)$$differentially private.

This is known as the Parallel Composition Theorem.

My question is: does this Parellel Composition Theorem extend to $(\epsilon, \delta)$ differential privacy? In other words, is the following statement true?:

If there are $n$ functions $M_1, M_2, \cdots, M_n$ computed on disjoint subsets of the private database whose privacy guarantees are $(\epsilon_1, \delta_1), \cdots ,(\epsilon_n, \delta_n)$ differential privacy, respectively, then any function $g$ of them: $g(M_1, \dots,M_n)$ is $$(\max_i \epsilon_i, \max_i \delta_i)$$differentially private.

If this statement is NOT true, then what bounds are there are on the privacy of the composition function $g$.

$\endgroup$
1
$\begingroup$

Your conjecture seems correct. If the sets are disjoint then the mapping $\bar{M} = (M_1,\dots,M_n)$ is $(\max(\epsilon_i),\max(\delta_i))$-DP. Note that for every database $D$ and any $x$, $\bar{M}(D)$ differs from $\bar{M}(D\setminus {x})$ in only one coordinate by the disjoint assumption, w.l.o.g., they differ in the $j$'th coordinate. Therefore, the difference between the density functions of $\bar{M}(D)$ and $\bar{M}(D\setminus {x})$ is the same as the difference between $M_j(D)$ and $M_j(D\setminus {x})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.