Dwork 2006 - Postprocessing, Composition and Group Privacy

Summary

Three structural properties of $\epsilon$-DP: anything computed from a private output (without more access to the data) is still $\epsilon$-DP; privacy losses add under (adaptive) composition up to a budget; and $(1,\epsilon /k)$-DP implies $(k,\epsilon )$-DP for groups of size $k$. Section 2.2 collects interpretations (immunity to auxiliary information, hypothesis-testing, game-theoretic, utility) and variants such as $(\epsilon ,\delta )$-DP.

Overview

These properties are what make DP programmable: complex analyses are built from private primitives. The paper notes (Sec. 2.2) that postprocessing and composition “did not appear in the initial version, although they were known at the time and have since become folklore”. The notation is for non-interactive mechanisms, but “the discussion applies equally well to the interactive case”.

Main Content

Immunity to auxiliary information

Differential privacy “makes no reference to an input distribution, and it makes sense regardless of what other information the adversary has - or will have in the future - about the data set.”

Postprocessing

Proposition 2.4 - Closure under postprocessing (p. 27)

Let $g$ be a randomized function. If $\mathcal{M}$ is an $\epsilon$-differentially private mechanism, then ${\mathcal{M}}^{\prime }=g\circ \mathcal{M}$ is $\epsilon$-differentially private.

Proof (p. 27)

Fix an event $S$ in the output space of $g$ and neighbouring $x,x^{\prime }$. Write $g(z)=\tilde{g}(z;R)$ with $\tilde{g}$ deterministic and $R$ the randomness of $g$. Then $\mathrm{Pr}(g(\mathcal{M}(x))\in S)=\mathrm{Pr}((\mathcal{M}(x),R)\in {\tilde{g}}^{-1}(S))$. For each value $r$ of $R$, let $S_r=\{s:(s,r)\in {\tilde{g}}^{-1}(S)\}$. By DP of $\mathcal{M}$, $\mathrm{Pr}(\mathcal{M}(x)\in S_r)\le e^{\epsilon }\mathrm{Pr}(\mathcal{M}(x^{\prime })\in S_r)$, hence $\mathrm{Pr}(\tilde{g}(\mathcal{M}(x),R)\in S\mid R=r)\le e^{\epsilon }\mathrm{Pr}(\tilde{g}(\mathcal{M}(x^{\prime }),R)\in S\mid R=r)$. Average over $R$ (independent of the data) to conclude.

Composition

Lemma 2.5 - Simple composition (p. 28)

Let ${\mathcal{M}}_1,\dots ,{\mathcal{M}}_k$ be a fixed sequence of mechanisms, ${\mathcal{M}}_i$ being ${\epsilon }_i$-DP. Their joint output $\mathcal{M}(x)=({\mathcal{M}}_1(x),\dots ,{\mathcal{M}}_k(x))$ is $\epsilon$-DP for $\epsilon ={\sum }_{i=1}^k{\epsilon }_i$. (Independent randomness per mechanism.)

The paper remarks that this holds even when later mechanisms are chosen adaptively. The formal adaptive model: at round $i=1,\dots ,k$ ($k$ finite but not fixed in advance) the analyst specifies a positive number ${\epsilon }_i$ and an ${\epsilon }_i$-DP mechanism ${\mathcal{M}}_i$; the curator returns $a_i\leftarrow {\mathcal{M}}_i(x)$. The transcript is the sequence of triples $({\epsilon }_i,{\mathcal{M}}_i,a_i)$.

Lemma 2.6 - Adaptive composition with a budget (p. 28)

Suppose the curator $\mathcal{M}$ stops answering in the first round $j$ where ${\sum }_{i=1}^j{\epsilon }_i>\epsilon$, so that ${\sum }_i{\epsilon }_i\le \epsilon$ for all answered rounds. Then $\mathcal{M}$ is $\epsilon$-differentially private.

Proof (pp. 28-29; $k=2$, discrete $O$)

Fix neighbours $x,x^{\prime }$ and the analyst’s coins (or take a deterministic analyst). Let ${\mathcal{M}}_1$ be the first mechanism chosen. The second depends on the first output $a$: call it ${\mathcal{M}}_2^{(a)}$ with privacy loss ${\epsilon }_2^{(a)}$. For an event $S\subseteq O\times O$ let $S_a=\{s:(a,s)\in S\}$. Then

$$\mathrm{Pr}(\mathcal{M}(x)\in S)=\sum _{a\in O}\mathrm{Pr}({\mathcal{M}}_1(x)=a)\mathrm{Pr}({\mathcal{M}}_2^{(a)}(x)\in S_a).$$

DP of ${\mathcal{M}}_1$ and of each ${\mathcal{M}}_2^{(a)}$ bounds each factor by $e^{{\epsilon }_1}$ and $e^{{\epsilon }_2^{(a)}}$ times the corresponding factor at $x^{\prime }$. Since ${\epsilon }_1+{\epsilon }_2^{(a)}\le \epsilon$ for all $a$ (budget rule), $\mathrm{Pr}(\mathcal{M}(x)\in S)\le e^{\epsilon }\mathrm{Pr}(\mathcal{M}(x^{\prime })\in S)$. Induction extends to all finite $k$. The decision to stop is not disclosive, since it depends only on the ${\epsilon }_i$ values, which the analyst chose.

Two consequences stated in the paper: (i) DP algorithms can be built modularly (an interactive protocol is DP if each round is; later rounds may depend on earlier outputs); (ii) running DP mechanisms on different datasets still composes for individuals appearing in several, e.g. two hospitals with overlapping patients running $\epsilon$-DP algorithms produce a joint output that is $2\epsilon$-DP. “Many natural approaches to defining privacy do not yield composable definitions.”

