Refinement Orders for Quantitative Information Flow and Differential Privacy ^†

The main contributions of this paper are the following:

We are not aware of many studies on refinement relations for QIF. Yasuoka and Terauchi [10] and Malacaria [11] have explored strong orders on deterministic mechanisms, focusing on the fact that such mechanisms induce partitions on the space of secrets. They showed that the orders produced by min-entropy leakage [5] and Shannon leakage [12,13] are the same and, moreover, they coincide with the partition refinement order in the Lattice of Information [14]. This order was extended to the probabilistic case in [6], resulting in the relation ${⊑}^{\mathrm{avg}}$ mentioned in Section 2. The same paper [6] proposed the theory of g-leakage and introduced the corresponding order ${⊑}_{\mathbb{G}}^{\mathrm{avg}}$. Furthermore, [6] proved that ${⊑}^{\mathrm{avg}}\subseteq {⊑}_{\mathbb{G}}^{\mathrm{avg}}$ and conjectured that also the reverse should hold. This conjecture was then proved valid in [7]. The max-case leakage, on which the relation ${⊑}_{\mathbb{Q}}^{\max }$ is based, was introduced in [9], but ${⊑}_{\mathbb{Q}}^{\max }$ and its properties were not investigated. Finally, ${⊑}^{\mathrm{prv}}$ is a novel notion introduced in this paper.

In the field of differential privacy, on the other hand, there have been various works aimed at trying understand the operational meaning of the privacy parameter $\epsilon$ and at providing guidelines for the choice of its values. We mention, for example [15,16], which consider the value of $\epsilon$ from an economical point of view, in terms of cost. We are not aware, however, of studies aimed at establishing orders between the level of privacy of different mechanisms, except the one based on the comparison of the $\epsilon$’s.

The relation between QIF and DP, LDP, and $\mathit{d}$-privacy is based on the so-called semantic interpretation of the privacy notions that regard these properties as expressing a bounds on the increase of knowledge (from prior to posterior) due to the answer reported by the mechanism. For $\mathit{d}$-privacy, the semantic interpretation is expressed by (2). To the best of our knowledge, this interpretation was first pointed out (for the location privacy instance) in [17]. The seminal paper on $\mathit{d}$-privacy, [3], also proposed a semantic interpretation, with a rather different flavor, although formally equivalent. As for DP, as explained in the Introduction, (2) instantiated to databases and Hamming distance corresponds to the odds ratio on which the semantics interpretation is based provided in [8]. Before that, another version of semantic interpretation was presented in [1] and proved equivalent to a form of DP called $\epsilon$-indistinguishability. Essentially, in this version, an adversary that queries the database, and knows all the database except one record, cannot infer too much about this record from the answer to the query reported by the mechanism. Later on, an analogous version of semantic interpretation was reformulated in [18] and proved equivalent to DP. A different interpretation of DP, called semantic privacy, was proposed by [19]. This interpretation is based on a comparison between two posteriors (rather between the posterior and the prior), and the authors show that, within certain limits, it is equivalent to DP.

A short version of this paper, containing only some of the proofs, appeared in [20].

In the next three sections, Section 2, Section 3 and Section 4, we define the order refinements ${⊑}_{\mathbb{G}}^{\mathrm{avg}}$, ${⊑}_{\mathbb{Q}}^{\max }$ and ${⊑}_{\mathbb{M}}^{\mathrm{prv}}$, respectively, and we study their properties. In Section 5.1, we investigate methods to verify them. In Section 6, we consider various mechanisms for DP and its variants, and we investigate the relation between the parameter $\epsilon$ and the orders introduced in this paper. In Section 7, we show that ${⊑}_{\mathbb{Q}}^{\max }$ and ${⊑}_{\mathbb{M}}^{\mathrm{prv}}$ form a lattice. Finally, Section 8 provides conclusions.

Note: In order to make the reading of the paper more fluid, we have moved all the proofs to the appendix at the end of the paper.

