Differential privacy, databases, and add/remove adjacency

Let $U$ be a nonempty set of possible records and let ${\mathbb{N}}_0=\{0,1,2,\dots \}$. A database is a function $D:U\to {\mathbb{N}}_0$ with finite support $\mathrm{supp}(D)=\{u\in U:D(u)\mathrm{\ne }0\}$; $D(u)$ is the number of occurrences of record $u$. Let $\mathcal{D}$ be the set of databases and equip it with the power-set sigma-algebra. For $u\in U$, let ${\mathbf{1}}_{\{u\}}$ be the function that is one at $u$ and zero elsewhere. Two databases $D,D^{\mathrm{\prime }}\in \mathcal{D}$ are neighbors, written $D\sim D^{\mathrm{\prime }}$, when $D^{\mathrm{\prime }}=D+{\mathbf{1}}_{\{u\}}$ or $D=D^{\mathrm{\prime }}+{\mathbf{1}}_{\{u\}}$ for some $u\in U$.

A randomized mechanism with output measurable space $(Y,\mathcal{B})$ is a probability kernel $K$ from $\mathcal{D}$ to $Y$: for each $D\in \mathcal{D}$, $A\mapsto K(D,A)$ is a probability measure on $(Y,\mathcal{B})$, and for each $A\in \mathcal{B}$, $D\mapsto K(D,A)$ is measurable. Given $\epsilon \ge 0$ and $0\le \delta \le 1$, the mechanism is $(\epsilon ,\delta )$-differentially private if, for every ordered neighboring pair $D\sim D^{\mathrm{\prime }}$ and every output event $A\in \mathcal{B}$,

$$K(D,A)\le e^{\epsilon }K(D^{\mathrm{\prime }},A)+\delta \mathrm{.}$$

The mechanism is $\epsilon$-differentially private, or pure $\epsilon$-differentially private, when $\delta =0$. The ordered-pair quantifier includes both directions because $\sim$ is symmetric.

Measurable spaces and sigma-algebras

Probability measures have total mass one

Probability-kernel conditions for randomized mechanisms

Dwork and Roth, The Algorithmic Foundations of Differential Privacy, Definition 2.4, printed pp. 17–18.

Vadhan, The Complexity of Differential Privacy, Definition 1.4, PDF pp. 8–9.