Group privacy

Definition 2.7 - $(k,\epsilon )$-differential privacy (p. 29)

$\mathcal{M}$ is $(k,\epsilon )$-DP if for all pairs $x,x^{\prime }$ with $d_{△}(x,x^{\prime })\le k$, all adversaries and all events $S$: $\mathrm{Pr}(\mathcal{M}(x)\in S)\le e^{\epsilon }\mathrm{Pr}(\mathcal{M}(x^{\prime })\in S)$. One says “$\epsilon$-DP for groups of size $k$“.

Lemma 2.8 - Group privacy (p. 29)

Every $(1,\epsilon /k)$-DP mechanism is also $(k,\epsilon )$-DP.

Proof (p. 29)

Take a chain of at most $k$ databases connecting $x$ to $x^{\prime }$, changing one entry at a time. The probability of any event changes by a factor $\exp (\pm \epsilon /k)$ per step, so $\frac{\mathrm{Pr}(\mathcal{M}(x)\in S)}{\mathrm{Pr}(\mathcal{M}(x^{\prime })\in S)}\in \exp (\pm \epsilon /k{)}^k=\exp (\pm \epsilon )$.

Interpretations and variants (Sec. 2.2, pp. 29-31)

• History. Originally called indistinguishability; “differential privacy” was suggested by Michael Schroeder and first used in Dwork (2006). Failures to compose in other approaches: Ganta et al. (2008). Stronger composition for relaxations: Dwork-Rothblum-Vadhan (2010), Dwork-Rothblum (2016), Bun-Steinke (2016).
• Semantic-privacy / prior-vs-posterior. The paper’s definition of semantic privacy bounds a Bayesian adversary’s posterior relative to its prior under assumptions on the prior’s form; such assumptions are known to be necessary (Dwork 2006; Dwork-Naor 2010; Kifer-Machanavajjhala 2011).
• Game-theoretic (McSherry-Talwar 2007). If individual $i$ has nonnegative utility $u_i:O\to {\mathbb{R}}_{\ge 0}$ over outcomes, then for neighbours differing in $i$‘s data: $E[u_i(\mathcal{M}(x))]\le e^{\epsilon }E[u_i(\mathcal{M}(x^{\prime }))]$ and $\ge e^{-\epsilon }E[u_i(\mathcal{M}(x^{\prime }))]$, so there is little incentive to misreport.
• Hypothesis-testing (Wasserman-Zhou 2010). Fix an $\epsilon$-DP mechanism, an i.i.d. data distribution, an index $i$ and disjoint sets $S,T$ of possible values of $x_i$. Any test of $H_1:x_i\in S$ versus $x_i\in T$ based on $\mathcal{M}(x)$ and full knowledge of the product distribution and mechanism satisfies $$1-\beta \le e^{\epsilon }\alpha ,\text{\hspace{1em}(3)}$$ with $\alpha$ the significance level and $1-\beta$ the power. “The test rejects the hypothesis with approximately the same probability regardless of whether the hypothesis is true.” Proved in Wasserman Zhou 2010 - Differential Privacy as a Hypothesis-Testing Constraint.
• Variants. $(\epsilon ,\delta )$-DP (first stated in Dwork et al. 2006a) adds $+\delta$ to inequality (1); when $\delta \ll 1/n$ it has semantics similar to $\epsilon$-DP (Kasiviswanathan-Smith 2008). Other variants incorporate graphs, dependencies among records, adversarial uncertainty, computation, and better composition.

Examples

Two hospitals (p. 28). Hospital 1 runs $\epsilon$-DP ${\mathcal{M}}_1$ on its patients, hospital 2 runs $\epsilon$-DP ${\mathcal{M}}_2$ on its own. View both as operating on parts of one combined dataset; a patient in both is protected at level $2\epsilon$ by Lemma 2.5.

Group of size 3. If a household of 3 shares a survey and each query is $(1,\epsilon /3)$-DP, Lemma 2.8 gives $(3,\epsilon )$: the household as a whole is protected at level $\epsilon$. Equivalently an $\epsilon$-DP mechanism protects a group of $k$ only at $k\epsilon$.

# Budgeted adaptive curator (Lemma 2.6): refuse once total epsilon would exceed budget
import numpy as np
class Curator:
    def __init__(self, data, budget, rng=None):
        self.x, self.budget, self.spent = np.asarray(data), budget, 0.0
        self.rng = rng or np.random.default_rng(0)
    def count(self, predicate, eps):
        if self.spent + eps > self.budget:
            return None                       # refusal depends only on eps's, so it is not disclosive
        self.spent += eps
        return predicate(self.x).sum() + self.rng.laplace(0, 1/eps)   # sensitivity 1
c = Curator(np.arange(1000), budget=1.0)
print(c.count(lambda v: v < 500, 0.4), c.count(lambda v: v < 100, 0.4), c.count(lambda v: v > 900, 0.4))  # third is None

Connections

• In measurement terms, the budget rule is the formal version of “each additional report on the same users spends privacy”: repeated breakdowns of the same conversion data (by channel, geo, week) are compositions, and the total $\epsilon$ is the sum unless advanced composition is used (Dwork Roth 2014 - Advanced Composition and the Gaussian Mechanism).
• Postprocessing is why a modeller may fit an MMM or lift model to a DP-released table without extra privacy cost, provided the model never touches the raw data again. See Bayesian Media Mix Modeling - Overview.

See Also

• Dwork 2006 - Differential Privacy Definition and Basic Examples
• Dwork 2006 - Sensitivity and the Laplace Mechanism
• Dwork Roth 2014 - Post-Processing, Group Privacy and What DP Promises
• Dwork Roth 2014 - Basic Composition and Divergence Tools