differential privacy

Differential privacy is the study of how to make mechanisms which act on databases (i.e., make queries) secure from leaking information.

Intuitively, a differentially private mechanism should be one which is not excessively reactive to small changes in the dataset. Let $\mathcal{D}$ be the set of all databases, and consider a function $g$ which acts on $\mathcal{D}$. (Think of a database as just some big data table where, e.g., each row corresponds to a different user.) For instance, given a database $x\in \mathcal{D}$, $g(x)$ might be the size of $x$, or the total amount user deposits in $x$, or it might ask for the number of users with some property (a “counting query”). We want to add noise to $g$ in such a way that, regardless of how it queries the database, it cannot back out sensitive information.

Formally, we call a (randomized) mechanism $f$ which acts on databases $(ϵ,\delta )$-differentially private if, for all outputs $A\subset \text{Range}(f)$ and all databases $x$ and $z$ such that $x$ and $z$ differ by one row,

$\mathbb{P}(f(x)\in A)\le e^{ϵ}\mathbb{P}(f(z)\in A)+\delta .$

If $\delta =0$, we call $f$ $ϵ$-differentially private.

The intuition behind the definition is easier to grasp if we negate it. If $f$ is not differentially private, this means there exists some $A$ such that $\mathbb{P}(f(x)\in A)\gg \mathbb{P}(f(z)\in A)$. That is, swapping just a single row of $x$ to $z$ changed the output distribution considerably, meaning that $f$ is sensitive to the data. If $f$ is differentiably private then, roughly speaking, small changes in the input result in small changes in the output.

A popular to write $ϵ$-differential privacy is as the likelihood ratio

$$\underset{A\in \text{image}(f)}{\sup }\underset{x_1,x_2:x_1\in {\delta }_1(x_2)}{\sup }\frac{\mathbb{P}(f(x_1)\in A)}{\mathbb{P}(f(x_2)\in A)}\le e^{ϵ},$$

where ${\delta }_1(x)$ is the set of databases which different by at most 1 row from $x$.

Example: The Laplace Mechanism

Consider a deterministic function $g:\mathcal{D}\to {\mathbb{R}}^k$. Define

$$\Delta =\underset{x,y:x\in {\delta }_1(x)}{\sup }||g(x)-g(y)|{|}_1=\underset{x,y:x\in {\delta }_1(y)}{\sup }\sum _{i=1}^k|g(x{)}_i-g(y{)}_i|.$$

$\Delta$ is often called the ${\ell }_1$-sensitivity of $g$. The Laplace mechanism is defined as

$$f(x)=g(x)+(Y_1,\dots ,Y_k),$$

where $Y_1,\dots ,,Y_k\sim \text{Lap}(0,\Delta /ϵ)$ independently. Recall that the Laplacian distribution $\text{Lap}(a,b)$ has pdf $p(x)=(2b{)}^{-1}\exp (-|x-a|/b)$. To show that this mechanism is differentially private, we show that

$${\int }_A\mathbb{P}(f(x)=z)dz\le e^{ϵ}{\int }_A\mathbb{P}(f(y)=z)dz,$$

for all $x\in {\delta }_1(y)$. To see this, it suffices to show that for all $z\in A$, $\mathbb{P}(f(z)=z)\le e^{ϵ}\mathbb{P}(f(y)=z$) and then to integrate over $A$. Note that,

$$\begin{array}{rl}\mathbb{P}(f(x)=z)& =\prod _{i=1}^k\mathbb{P}(M(x{)}_i=z_i)=\prod _{i=1}^k\mathbb{P}(Y_i=z_i-g(x{)}_i)\\ & =\prod _{i=1}^k\frac{ϵ}{\Delta }\exp (-\frac{ϵ}{\Delta }|z_i-g(x{)}_i|).\end{array}$$

Therefore, by the reverse triangle inequality,

$$\begin{array}{rl}\frac{\mathbb{P}(f(x)=z)}{\mathbb{P}(f(y)=z)}& =\prod _{i=1}^k\exp (\frac{ϵ}{\Delta }(|z_i-g(y{)}_i|-|z_i-g(x{)}_i|))\\ & \le \prod _{i=1}^k\exp (\frac{ϵ}{\Delta }(|g(y{)}_i-g(x{)}_i|))\\ & =\exp (\frac{ϵ}{\Delta }\sum _{i=1}^k|g(y{)}_i-g(x{)}_i|)\le \exp (ϵ).\end{array}$$

