Lowering the cost of anonymization

2.2.6 Change in formalism (F)

The definition of differential privacy using $ε$ -indistinguishability compares the distribution of outputs given two neighboring inputs. This is not the only way to capture the idea that a attacker should not be able to gain too much information on the dataset. Other formalisms have been proposed, which model the attacker more explicitly.

One such formalism reformulates DP in terms of hypothesis testing by limiting the type I and the type II error of the hypothesis that the output $O$ of a mechanism originates from $D_{1}$ (instead of $D_{2}$ ). Other formalisms model the attacker explicitly, by formalizing their prior belief as a probability distribution over all possible datasets. This can be done in two distinct ways. Some variants consider a specific prior (or family of possible priors) of the attacker, implicitly assuming a limited background knowledge, like in Section 2.2.5. We show that these variants can be interpreted as changing the prior-posterior bounds of the attacker. Finally, rather than comparing prior and posterior, a third formalism compares two possible posteriors, quantifying over all possible priors.

Definitions in this section provide a deeper understanding of the guarantees given by differential privacy, and some of them lead to tighter and simpler theorems on differential privacy, like composition or amplification results.

Hypothesis testing

First, differential privacy can be interpreted in terms of hypothesis testing [WZ10, KOV17]. In this context, an adversary who wants to know whether the output $O$ of a mechanism originates from $D_{1}$ (the null hypothesis) or $D_{2}$ (the alternative hypothesis). Calling $S$ the rejection region, the probability of false alarm (type I error), when the null hypothesis is true but rejected, is $P_{FA} = P [M (D_{1}) \in S]$ . The probability of missed detection (type II error), when the null hypothesis is false but retained, is $P_{FA} = P [M (D_{2}) \in O ∕ S]$ .

It is possible to use these probabilities, to reformulate DP: a mechanism is $ε$ -DP iff for all $S \subseteq O$ , $P_{FA} + e^{ε} P_{MD} \geq 1$ and $e^{ε} P_{FA} + P_{MD} \geq 1$ ; or equivalently, iff $P_{FA} + P_{MD} \geq \frac{2}{1 + e^{ε}}$ . Similarly, a mechanism is $(ε, δ)$ -DP iff $(P_{FA}, P_{MD}) = {(α, β) \in [0, 1] \times [0, 1] | (1 - α \leq e^{ε} β + δ)}$ .

This hypothesis testing interpretation was used in [DRS19] to define $f$ -differential privacy, which avoids difficulties associated with divergence based relaxations. Specifically, its composition theorem is lossless as it provides a computationally tractable tool for analytically approximating the privacy loss. Moreover, there is a general duality between $f$ -DP and infinite collections of $(ε, δ)$ -DP guarantees.

Definition 36 ( $f$ -differential privacy [DRS19]). Let $f : [0, 1] \to [0, 1]$ be a convex, continuous, and non-increasing function such that for all $x \in [0, 1]$ , $f (x) \leq 1 - x$ . A privacy mechanism $M$ satisfies $f$ -differential privacy ( $f$ -DP) if for all neighboring $D_{1}, D_{2}$ and all $x \in [0, 1]$ :

inf S {1 - P [M (D_{2}) \in S] | P [M (D_{1}) \in S] \leq x} \geq f (x) .

Here, $S$ is the rejection region; and the infimum is the trade-off function between $M (D_{1})$ and $M (D_{2})$ . The authors also introduce Gaussian differential privacy (GaussDP) as an instance of $f$ -differential privacy, which tightly bounds from below the hardness of determining whether an individual’s data was used in a computation than telling apart two shifted Gaussian distributions.

Changing the shape of the prior-posterior bounds