Quantitative Information Flow studies the problem of quantifying the information leakage of a system (e.g., a program, or an anonymity protocol). A common model in this area is to consider that the user has a secret x from a finite set of possible secrets $\mathcal{X}$, about which the adversary has some probabilistic knowledge $\pi :\mathbb{D}\mathcal{X}$ ($\mathbb{D}\mathcal{X}$ denoting the set of probability distributions over $\mathcal{X}$). A function $V:\mathbb{D}\mathcal{X}\to {\mathbb{R}}_{\ge 0}$ is then employed to measure the vulnerability of our system: $V\left(\pi \right)$ quantifies the adversary’s success in achieving some desired goal, when his knowledge about the secret is $\pi$.

Various such functions can be defined (e.g., employing well-known notions of entropy), but it quickly becomes apparent that no single vulnerability function is meaningful for all systems. The family of g-vulnerabilities [6] tries to address this issue by parametrizing V in an operational scenario: first, the adversary is assumed to possess a set of actions $\mathcal{W}$; second, a gain function $g(w,x)$ models the adversary’s gain when choosing action w and the real secret is x. g-vulnerability can be then defined as the expected gain of an optimal guess: $V_g\left(\pi \right)={\max }_{w:\mathcal{W}}{\sum }_{x:\mathcal{X}}{\pi }_{x}g(w,x)$. Different adversaries can be modelled by proper choices of $\mathcal{W}$ and g. We denote by $\mathbb{G}\mathcal{X}$ the set of all gain functions.

A system is then modelled as a channel: a probabilistic mapping from the (finite) set of secrets $\mathcal{X}$ to a finite set of observations $\mathcal{Y}$, described by a stochastic matrix C, where $C_{x,y}$ is the probability that secret x produces the observation y. When the adversary observes y, he can transform his initial knowledge $\pi$ into a posterior knowledge ${\delta }^y:\mathbb{D}\mathcal{X}$. Since each observation y is produced with some probability $a_y$, it is sometimes conceptually useful to consider that the result of running a channel C, on the initial knowledge $\pi$, is a “hyper” distribution $[\pi ,C]$: a probability distribution on posteriors ${\delta }^y$, each having probability $a_y$.

It is then natural to define the (average-case) posterior vulnerability of the system by applying V to each posterior ${\delta }^y$, then averaging by its probability $a_y$ of being produced: when defining vulnerability in this way, it can be shown [9] that V has to be convex on π; otherwise, fundamental properties (such as the data processing inequality) are violated. Any continuous and convex function V can be written as $V_g$ for a properly chosen g, so, when studying average-case leakage, we can safely restrict to using g-vulnerability.

Leakage can be finally defined by comparing the prior and posterior vulnerabilities, e.g., as ${\mathcal{L}}_g^{+}(\pi ,C)=V_g[\pi ,C]-V_g\left(\pi \right)$. (Comparing vulnerabilities “multiplicatively” is also possible but is orthogonal to the goals of this paper.)

A fundamental question arises in the study of leakage: can we guarantee that a system B is no less safe than a system A? Having a family of vulnerability functions, we can naturally define a strong order ${⊑}_{\mathbb{G}}^{\mathrm{avg}}$ on channels by explicitly requiring that B leaks (Note that comparing the leakage of $A,B$ is equivalent to comparing their posterior vulnerability, so we choose the latter for simplicity.) no more than A, for all priors $\pi$ and all gain functions $g:\mathbb{G}\mathcal{X}$: (Note also that quantifying over $g:\mathbb{G}\mathcal{X}$ is equivalent to quantifying over all continuous and convex vulnerabilities.)

Although ${⊑}_{\mathbb{G}}^{\mathrm{avg}}$ is intuitive and provides clear leakage guarantees, the explicit quantification over vulnerability functions makes it hard to reason about and verify. Thankfully, this order can be characterized in a “structural” way that is as a direct property of the channel matrix. We first define the refinement order ${⊑}^{\mathrm{avg}}$ on channels by requiring that B can be obtained by post-processing A by some other channel R that is:

A fundamental result [6,7] states that ${⊑}^{\mathrm{avg}}$ and ${⊑}_{\mathbb{G}}^{\mathrm{avg}}$ coincide.

