Differential privacy mechanisms and composition — Examples

If $D^{\mathrm{\prime }}$ is obtained from $D$ by adding one occurrence of $u$, then $f(D^{\mathrm{\prime }})-f(D)=P(u)\in \{0,1\}$; removing one occurrence gives the negative of this change. Thus every adjacent difference has absolute value at most $1$. The empty database and the database containing only $u_0$ are neighbors and their counts differ by $1$, so the maximum is attained and ${\mathrm{\Delta }}_{1}f=1$.

By [F3], the scalar release uses scale ${\mathrm{\Delta }}_{1}f\mathrm{/}\epsilon =1\mathrm{/}\epsilon$ and is exactly the stated noisy count. This query has finite dimension one and sensitivity one, so [F4] proves its $(\epsilon ,0)$ guarantee.

For the first utility, every score is independent of $D$, so every adjacent-pair difference is zero and ${\mathrm{\Delta }}_u=0$ by [F2]. This fails the positive-sensitivity hypothesis in [F3], so the algorithm is not defined for that utility.

For the second utility, adding or removing a record other than $u_{\ast }$ leaves $s(D)$ unchanged; adding or removing $u_{\ast }$ changes it by at most one. The empty database and the database with one occurrence of $u_{\ast }$ are neighbors and change $s$ from zero to one. The score at $a$ is constant, and the score at $b$ changes by exactly the change in $s$, so the maximum adjacent score difference is attained and equals ${\mathrm{\Delta }}_u=1$.

With ${\mathrm{\Delta }}_u=1$, the weights are $w_D(a)=e^{\epsilon \mathrm{/}2}$ and $w_D(b)=e^{\epsilon (1-s(D))\mathrm{/}2}$. Normalizing their sum gives the displayed selection probability. Since the range is finite nonempty and the sensitivity is positive, [F4] proves the privacy claim.

Adding or removing a record $u$ changes $f(D)$ by $P(u)\in \{0,1\}$ in absolute value. Every neighboring difference is at most one, and the empty database versus the singleton database containing $u_0$ attains one. Thus ${\mathrm{\Delta }}_{1}f=1$ by [F1] and [F2], and [A1, F3] gives the corresponding Laplace law, so the noisy count has noise scale $1\mathrm{/}\epsilon$ and is $(\epsilon ,0)$-DP.

Define $\varphi (x)={\mathbf{1}}_{\{x\ge c\}}$. Its preimages of $\{1\}$ and $\{0\}$ are $[c,+\mathrm{\infty })$ and $(-\mathrm{\infty },c)$, respectively, so [F4] makes $\varphi$ Borel measurable. The deterministic kernel $L(x,B)={\mathbf{1}}_B(\varphi (x))$ on $\{0,1\}$ is a probability kernel and is independent of the database. Applying [F5] to the noisy-count release proves that the threshold output retains the same $(\epsilon ,0)$ guarantee.

List the client’s 100 occurrences as $u_1,\dots ,u_{100}$, with repetitions allowed. For $j=0,\dots ,100$, let $D_j=D_0+{\sum }_{\mathrm{\ell }=1}^j{\mathbf{1}}_{\{u_{\mathrm{\ell }}\}}$. Then $D_{j-1}$ and $D_j$ differ by adding one occurrence, so [F1] makes each consecutive pair neighbors.

The count-function difference between $D_0$ and $D_{100}$ has total absolute count ${\sum }_{u\in U}\mathrm{\mid }{D}_{100}(u)-D_0(u)\mathrm{\mid }=100$, counting repeated contributions with multiplicity. A single add/remove neighbor pair has this total equal to $1$ by [F1]. Hence the full contribution is not a record-level neighboring step. Treating it as one step changes the adjacency relation, and [F2] says that any claimed client-level guarantee needs that relation and a proof under it.