As we mentioned in Section 2.1.6, differential privacy can be interpreted as giving a bound on the posterior of a Bayesian attacker as a function of their prior. This is exactly the case in indistinguishable privacy (IndPr), an equivalent reformulation of differential privacy defined in [LXL13]. Assuming that the attacker is trying to distinguish between options $D = D_{1}$ and $D = D_{2}$ , where $D_{1}$ corresponds to the option “ $t \in D$ ” and $D_{2}$ to “ $t \notin D$ ”, we end up with a bound on the posterior probability depending on the prior probability that we derived in Section 2.1.6 (Proposition 1)¹⁸:

\frac{P [t \in D]}{e^{ε} + (1 - e^{ε}) P [t \in D]} \leq P [t \in D | M (D) = O] \leq \frac{e^{ε} \cdot P [t \in D]}{1 + (e^{ε} - 1) P [t \in D]}

We visualize these bounds on the top-left graph of Figure

2.8

Some variants of differential privacy use this idea in their formalism, rather than obtaining the posterior bound as a corollary to the classical DP definition. For example, positive membership privacy [LQS $+$ 13] requires that the posterior does not increase too much compared to the prior. Like noiseless privacy, it assumes an attacker with limited background knowledge.

Definition 37 ( $(Θ, ε)$ -positive membership privacy [LQS $+$ 13]). A privacy mechanism $M$ provides $(Θ, ε)$ -positive membership privacy (PMPr) if for any distribution $θ \in Θ$ , any record $t \in D$ and any $S \subseteq O$ :

\begin{matrix} P_{D \sim θ} [t \in D | M (D) \in S] & \leq e^{ε} P_{D \sim θ} [t \in D] P_{D \sim θ} [t \notin D | M (D) \in S] & \geq e^{- ε} P_{D \sim θ} [t \notin D] . \end{matrix}

Note that this definition is asymmetric: the posterior is bounded from above, but not from below. In the same paper, the authors also define negative membership privacy (NMPr), which provides the symmetric lower bound, and membership privacy¹⁹ (MPr), which is the conjunction of positive and negative membership privacy. They show that this definition can represent differential privacy (in its bounded and unbounded variants), as well as other definitions like differential identifiability [LC12] and sampling DP [LQS11, LQS12], which we mention in Section 2.2.10. Bounding the ratio between prior and posterior by $e^{ε}$ is also done in the context of location privacy: in [DGY $+$ 18], authors define $ε$ -DP location obfuscation, which formalizes the same intuition as membership privacy. A previous attempt at formalizing the same idea was presented in [RHMS09] as adversarial privacy. This definition is similar to positive membership privacy, except only the first relation is used, and there is a small additive $δ$ as in approximate DP. We visualize the corresponding bounds on the third figure of Figure 2.8.

Definition 38 ( $(Θ, ε, δ)$ -adversarial privacy [RHMS09]). An algorithm $M$ is $(Θ, ε, δ)$ -adversarial private (AdvPr) if for all $S \subseteq O$ , tuples $t$ , and distributions $θ \in Θ$ :

P_{D \sim θ} [t \in D | M (D) \in S] \leq e^{ε} \cdot P_{D \sim θ} [t \in D] + δ .

Adversarial privacy (without $δ$ ) was also redefined in [WXH17] as information privacy²⁰. Finally, aposteriori noiseless privacy is a similar variant of noiseless privacy introduced in [BBG $+$ 11]; the corresponding bounds can be seen on the last figure of Figure 2.8.

Definition 39 ( $(Θ, ε)$ -aposteriori noiseless privacy [BBG $+$ 11]). A mechanism $M$ is said to be $(Θ, ε)$ -aposteriori noiseless private (ANPr) if for all $θ \in Θ$ , all $S \subseteq O$ and all $i$ :

{D (i)}_{| D \sim θ, M (D) \in S} \approx_{ε} {D (i)}_{| D \sim θ} .

We visualize the prior/posterior bounds for these various definitions in Figure 2.8.