We read $A{⊑}^{\mathrm{avg}}B$ as “A is refined by B”, or “B is as safe as A”. When $A{⊑}^{\mathrm{avg}}B$ holds, we have a strong privacy guarantee: we can safely replace A by B without decreasing the privacy of the system, independently from the adversary’s goals and his knowledge. However, refinement can be also useful in case $A/ {⊑}^{\mathrm{avg}}B$; namely, we can conclude that some adversary must exist, modelled by a gain function g, and some initial knowledge $\pi$, such that the adversary actually prefers to interact with A rather than interacting with B. (Whether this adversary is of practical interest or not is a different issue, but we know that one exists.) Moreover, we can actually construct such a “counter-example” gain function; this is discussed in Section 5.

Differential privacy relies on the observation that some pairs of secrets need to be indistinguishable from the point of view of the adversary in order to provide some meaningful notion of privacy; for instance, databases differing in a single individual should not be distinguishable, otherwise the privacy of that individual is violated. At the same, other pairs of secrets can be allowed to be distinguishable in order to provide some utility; for instance, distinguishing databases differing in many individuals allows us to answer a statistical query about those individuals.

This idea can be formalized by a distinguishability metric $\mathit{d}$. (To be precise, $\mathit{d}$ is an extended pseudo metric, namely one in which distinct secrets can have distance 0, and distance $+\infty$ is allowed.) Intuitively, $\mathit{d}(x,x^{\prime })$ models how distinguishable we allow these secrets to be. A value 0 means that we require x and $x^{\prime }$ to be completely indistinguishable to the adversary, while $+\infty$ means that she can distinguish them completely.

In this context, a mechanism is simply a channel (the two terms will be used interchangeably), mapping secrets $\mathcal{X}$ to some observations $\mathcal{Y}$. Denote by $\mathbb{M}\mathcal{X}$ the set of all metrics on $\mathcal{X}$. Given $\mathit{d}\in \mathbb{M}\mathcal{X}$, we define $\mathit{d}$-privacy as follows:

Intuitively, this definition requires that the closer x and $x^{\prime }$ are (as measured by $\mathit{d}$), the more similar (probabilistically) the output of the mechanism on these secrets should be.

Using a generic metric $\mathit{d}$ in this definition allows us to express different scenarios, depending on the domain $\mathcal{X}$ on which the mechanism is applied and the choice of $\mathit{d}$. For instance, in the standard model of differential privacy, the mechanism is applied to a database x (i.e., $\mathcal{X}$ is the set of all databases), and produces some observation y (e.g., a number). The Hamming metric ${\mathit{d}}_{\mathrm{H}}$—defined as the number of individuals in which x and $x^{\prime }$ differ—captures standard differential privacy.

In the case of an oblivious mechanism, a query $f:\mathcal{X}\to \mathcal{Y}$ is first applied to database x, and a noise mechanism H from $\mathcal{Y}$ to $\mathcal{Z}$ is applied to $y=f\left(x\right)$, producing an observation z. In this case, it is useful to study the privacy of H wrt some metric ${\mathit{d}}_{\mathcal{Y}}$ on $\mathcal{Y}$. Then, to reason about the ${\mathit{d}}_{\mathcal{X}}$-privacy of the whole mechanism $H\circ f$, we can first compute the sensitivity of f wrt ${\mathit{d}}_{\mathcal{X}},{\mathit{d}}_{\mathcal{Y}}$: and then use the following property [3]:

For instance, the geometric mechanism $G^{\epsilon }$ satisfies $\epsilon ·{\mathit{d}}_{\mathrm{E}}$-privacy (where ${\mathit{d}}_{\mathrm{E}}$ denotes the Euclidean metric), hence it can be applied to any numeric query f: the resulting mechanism $G^{\epsilon }\circ f$ satisfies ${\Delta }_{{\mathit{d}}_{\mathrm{H}},{\mathit{d}}_{\mathrm{E}}}^f·\epsilon$-differential privacy. The sensitivity wrt the Hamming and Euclidean metrics reduces to ${\Delta }_{{\mathit{d}}_{\mathrm{H}},{\mathit{d}}_{\mathrm{E}}}^f={\max }_{x\sim x^{\prime }}|f\left(x\right)-f\left(x^{\prime }\right)|$ where $x\sim x^{\prime }$ denotes ${\mathit{d}}_{\mathrm{H}}(x,x^{\prime })=1$.

