Explaining $\epsilon$ in local differential privacy through the lens of quantitative information flow

An important development in both the information theory and security communities has been an interest in operationally relevant leakage measures to provide information about the relative security of different probabilistic data sharing systems. In this context, operational measures are ones which provide interpretable guarantees in terms of an adversary’s gain or loss upon interacting with the system. The value produced by such a leakage measure therefore has a correspondence with some measurable information gain to the adversary, justifying its use as a security measure. For both of the above communities, the $\epsilon$ of differential privacy still lacks a robust operational meaning, despite the privacy community’s explanation in terms of the differential privacy attacker who knows all-but-one secret in the dataset. The following example illustrates this more clearly.

Consider a local differential privacy scenario in which a user wishes to obfuscate their own sensitive data before releasing it to an untrusted data curator. The user is given a choice of two mechanisms to use. The scenario is depicted by the two mechanisms below, in which, for example, the user is answering a question in a survey, and the values {y, m, n} correspond to the answers ‘yes’, ‘maybe’ and ‘no’, respectively. Note that we describe our mechanisms as ‘channels’, in which the row labels correspond to secrets and the column labels correspond to observations. The value in row-$i$ column-$j$ represents the conditional probability $P(j|i)$; that is the probability of observing output $j$ given input $i$. In the example below, in the channel $G$ we have that the probability of observing $y$ given an input $n$ is $\nicefrac{{1}}{{6}}$, given by the value in the bottom left of the channel matrix.

From the perspective of differential privacy, the choice of the user’s noisy mechanism should be determined by the $\epsilon$ parameter described by the DP equation (1); in the DP literature, the smaller the $\epsilon$, the more privacy is said to be guaranteed to the user.

In the mechanisms described above, notice that the mechanism $G$ satisfies $\log(4)$-DP and the mechanism $R$ satisfies $\log(3)$-DP. ³³3The mechanisms $G$ and $R$ are in fact instances of the well-known Geometric and Randomised-Response mechanisms from DP, respectively. (In fact this corresponds to the maximum ratio between any two values within a column). We would therefore expect that $R$ is more private and so leaks less information to an adversary than does $G$.

We now ask: for each of these mechanisms, what would be the expected gain to an attacker who is trying to guess the secret in one try? We can model this attack by assuming a uniform prior for the adversary (say), and applying Bayes rule to compute the adversary’s posterior knowledge after making an observation from each mechanism. ⁴⁴4This is the model used in the QIF framework and is described in more detail in §II-C. The posterior probability of success for the attacker is given by the maximum probability in each posterior, averaged by the marginal on that posterior ⁵⁵5In QIF this is called the posterior Bayes vulnerability.. The resulting computation yields that the leakage of the system computed using the adversary’s expected posterior gain from $G$ is $1.67$ whereas the equivalent leakage from $R$ is $1.80$ (see Appendix A for complete details). So, in fact, our attacker learns more from $R$ than she does from $G$.

But since $\epsilon$ represents a “max-case” measure and the adversarial scenario above uses the expected gain of the attacker, i.e., an “average-case” measure, we might think that the above anomaly occurs because the measures we are using are incompatible. Let us consider now a max-case scenario: an attacker whose advantage is measured by the maximum probability of guessing the secret in one try regardless of which output was observed. In this scenario, the leakage to the attacker is given by the maximum leakage of any of the posteriors of the channel, independent of the marginal probability on that posterior. In this instance, we find that, again under a uniform prior, the max-case leakage computed using the posterior max-case vulnerability for $G$ is $1.71$ whereas for $R$ it is $1.80$ (see Appendix A for full details). And so $R$ also leaks more information to this max-case adversary than does $G$, even though its $\epsilon$ suggests that $R$ should be safer than $G$.

