Dwork 2006 - Differential Privacy Definition and Basic Examples

Summary

A mechanism is $\epsilon$-differentially private if its output distribution changes by at most a factor $e^{\epsilon }$ when one individual’s data is added, removed or changed. Randomized response and Laplace-noised counts are the two canonical examples: both are $\epsilon$-DP, but the Laplace count has error $O(1/\epsilon )$ while randomized response has error $\Theta (\sqrt{n}/\epsilon )$. Statistical (total-variation) closeness is not a substitute, as Example 3 shows.

Overview

The paper models an interaction between a database access protocol $\mathcal{M}$ run on a static dataset $x$ and a computationally unbounded, probabilistic adversary $\mathcal{A}$. ${\mathrm{View}}_{\mathcal{M},\mathcal{A}}(x)$ is the list of messages exchanged plus the adversary’s internal state and random choices; randomness comes from the coins of $\mathcal{M}$ and $\mathcal{A}$. For non-interactive schemes there is no dependence on $\mathcal{A}$ and one writes $\mathcal{M}(x)$.

Main Content

Data model and neighbours

Dataset, set-difference metric, neighbours (p. 23)

A dataset is a finite multiset over a domain $D$ (typically $\{0,1{\}}^d$ or ${\mathbb{R}}^d$), represented as a histogram vector $x\in {\mathbb{N}}^{|D|}$ whose $i$-th entry counts occurrences of the $i$-th element of $D$. The distance is $d_{△}(x,x^{\prime })=\Vert x-x^{\prime }{\Vert }_1$ (size of the symmetric difference). Datasets are neighbours (adjacent) if $d_{△}(x,x^{\prime })=1$.

Remark 2.1 - Hamming vs set difference (p. 24)

The preliminary version used vectors of known length $n$ and Hamming distance $d_H$. Embed ordered lists as sets $x=\{(1,{\tilde{x}}_1),\dots ,(n,{\tilde{x}}_n)\}\subset [n]\times D$. Two such sets differing in one row have $d_{△}=2$, so an $\epsilon$-DP mechanism under set difference is $2\epsilon$-DP under Hamming: $\mathrm{Pr}[\mathcal{M}(x)\in S]\le e^{2\epsilon }\mathrm{Pr}[\mathcal{M}(x^{\prime })\in S]$. Results extend to Hamming with “only minor changes”, with “subtly different interpretations”.

The definition

Definition 2.1 - $\epsilon$-differential privacy (non-interactive; p. 23)

A randomized function $\mathcal{M}:{\mathbb{N}}^D\times \Omega \to O$ is $\epsilon$-differentially private if for all neighbouring datasets $x,x^{\prime }$ and for all measurable events $S\subseteq O$,

$$\mathrm{Pr}(\mathcal{M}(x)\in S)\le e^{\epsilon }\mathrm{Pr}(\mathcal{M}(x^{\prime })\in S).\text{\hspace{1em}(1)}$$

The probability is over the coin flips of $\mathcal{M}$. $\epsilon$ is a bound on the privacy loss and is “a parameter chosen by policy”.

Consequences the paper states (pp. 24-25):

• Multiplicative, not additive. One can have two distributions at arbitrarily small statistical distance whose ratio $\mathrm{Pr}(\mathcal{M}(x)\in S)/\mathrm{Pr}(\mathcal{M}(x^{\prime })\in S)$ is infinite (a point where one assigns probability zero).
• Worst case over pairs, randomness only in $\mathcal{M}$. Except for constant mechanisms, deterministic mechanisms cannot be differentially private.
• Singleton events suffice in the usual cases: for discrete $O$ it suffices that $\mathrm{Pr}(\mathcal{M}(x)=t)\le e^{\epsilon }\mathrm{Pr}(\mathcal{M}(x^{\prime })=t)$ for all $t$; for continuous $O$ with density $p_x$ it suffices that $p_x(t)\le e^{\epsilon }{p}_{x^{\prime }}(t)$ for all $t$.
• Multiplicative distance. DP says $\mathcal{M}(x)$ and $\mathcal{M}(x^{\prime })$ are close in the metric ${\sup }_S\left|\ln \frac{p(S)}{q(S)}\right|=\inf \{\epsilon :p(S)\le e^{\epsilon }q(S)\text{ and }q(S)\le e^{\epsilon }p(S)\forall S\}$. Write $A{\approx }_{\epsilon }B$ if the distributions of random variables $A,B$ are within multiplicative distance $\epsilon$. The logarithm makes the triangle inequality usable.

Definition 2.3 - $\epsilon$-DP for interactive mechanisms (p. 27)