There are also scenarios in which a mechanism C is applied directly to the data of a single individual (that is, $\mathcal{X}$ is the set of possible values). For instance, in the local model of differential privacy [2], the value of each individual is obfuscated before sending them to an untrusted curator. In this case, C should satisfy ${\mathit{d}}_{\mathrm{D}}$-privacy, where ${\mathit{d}}_{\mathrm{D}}$ is the discrete metric, since any change in the individual’s value should have negligible effects.

Moreover, in the context of location-based services, a user might want to obfuscate his location before sending it to the service provider. In this context, it is natural to require that locations that are geographically close are indistinguishable, while far away ones are allowed to be distinguished (in order to provide the service). In other words, we wish to provide ${\mathit{d}}_{\mathrm{E}}$-privacy, for the Euclidean metric on ${\mathbb{R}}^2$, called geo-indistinguishability in [17].

Scaling $\mathit{d}$ by a privacy parameter $\epsilon$ allows us to turn $\mathit{d}$-privacy (for some fixed $\mathit{d}$) into a quantitative “leakage” measure, by associating each channel to the smallest ε by which we can scale $\mathit{d}$ without violating privacy.

Note that ${\mathrm{Priv}}_{\mathit{d}}\left(C\right)=+\infty$ iff there is no such $\epsilon$; also ${\mathrm{Priv}}_{\mathit{d}}\left(C\right)\le 1$ iff C satisfies $\mathit{d}$-privacy.

It is then natural to compare two mechanisms A and B based on their “smallest $\epsilon$”.

For instance, $A{⊑}_{{\mathit{d}}_{\mathrm{H}}}^{\mathrm{prv}}B$ means that B satisfies standard differential privacy for $\epsilon$ at least as small as the one of A.

When discussing the average- and max-case leakage orders ${⊑}_{\mathbb{G}}^{\mathrm{avg}},{⊑}_{\mathbb{Q}}^{\max }$, we obtained strong leakage guarantees by quantifying over all vulnerability functions. It is thus natural to investigate a similar quantification in the context of $\mathit{d}$-privacy. Namely, we define a stronger privacy-based “leakage” order, by comparing mechanisms not on a single metric $\mathit{d}$, but on all metrics simultaneously.

Similarly to the other leakage orders, the drawback of ${⊑}_{\mathbb{M}}^{\mathrm{prv}}$ is that it quantifies over an uncountable family of metrics. As a consequence, our first goal is to characterize it as a property of the channel matrix alone, which would make it much easier to reason about or verify.

To do so, we start by recalling an alternative way of thinking about $\mathit{d}$-privacy. Consider the multiplicative total variation distance between probability distributions $\mu ,{\mu }^{\prime }\in \mathbb{D}\mathcal{Y}$, defined as:

If we think of C as a function $\mathcal{X}\to \mathbb{D}\mathcal{Y}$ (mapping every x to the distribution $C_{x,-}$), C satisfies $\mathit{d}$-privacy iff ${\mathrm{tv}}_{\otimes }(C_{x,-},C_{x^{\prime },-})\le \mathit{d}(x,x^{\prime })$, in other words iff C is non-expansive (1-Lipschitz) wrt ${\mathrm{tv}}_{\otimes },\mathit{d}$.

Then, we introduce the concept of the distinguishability metric ${\mathit{d}}_C\in \mathbb{M}\mathcal{X}$ induced by the channel C, defined as

Intuitively, ${\mathit{d}}_C(x,x^{\prime })$ expresses exactly how much the channel distinguishes (wrt ${\mathrm{tv}}_{\otimes }$) the secrets $x,x^{\prime }$. It is easy to see that ${\mathit{d}}_C$ is the smallest metric for which C is private; in other words, for any $\mathit{d}$:

We can now give a refinement order on mechanisms, by comparing their corresponding induced metrics.

This achieves our goal of goal of characterizing ${⊑}_{\mathbb{M}}^{\mathrm{prv}}$.

We now turn our attention to the question of how these orders relate to each other.