These examples motivate the question: what does $\epsilon$ tell us about other kinds of attacking threats apart from the one modelled in the DP literature? ⁶⁶6The DP literature describes $\epsilon$ as a measure of indistinguishability against an attacker who knows every secret in the dataset except for one. If $\epsilon$ is indeed a robust measure for privacy, it should be useful for making judgments about many different kinds of privacy threats. One way of assessing robustness from the QIF perspective would be to ask: does $\epsilon$ correspond to a leakage bound for some class of (Bayesian) adversaries? If so, this would give $\epsilon$ a robust operational meaning, allowing its guarantees to be explained in terms of a large number of attacking threats relevant to the security community. For the privacy community, this may assist in providing some explainability for $\epsilon$ in terms of its measurement of leakage. This could be used to guide privacy practitioners in determining a reasonable value for $\epsilon$, which is a problem that has been identified by, for example, the implementers of differential privacy for the US Census Bureau [15].

In this paper, we bring together the information-theoretic, differential privacy and QIF frameworks to show how the measures of lift from information theory and $g$-leakage from QIF can be used to bring a robust operational meaning – an explanation in terms of a broad class of adversarial attacks – to the parameter $\epsilon$ in (local) differential privacy.

Despite a large body of existing work, a number of questions remain open at the intersection of these frameworks.

While $\epsilon$ in both the local and central models of DP is agnostic to the adversarial gain function and prior knowledge, it is not clear whether $\epsilon$ has a robust interpretation in the QIF sense (i.e., in terms of protection against a class of adversaries as highlighted in the example earlier). Such a robust operational interpretation is missing from the DP literature.

In addition, it is still not clear whether the measure of log-lift (in this paper lift) has an operational significance as a measure of privacy leakage or is capable of robustly quantifying maximum privacy leakage in strong adversarial threat models via the QIF framework.

Last, the current theory of max-case leakage in QIF leaves open the question of how best to model the max-case adversarial threats or how to characterise max-case capacity over all priors and a wide class of adversarial threats.

The following contributions of this paper address these questions.

1. 1.

   We propose a new set of measures: max-case $g$-leakages (Defn 3), which are a subset of the set of general max-case measures for QIF, which have been extensively studied in [16]. The max-case $g$-leakages have a clear operational significance: they correspond to adversaries whose goal is to maximise their gain over any output. Note that $g$-leakages model information-theoretic Bayesian adversaries and therefore represent a very general threat model.

2. 2.

   We prove the first robust and operationally meaningful interpretation of $\epsilon$ in local DP via the proposed max-case $g$-leakage framework. Specifically, we show that $e^{\epsilon}$ is exactly the max-case $g$-leakage capacity, which measures the maximum leakage of a system wrt  any Bayesian attack modelled using either average-case or max-case $g$-leakage measures, and is robustly independent of adversarial gain functions and priors.

3. 3.

   We introduce the lift capacity (Defn 4), which quantifies lift over all priors, and show that it is equivalent to $e^{\epsilon}$ in the local DP framework. This provides the missing connection between lift and $\epsilon$ which has been a subject of interest in the information theory literature.

We remark that although one conclusion we draw – that the $\epsilon$ of the DP framework is robustly independent of the adversary – may seem expected or unsurprising, the method developed in this paper of obtaining the result via the QIF framework is non-trivial.

Technically speaking, the first contribution of this work is establishing a link between lift in information-theoretic privacy and a notion of max-case $g$-leakage, which we introduce in this paper via the QIF framework. Specifically, in Defn 3 we introduce a max-case multiplicative $g$-leakage, denoted by $\mathcal{L}^{\mathrm{max}}_{g}(\pi,C)$, using the standard notion of $g$-vulnerability in QIF framework. We then show via Thm 2 that lift upper bounds $\mathcal{L}^{\mathrm{max}}_{g}(\pi,C)$ with respect to any gain function $g$ for any given prior $\pi$. In Thm 1, we show that lift is indeed realisable as a max-case $g$-leakage for an adversary who chooses a suitable prior-dependent gain function.

In addition, we establish an important result, linking all three information-theoretic privacy, local differential privacy and QIF frameworks in an operationally robust manner. Specifically in the information-theoretic privacy framework, we define in Defn 4 the supremum of lift over all priors for a channel $C$ as lift capacity and denote it by $\mathcal{M}\mathrm{Lift}(C)$. We then show in Thm 3 and Cor 2 that lift capacity is equivalent to $\epsilon$ in the local DP framework. Combining this result with Thm 1 and Thm 2 we conclude that lift capacity, aka $e^{\epsilon}$, is also equal to the max-case $g$-leakage capacity in the QIF framework. This gives lift a robust operational interpretation in terms of strong max-case adversarial threats and explains $\epsilon$ in local DP as a capacity measure from the lens of information theory and QIF.