ℙ [t ∈ D |ℳ (D) ∈ S] — Figure 2.8: From top to bottom, using $ε = ln 3$ : posterior-prior bounds in differential privacy, positive membership privacy, adversarial privacy (with $δ = 0.05$ ) and aposteriori noiseless privacy. Both axes are linear and go from $0$ to $1$ .

Figure 2.8: From top to bottom, using $ε = ln 3$ : posterior-prior bounds in differential privacy, positive membership privacy, adversarial privacy (with $δ = 0.05$ ) and aposteriori noiseless privacy. Both axes are linear and go from $0$ to $1$ .

Comparing two posteriors

In [KS14], the authors propose an approach that captures an intuitive idea proposed by Dwork in [Dwo06]: “any conclusions drawn from the output of a private algorithm must be similar whether or not an individual’s data is present in the input or not”. They define semantic privacy: instead of comparing the posterior with the prior belief like in DP, this bounds the difference between two posterior belief distributions, depending on which dataset was secretly chosen. The distance chosen to represent the idea that those two posterior belief distributions are close is the statistical distance. One important difference between the definitions in the previous subsection is that semantic privacy quantifies over all possible priors: like in DP, the attacker is assumed to have arbitrary background knowledge.

Definition 40 ( $ε$ -semantic privacy [GKS08, KS14]). A mechanism $M$ is $ε$ -semantically private (SemPr) if for any distribution over datasets $θ$ , any index $i$ , any $S \subseteq O$ , and any set of datasets $X \subseteq D$ :

\begin{matrix} | P_{D \sim θ} [D \in X | M (D) \in S] - P_{D \sim θ} [D \in X | M (D_{- i}) \in S] | \leq ε . \end{matrix}

A couple of other definitions also compare posteriors directly: inferential privacy [GK17a] is a reformulation of noiseless privacy, and range-bounded privacy [DR19] (RBPr) requires that two different values of the PLRV are close to each other (instead of being between centered around zero like in $ε$ -DP). It is equivalent to $ε$ -DP up to a change in parameters, and is used as a technical tool to prove composition results.

Multidimensional definitions

Definitions that limit the background knowledge of the adversary explicitly formulate it as a probability distribution. As such, they are natural candidates for Bayesian reformulations. In [WXH17], the authors introduce identity DP, which is an equivalent Bayesian reformulation of noiseless privacy. Another example is inference-based causal DP, which we define in Definition 52 in Section 3.1.2. It is similar to aposteriori noiseless DP, except it uses causal DP instead of noiseless DP.

Further, it is possible to consider different definitions of neighborhood. In [dPCF12], authors introduce information privacy²¹, which can be seen as a posteriori noiseless privacy combined with free lunch privacy: rather than only considering the knowledge gain of the adversary on one particular user, it considers its knowledge gain about any possible group of values of the dataset.

Definition 41 ( $(Θ, ε)$ -information privacy [dPCF12]). A mechanism $M$ satisfies $(Θ, ε)$ -information privacy (InfPr) if for all probability distributions $θ \in Θ$ , all $D \in D$ and all $O \in O$ , $D_{| D \sim θ} \approx_{ε} D_{| D \sim θ, M (D) = O}$ .

The authors further prove that if $Θ$ contains a distribution whose support is $D$ , then $(Θ, ε)$ -InfPr implies $2 ε$ -DP.

Apart from the hypothesis testing reformulations, which can be used to improve composition and amplification results, the definitions in this section mostly appear in theoretical research papers, to provide a deeper understanding of guarantees offered by DP and its alternatives. They do not seem to be used in practical applications.

¹⁸Note that the original formalization used in [LXL13] was more abstract, and it used polynomially bounded adversaries, which we introduce in Section 2.2.8.

¹⁹Another definition with the same name is introduced in [SMS $+$ 19], we mention it in Section 2.2.1.

²⁰Another definition with the same name is introduced in [dPCF12], we mention it later in this section.

²¹Another definition with the same name is introduced in [WXH17], we mention it earlier in this section.

LINKPREV LINKUP LINKNEXT