The fact that ${⊑}^{\max }$ is stronger than ${⊑}^{\mathrm{prv}}$ is due to the fact than ${\mathrm{Priv}}_{\mathit{d}}$ can be seen as a max-case information leakage, for a properly constructed vulnerability function $V_{\mathit{d}}$. This is discussed in detail in Section 4.7. This implication means that ${⊑}^{\mathrm{avg}},{⊑}^{\max }$ can be useful even if we “only” care about $\mathit{d}$-privacy.

We conclude the discussion on privacy-based refinement by showing the usefulness of our strong ${⊑}^{\mathrm{prv}}$ order in the case of oblivious mechanisms.

This means that replacing A by B is the context of an oblivious mechanism is always safe, regardless of the query (and its sensitivity) and regardless of the metric by which the privacy of the composed mechanism is evaluated.

Assume, for instance that we care about standard differential privacy, and we have properly constructed A such that $A\circ f$ satisfies $\epsilon$-differential privacy for some $\epsilon$. If we know that $A{⊑}^{\mathrm{prv}}B$ (several such cases are discussed in Section 6), we can replace A by B without even knowing what f does. The mechanism $B\circ f$ is guaranteed to also satisfy $\epsilon$-differential privacy.

Note also that the above theorem fails for the weaker order ${⊑}_{\mathit{d}}^{\mathrm{prv}}$. Establishing $A{⊑}_{{\mathit{d}}_{\mathcal{Y}}}^{\mathrm{prv}}B$ for some metric ${\mathit{d}}_{\mathcal{Y}}:\mathbb{M}\mathcal{Y}$ gives no guarantees that $A\circ f{⊑}_{{\mathit{d}}_{\mathcal{X}}}^{\mathrm{prv}}B\circ f$ for some other metric of interest ${\mathit{d}}_{\mathcal{X}}:\mathbb{M}\mathcal{X}$. It is possible that replacing A by B in that case is not safe (one would need to re-examine the behavior of B, and possibly reconfigure it to the sensitivity of f).

Table 3 summarizes the relations between the various orderings.

In this section we show that $\mathit{d}$-privacy can be expressed as a (max-case) information leakage. Note that this provides an alternative proof that ${⊑}^{\max }$ is stronger than ${⊑}^{\mathrm{prv}}$. We start this by defining a suitable vulnerability function:

Note the difference between $V_{\mathit{d}}\left(\pi \right)$ (a vulnerability function on distributions) and ${\mathrm{Priv}}_{\mathit{d}}\left(C\right)$ (a “leakage” measure on channels).

A fundamental notion in QIF is that of capacity: the maximization of leakage over all priors. In turns out that, for $V_{\mathit{d}}$, the capacity-realizing prior is the uniform one. In the following, ${\mathcal{L}}_{\mathit{d}}^{+,\max }$ denotes the additive max-case $\mathit{d}$ leakage, namely: and $\mathcal{M}{\mathcal{L}}_{\mathit{d}}^{+,\max }$ denotes the additive max-case $\mathit{d}$-capacity, namely:

This finally brings us to our goal of expressing ${\mathrm{Priv}}_{\mathit{d}}$ in terms of information leakage (for a proper vulnerability function).

Verifying $A{⊑}^{\mathrm{avg}}B$ can be done in polynomial time (in the size of $A,B$) by solving the system of equations $AR=B$, with variables R, under the linear constraints that R is a channel matrix (non-negative and rows sum up to 1). However, if the system has no solution (i.e., $A{/⊑}^{\mathrm{avg}}B$), this method does not provide us with a counter-example gain function g.

We now show that there is an alternative efficient method: define $C^{\uparrow }=\left\{CR\right|R\mathrm{is}\mathrm{a}\mathrm{channel}\}$, the set of all channels obtainable by post-processing C. The idea is to compute the projection of B on $A^{\uparrow }$. Clearly, the projection is B itself iff $A{⊑}^{\mathrm{avg}}B$; otherwise, the projection can be directly used to construct a counter-example g.

Since ${\parallel x-y\parallel }_2^2=x^{T}x-2x^{T}y+y^{T}y$, the projection of y to a convex set can be written as ${\min }_x{x}^{T}x-2x^{T}y$ for $Ax\le b$. This is a quadratic program with Q being the identity matrix, which is positive definite, hence it can be solved in polynomial time.