Finally, we address a question raised in [6] as to whether the $g$-leakage framework is sufficient to describe adversarial scenarios in which the attacker is trying to guess a randomised function of the secret. In fact the Dalenius leakage described in [16, Ch 10] already addresses this in the case of average-case $g$-leakage, demonstrating that $g$-leakage is unchanged when considering randomised functions of the secret. We extend these results to the cases of lift and lift capacity, showing that – as with the Bayes capacity – both measurements are unaffected under such adversarial scenarios.

Table I visualises existing results in the literature and our contributions. As seen from the Table, this paper bridges between several results in the information-theoretic privacy, differential privacy and QIF literature and establishes new relations between lift and other measures of privacy. Our new results, together with our consolidated summary of existing results, depicts a fuller picture on deep connections between the information-theoretic, differential privacy and QIF frameworks.

A key motivating example for the importance of operational security measures came from Geoffrey Smith [4] who observed that traditional information-theoretic measures such as mutual information can underestimate the threat to a system. This work led to the study of $g$-leakages, which directly model attacking threats and provide leakage measures which can be interpreted in terms of a concrete information gain to an attacker. The relevance of such leakage measures to the security community is that they are explainable in terms of explicit adversarial threats, and therefore give meaningful security assessments. The study of $g$-leakages now sits under the QIF umbrella [17, 16].

In parallel to the above, recent work from the information theory community has identified the importance of operational measures for information leakage [6]. Of particular interest is the problem of providing an operational interpretation to privacy measures such as $\epsilon$ (in differential privacy) and log-lift (from information theory). Key work in this area by Issa et al. [6] has independently discovered several results overlapping with QIF, which will be outlined later in this paper. Importantly, both communities use an information-theoretic and decision-theoretic (Bayesian) approach to modelling adversarial threats. Therefore, although in this paper we use the notation and framework of quantitative information flow, the results will be relevant and interpretable for the information theory community as well.

We adopt notation from QIF [16], a mathematical framework for studying and quantifying information leaks with respect to adversarial attack scenarios.

A probabilistic channel $C$ maps inputs (secrets) $x\in\mathcal{X}$ to observations $y\in\mathcal{Y}$ according to a distribution $\mathbb{D}{\mathcal{Y}}$. In the discrete case, such channels are $\mathcal{X}{\times}\mathcal{Y}$ matrices $C$ whose row-$x$, column-$y$ element $C_{x,y}$ is the probability that input $x$ produces observation $y$. The $x$-th row $C_{x,-}$ is thus a discrete distribution in $\mathbb{D}{\mathcal{Y}}$. We write $\mathcal{X}\rightarrow\mathbb{D}{\mathcal{Y}}$ for the type of the channel $C$.

We can use Bayes rule to model an adversary who uses their observations from a channel to (optimally) update their knowledge about the secrets $\mathcal{X}$. Given a prior distribution $\pi:\mathbb{D}{\mathcal{X}}$ (representing an adversary’s prior knowledge) and channel $C$, we can compute a joint distribution $J:\mathbb{D}(\mathcal{X}{\times}\mathcal{Y})$ where $J_{x,y}=\pi_{x}C_{x,y}$. Marginalising down columns yields the $y$-marginals $p(y)=\sum_{x}\pi_{x}C_{x,y}$ each having a posterior over $\mathcal{X}$ corresponding to the posterior probabilities $P_{X|y}(x)$, computed as $\nicefrac{{J_{x,y}}}{{p(y)}}$ (when $p(y)$ is non-zero). We denote by $\delta^{y}$ the posterior distribution $P(X|y)$ corresponding to the observation $y$. The set of posterior distributions and the corresponding marginals can be used to compute the adversary’s posterior knowledge after making an observation from the channel.