Composition

One immediate question is how differentially private mechanisms behave under composition. For instance, can we employ multiple differentially private algorithms in tandem and retain differential privacy? Sort of.

Suppose $f_1,f_2$ are $({ϵ}_1,{\delta }_1)$, $({ϵ}_2,{\delta }_2)$ differentially private, respectively. Considering concatenating the output so that, given a database $x$, we construct a new map $g$ such that $g(x)=(f_1(x),f_2(x))$, where we run $f_1$ and $f_2$ independently of one another. Will $g$ be differentially private?

It turns out that $g$ will be $({ϵ}_1+{ϵ}_2,{\delta }_1+{\delta }_2)$ differentially private. You’ll often see this result referred to as “the epsilons and deltas add up.” Unfortunately, when people cite this result, they typically cite Theorem 1 of this paper, which has an incorrect proof. There is a corrected proof in the book by Dwork and Roth, but I think it’s more complicated than necessary. Here’s a simpler proof.

Note the range of $g$ is the product space $\text{range}(f_1)\times \text{range}(f_2)$. Since we run $f_1$ and $f_2$ independently, we have, for any $A\times B\in range(g)$ and any neighboring databases $x$ and $z$,

$$\begin{array}{rl}\mathbb{P}(g(x)\in A\times B)& =\mathbb{P}((f_1(x),f_2(x))\in A\times B)\\ & =\mathbb{P}(f_1(x)\in A)\mathbb{P}(f_2(x)\in B)\\ & \le \min \{e^{{ϵ}_1}\mathbb{P}(f_1(z)\in A+{\delta }_1,1\}\mathbb{P}(f_2(x)\in B)\\ & \le (\min \{e^{{ϵ}_1}\mathbb{P}(f_1(z)\in A),1\}+{\delta }_1)\mathbb{P}(f_2(x)\in B)\\ & \le \min \{e^{{ϵ}_1}\mathbb{P}(f_1(z)\in A),1\}\mathbb{P}(f_2(x)\in B)+{\delta }_1\\ & \le \min \{e^{{ϵ}_1}\mathbb{P}(f_1(z)\in A),1\}(e^{{ϵ}_2}\mathbb{P}(f_2(z)\in B)+{\delta }_2)+{\delta }_1\\ & \le \min \{e^{{ϵ}_1}\mathbb{P}(f_1(z)\in A),1\}(e^{{ϵ}_2}\mathbb{P}(f_2(z)\in B)+{\delta }_2+{\delta }_1\\ & \le e^{{ϵ}_1+{ϵ}_2}\mathbb{P}(f_1(z)\in A)\mathbb{P}(f_2(z)\in B)+{\delta }_1+{\delta }_2\\ & =e^{{ϵ}_1+{ϵ}_2}\mathbb{P}(g(z)\in A\times B)+{\delta }_1+{\delta }_2.\end{array}$$

Here we’ve just used basic facts of the min function and recognized that probabilities can be at most 1. Of course, we can extend this result by induction and conclude that given finitely many mechanisms $\{f_i\}$ where $f_i$ is $({ϵ}_i,{\delta }_i)$-differentially private, then the mechanism $g:\mathcal{X}\to {⨂}_i\text{range}(f_i)$ given by $g:x\mapsto {\otimes }_i{f}_i(x)$ is $({\sum }_i{ϵ}_i,{\sum }_i{\delta }_i)$ differentially private.

We can also consider deterministic composition, and demonstrate that it does not affect the privacy guarantees. Indeed, suppose $f:\mathcal{D}\to U$ is $(ϵ,\delta )$ private and let $g:U\to V$ be deterministic and invertible. Then for any $W\subset V$,

$$\begin{array}{rl}\mathbb{P}(f\circ g(x)\in W)& =\mathbb{P}(f(x)\in g^{-1}(W))\\ & \le e^{ϵ}\mathbb{P}(f(y)\in g^{-1}(W))=\mathbb{P}(f\circ g(y)\in W),\end{array}$$

so $f\circ g$ is $(ϵ,\delta )$ private.

DP in practice

Differential privacy is now used in a lot of applications. Apple started using it in macOS Sierra and has since expanded its application to Safari. Google used differential privacy when gathering insights from searches related to Covid-19, and for their Covid-19 mobility reports. Other examples include LinkedIn, Microsoft and Uber.