Note that the proof that ${⊑}_{\mathbb{G}}^{\mathrm{avg}}$ is stronger than ${⊑}^{\mathrm{avg}}$ (the “coriaceous” theorem of [7]) uses the hyperplane-separation theorem to show the existence of a counter example g in case $A{/⊑}^{\mathrm{avg}}B$. The above technique essentially computes such a separating hyperplane.

Similarly to ${⊑}^{\mathrm{avg}}$, we can verify $A{⊑}^{\max }B$ directly using its definition, by solving the system $R\tilde{A}=\tilde{B}$ under the constraint that R is a channel.

In contrast to ${⊑}^{\mathrm{avg}}$, when $A{/⊑}^{\max }B$, the proof of Theorem 2 directly gives us a counter-example: where $S=$ ch supp $[\pi ,A]$ and $\pi$ is any full-support prior. For this vulnerability function, it holds that $V^{\max }(\pi ,A)<V^{\max }(\pi ,B)$.

The ${⊑}^{\mathrm{prv}}$ order can be verified directly from its definition, by checking that ${\mathit{d}}_A\ge {\mathit{d}}_B$. This can be done in time $O\left(\right|\mathcal{X}{|}^2\left|\mathcal{Y}\right|)$, by computing ${\mathrm{tv}}_{\otimes }(C_{x,-},C_{x^{\prime },-})$ for each pair of secrets. If $A{/⊑}^{\mathrm{prv}}B$, then $\mathit{d}={\mathit{d}}_B$ provides an immediate counter-example metric, since B satisfies ${\mathit{d}}_B$-privacy, but A does not.

We define each family of mechanisms in terms of their channel construction. We assume that mechanisms operate on a set of inputs (denoted by $\mathcal{X}$) and produce a set of outputs (denoted $\mathcal{Y}$). In this sense, our mechanisms can be seen as oblivious (as in standard DP) or as LDP mechanisms. (We use the term ‘mechanism’ in either sense). We denote by $M^{\epsilon }$ a mechanism parametrized by $\epsilon$, where $\epsilon$ is defined to be the same as ${\mathrm{Priv}}_{\mathit{d}}\left(M\right)$. For the purposes of comparison, we make sure that we use the best possible $\epsilon$ for each mechanism. In order to compare mechanisms, we restrict our input and output domains of interest to sequences of non-negative integers. We assume $\mathcal{X},\mathcal{Y}$ are finite unless specified. In addition, as we are operating in the framework of $\mathit{d}$-privacy, it is necessary to provide an appropriate metric defined over $\mathcal{X}$; here, it makes sense to use the Euclidean distance metric ${\mathit{d}}_{\mathrm{E}}$.

In practice, the truncated geometric mechanism is preferred to the infinite geometric. We define the truncated geometric mechanism as follows.

It is also possible to define the ‘over-truncated’ geometric mechanism whose input space is not entirely included in the output space.

For example, the set of inputs to an over-truncated geometric mechanism could be integers in the range $[0\dots 100]$, but the output space may have a range of $[0\dots 50]$ or perhaps $[-50\dots 50]$. In either of these cases, the mechanism has to ‘over-truncate’ the inputs to accommodate the output space.

We remark that we do not consider the over-truncated mechanism a particularly useful mechanism in practice. However, we provide results on this mechanism for completeness since its construction is possible, if unusual.

Note that the construction presented in Definition 12 uses the Euclidean distance metric since we only consider integer domains. The general construction of the exponential mechanism uses arbitrary domains and arbitrary metrics. Note that its parameter $\epsilon$ does not correspond to the true (best-case) $\epsilon$-DP guarantee that it provides. We will denote by $E^{\epsilon }$ the exponential mechanism with ‘true’ privacy parameter $\epsilon$ rather than the reported one, as our intention is to capture the privacy guarantee provided by the channel in order to make reasonable comparisons.

We note that the randomized response mechanism also satisfies $\epsilon ·{\mathit{d}}_{\mathrm{E}}$-privacy.