An interactive mechanism $\mathcal{M}$ is $\epsilon$-differentially private if for all neighbouring $x,x^{\prime }$, all adversaries $\mathcal{A}$, and all measurable sets $S$ of views,

$$\mathrm{Pr}({\mathrm{View}}_{\mathcal{M},\mathcal{A}}(x)\in S)\le e^{\epsilon }\mathrm{Pr}({\mathrm{View}}_{\mathcal{M},\mathcal{A}}(x^{\prime })\in S).\text{\hspace{1em}(2)}$$

Usually one does not need this: designing each round as a non-interactive ${\epsilon }_i$-DP mechanism and using the composition lemma suffices.

Example 1 - randomized response

Example 1 (Warner 1965), pp. 25-26

Setup. $n$ known individuals, each with a secret bit $x_i\in \{0,1\}$ (for example, engages in an embarrassing activity). Neighbours differ in one person’s bit. For $b\in \{0,1\}$ let $R(b)$ be a Bernoulli variable with $\mathrm{Pr}(R(b)=b)=\frac{e^{\epsilon }}{e^{\epsilon }+1}$ and $\mathrm{Pr}(R(b)=1-b)=\frac{1}{e^{\epsilon }+1}$. Mechanism: $\mathcal{M}(x_1,\dots ,x_n)=(R(x_1),\dots ,R(x_n))$.

Privacy. For neighbours differing in entry $i$ and output $y$, $\frac{\mathrm{Pr}(\mathcal{M}(x)=y)}{\mathrm{Pr}(\mathcal{M}(x^{\prime })=y)}=\frac{\mathrm{Pr}(R(x_i)=y_i)}{\mathrm{Pr}(R(x_i^{\prime })=y_i)}\in e^{\pm \epsilon }$, since all other coordinates cancel.

Estimator. $g(y)={\sum }_i\frac{(e^{\epsilon }+1)y_i-1}{e^{\epsilon }-1}$ is unbiased for the number of 1’s, with standard deviation $\Theta (\sqrt{n}/\epsilon )$ as $n\to \infty$, $\epsilon \to 0$. It supports estimating proportions of 1’s in any subset of individuals “with no further privacy loss”.

Derivation of the estimator's variance (derived here)

Let $q=e^{\epsilon }/(e^{\epsilon }+1)$. Then $E[y_i\mid x_i]=q{x}_i+(1-q)(1-x_i)=(1-q)+(2q-1)x_i$ with $2q-1=\frac{e^{\epsilon }-1}{e^{\epsilon }+1}$ and $1-q=\frac{1}{e^{\epsilon }+1}$, so $E\left[\frac{(e^{\epsilon }+1)y_i-1}{e^{\epsilon }-1}\mid x_i\right]=\frac{1+(e^{\epsilon }-1)x_i-1}{e^{\epsilon }-1}=x_i$ (unbiased). Conditional on $x$, $\mathrm{Var}(y_i)=q(1-q)=\frac{e^{\epsilon }}{(e^{\epsilon }+1{)}^2}$, so each term has variance $\frac{(e^{\epsilon }+1{)}^2}{(e^{\epsilon }-1{)}^2}\cdot \frac{e^{\epsilon }}{(e^{\epsilon }+1{)}^2}=\frac{e^{\epsilon }}{(e^{\epsilon }-1{)}^2}\approx \frac{1}{{\epsilon }^2}$ for small $\epsilon$. Summing $n$ independent terms: $\mathrm{sd}=\sqrt{n}{e}^{\epsilon /2}/(e^{\epsilon }-1)\approx \sqrt{n}/\epsilon$.

Example 2 - Laplace noise on a count

Definition 2.2 - Laplace distribution (p. 25)

$\mathrm{Lap}(\lambda )$ has density $h(y)=\frac{1}{2\lambda }\exp (-|y|/\lambda )$, mean $0$ and standard deviation $\sqrt{2}\lambda$. (The later Definition 3.2 in the same paper prints the exponent as $e^{-\lambda |x|}$, a typographical slip for $e^{-|y|/\lambda }$, as the mean/sd and the proofs show.)

Example 2 - noisy count (p. 25)

Setup. $D=\{0,1\}$, $f(x)=x(1)$ is the number of 1’s, using the histogram representation, so neighbours satisfy $\Vert x-x^{\prime }{\Vert }_1=1$. Mechanism. $\mathcal{M}(x)=f(x)+Y$, $Y\sim \mathrm{Lap}(1/\epsilon )$.

