Dwork 2006 - Sensitivity and the Laplace Mechanism

Summary

Define the ${\ell }_1$ sensitivity $S(f)={\sup }_{x,x^{\prime }\text{ neighbours}}\Vert f(x)-f(x^{\prime }){\Vert }_1$. Adding i.i.d. $\mathrm{Lap}(S(f)/\epsilon )$ noise to each coordinate of $f(x)$ is $\epsilon$-DP (Prop. 3.3), and the guarantee extends to adaptively chosen queries when the server refuses to answer once the joint sensitivity of the query sequence exceeds a threshold $T$ (Thm. 3.4). Noise scale depends only on $S(f)/\epsilon$, not on $n$ or the output dimension.

Overview

Sec. 3 presents “the most basic tool for constructing differentially private mechanisms”: formally define sensitivity of functions, prove that Laplace noise with expected magnitude $S(f)/\epsilon$ ensures $\epsilon$-DP, extend to vector-valued and adaptively chosen queries. The paper’s phrase: “this analysis shows how a ‘privacy budget’ $\epsilon$ can be spent by a sequence of queries.”

Main Content

Definition 3.1 - ${\ell }_1$ sensitivity (p. 31)

The ${\ell }_1$ sensitivity of $f:D^{\ast }\to {\mathbb{R}}^d$ is the smallest $S(f)$ such that for all neighbouring $x,x^{\prime }$: $\Vert f(x)-f(x^{\prime }){\Vert }_1\le S(f)$. With neighbours defined by symmetric difference of size one, $S(f)={\sup }_{x,x^{\prime }:d_{△}(x,x^{\prime })=1}\Vert f(x)-f(x^{\prime }){\Vert }_1$. By the triangle inequality sensitivity is a Lipschitz condition: $\frac{\Vert f(x)-f(x^{\prime }){\Vert }_1}{d_{△}(x,x^{\prime })}\le S(f)$ for all $x,x^{\prime }$.

If neighbours are defined via Hamming distance instead, all results “can be easily modified”; one can also define sensitivity for any metric on the output space (Sec. 3.3). Note $S(f)$ “is a quantity inherent in $f$; it is not chosen by policy and is independent of the database” (p. 18).

Example 4 - sums, counts, histograms (pp. 31-32)

Sums. ${\mathrm{SUM}}_v(x)={\sum }_{i=1}^{|x|}v(x_i)$ with $v:D\to {\mathbb{R}}^d$ and $\Vert v(x){\Vert }_1\le \gamma$ for all $x\in D$ has $S({\mathrm{SUM}}_v)\le \gamma$. Count. Taking $v\equiv 1$: $\mathrm{COUNT}(x)=|x|$ has $S(\mathrm{COUNT})=1$. Histogram. Partition $D$ into disjoint regions $B_1,\dots ,B_d$; $\mathrm{HIST}(x)=(|x\cap B_1|,\dots ,|x\cap B_d|)={\sum }_{i}v(x_i)$ with $v(x)$ a one-hot vector of dimension $d$. $\Vert v(x){\Vert }_1=1$ so $S(\mathrm{HIST})=1$: neighbouring databases differ in exactly one count (one bin gains or loses a point).

Definition 3.2 - Laplace distribution, $d$-dimensional (p. 32)

$\mathrm{Lap}(\lambda )$ on $\mathbb{R}$ has density $p(y)=\frac{1}{2\lambda }{e}^{-|y|/\lambda }$, mean $0$, standard deviation $\lambda \sqrt{2}$. $\mathrm{Lap}(\lambda {)}^d$ is a product of $d$ i.i.d. $\mathrm{Lap}(\lambda )$. For $y,y^{\prime }\in {\mathbb{R}}^d$ the densities satisfy

$$\frac{p(y)}{p(y^{\prime })}\le \exp \left(\Vert y-y^{\prime }{\Vert }_1/\lambda \right).\text{\hspace{1em}(4)}$$

(The printed text writes $\lambda$ where it should write $1/\lambda$ in the exponent; the proofs below use the correct form.)

Proposition 3.3 - Laplace mechanism, non-adaptive version (p. 32)

For all $f:D^{\ast }\to {\mathbb{R}}^d$, the mechanism ${\mathcal{M}}_f(x)=f(x)+(Y_1,\dots ,Y_d)$ with $Y_i$ i.i.d. $\mathrm{Lap}(S(f)/\epsilon )$ is $\epsilon$-differentially private.

Proof (p. 32)

Let $p[\mathcal{M}(x)=z]$ be the density at $z$. For neighbours $x,x^{\prime }$, Eq. (4) with $\lambda =S(f)/\epsilon$ gives

$$\frac{p[{\mathcal{M}}_f(x)=z]}{p[{\mathcal{M}}_f(x^{\prime })=z]}\le \exp \left(\frac{\epsilon \Vert f(x)-f(x^{\prime }){\Vert }_1}{S_{L1}(f)}\right)\le \exp (\epsilon ).\text{\hspace{1em}(5)}$$

For measurable $Z\subseteq {\mathbb{R}}^d$, $\mathrm{Pr}[{\mathcal{M}}_f(x)\in Z]={\int }_{z\in Z}p[{\mathcal{M}}_f(x)=z]dz\le e^{\epsilon }{\int }_{z\in Z}p[{\mathcal{M}}_f(x^{\prime })=z]dz=e^{\epsilon }\mathrm{Pr}[{\mathcal{M}}_f(x^{\prime })\in Z]$.