Intuitively, the randomized response mechanism returns the true answer with high probability and all other responses with equal probability. In the case where the input x lies outside $\mathcal{Y}$ (that is, in ‘over-truncated’ mechanisms), all of the outputs (corresponding to the outlying inputs) have equal probability.

We now have three families of mechanisms which we can characterize by channels, and which satisfy $\epsilon ·{\mathit{d}}_{\mathrm{E}}$-privacy. For the remainder of this section, we will refer only to the $\epsilon$ parameter and take ${\mathit{d}}_{\mathrm{E}}$ as given, as we wish to understand the effect of changing $\epsilon$ (for a fixed metric) on the various leakage measures.

We first ask which refinement orders hold within a family of mechanisms. That is, when does reducing $\epsilon$ for a particular mechanism produce a refinement? Since we have the convenient order ${⊑}^{\mathrm{avg}}\subset {⊑}^{\max }\subset {⊑}^{\mathrm{prv}}$, it is useful to first check if ${⊑}^{\mathrm{avg}}$ holds as we get the other refinements ‘for free’.

For the (infinite) geometric mechanism, we have the following result.

This means that reducing $\epsilon$ in an infinite geometric mechanism is safe against any adversary that can be modelled using, for example, max-case or average-case vulnerabilities.

For the truncated geometric mechanism, we get the same result.

However, the over-truncated geometric mechanism does not behave so well.

We can think of this last class of geometrics as ‘skinny’ mechanisms, that is, corresponding to a channel with a smaller output space than input space.

Intuitively, this theorem means that we can always find some (average-case) adversary who prefers the over-truncated geometric mechanism with the smaller $\epsilon$.

We remark that the gain function we found can be easily calculated by treating the columns of channel A as vectors, and finding a vector orthogonal to both of these. This follows from the results in Section 5.1. Since the columns of A cannot span the space ${\mathbb{R}}^3$, it is always possible to find such a vector, and, when this vector is not orthogonal to the ‘column space’ of B, it can be used to construct a gain function preferring B to A.

Even though the ${⊑}^{\mathrm{avg}}$ refinement does not hold, we can check whether the other refinements are satisfied.

This means that, although a smaller $\epsilon$ does not provide safety against all max-case adversaries, it does produce a safer mechanism wrt d-privacy for any choice of metric we like.

Intuitively, the ${⊑}^{\mathrm{prv}}$ order relates mechanisms based on how they distinguish inputs. Specifically, if $A{⊑}^{\mathrm{prv}}B$, then, for any pair of inputs $x,x^{\prime }$, the corresponding output distributions are ‘further apart’ in channel A than in channel B, and thus the inputs are more distinguishable using channel A. When ${⊑}^{\mathrm{prv}}$ fails to hold, it means that there are some inputs in A which are more distinguishable than in B, and vice versa. This means an adversary who is interested in distinguishing some particular pair of inputs would prefer one mechanism to the other.

We now consider the exponential mechanism. In this case, we do not have a theoretical result, but, experimentally, it appears that the exponential mechanism respects refinement, so we present the following conjecture.

Finally, we consider the randomized response mechanism.

In conclusion, we can say that, in general, the usual DP families of mechanisms are ‘well-behaved’ wrt all of the refinement orders. This means that it is safe (wrt any adversary we model here) to replace a mechanism from a particular family with another mechanism from the same family with a lower $\epsilon$.

Now, we explore whether it is possible to compare mechanisms from different families. We first ask: can we compare mechanisms which have the same $\epsilon$? We assume that the input and output domains are the same, and the intention is to decide whether to replace one mechanism with another.

Intuitively, the randomized response mechanism maintains the same ($\epsilon$) distinguishability level between inputs, whereas the exponential mechanism causes some inputs to be less distinguishable than others. This means that, for the same (true) $\epsilon$, an adversary who is interested in certain inputs could learn more from the randomized response than the exponential. In the above counter-example, points $x_2,x_3$ in the exponential mechanism of channel A are less distinguishable than the corresponding points in the randomized response mechanism B.

