# How is it possible to define differential privacy on two databases that differ more than a single entry?

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?

## 1 Answer

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.

• 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. – Thomas Oct 1 '19 at 23:24