The original definition of $\epsilon-$differential privacy is for two databases $D_1$, $D_2$ that differ at most one entry and an randomized algorithm $A$.

We have a bound on the probability ratio $\frac{Pr[A(D_1) \in S]}{Pr[A(D_2) \in S]} \leq e^\epsilon$ where $S$ is subset of range of $A$.

How do we define such thing for two databases that differ more than one entry?


One of the advantages of differential privacy is composition. That is, if $D_1$ and $D_k$ differ on $k$ entries, then $k\cdot\epsilon$ differential privacy is achieved. This is easily shown by writing a series of equations. Specifically, let $D_1$ and $D_k$ differ on $k$ entries, and let $D_i$ be a database that differs from $D_{i-1}$ on one entry (for $i=2,...,k$). Then, $$ \frac{\Pr[A(D_1)\in S]}{\Pr[A(D_k)\in S]} = \frac{\Pr[A(D_1)\in S]}{\Pr[A(D_2)\in S]} \cdot \frac{\Pr[A(D_2)\in S]}{\Pr[A(D_3)\in S]}\cdots \frac{\Pr[A(D_{k-1})\in S]}{\Pr[A(D_k)\in S]} \leq (e^\epsilon)^k = e^{k\cdot\epsilon} $$ where each $$ \frac{\Pr[A(D_{i-1})\in S]}{\Pr[A(D_i)\in S]} \leq e^\epsilon $$ by the assumption of differential privacy for databases that differ on a single entry.

| improve this answer | |
  • 1
    $\begingroup$ One nitpick about this answer: This property is usually called "group privacy" instead of "composition". Composition is when you do this chaining calculation over multiple algorithms, whereas group privacy is more or less the same calculation over multiple entries in the dataset. $\endgroup$ – Thomas Oct 1 '19 at 23:24

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.