As an example, let’s say the mechanisms are to be used in geo-location privacy and the inputs represent adjacent locations (such as addresses along a street). Then, an adversary (your boss) may be interested in how far you are from work, and therefore wants to be able to distinguish between points distant from $x_1$ (your office) and points within the vicinity of your office, without requiring your precise location. Your boss chooses channel A as the most informative. However, another adversary (your suspicious partner) is more concerned about where exactly you are, and is particularly interested in distinguishing between your expected position ($x_2$, the boulangerie) versus your suspected position ($x_3$, the brothel). Your partner chooses channel B as the most informative.

Regarding the other refinements, we find (experimentally) that in general they do not hold between families of mechanisms. (Recall that we only need to produce a single counter-example to show that a refinement doesn’t hold, and this can be done using the methods presented in Section 5.)

We next check what happens when we compare mechanisms with different epsilons. We note the following.

This tells us that, once we have a refinement between mechanisms, it continues to hold for reduced $\epsilon$ in the refining mechanism.

Thus, it is safe to ‘compare epsilons’ wrt ${⊑}^{\mathrm{prv}}$ if we want to replace a geometric mechanism with either a randomized response or exponential mechanism. (As with the previous theorem, note that the results for the exponential mechanism are stated as conjecture only, and this conjecture is assumed in the statement of this corollary.) What this means is that if, for example, we have a geometric mechanism $TG$ that operates on databases with distance measured using the Hamming metric ${\mathit{d}}_{\mathrm{H}}$ and satisfying $\epsilon ·{\mathit{d}}_{\mathrm{H}}$-privacy, then any randomized response mechanism R parametrized by ${\epsilon }^{\prime }\le \epsilon$ will also satisfy $\epsilon ·{\mathit{d}}_{\mathrm{H}}$-privacy. Moreover, if we decide we’d rather use the Manhattan metric ${\mathit{d}}_{\mathrm{M}}$ to measure distance between the databases, then we only need to check that $TG$ also satisfies $\epsilon ·{\mathit{d}}_{\mathrm{M}}$-privacy, as this implies that R will too.

The following Table 4, Table 5 and Table 6 summarize the refinement relations with respect to the various families of mechanisms.

We now consider the behavior of the relations when $\epsilon$ approximates 0, which represents the absence of leakage. We start with the following result:

While this result may be unsurprising, it means that we know that refinement must eventually occur when we reduce $\epsilon$. It is interesting then to ask just when this refinement occurs. We examine this question experimentally by considering different mechanisms and investigating for which values of $\epsilon$ average-case refinement holds. For simplicity of presentation, we show results for $5\times 5$ matrices, noting that we observed similar results for experiments across different matrix dimensions, at least wrt the coarse-grained comparison of plots that we do here. The results are plotted in Figure 3.

The plots show the relationship between ${\epsilon }_1$ (x-axis) and ${\epsilon }_2$ (y-axis) where ${\epsilon }_1$ parametrizes the mechanism being refined and ${\epsilon }_2$ parametrizes the refining mechanism. For example, the blue line on the top graph represents $T{G}^{{\epsilon }_1}{⊑}^{\mathrm{avg}}{E}^{{\epsilon }_2}$. We fix ${\epsilon }_1$ and ask for what value of ${\epsilon }_2$ do we get a ${⊑}^{\mathrm{avg}}$ refinement. Notice that the line ${\epsilon }_1={\epsilon }_2$ corresponds to the same mechanism in both axes (since every mechanism refines itself).

We can see that refining the randomized response mechanism requires much smaller values of epsilon in the other mechanisms. For example, from the middle graph, we can see that $R^4{⊑}^{\mathrm{avg}}T{G}^1$ (approximately) whereas, from the top graph, we have $T{G}^4{⊑}^{\mathrm{avg}}{R}^4$. This means that the randomized response mechanism is very ‘safe’ against average-case adversaries compared with the other mechanisms, as it is much more ‘difficult’ to refine than the other mechanisms.

We also notice that, for ‘large’ values of ${\epsilon }_1$, the exponential and geometric mechanisms refine each other for approximately the same ${\epsilon }_2$ values. This suggests that, for these values, the epsilons are comparable (that is, the mechanisms are equally ‘safe’ for similar values of $\epsilon$). However, smaller values of ${\epsilon }_1$ require a (relatively) large reduction in ${\epsilon }_2$ to obtain a refinement.