Local differential privacy (LDP), as applied by an individual, can be defined as a property of a channel $C:\mathcal{X}\rightarrow\mathbb{D}{\mathcal{Y}}$ taking data $\mathcal{X}$ to noisy outputs $\mathcal{Y}$.

Notably, the intuition behind lift as expressed in Eqn. (3) is that it measures the adversary’s change in knowledge, through (multiplicative) comparison of her prior and posterior beliefs for each secret and observation. The observation providing the biggest “knowledge gap” or lift thereby produces the most leakage.

Note that the argument of maximisation $\frac{J_{x,y}}{\pi_{x}p(y)}$ in Eqn. (4) is indeed

in plain probability notation as described in §I and its logarithm is known as the information density. Here, we provide a brief account of some works which have used such quantities in defining privacy measures.

In [9], a mechanism is said to provide $\epsilon$-local information privacy (LIP) if

A similar definition was earlier studied in [1] for sensitive features of datasets. In [10, 11], $\epsilon$-lift was said to be satisfied if the logarithm of the above inequalities held true for a sensitive variable $S$ and useful variable $X$ according to the Markov chain $S\to X\to Y$.

An important distinction between our definition of lift and the above works is that they imposed an additional lower bound, $e^{-\epsilon}$, on the ratio of the posterior to prior beliefs. Whereas in this work, we are only concerned with the largest lift ratio (i.e., the upper bound), which we simply call lift (removing the logarithm). Our definition captures the notion of maximum realisable leakage [6], which is proved in [6, Theorem 13] to be equal to the lift as stated in our Definition 2. This also coincides with the notion of almost-sure pointwise maximal leakage in [18, Definition 4].

In [9, 1, 10, 8], it is proven that Eqn (5) implies $2\epsilon$-LDP. This bound can be improved through optimisation as shown in [9]. However, we highlight that Eqn (5) and the aforementioned relations to LDP depend on the prior $\pi$. In §III-B, we will establish robust results strongly and directly linking a prior-independent notion of lift capacity to $\epsilon$-LDP. The reverse direction, linking $\epsilon$-LDP to Eqn (5) is already strong: it has been shown that in works such as [1, 8, 9] that $\epsilon$-LDP implies Eqn (5).

An important development over the past decade in security has been the use of operationally relevant leakage measures to provide information about the relative security of different probabilistic systems. Operational measures – those which have a direct correspondence with an adversarial scenario – are crucial to a proper understanding of the security properties of a system. Foundational work in this area by Geoffrey Smith [4] has led to the study of $g$-leakage under the umbrella of QIF [17, 16].

In QIF, adversaries are modelled as Bayesian: they are equipped with a prior $\pi:\mathbb{D}{\mathcal{X}}$ over secrets $\mathcal{X}$ and a gain function $g:\mathcal{W}{\times}\mathcal{X}{\rightarrow}\mathbb{R}_{\geq 0}$ (over actions $\mathcal{W}$ and secrets $\mathcal{X}$), which models the gain to the adversary upon taking action $w\in\mathcal{W}$ when the true value of the secret is $x\in\mathcal{X}$. Before observing an output from the system, the adversary’s prior expected gain, which we call the expected prior vulnerability of the secret, can be expressed as

The adversary can use their knowledge of the system (modelled as a channel $C:\mathcal{X}{\rightarrow}\mathbb{D}{\mathcal{Y}}$) to maximise their expected gain after making an observation. This is called the expected posterior vulnerability and is expressed as

where in the last equality, we have used the definition of vulnerability in Eqn. (6) for the posterior distribution, denoted $\delta^{y}$. Finally, the difference between the prior and posterior vulnerabilities gives a measure of the leakage of the system to this adversary; the greater the difference, the better is the adversary able to use the transmitted information to infer the value of the secret. This can be computed multiplicatively as

The $g$-leakage framework models a wide variety of attack scenarios, including guessing the secret in $n$ tries, guessing a property of the secret or guessing a value close to the secret. ⁷⁷7In fact, it has been shown that any convex vulnerability function is expressible as a $g$-vulnerability [19]. Moreover, attached to each leakage measure is an operational scenario given by the gain function and prior which describes a specific adversarial threat.