Privacy. For any reals $y,y^{\prime }$, $h(y)/h(y^{\prime })\le e^{|y-y^{\prime }|/\lambda }$. Since $f(x),f(x^{\prime })$ differ by at most one, the ratio of densities at $t$ is $\frac{h(t-f(x))}{h(t-f(x^{\prime }))}\le e^{\epsilon |f(x)-f(x^{\prime })|}\le e^{\epsilon }$.

Utility. Noise magnitude is about $1/\epsilon$ independent of $n$, a factor roughly $\sqrt{n}$ smaller than randomized response in Example 1. The same mechanism releases the total count $x(0)+x(1)$.

The paper’s moral: “for a given goal, there may be several differentially private algorithms with the same privacy parameter and different levels of success”. For fixed $\epsilon$ the definition specifies a set of acceptable algorithms.

Why non-negligible leakage, and why the multiplicative measure

In Example 2, to get a reasonable approximation of $f(x)$ one needs $\epsilon$ at least about $1/\Vert x\Vert$ ($\Vert x\Vert$ = number of entries). That is large by cryptographic standards, where leakage should fall faster than any polynomial. But it is necessary: if neighbouring databases induce distributions at distance $\epsilon \ll 1/\Vert x\Vert$, then any two databases of size $\Vert x\Vert$ induce distributions at distance at most $\epsilon \Vert x\Vert$ (triangle inequality along a chain), close to zero, so “no statistic about the database can be usefully approximated”.

Example 3 - why total variation is not enough (p. 26)

Setup. Each entry includes identifying information making it unique (name or SSN). Candidate “sanitization” $\mathcal{M}$: independently output each element of $x$ with probability $\epsilon$ (a subsample).

Statistical difference. If $x,x^{\prime }$ differ in a single position, the statistical difference between $\mathcal{M}(x)$ and $\mathcal{M}(x^{\prime })$ is exactly $\epsilon$ (the probability the one differing element appears), identical otherwise.

Yet it leaks. About an $\epsilon$ fraction of individuals is revealed in full; when $\epsilon \ge 1/\Vert x\Vert$ the expected size of the released set is at least 1.

DP status. Not ${\epsilon }^{\prime }$-DP for any finite ${\epsilon }^{\prime }$: if $x^{\prime }=x\cup \{x_0\}$, the event “output includes $x_0$” has probability $0$ under $x$ and $\epsilon$ under $x^{\prime }$. The authors find unpalatable “a ‘lottery’ philosophy that sacrifices a small number of individuals on every invocation.”

Examples

Numerical check of Examples 1 and 2 (own code; the paper has no tables):

import numpy as np
rng = np.random.default_rng(0)
n, p, eps = 100_000, 0.3, 1.0
x = rng.random(n) < p                      # secret bits
 
# Example 1: eps-randomized response, unbiased estimator of sum(x)
q = np.exp(eps) / (np.exp(eps) + 1)
y = np.where(rng.random(n) < q, x, ~x)
est_rr = (((np.exp(eps) + 1) * y - 1) / (np.exp(eps) - 1)).sum()
sd_rr = np.sqrt(n) * np.exp(eps / 2) / (np.exp(eps) - 1)   # conditional sd, derived above
 
# Example 2: Laplace(1/eps) on the count
est_lap = x.sum() + rng.laplace(0, 1 / eps)
 
print(est_rr, est_lap, x.sum(), "RR sd ~", round(sd_rr), "Laplace sd ~", round(np.sqrt(2) / eps, 2))

With $\epsilon =1$, $n=10^5$ the randomized-response standard deviation is about $\sqrt{n}{e}^{0.5}/(e-1)\approx 303$ people while the Laplace count has sd $\sqrt{2}\approx 1.4$: a factor of about 200 apart, matching the paper’s "$\sqrt{n}$" claim (up to constants). Local randomization needs no trusted curator; that is its price.

Connections

• The trust-model distinction here (curator-held vs randomize-before-collection) is the same as the difference between a clean-room aggregate report and on-device noising in privacy-preserving measurement. Local noise costs $\sqrt{n}$ more error, which matters when a lift study is small. See Conversion Lift Studies on Ad Platforms.
• The ”$\epsilon \gtrsim 1/n$ for any utility” argument is the formal reason tiny cells (small geos, rare conversions) cannot be reported privately and accurately at once; compare Geo-Experiment Design and Power Analysis.

See Also

• Dwork 2006 - Postprocessing, Composition and Group Privacy
• Dwork 2006 - Sensitivity and the Laplace Mechanism
• Dwork Roth 2014 - Differential Privacy Definition and Model of Computation ($(\epsilon ,\delta )$ generalisation and the histogram-based textbook definition)
• Dwork Roth 2014 - Randomized Response