Adaptivity

Proposition 3.3 is a special case of a more general, possibly adaptive process. An adaptive querying strategy $\mathcal{A}$ issues $k$ queries $f_i:{\mathbb{N}}^{|D|}\to \mathbb{R}$, where $f_i$ is determined by earlier answers $a_1,\dots ,a_{i-1}$ and the analyst’s coins $r$. The view is $v=(r,a_1,\dots ,a_k)$; for a view $v$ define $f^v:{\mathbb{N}}^D\to {\mathbb{R}}^k$ with $i$-th coordinate $f_i^v$. The server either (a) answers $a_i=f_i^v(x)+\mathrm{Lap}(\lambda )$ for fixed $\lambda$, or (b) refuses ($a_i=\perp$). It refuses once the joint sensitivity $S(f_1^v,\dots ,f_i^v)$ exceeds a threshold $T$. This decision depends only on the queries, “independent of the data set”, so it is “not disclosive, since it can be computed by the user submitting the queries”.

Theorem 3.4 - Laplace mechanism, adaptive version (p. 33)

Consider an arbitrary adaptive query strategy with query function $f^v(x):{\mathbb{N}}^{|D|}\to {\mathbb{R}}^k$ parameterised by a view $v=(r,a_1,\dots ,a_k)$. The mechanism that answers $a_i=f_i^v(x)+\mathrm{Lap}(T/\epsilon )$ as long as $S(f^v)\le T$ is $\epsilon$-differentially private.

Proof (p. 33)

For neighbours $x,x^{\prime }$, the chain rule gives

$$\frac{p[(r,\mathcal{M}(x))=(r,a_1,\dots ,a_k)]}{p[(r,\mathcal{M}(x^{\prime }))=(r,a_1,\dots ,a_k)]}=\prod _{i\le k}\frac{p[\mathcal{M}(x{)}_i=a_i\mid r,a_1,\dots ,a_{i-1}]}{p[\mathcal{M}(x^{\prime }{)}_i=a_i\mid r,a_1,\dots ,a_{i-1}]}.$$

Fixing $r$ and the first $i-1$ answers fixes the values $f_i^v(x),f_i^v(x^{\prime })$, so each conditional is either $\mathrm{Lap}(\lambda )$ with $\lambda =T/\epsilon$ centred at $f_i^v(\cdot )$, or the constant $\perp$. Hence the product is at most ${\prod }_i\exp (|f_i^v(x)-f_i^v(x^{\prime })|/\lambda )=\exp (\Vert f^v(x)-f^v(x^{\prime }){\Vert }_1/\lambda )\le \exp (S_{L1}(f^v)/\lambda )\le e^{\epsilon }$.

This is a “more nuanced version of composition” than Lemma 2.6: budgeting on the joint sensitivity rather than summing ${\epsilon }_i$. For $k$ counting queries the joint sensitivity can be as large as $k$ (each person may affect every count), recovering the $\epsilon /k$-per-query accounting; for disjoint (histogram) queries it stays $1$.

Examples

Accuracy (derived, not stated in this paper). Since $\mathrm{Pr}[|Y|\ge t\lambda ]=e^{-t}$ for $Y\sim \mathrm{Lap}(\lambda )$, a single released coordinate is within $\frac{S(f)}{\epsilon }\ln (1/\beta )$ of the truth with probability $1-\beta$; a union bound over $d$ coordinates gives $\Vert f(x)-{\mathcal{M}}_f(x){\Vert }_{\infty }\le \frac{S(f)}{\epsilon }\ln (d/\beta )$ (the textbook statement, Dwork Roth 2014 - Laplace Mechanism).

Empirical check of the density-ratio bound (own code).

import numpy as np
rng = np.random.default_rng(0)
eps, S = 0.5, 1.0                       # count query, sensitivity 1
lam = S / eps
lap_pdf = lambda y, mu: np.exp(-np.abs(y - mu) / lam) / (2 * lam)
f_x, f_xp = 100.0, 101.0                # neighbouring databases: counts differ by 1
z = np.linspace(80, 120, 4001)
ratio = lap_pdf(z, f_x) / lap_pdf(z, f_xp)
print(ratio.max(), np.exp(eps))         # max density ratio equals e^eps (attained far in the tail)

The maximum ratio is $e^{\epsilon }$ (attained for $z\le f(x)$), so the bound in Eq. (5) is tight for counts.

Connections

• Marketing measurement. To release $K$ campaign-level conversion counts with each user contributing to at most one campaign (a histogram), noise scale is $1/\epsilon$ per cell regardless of $K$. If a user can convert in several campaigns, sensitivity is the maximum number of cells touched (or clipped contribution), and noise scale grows linearly in that. This is why privacy-preserving measurement APIs cap per-user contributions: the cap is the sensitivity bound.
• Known noise law enables debiasing and likelihood modelling: ${\tilde{y}}_k=y_k+\mathrm{Lap}(S/\epsilon )$ is an additive measurement-error model with a known error distribution, easy to place inside a Bayesian model (Bayesian Estimation and Priors for MMM).

See Also

• Dwork 2006 - Low-Sensitivity Functions and Applications
• Dwork 2006 - Sensitivity in General Metric Spaces
• Dwork Roth 2014 - Laplace Mechanism
• Wasserman Zhou 2010 - Setup, Data Release Mechanisms and Differential Privacy (Lemma 2.6 part 3 restates this proposition)