An important notion in QIF is that of capacity, which corresponds to the maximum leakage of a system quantified over all priors, or all gain functions, or both. Capacities thus provide robust, interpretable leakage bounds; robust because they quantify over large classes of adversaries and therefore are “robust” to variations in adversarial assumptions; interpretable because the bounds provide security guarantees which can be explained in terms of the particulars of adversarial attacks.

Of particular note is the Bayes capacity, defined as

where the first equality is proved in [17] and the last equality is due to the fact that the capacity is realised under the uniform prior [17, “Miracle Theorem”]. The Bayes capacity has an important operational significance: it is a tight upper bound on the multiplicative leakage of any channel in the average sense, quantified over all priors and gain functions [16]. In other words, there is no adversarial scenario, modelled using the expected gain of an adversary with any prior knowledge, for which the channel leakage exceeds the amount given by the Bayes capacity. This provides a robust leakage bound on the security risk to a system against any average-case attacker.

We conclude this section by showing the connection between Bayes capacity and the information-theoretic measure lift: it turns out that lift is an upper bound on the Bayes capacity. The following lemma has been expressed in [6, Corollary of Theorem 13]; our contribution here is an alternative proof of this result in a QIF formulation.

Further, we find that the bound is strict, in that lift can be strictly greater than Bayes capacity. Recalling that Bayes capacity is an upper bound on average-case $g$-leakage measures, this result then shows that lift cannot be represented as an average-case $g$-leakage measure.

Next, we study the relationship between lift and max-case measures of leakage.

Using Defn 3 above, we now show that lift can be expressed as a max-case $g$-leakage.

The significance of Thm 1 is that it gives an operational meaning to lift in terms of the adversary realised by $V_{g_{\pi}}$. To give some intuition, for some distribution $\sigma$, $V_{g_{\pi}}(\sigma)$ is given by $\max_{x}\frac{\sigma_{x}}{\pi_{x}}$; i.e., it measures the maximum “surprise” to the adversary, achieved on the secret $x$ for which the probability $\sigma_{x}$ most differs (multiplicatively) from the adversary’s prior $\pi_{x}$. ⁹⁹9We remark that the gain function $g_{\pi}$ is also known as the distribution-reciprocal gain function [16, Ch 3].

Continuing with our running example (Ex. 1), we can compute the gain function $g_{\pi}$ for $\pi(b,g,bg)=(\nicefrac{{1}}{{4}},\nicefrac{{1}}{{2}},\nicefrac{{1}}{{4}})$ as $g_{\pi}(b,b)=4$, $g_{\pi}(g,g)=2$, $g_{\pi}(bg,bg)=4$.

The prior vulnerability is

The posterior vulnerability is then given by

where

and

And so $\mathcal{L}^{\mathrm{max}}_{g_{\pi}}(\pi,C)=\nicefrac{{19}}{{11}}=1.73$ which is what we calculated for lift in Ex. 1.

We find, however, that lift has a much stronger property: it is in fact an upper bound on any max-case $g$-leakage measure (that is, using any gain function) with the minor restriction that the gain function must be non-negative. ¹⁰¹⁰10Note that this non-negativity restriction is also required in the case of Bayes capacity as an upper bound on average-case leakage.

Thm 2 tells us that lift is a surprisingly robust measure; for any prior, lift is a measure of the maximum $g$-leakage of a channel wrt any (non-negative) gain function. Moreover, this upper bound holds regardless of whether we consider average-case leakage or max-case leakage: the max-case we proved above (Thm 2); the average-case follows from the fact that lift upper bounds Bayes capacity (Lem 1) and Bayes capacity is, by definition, an upper bound on any average-case $g$-leakage, for any prior and any (non-negative) gain function.

To illustrate, consider again the running example (Ex. 1). For the gain function we will choose the gid function which models the adversary who wishes to guess the secret in one try. This is defined:

Then the max-case $gid$-leakage given the prior $\pi=(\nicefrac{{1}}{{4}},\nicefrac{{1}}{{2}},\nicefrac{{1}}{{4}})$ is given by:

And the lift we computed earlier as $1.73$, which is larger than the $gid$-leakage, as we expected. Thm 2 tells us that in fact for any gain function we choose and any prior, the lift will always be at least as large as the max-case $g$-leakage.

Typically, leakage measures (as defined e.g., in QIF) are not robust – that is, they depend on the specifics of the adversary (their prior and gain function), and therefore may not provide a reliable measure of the safety of a channel against different (Bayesian) adversaries having different prior knowledge and intent. A more robust way to characterise a channel’s leakage properties is to measure its maximum leakage ¹¹¹¹11Note the distinction between maximum leakage and max-case leakage: the former quantifies over all priors and gain functions; the latter uses a max-case posterior vulnerability measure. – that is, quantified over all priors, or over all gain functions, or both. Such quantities are termed capacities (see §II-C), and have been previously studied in the context of average-case leakage [22]; the Bayes capacity (recall Eqn (11)) is the most well-known and provides robust upper bounds on the average-case leakage of any channel.

There has, to date, been no study of max-case capacities. However, Thm 2 gives an immediate result in this direction – it shows that lift can be seen an example of a max-case capacity, since it provides an upper bound on max-case leakages quantified over all gain functions. It follows also that, by quantifying over all priors as well, the resulting lift capacity is an upper bound on all max-case $g$-leakages for all priors.

We now show that this so-called lift capacity also has an important relationship with the epsilon of local differential privacy.

Thm 3 and Cor 2 establish the equivalence between the lift capacity and the epsilon parameter of local differential privacy, and by Thm 1 and Thm 2 this gives that epsilon (or rather, $e^{\epsilon}$) is a tight upper bound on the max-case $g$-leakage of any channel. That is, $e^{\epsilon}$ is the max-case $g$-leakage capacity, quantified over all priors and gain functions. This result connecting $\epsilon$ with the $g$-leakage framework provides the first robust, operational interpretation for local differential privacy in terms of Bayesian adversarial threats.

We note that $\epsilon$ has previously been interpreted as a capacity under QIF [20]. However, in that work the vulnerability function chosen was not expressible as a $g$-vulnerability, and therefore did not carry with it the operational interpretation attached to the $g$-leakage framework. This was Smith’s original motivation for a $g$-leakage based model for secure information leakage measurements.

We also remark that the relationship between lift and local differential privacy has been established previously (eg. [6, 23]), but these results have not been tied back to the $g$-leakage framework, and did not establish the operational significance of $\epsilon$ in terms of max-case $g$-leakage measures.

Thm 2 above tells us that lift bounds max-case $g$-leakage. To give some intuition for what this means in practice, suppose that we are worried about the leakage of a system to some attacker, both wrt  any single individual in our system (i.e., the max-case leakage to the attacker) and wrt  the system as a whole (i.e., the attacker’s expected gain). Let’s also assume that we can estimate the prior knowledge of the attacker, but we do not know exactly what the attacker is trying to achieve (i.e., what is her gain function). What Thm 2 tells us is that without knowing anything about the attacker’s goal, we can still compute an upper bound on the leakage of the system to this attacker (i.e., we can measure how much more the attacker can gain by having access to the system). This upper bound is given by the lift - a quantity independent of the gain function - and this is an upper bound on both average-case and max-case leakage to Bayesian adversaries.

Now let’s assume that we are worried about the same attacker, however this time we know nothing about her prior knowledge nor her specific goal. What Cor 2 tells us is that we can still compute an upper bound on the leakage of the system to this attacker, and in this case the upper bound is given by the lift capacity, or alternatively by $e^{\epsilon}$ (computed in the local differential privacy sense). This upper bound is robust, in the sense that it makes no assumptions about the adversary’s prior knowledge or goal; thus it is termed a capacity, consistent with the QIF literature. The $\epsilon$ capacity differs from the existing Bayes capacity in QIF, in that Bayes capacity is an upper bound on adversaries whose leakage is computed in the average-case, whereas the $e^{\epsilon}$ upper bound is a capacity on adversaries computed using either average-case or max-case leakage measures. The significance of these results is that we can now justify $\epsilon$ as a robust security parameter with an operational interpretation in terms of a large class of Bayesian attackers.

Recall the motivating example presented in the introduction (§I-A) in which a user is given a choice of local differential privacy mechanisms $G$ and $R$ with $\epsilon$ values of $\log(4)$ and $\log(3)$, respectively. Remember that we found that $R$ had a larger leakage (wrt  both an average-case and a max-case Bayesian attacker) than $G$, even though it has a smaller $\epsilon$. The results of Thm 2 and Cor 2 do not tell us when one mechanism will be better than another against a particular attack; for this we would turn to the refinement orders of QIF (studied in [20]) which tell us when one mechanism is better than another against all attacks; or alternatively we would compute the leakage of each mechanism wrt  an individual attack of concern (as we did in the introduction).

What Thm 2 and Cor 2 do tell us is that there cannot be any attack (max-case or average-case) which produces more leakage than what the lift tells us (if we know the attacker’s prior), or what $e^{\epsilon}$ tells us (if we do not). In the case of $R$ and $G$, Cor 2 tells us that there does not exist an attack (max-case or average-case, and regardless of the adversary’s prior) that produces more leakage than $e^{\epsilon}=3$ or $e^{\epsilon}=4$, respectively. Moreover these bounds are tight: there exists an attack which does induce an $e^{\epsilon}$ leakage (and, in fact, Thm 3 gives a construction for such an attacker). This means that we can conclude that $R$ is generally safer than $G$, because its leakage never exceeds $3$, even though $G$ may be better than $R$ in some specific circumstances.

Notice that the leakages we computed in the example in §I-A for $G$ were $1.67$ and $1.71$, and for $R$ they were both $1.80$. These are indeed lower than the corresponding $e^{\epsilon}$ bounds of $4$ and $3$, respectively. Interestingly, if we compute the Bayes capacity for $G$ and $R$, we find that these are $1.67$ and $1.80$, respectively (because the Bayes capacity is realised on a uniform prior for exactly the adversarial scenario we computed). What this tells us is that if we are only concerned with attackers modelled in the average-case, then $G$ is in fact generally better than $R$ (but may be worse for particular attackers). The leakage of $1.71$ that we measured for $G$ was for a max-case attacker; and in fact the max-case leakage is always at least as large as the average-case leakage for any prior and any gain function, as we will prove later (see Lem 3 in §IV).

Up until this point, we have been satisfied with computing leakage measures with respect to deterministic functions of the domain $\mathcal{X}$ (described by a prior $\pi$). As pointed out in [6], one may also be concerned about potentially randomised functions of $\mathcal{X}$. The QIF theory of Dalenius leakage [16, Ch 10] accounts for such functions by modelling the leakage that a channel $C{:}\mathcal{X}{\rightarrow}\mathbb{D}{\mathcal{Y}}$ induces on a secret $\mathcal{Z}$ through an unknown correlation $J{:}\mathbb{D}{(\mathcal{Z}{\times}\mathcal{X})}$. Given such a correlation $J$, we can factorise it into a prior $\rho{:}\mathbb{D}{\mathcal{Z}}$ and a channel $D{:}\mathcal{Z}{\rightarrow}\mathbb{D}{\mathcal{X}}$ so that $J_{z,x}=\rho_{z}{\times}D_{z,x}$.

In [16] it is shown that the multiplicative Bayes capacity of the combined system $DC$ (writing $DC$ for matrix multiplication) is in fact bounded from above by the multiplicative Bayes capacity of $C$; and thus considering arbitrary randomised functions of the secret $\mathcal{X}$ is not necessary for quantifying the maximum multiplicative leakage of a channel.

Here we confirm that this property also holds for the max-case leakage capacity (given by $\mathcal{M}\mathrm{Lift}$), and also by lift itself. This means that the capacity results proven in this paper also hold for randomised functions of $\mathcal{X}$, and therefore there is no advantage in considering randomised functions of the secret space.

The max-case $g$-leakage of $\mathcal{Z}$ caused by $J$ and $C$ can be written as $\mathcal{L}^{\mathrm{max}}_{g}(\rho,DC)$. We now have the following: