Mário S Alvim

Konstantinos Chatzikokolakis

Annabelle Mciver

Carroll Morgan

Catuscia Palamidessi

Geoffrey Smith

Additive and multiplicative notions of leakage, and their capacities

Keywords: Quantitative information flow, channel capacity, confidentiality, Dalenius Desideratum

Protecting sensitive information from improper disclosure is a fundamental security goal. It is complicated, and difficult to achieve, often because of unavoidable or even unpredictable operating conditions that can lead to breaches in planned security defences. An attractive approach is to frame the goal as a quantitative problem, and then to design methods that measure system vulnerabilities in terms of the amount of information they leak. A consequence is that the precise operating conditions, and assumptions about prior knowledge, can play a crucial role in assessing the severity of any measured vunerability.

We develop this theme by concentrating on vulnerability measures that are robust in the sense of allowing general leakage bounds to be placed on a program, bounds that apply whatever its operating conditions and whatever the prior knowledge might be. In particular we propose a theory of channel capacity, generalising the Shannon capacity of information theory, that can apply both to additive-and to multiplicative forms of a recentlyproposed measure known as g-leakage. Further, we explore the computational aspects of calculating these (new) capacities: one of these scenarios can be solved efficiently by expressing it as a Kantorovich distance, but another turns out to be NP-complete.

We also find capacity bounds for arbitrary correlations with data not directly accessed by the channel, as in the scenario of Dalenius's Desideratum.

I. Introduction

Protecting sensitive information from improper disclosure is a fundamental security goal, but one that is clearly not being achieved well in today's cyber infrastructure. The issue is complicated by the fact that some leakage of sensitive information is often unavoidable in practice, due either to system functionality (e.g. a statistical database must by design reveal information derived from the database entries, even if those entries themselves should be confidential) or due to side-channels (e.g. it is difficult to prevent running time or power consumption from depending on secrets). For this reason, it is attractive to approach the problem quantitatively, and indeed there has been good progress in recent years in the area of quantitative information flow, including works with a foundational focus [START_REF] Clark | Quantitative information flow, relations and polymorphic types[END_REF]- [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF], works aimed at the development of verification techniques [START_REF] Clark | A static analysis for quantifying information flow in a simple imperative language[END_REF]- [START_REF] Meng | Calculating bounds on information leakage using two-bit patterns[END_REF], and works analyzing the leakage in real-system vulnerabilities [START_REF] Köpf | Vulnerability bounds and leakage resilience of blinded cryptography under timing attacks[END_REF]- [START_REF] Köpf | Automatic quantification of cache side-channels[END_REF].

One important quantitative theme has been the development of leakage measures with strong operational significance for confidentiality, so that the amount of information leaked is associated with the constraints and rewards of real attacks. In this respect, notable measures include min-entropy leakage [START_REF] Smith | On the foundations of quantitative information flow[END_REF] and g-leakage [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF]. Assuming that an adversary's prior knowledge about the secret is represented as a probability distribution π, min-entropy leakage is based on the ratio of the secret's posterior-and prior vulnerability to being guessed correctly in one try by the adversary. One-try vulnerability is clearly a basic and important measure of confidentiality, but it should be recognized that it is not appropriate in all situations. For this reason, g-leakage generalizes vulnerability with a gain function g that models the operational scenario, allowing us to consider situations in which the adversary gains e.g. by guessing the secret partially, approximately, or within k tries. It can also model scenarios where there is a penalty for making incorrect guesses.

A second important theme concerns robustness. The leakage caused by a channel C depends on both the prior distribution π and the particular leakage measure used (e.g. Shannon entropy, guessing entropy, min-entropy, g-leakage ). But what if we do not know π, or don't know the leakage measure, or don't know either? Then we might worry that our conclusions about information leakage lack robustness. Precisely for this reason, there has been considerable interest in achieving results that are less sensitive to the particular assumptions made of prior or entropy-measure. Capacity is the maximum leakage over all prior distributions-and its utility is that when a channel has small capacity, its leakage is small, no matter what the prior may be. It is also interesting to establish capacity relationships between different leakage measures. For instance, the Miracle Theorem of [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF] shows that min-capacity (the maximum minentropy leakage over all priors) is an upper bound on g-leakage for every gain function g-this means that a channel with small min-capacity has small g-leakage, no matter what prior or gain function is used. A second approach to robustness concerns comparisons between channels. It has recently been shown in the Coriaceous Theorem of [START_REF] Mciver | Abstract channels and their robust information-leakage ordering[END_REF] that a channel A never leaks more than a channel B, on any prior π and gain function g, if and only if A secures B in the sense that that A is equivalent to the combination of B with some "post-processing" R.

This paper builds on these successes of the g-leakage model, achieving advances in both operational significance and robustness.

With respect to operational significance, recall that (as mentioned above) standard g-leakage is based on the ratio of the posterior and prior g-vulnerabilities. But there are situations where it seems more significant to consider instead the difference of the vulnerabilities. For instance, a system whose prior-and posterior vulnerabilities are 2 -1000 and 2 -700 respectively has a huge multiplicative increase of 2 300 , but its additive increase is less than 2 -700 , which might well be considered negligible. Moreover, g-vulnerabilities can be used to model the economic value to the adversary of the priorand posterior situations; here too it seems more significant to consider their difference rather than their ratio. Finally, we discover that both guessing-entropy and Shannon-entropy leakage can be expressed as additive g-leakages. For these reasons, in this paper we develop the theory of additive gleakage, complementing the existing multiplicative theory.

With respect to robustness, this paper presents a systematic study of g-capacity. Since the g-leakage of a channel C depends on both the prior π and the gain function g, we consider several versions of capacity: we can fix g and universally quantify π, or we can fix π and universally quantify g, or we can universally quantify both π and g. By considering both multiplicative-and additive leakage, we get a total of six capacity scenarios. We also consider a seventh capacity scenario related to the famous ad-omnia privacy desideratum proposed by Dalenius [START_REF] Dalenius | Towards a methodology for statistical disclosure control[END_REF] for statistical databases, which states that nothing about an individual should be learnable with the database that could not equally well have been learned without it. As shown by Dwork [START_REF] Dwork | Differential privacy[END_REF], this desideratum is too strong to be achievable: for any useful database there is always some prior knowledge the adversary can use to induce a leakage of information. Analogously, we show here that gleakage can quantify the leakage about a secret X caused by an apparently unrelated channel C from Y to Z when the adversary knows some correlations between X and Y.

Beyond our systematic study, we make novel and significant contributions in four of those seven capacity scenarios:

• Given a prior π, we show that a gain function g π maximizing the multiplicative leakage can be computed efficiently. ( §VI-B)

• For the specific gain function g id , we show that the maximum additive leakage over all priors is NPcomplete. ( §VII-A)

• Given a prior π, we show that the maximum additive leakage over all gain functions can be computed in linear time, because this leakage can be expressed as a Kantorovich distance. ( §VII-B)

• We show that the "Dalenius" leakage of X caused by a channel C from Y to Z is bounded by the capacity of C, regardless of the correlations that may exist between X and Y. ( §IX)

The rest of this paper is organized as follows. Section II gives preliminaries, Section III motivates additive g-leakage, and Section IV presents useful algebraic properties for gain functions. Section V then defines the seven capacity scenarios that we consider. Sections VI and VII present our results on the multiplicative-and additive scenarios respectively, with Section VIII giving some examples. Section IX presents our "Dalenius" bounds, proven using new results about the additive capacity of channel cascades. Finally, Sections X and XI discuss related work and conclude.

II. Preliminaries

A. Basic notations

We begin by recalling the basic definitions of informationtheoretic channels [START_REF] Cover | Elements of Information Theory[END_REF]. A channel is a triple (X, Y, C) where X and Y are finite sets (typically of secret input values and observable output values resp.) and C is an |X|×|Y| channel matrix whose entries are between 0 and 1 and whose rows each sum to 1. Typically we use upper-case Roman letters (like C) for channels, and calligraphic letters (like X, Y) for the sets over which they operate. We write C x,y for the element of C at row x in X and column y in Y. For the (entire) row x we write C x,-, and for column y we write C -,y .

The value C x,y is the conditional probability of output y's being produced by C from input x. A channel is deterministic just when all its elements are either 0 or 1, implying that each input row contains a single 1 which identifies that input's unique corresponding output.

Typically we assume knowledge of a prior distribution π on X, using lower-case Greek letters for simple distributions like that; by analogy with C x,y indexing a matrix, as above, we write π x for π at x, thus the probability that π gives to x. For more complex distributions we use upper-case Greek letters; 1 for example the joint distribution on X×Y determined by input distribution π and channel C is typically written Π x,y =π x C x,y ; when Π is understood, we can use a Π-implicit convention to write that as just p(x, y). The jointly distributed random variables X, Y have marginal probabilities that (again Π-implicitly) we write p(x)= y p(x, y) (which of course is just π x again) and p(y)= x p(x, y); occasionally we also write X, Y informally for "the (unnamed) distribution on X, Y " resp. The conditional probabilities are then given by p(y|x)= p(x,y) /p(x)

(if p(x) is non-zero) and p(x|y)= p(x,y) /p(y) (if p(y) is non-zero).
Note that Π is the unique joint distribution that recovers π and C, in that p(x)=π x and p(y|x)=C x,y (if p(x) is non-zero). When necessary to avoid ambiguity, we write these Π-implicit distributions with subscripts, e.g. p X or p XY or p Y .

For example given |X|=3 and |Y|=4, we could consider a channel C (at left) which, when applied to (the uniform) prior π = ( 1 /3, 1 /3, 1 /3) produces the joint matrix Π (at right):

C y 1 y 2 y 3 y 4 x 1 1 0 0 0 x 2 0 1 /2 1 /4 1 /4 x 3 1 /2 1 /3 1 /6 0 π -→ Π y 1 y 2 y 3 y 4 x 1 1 /3 0 0 0 x 2 0 1 /6 1 /12 1 /12 x 3 1 /6 1 /9 1 /18 0 (1)
By summing Π's columns we get the Y-marginal distribution p Y = ( 1 /2,5 /18, 5 /36, 1 /12), and by normalizing those columns we obtain the four posterior distributions p X|y 1 = (2 /3, 0, 1 /3), p X|y 2 = (0,3 /5, 2 /5), p X|y 3 = (0, 3 /5, 2 /5) and p X|y 4 = (0, 1, 0). We use D() to construct the set of distributions on a set, so that DX is typically the set of distributions on the input and DY is the set of distributions on the output. For a pointor equivalently Dirac distribution assigning probability 1 to some x in X (and thus 0 to all other elements of X) we write [x]. We write ⌈π⌉ for the support of distribution π, that is the (sub-)set of elements where it is not zero. 2 For the sum of a (sub-)distribution π we write just Σπ; using that we could write more succinctly p(x) = Π x,-and p(y) = Π -,y .

For the expected value over a distribution π: DX of some random variable F: X→R, where R is usually the reals R but more generally can be a vector space, we write E π F; thus in the discrete case we have E π F = x π x F(x). If X itself is a vector space, then we abbreviate E π (id) by just Eπ, the "average" of the distribution π on X.

Leakage measures can be defined based on various entropylike functions of the prior distribution π and the posterior distributions p X|y , together with their probabilities p(y). Here are some examples. [START_REF] Shannon | A mathematical theory of communication[END_REF] of the prior distribution 3

Shannon leakage is based on the Shannon entropy H

[π] = -x π x lg π x

and the expected Shannon entropy of the posterior distributions H[π, C] = y p(y)H[p X|y ]. It is their difference H[π]-H[π, C

] that equals the mutual information I(π, C). 4Guessing-entropy leakage is based on the guessing entropy [START_REF] Massey | Guessing and entropy[END_REF] of the prior distribution, that is G[π] = i i π x i where the i-indexing of X is in non-increasing probability order, and on the expected guessing entropy of the posterior distributions G[π, C] = y p(y)G[p X|y ]. The guessing-entropy leakage then is the difference

G[π] -G[π, C].
The operational significance of both Shannon-and guessing entropy can be stated in terms of the expected number of bruteforce guesses an adversary would need to find the secret. 5 Min-entropy leakage [START_REF] Smith | On the foundations of quantitative information flow[END_REF] is based on the prior vulnerability V[π]= max x π x , the probability of the secret's being guessed in one try, and the expected vulnerability of the posterior distributions

V[π, C] = y p(y)V[p X|y ].
The min-entropy leakage L(π, C) is the logarithm of the ratio of the posterior-and prior vulnerabilities:

L(π, C) = lg(V[π, C]/V[π]) . (2)
Note that vulnerability implicitly assumes an operational scenario in which the adversary gains only by guessing the secret exactly, and in one try.

For this reason, g-leakage [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF] generalizes vulnerability to incorporate a gain function g, the choice of which allows the modelling of differing operational scenarios. In each scenario, there will be some set W of guesses that the adversary could make about the secret, and for any guess w and secret x, there will be some gain g(w, x) that the adversary gets by having chosen w when the secret's actual value was x; gains range from 0, when choosing w has no value at all, to 1, when w is ideal. (In §III-A, and Def. 3 in §V this is generalised, however.) Formally g: W×X → [0, 1], where W is a finite set. Given a gain function g, the prior g-vulnerability is defined as the maximum expected gain over all possible guesses:

V g [π] = max w x π x g(w, x) . (3)
The posterior g-vulnerability and the g-leakage are then defined as for min-entropy leakage above, so that we have

V g [π, C] = y p(y)V g [p X|y ] , (4)
and then

L g (π, C) = lg(V g [π, C]/V g [π]
) .

Note that the identity gain function g id , which gives gain 1 for guessing the secret correctly and 0 otherwise, makes g-leakage coincide with min-entropy leakage, which latter is thus a special case. But gain functions can do much more. As explained in [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF], they can model a wide variety of practical operational scenarios, including those where the adversary benefits from guessing a value close to the secret, guessing a part of the secret, guessing a property of the secret or guessing the secret within some bounded number of tries. They can also model scenarios where there is a penalty for incorrect guesses.

We now recall some previous results about capacity. Shannon capacity and min-capacity are, respectively, the maximum Shannon leakage and maximum min-entropy leakage, over all priors. The min-capacity of C, denoted ML(C), is always realized on the uniform prior and it is equal to the logarithm of the sum of the column maximums of C [START_REF] Köpf | Vulnerability bounds and leakage resilience of blinded cryptography under timing attacks[END_REF], [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF]. Mincapacity is an upper bound on Shannon capacity [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF], and the two coincide on deterministic channels [START_REF] Smith | Quantifying information flow using min-entropy[END_REF]. Finally, the Miracle Theorem [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF] shows that min-capacity is an upper bound on g-leakage, for every prior π and gain function g.

B. Hyper-distributions and their notations

A more abstract view of the action of a channel on a prior (e.g. more abstract than producing a joint distribution) is that it produces a distribution of posteriors. Following [START_REF] Mciver | Compositional closure for Bayes risk in probabilistic noninterference[END_REF], [START_REF] Mciver | Abstract channels and their robust information-leakage ordering[END_REF], we call those hyper-distributions, for brevity writing just "hyper".

A hyper on the input space X is of type D 2 X. Consider a prior π on X and a channel C: X→Y which, as usual, determines a joint distribution Π: D(X×Y). As above, with Π understood we have a distribution p Y on the outputs and, for each y, a corresponding posterior distribution p X|y on the inputs. If instead of considering p Y to be a distribution on Y we consider it to be a distribution on the corresponding posteriors (i.e. on the normalised columns of Π themselves, rather than on their Y-labels), then we have a hyper which we write [π, C]. For the example at (1) above, that hyper would assign probabilities ( 1 /2, 15 /36, 1 /12) to the posteriors ( 2 /3, 0, 1 /3), (0, 3 /5, 2 /5), and (0, 1, 0), respectively. 6Because hyper [π, C] is of type D 2 X, that is DV where V=DX is a vector space, we can just average that hyper itself, in effect "collapsing" it; and that gives the original prior again. That is we have the convenient identity E[π, C] = π.

A special case of a hyper is the point hyper on a particular (simple) distribution, say π: we write that as [π], as stated above for point distributions generally and of which this is just a special case. In this way we can regard g-vulnerability V g as acting on hypers in all cases. In particular V g [π] viewed this way, i.e. as a function V g of type D 2 X→R applied to a (point) hyper, remains equal to max w x π x g(w, x) as we defined it above.

III. Additive Leakage

Additive leakage is the difference between the posterior and prior vulnerabilities, and we write it

L + g (π, C) = V g [π, C] -V g [π]
. Note that the additive version of min-entropy leakage (i.e. with respect to g id ) was considered previously in [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF] and [START_REF] Andrés | Computing the leakage of information-hiding systems[END_REF]. (Standard g-leakage is defined multiplicatively, based on the ratio of the posterior and prior g-vulnerabilities. 7 )

We observe that calculating leakage additively rather than multiplicatively will not have any impact on channels' leakage ordering, since the additive leakage ordering L + g (π, A) ≤ L + g (π, B) and its multiplicative version

L g (π, A) ≤ L g (π, B) are both equivalent to V g [π, A] ≤ V g [π, B] (provided that V g [π]
>0 in the multiplicative case). But we believe that additive g-leakage is interesting and important in several respects, explained below.

A. Operational significance

First, there are a number of situations where additive leakage may have greater operational significance than does multiplicative leakage. To illustrate, consider a secret array X of uniformly distributed 10-bit passwords for 1,000 users. The following probabilistic channel (it is (Ex1) from [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF]) reveals some randomly-chosen user's password:

u ? ← {0..999}; Y = (u, X[u]);
When analyzed using min-entropy leakage, it leaks 10 bits, since it increases the vulnerability from 2 -10000 to 2 -9990 , a factor of 2 10 . But this analysis is inadequate if we are concerned about the loss of any user's password, and not just about the loss of the entire database. Hence [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF] defines a gain function g where

W = {(u, x) | 0 ≤ u ≤ 999 and 0 ≤ x ≤ 1023} and g((u, x), X) = 1, if X[u] = x 0, otherwise.
Note that this g gives the adversary a gain of 1 for correctly guessing the password of any user. When analyzed using g, the channel now increases the g-vulnerability from 2 -10 to 1. But 7 The g-leakage is the logarithm of this ratio, which just changes the scale.

this is again a factor of 2 10 , which means that the g-leakage is 10 bits, exactly the same as was the min-entropy leakage!

The point is that if we consider only the ratios of the vulnerabilities, an increase from 2 -10000 to 2 -9990 is exactly equivalent to an increase from 2 -10 to 1. But, additively, the former increase is less than 2 -9990 , a completely negligible quantity, while the latter is about 0.999, a huge difference. 8Another important motivation for considering additive leakage is the possibility of viewing vulnerabilities in economic terms. That is, we could define a gain function g so that the prior and posterior vulnerabilities would model the economic value to the adversary of its prior-and posterior knowledge about the secret. In this case, the additive leakage would represent the expected monetary gain from carrying out the attack represented by the channel C. Since making the attack might involve costs to the adversary, costs that he can predict, the additive leakage would then be crucial in his decision of whether the attack makes sense economically.

A technical issue to be considered concerns the range of gain functions. In [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF], [START_REF] Mciver | Abstract channels and their robust information-leakage ordering[END_REF], gain functions are required to return values in the range [0, 1]. Note that in the multiplicative context, negative vulnerabilities would cause mathematical problems, and merely allowing a larger range [0, a] would make no difference. In the additive context, however, it would make good sense to allow a wider range of gain valueslarge values could represent large economic gains, and negative values could represent losses (as in the gain function g tiger of [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF]). 9 We will say more about this issue in Section V below.

B. Expressiveness

Additive leakage is also interesting because some important existing leakages are special cases of additive g-leakages.

First, we find that we can express guessing entropy as a negative g-vulnerability. If we let W be the set of all permutations f of X, we can then define the gain function

g( f, x) = -i
where i is the unique index of x within permutation f , assumed to range from 1 to n. (Note that this requires extending the allowed range of gain functions, since g has range in [-n, -1].) With this definition, we find that

V g [π] = -G[π] and V g [π, C] = -G[π, C],
which means that the additive g-leakage is exactly the guessing-entropy leakage:

L + g (π, C) = V g [π, C]-V g [π] = G[π]-G[π, C] .
We might of course wonder whether guessing-entropy leakage could also be expressed as a multiplicative g-leakage, but we suspect that in general this is not possible.

Finally, we can even express Shannon leakage (mutual information) as an additive g-leakage, although this does require further extension.

To do this, we let W be the (uncountably infinite) set of all probability distributions ω on X, and we define g by

g(ω, x) = lg ω x .
Since ω x is in [0, 1], this gain function has range [-∞, 0]. The g-vulnerability associated with this gain function is

V g [π] = sup ω x π x lg ω x .
It turns out that V g is realized when ω=π, thanks to Gibbs' inequality [START_REF] Mackay | Information Theory, Inference, and Learning Algorithms[END_REF], which implies that

V g [π] = -H[π]
. This implies that the additive g-leakage for this g is exactly the Shannon leakage.

Using continuity arguments, we could restrict to a countably infinite W and a gain function with range (-∞, 0]. Still, W needs to be infinite and g unbounded in order to capture Shannon leakage. Although such gain functions are interesting from the point of view of expressiveness, in this paper we restrict to finite sets of guesses W.

IV. Gain-function algebra

Using gain functions to analyse leakage properties of channels can be simplified by establishing some general algebraic properties. Fix a channel C, prior π and gain function g. We define the following special g-functions, for k: R:

g ×k (w, x) = g(w, x) × k g +k (w, x) = g(w, x) + k g +k@x ′ (w, x) = g(w, x) + (k if x=x ′ else 0) . (5)
(Notice that in this section we are allowing completely unrestricted gain functions W×X → R, for some finite W.)

These new gain functions satisfy the following properties, which we prove in App. A:

x-Shift V g +k@x ′ [π, C] = V g [π, C] + kπ x ′ Global Shift V g +k [π, C] = V g [π, C] + k Scale V g ×k [π, C] = k × V g [π, C] , for k≥0 (6)
In consequence, we have the following invariance results for leakages, simple corollaries of the above equalities:

Lemma 1: Scaling invariance For fixed gain function g and channel C, multiplicative leakage is invariant under positive Scale.

Lemma 2: Shifting invariance For fixed gain function g and channel C, additive leakage is invariant under Shift (of either kind).

V. Channel capacity

Shannon's original definition of channel capacity uses mutual information as the measure of information flow and maximises over all priors. The classic significance of the value obtained is that it provides a tight bound on the amount of information that can be transmitted reliably over the channel. In the security context, we look instead for bounds that tell us something about the "level of secrecy" of information, formulated for us in terms of relative (multiplicative) or comparative (additive) increases in g-vulnerability.

A useful notion of g-capacity would provide a robust measure of leakage that allowed meaningful predictions about how an attacker could use the channel for his gain. For robustness, we can consider universally quantifying over the prior π, over the gain function g, or over both. In quantifying over the prior π we are acknowledging that, in many situations, the prior is unknown and the assumption that it is uniform is not reasonable. (For example, large-scale studies have shown that password selection is not at all uniform [START_REF] Bonneau | The science of guessing: Analyzing an anonymized corpus of 70 million passwords[END_REF].) In quantifying over the gain function g we are acknowledging that we might not know the value to the adversary of different sorts of partial information about the secret, neither now nor even in the future. (In medical research, for instance, new correlations between diet and susceptibility to disease are constantly discovered: although knowing someone's favorite dish might be relatively harmless today, it might not be so in the future.)

Since we can universally quantify over the prior π, over the gain function g, or over both, and since we are interested in both multiplicative-and additive g-leakage, we arrive at a total of six scenarios, which we write as follows:

L g (∀, C), L ∀ (π, C), L ∀ (∀, C), L + g (∀, C), L + ∀ (π, C), L + ∀ (∀, C).
Each of them is of independent interest, and we define them precisely below.

For those scenarios that quantify over the gain function g, a first issue to be resolved is the set of gain functions that we allow. In previous work [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF], [START_REF] Mciver | Abstract channels and their robust information-leakage ordering[END_REF], a gain function is required to have type W × X → [0, 1] for some finite set W. But, as motivated in Section III, with additive leakage we may wish to allow gain functions with a range different from [0, 1]. Can we find a suitable set of gain functions to use in both multiplicative and additive g-capacity?

Note first that negative gain values are mathematically problematic for multiplicative leakage. But they are inessential for additive leakage, since negative gain values can be eliminated by shifting (g is bounded since W is assumed finite), with no effect on additive leakage (Lemma 2). We therefore restrict our attention to non-negative gain functions.

Next consider an unbounded range [0, ∞). Note that although any individual g is bounded (since W is finite), still an unbounded range allows to choose arbitrarily large gain functions when quantifying over them. For the multiplicative case this makes no difference, since any g (since it's bounded) can be scaled down to [0, 1] without affecting the leakage (Lemma 2). On the other hand, scaling does affect the additive leakage, and the unbounded range of g can cause the additive capacities L + ∀ (π, C), L + ∀ (∀, C) to be ill defined. Instead of bounding the range of g, we adopt the more permissive and mathematically attractive approach (for reasons explained in §VII) to restrict to 1-spanning gain functions, whose gain values, for a given guess w, span a range of size at most 1:

Definition 3: 1-spanning A gain function g is 1- spanning if |g(w, x) -g(w, x ′ )| ≤ 1 for all x, x ′ : X, w: W.
We write G 1 X to denote the set of non-negative, 1-spanning gain functions on X. When we formally define the different gcapacities below, this is the set of gain functions that we allow. Note that bounded range [0, k] gain functions are a special case: they are scalar multiples of 1-spanning gain functions.

A. Multiplicative capacities defined

Recall that DX is the set of distributions over a finite (and fixed) space of secrets X. Both priors π and posterior distributions are elements of DX.

1) Fixed g, universally quantified π -L g (∀, C): Definition 4: Multiplicative g-capacity

For channel C and gain function g, the multiplicative g-capacity is given by

L g (∀, C) = sup π: DX L g (π, C) = sup π: DX lg(V g [π, C]/V g [π]) .
2) Universally quantified g, fixed π -L ∀ (π, C):

Definition 5: Multiplicative π-capacity For channel C and prior π, the multiplicative π-capacity is given by

L ∀ (π, C) = sup g: G 1 X L g (π, C) = sup g: G 1 X lg(V g [π, C]/V g [π]) .
It is worth pointing out that quantifying over gain functions in G 1 X is exactly equivalent here (in the multiplicative case) to quantifying over gain functions with range [0, 1] (as used in previous work). First, gain functions with range [0, 1] are in G 1 X. Second, any g: G 1 X can be scaled to have range [0, 1], with no effect on the multiplicative leakage.

3) Universally quantified g and π -L ∀ (∀, C): Definition 6: Multiplicative capacity For channel C the general multiplicative capacity is given by

L ∀ (∀, C) = sup g: G 1 X L g (∀, C) = sup π: DX L ∀ (π, C) .

B. Additive capacities defined 1) Fixed g, universally quantified π -L + g (∀, C): Definition 7: Additive g-capacity

For channel C and gain function g, the additive g-capacity is given by

L + g (∀, C) = sup π: DX L + g (π, C) = sup π: DX V g [π, C] -V g [π] .
This generalises Shannon capacity, but with Shannon entropy replaced by some g-vulnerability.

2) Universally quantified g, fixed π -L + ∀ (π, C): Definition 8: Additive π-capacity

For channel C and prior π, the additive π-capacity is given by

L + ∀ (π, C) = sup g: G 1 X L + g (π, C) = sup g: G 1 X V g [π, C] -V g [π] .
As mentioned above, restricting gain functions to G 1 X does make a difference in additive leakage. But note that a gain function with arbitrary range can always be expressed as a gain function in G 1 X followed by some shifting (which has no effect on the additive leakage) and scaling (which multiplies the additive leakage by a constant k). Hence we can, if desired, simply scale L + ∀ (π, C) to account for a larger class of gain functions.

3) Universally quantified g and π -L + ∀ (∀, C): Definition 9: Additive capacity For channel C the general additive capacity is given by

L + ∀ (∀, C) = sup g: G 1 X L + g (∀, C) = sup π: DX L + ∀ (π, C) .

C. A capacity scenario related to Dalenius's Desideratum

In addition to the six capacity scenarios considered above, we can also identify a seventh scenario that is considerably more "open ended".

In the context of differential privacy [START_REF] Dwork | Differential privacy[END_REF], [START_REF] Dwork | A firm foundation for private data analysis[END_REF], a major motivation is the possibility that the adversary knows interesting correlations among secrets. Recall Dwork's argument for the impossibility of Dalenius's Desideratum-she imagines the prior knowledge "Alan Turing is two inches taller than the average Lithuanian woman." With such knowledge, revealing information about Lithuanian women has the surprising effect of revealing information about Alan Turing.

And indeed we can consider such scenarios in the context of g-leakage. Suppose we have a secret X with prior π, and an adversary interested only in learning about X, as measured by a gain function g : W × X → R. Now imagine a channel C from Y to Z, apparently having nothing at all to do with X. But still the adversary might know some interesting correlation between X and Y, expressed as a joint distribution Π on X × Y (which must induce marginal distribution π on X). In this case, we can quantify how much C (surprisingly) teaches the adversary about X. For we can extend C to a channel C * from (X, Y) to Z, defined by C * (x,y),z = C y,z . (Note that C * ignores the value of X.) And we can extend gain function g to a gain function g * for (X, Y), defined by g * (w, (x, y)) = g(w, x); this reflects the fact that the adversary cares only about X. With this done, we find that L g * (Π, C * ) tells how much channel C leaks about X, given knowledge of correlations Π.

Note here that

V g * [Π] = V g [π], but V g * [Π, C * ]
could be much larger. This means that the adversary's knowledge of the correlations Π between X and Y does not immediately teach him anything new about X. It is only observing the output of C * that gives him new information about X-and this in spite of the fact that channel C * completely ignores the value of X.

Hence it would be especially significant to establish upper bounds on the capacity (whether additive or multiplicative) on C * in terms of the capacity of C-such bounds would give us a way to limit the harm that channel C could cause to X, no matter what correlations might subsequently be discovered to exist between X and Y. We give such bounds in Corollaries 22 and 23 in §IX below.

VI. Calculating multiplicative capacities

We now consider the efficiency of calculating capacities in our three multiplicative scenarios.

A. Fixed g, universally quantified π -L g (∀, C) This scenario appears quite challenging. For the identity gain function g id (i.e. min-entropy leakage), we know from [START_REF] Köpf | Vulnerability bounds and leakage resilience of blinded cryptography under timing attacks[END_REF], [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF] that a uniform prior always realizes the capacity. But this is not true in general. In [11, §V-D] are a channel and gain function whose multiplicative leakage is not maximized by a uniform prior but instead by π = ( 1 /2, 1 /2, 0). It is unclear whether there is an efficient algorithm in this case.

B. Universally quantified g, fixed π -L ∀ (π, C)

Here we have discovered a complete solution:

Theorem 10:

For any full-support π, there exists a gain function g π such that for any C we have L g π (π, C) = ML(C). (As a consequence, L g π (π, C) = L ∀ (π, C) since, by the Miracle Theorem of [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF], we have ML(C) = L ∀ (∀, C).) Proof: Let g π : X×X → [0, 1] be given by

g π (x, x ′ ) = a/π x if x=x ′ 0 otherwise, (7)
where a = min x π x . Note that g π is independent of C; it can be written as a diagonal matrix whose entries are the reciprocals of the entries of π, normalized to be in [0, 1]. Intuitively, g π cancels out the "hints" coming from a skewed prior, making every element of X equally good a priori.

Now straightforward calculations show that V g π [π] = a and V g π [π, C] = a y max x C x,y , giving L g π (π, C) = lg y max x C x,y .
The latter is the logarithm of the sum of the column maximums of C, which is ML(C) by the theorem of [START_REF] Köpf | Vulnerability bounds and leakage resilience of blinded cryptography under timing attacks[END_REF], [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF].

As an example, consider the imperfect cancer test from [START_REF] Smith | Quantifying information flow using min-entropy[END_REF], with channel matrix we find that the g π -leakage is log 1.83 = ML(C).

C
Finally, note that if π is not full support, we can just delete the rows of C corresponding to values of X not in the support.

C. Universally quantified g and π -L ∀ (∀, C)

Here we also have a complete solution. By the Miracle Theorem, multiplicative leakage is maximized by g id and the uniform π, which give the min-capacity L ∀ (∀, C). In fact, by §VI-B we can let π be any full-support prior and let g be the "reciprocals of π" gain function g π .

VII. Calculating additive capacities

We now consider the efficiency of calculating capacities in our three additive scenarios.

A. Fixed g, universally quantified π -L + g (∀, C) Here we know a number of interesting things. For g id (which gives additive min-entropy leakage), it is shown in [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF] that the additive leakage is maximized by some "corner point" distribution, i.e. one that is uniform on some subset of X. If |X|=n, there are 2 n -1 corner-point distributions, making the maximum additive leakage computable. But, because the number of corner-point distributions is exponential in the size of C, this does not give an efficient algorithm. And the following theorem shows that an efficient algorithm probably does not exist: it is NP-complete to decide whether C's additive g id -capacity exceeds a given threshold. 10Theorem 11:

Given a channel matrix C and a threshold t, it is NP-complete to decide whether L + g id (∀, C) ≥ t. Proof: Before beginning the proof, we establish some basic properties and notation for corner-point distributions. Given a non-empty subset S of X, the corner-point distribution π S gives probability 1 |S| to the values in S and (therefore) gives probability 0 to the values in X-S. Now observe that

L + g id (π S , C) = V[π S , C] -V[π S ]
"g id gives ordinary vulnerability"

= y: Y max x: X π S x C x,y -max x ′ : X π S x ′ = y: Y max x: S 1 |S| C x,y -1 |S| = 1 |S| ( y: Y max x: S C x,y -1)
. Notice that y: Y max x: S C x,y is simply the sum of the column maximums of C, restricted to the rows in S. To simplify notation we let σ S abbreviate this sum, allowing us to write

L + g id (π S , C) = σ S -1 |S| . (8)
Now we proceed with the proof. By the result in [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF], it is easy to see that the decision problem "L + g id (∀, C) ≥ t ?" is in NP. For we can simply guess a non-empty subset S and verify that L + g id (π S , C) ≥ t. We complete the NP-completeness proof by showing a reduction from the Set-Packing problem [SP3] of [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF], which is the problem of deciding whether a collection of sets U = {U 1 , . . . , U n } contains k pairwise disjoint sets.

Suppose that the elements of the U i are drawn from universe {a 1 , . . . , a m }. We begin our reduction by constructing an n × m channel matrix11 C U where

C U i, j = 1 |U i | if a j ∈ U i 0 otherwise. Now notice that if U contains k pairwise disjoint sets, k ≥ 1,
then C U contains k pairwise non-overlapping rows. This means that C U is a perfect channel on the corresponding k inputs, since any possible output from those inputs will uniquely determine the input. Hence the additive leakage on the corner-point distribution on those k inputs is k-1 k , since the vulnerability is increased from 1 k to 1. We can see this more formally from equation ( 8) above. For if we let S be a set consisting of the indices of k pairwise disjoint sets in U, then we have

L + g id (π S , C U ) = σ S -1 k
where σ S is the sum of the column maximums of C U , restricted to the rows in S. But, since the rows in S are nonoverlapping, we know that each nonzero entry in each of these rows is the only nonzero entry in its column (restricted to the rows in S), and hence is included in the sum σ S . So, since each row sums to 1, we get that σ S = k, which gives

L + g id (π S , C U ) = k -1 k .
So far we have shown that if U contains k pairwise disjoint sets, then we have L + g id (∀, C U ) ≥ k-1 k . But does the converse hold? Not necessarily, as shown by the following counterexample:

C U =             1 0 0 0 0 0 0 1 4 1 4 1 4 1 4 0 0 0 1 4 0 0 0 1 4 1 4 1 4             .
In this case, U does not contain 2 disjoint sets, but nevertheless

L + g id (∀, C U ) ≥ 2-1 2 = 1 2
, since the corner-point distribution on all 3 rows gives additive leakage of 1 3 ( 5 2 -1) = 1 2 . To correct this difficulty, we need to convert U into a channel matrix in a slightly more complicated way, one which boosts the "penalty" for including an overlapping row in a corner-point distribution.

To this end, let p ≥ 1 be the maximum cardinality of any of the sets in U. 12 Let C U be embedded into a block matrix C U with p new rows and p new columns:

C U = I p×p 0 p×m 0 n×p C U
(Here I denotes the identity matrix, and 0 a zero matrix.)

Extending our previous calculation, note that if U contains k pairwise disjoint sets, then we have

L + g id (∀, C U ) ≥ p + k -1 p + k ,
since the p new rows are all non-overlapping.

But we can now argue that the converse also holds. For if L + g id (∀, C U ) ≥ p+k-1 p+k , then there exists a set S of indices such that L + g id (π S , C U ) ≥ p+k-1 p+k . Assume further that we choose S of minimum size that can achieve this additive-leakage threshold. Then we can argue by contradiction that the rows in S must be nonoverlapping, because if S contains a row that overlaps some other row of S, then we can delete it without decreasing the additive leakage.

For suppose that |S| = s for s ≥ 2, and that S ′ is formed by deleting a row with some overlap with the other rows of S. Recall that

L + g id (π S , C U ) = σ S -1 s ,
where σ S is the sum of the column maximums of C U , restricted to the rows in S. Now observe that when we pass from S to S ′ , we lose the contribution to σ S from the deleted row; this loss is at most p-1 p , since the deleted row must have overlap of at least 1 p with the other rows of S. Hence we have

L + g id (π S ′ , C U ) = (σ S ′ -1)/(s -1) ≥ (σ S -p-1 p -1)/(s -1) ≥ (σ S -p+k-1 p+k -1)/(s -1) "k ≥ 0" ≥ (σ S -σ S -1 s -1)/(s -1) "L + g id (π S , C U ) ≥ p+k-1 p+k " = ( (σ S -1)(s-1) s )/(s -1) = (σ S -1)/s = L + g id (π S , C U ) .
Having proved that the rows in S are nonoverlapping, we now note that S must contain at least p+k rows, since a nonoverlapping set of size u gives additive leakage u-1 u , which is less than p+k-1 p+k unless u ≥ p+k. And, finally, at least k of the nonoverlapping rows must come from C U , which implies that U contains k pairwise disjoint sets.

We have thus shown that U contains k pairwise disjoint sets iff L + g id (∀, C U ) ≥ p+k-1 p+k . Hence indeed Set Packing polynomialtime reduces to Maximum Additive Leakage.

Given the result for g id specifically, we cannot of course expect the problem to be efficiently solvable for g in general.

But we observe that we can use the linear-programming-based algorithm for Problem 6.1 of [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF] to find a maximizing π: given channels C 1 and C 2 , that algorithm finds a π that maximizes

V g [π, C 1 ] -V g [π, C 2 ]
. (It is aimed at testing whether C 1 's gleakage can ever exceed C 2 's.) Here we can just let C 1 be C and let C 2 be O, where O is a channel with just one column, 13 so that it satisfies noninterference, giving

V g [π, O]=V g [π]. Hence we get V g [π, C 1 ]-V g [π, C 2 ] = V g [π, C]-V g [π] = L + g (π, C).
To use linear programming, the algorithm in [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF] applies a strategy-based formulation of posterior g-vulnerability. A strategy S reifies the choice of best guess as a channel from Y (the set of outputs of C) to W (the set of allowable guesses). We see then that we can formulate posterior vulnerability as

V g [π, C] = max S
x,y,w π x C x,y S y,w g(w, x) .

But notice that if we then try to compute the maximization max

π (V g [π, C 1 ] -V g [π, C 2 ]) ,
we have nested maxes and a quadratic objective function, since the entries of both π and S are variables.

However, we can assume without loss of generality that the strategy S is deterministic, which allows the algorithm to try explicitly all strategies S 1 for C 1 and S 2 for C 2 , adding linear constraints to express that π is a prior for which S 1 and S 2 are optimal. In this way, it is able to find a π that maximizes additive g-leakage by solving |W| |Y|+1 linearprogramming problems. Of course, solving exponentially many linear-programming problems is not going to be feasible, except on very small channels.

But it appears that we can reformulate our problem as a single Quadratic-Programming problem, where the objective function is quadratic but the constraints are still linear. Quadratic programming cannot be solved efficiently in general, but there exist many mature quadratic-programming tools, and it appears likely that these could be applied fruitfully to the computation of L + g (∀, C).

B. Universally quantified g, fixed π -L + ∀ (π, C) We next study the complexity of calculating L + ∀ (π, C). A first observation is that we can use the linear-programmingbased algorithm for Problem 6.2 of [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF] to find a maximizing g. This algorithm, very similar to the one described just above in §VII-A, requires the solution of exponentially many linearprogramming problems.

But we find that we can do far better by exploiting some abstract mathematics. We show here that the quantification over G 1 X can be eliminated, because L + ∀ (π, C) reduces to the well-known Kantorovich distance [START_REF] Deng | The Kantorovich Metric in computer science: A brief survey[END_REF] We begin by recalling the Kantorovich distance between discrete probability distributions, and then we show how it applies in this context. Given a discrete probability distribution α: DA and random variable F recall that we write E α F for the expected value of F: A→R over α. Observe that when α is a point distribution centred at a that E α F = F(a). Definition 12: Kantorovich Construction Let d: A×A→ R be a metric on A. We write (DA, d) for the probability space on A determined by the sigma algebra generated by the open sets on A. Given two discrete distributions α, α ′ : DA, the Kantorovich distance between them is

K DA (α, α ′ ) = sup F: L 1 A | E α F -E α ′ F| ,
where L 1 A is the set of 1-Lipschitz functions on A [START_REF] Deng | The Kantorovich Metric in computer science: A brief survey[END_REF].

The distance K DA (α, α ′ ) on distributions is again a metric, and can be used via Def. 12 to construct (D 2 A, K DA (α, α ′ )) [START_REF] Van Breugel | The metric monad for probabilistic nondeterminism[END_REF]. In our context Def. 12 gives equivalent Kantorovich presentations for DX and D 2 X, allowing us to access very general calculational tools for evaluating channel capacities.

In our setting we start with the discrete metric on X to distinguish secrets because it simply treats all secrets as distinct. With this view we can use Def. 12 to derive the space of probability distributions over DX together with an associated metric on DX. The next lemma recalls however that this derived metric in fact turns out to be (half of) the well-known Manhattan metric [START_REF] Mciver | A Kantorovich-monadic powerdomain for information hiding, with probability and nondeterminism[END_REF]. (See App. B.) Lemma 13: Discrete Kantorovich metric Let d: X×X → R on X be the discrete metric, i.e. such that d(x 1 , x 2 ) is 0 or 1 according to x 1 =x 2 . Then K DX (π, π ′ ) is half the Manhattan metric on DX: that is

K DX (π, π ′ ) = 1 2 x | π ′ x -π x |
We next use the Manhattan metric to generate the probability space for D 2 X, together with its associated Kantorovich distance between hypers. Our first observation is that by regarding V g as a 1-Lipschitz function on DX, we immediately obtain that L + ∀ (π, C) is well-defined. In particular the connection between leakage calculations and expected values is given by the equality V g [π, C] = E [π,C] V g , a technical result that we prove in App. A as Lem. 24.

Lemma 14: Well defined capacity

L + ∀ (π, C) is welldefined, and satisfies

L + ∀ (π, C) ≤ K D 2 X ([π], [π, C]
). Proof: For any (1-spanning) g: G 1 X, the gain-function test V g regarded as a function from DX → R, which takes a distribution π: DX and maps it to V g [π], is a 1-Lipschitz function (Lem. 26 of App. A). This implies from Def. 12 that L + ∀ (π, C) can be no more than the Kantorovich distance between [π] and[π, C].

An important property of the Kantorovich distance between probability distributions is that it has a dual formulation as the Wasserstein metric, commonly known as the "earthmoving metric" [START_REF] Deng | The Kantorovich Metric in computer science: A brief survey[END_REF]; this in particular gives access to efficient algorithms for computing it, and strengthening the upper bound in Lem. 14. Earth moving formalises the idea of measuring the cost of transforming one distribution into another; it uses the underlying Kantorovich distance to define the cost function, which is then averaged over a strategy for re-distributing the probability mass in the resulting transformation. The earthmoving distance is defined by the minimum such cost.

We specialise the Wasserstein metric to the case of a discrete distribution on a set D, with some metric d: D 2 → R.

Definition 15: The earth-moving metric on DD

Consider two distributions σ, τ: DD with σ the "source" distribution and τ the "target" distribution. Then an earth-moving strategy on DD is a (joint) distribution in D(D 2 ) whose two marginals are σ and τ. Write S σ,τ for the set of such strategies.

The earth-moving distance between σ and τ is then the infimum over all such strategies S : S σ,τ of E S d. Informally it is the least sum of products "amount of earth moved" times "distance moved". More precisely we define

W DD (σ, τ) = inf S : S σ,τ E S d .
Now we specialise the Wasserstein distance to the same domain as our definition Def. 15 of the Kantorovich distance, that is taking D to be DX, so that DD becomes D 2 X, and the metric d on DX is half the Manhattan distance. Thus σ, τ: DD become hypers in D 2 X and, furthermore, those hypers have finite support (since we are only considering finite channels). That means that the strategies S considered in Def. 15 can also be limited to discrete distributions for our purposes.

That done, we conclude that the two metrics are the same: Theorem 16: Kantorovich-Rubinstein [START_REF] Deng | The Kantorovich Metric in computer science: A brief survey[END_REF] The Kantorovich distance and the earth-moving distance between hypers are the same.

Thm. 16 applied here will allow us to show that channel capacities are in fact the same as Kantorovich distances between the prior, considered as a point hyper in D 2 X, and the hyper produced by the channel acting on that prior.

Theorem 17: Additive π-capacity as Kantorovich distance

Let C: X→Y be a channel and π a prior on X. Then the channel capacity of C at π is equal to the Kantorovich distance between the hypers [π] and [π, C]. That is, we have

L + ∀ (π, C) = W D 2 X ([π], [π, C]) = K D 2 X ([π], [π, C]
) . (Note that the second equality is immediate from Thm. 16.)

Proof: Adopt the notation of Def. 15 so that our source distribution is the point hyper Σ=[π] and our target is T=[π, C], where we are using capital letters here (instead of σ, τ as earlier) to remind us that the source and target are hypers.

Because Σ is a point distribution (centred on the prior π), there is only one strategy in S Σ,T that has the appropriate marginals Σ=[π] and T=[π, C]. Given any two marginals Σ, T with Σ being a point distribution, the set S Σ,T of all joint distributions with the given marginals Σ, T contains only one member: any discrete joint distribution whose left (say) marginal is 1 at some x and zero elsewhere is expressible as a matrix where only the x-row is non-zero -and that row is the right marginal exactly. Put informally, if there is only one source "pile of earth," then any earth in any target pile can have come only from that single source.

For general σ, τ: DX the optimal strategy is given by

S σ,τ = T τ if σ=π else 0 , (9)
so that all earth transfers from ⌈Σ⌉ start from π; and the proportion of earth "at π" that is moved to any posterior τ in ⌈T⌉ is the probability [π, C] τ (= T τ ) that the hyper [π, C] assigns to that τ.

Thus we calculate

W D 2 X ([π], [π, C]) = min S : S Σ,T E S d "d is underlying metric; Def. 15" = E S d "take unique S in S as at (9)" = E [π,C] d π "define d σ (τ) = d(σ, τ) to allow Currying; S at (9) has point left-marginal [π]" = V g [π, C] -1 "define g so that V g [τ] = d π (τ)+1; see below" = V g [π, C] -V g [π] "V g [π] = d π (π)+1 = 1" ≤ L + ∀ (π, C) "Def. 8" ≤ K D 2 X ([π], [π, C]) , "Lem. 14"
whence the result follows because we have sandwiched

L + ∀ (π, C) between W D 2 X ([π], [π, C]) and K D 2 X ([π], [π, C]
)which from Thm. 16 are equal.

For the "see below" we exhibit a W together with a nonnegative and 1-spanning gain function g: W×X → R such that V g [τ] = d(π, τ)+1. To do this we observe that

d(π, τ) + 1 = K DX (π, τ) + 1 "definition d" = x |τ x -π x |/2 + 1 "Lem. 13" = max w x (τ x -π x )w(x)/2 + 1 "define W = X→{-1, 1}" = max w x τ x g(w, x) "define g(w, x) = 1 + (w(x) + x ′ π x ′ w(x ′ ))/2; see App. C" = V g [τ] .
"definition V g for this W"

We now have

E [π,C] d π = E [π,C] (V g -1) = (E [π,C] V g ) -1 = V g [π, C] -1 ,
where the last equality follows from Lem. 24 of App. A. We note that g is at least zero, since [w(x) + x ′ π x ′ w(x ′ )]/2 has minimum value at least -1, and finally g is 1-spanning since

|g(w, x) -g(w, x ′ )| = |w(x) -w(x ′ )|/2 ≤ 1 .
We can now compute L + ∀ (π, C) efficiently. Corollary 18: Efficient calculation of additive capacity Given channel C: X→Y and prior π: DX, the additive capacity

L + ∀ (π, C) has complexity O(|X||Y|).
Proof: From Thm. 17 we have the equality

L + ∀ (π, C) = W D 2 X ([π], [π, C]), whose rhs. is the optimal cost of earth- moving [π] to [π, C].
In the proof of that theorem we see that the cost is the expected value of the Kantorovich distance between prior π and the posteriors

p X|y in [π, C] (i.e. E [π,C] d π ).
That is, the optimal earth-move is calculated from the Ymarginal p Y of the joint distribution Π generated from π and C, using the Manhattan distance (Lem. 13) between π and each posterior p X|y . Thus the computational cost is given by the cost of computing the Y-marginal plus the cost of computing the average Manhattan distance, if we know the marginal.

Computing the Y-marginal takes |X||Y| time and, once done, computing each p X|y takes |X| time. Similarly, computing the Manhattan distance between each π and p X|y takes |X| time. Finally the cost of computing the expected optimal earth move takes |X||Y| time, giving a total overall complexity of O(|X||Y|).

C. Universally quantified g and π -L + ∀ (∀, C) For additive capacity (unlike multiplicative), it is not the case that the prior that optimises the capacity is known (or that it can be easily calculated). Nevertheless, we have made some progress: thanks to Thm. 17 we can remove one level of quantification over the gain functions, still leaving an optimisation problem for computing the capacity but it is less complex than before. Let C: X→Y be a channel. We can reformulate Def. 9 as follows:

sup π L + ∀ (π, C) = sup π K D 2 X ([π], [π, C]) "Thm. 17" = sup π y,x π x |C xy -x ′ C x ′ y π x ′ |/2 . "Def. 15; see App. B"
This has the form of an optimisation over variables π x constrained by π x ≥0 and x π x = 1. The O(|X||Y|) occurrences of absolute value seem potentially to make the calculation more complicated in general than e.g. a quadratic optimisation.

VIII. Example calculations

Here are some examples of the techniques of Section VII.

A. Additive capacity, fixed g -L + g (∀, C) Let channel C and gain function g be C y 1 y 2 y 3 x 1 0.9 0.1 0 x 2 0.1 0.7 0.2 x 3 0.1 0.5 0.4 g x 1 x 2 x 3 w 1 0.7 0.1 0.4 w 2 0.1 0.4 0.9

On this example, the algorithm described in §VII-A needs to solve |W| |Y|+1 = 2 4 = 16 linear programming problems. It finds that L + g (∀, C) = 12 /55, realized on prior π = ( 5 /11, 0, 6 /11). Using g id , in contrast, the algorithm needs to solve 3 4 = 81 linear programming problems, and it finds that L + g id (∀, C) = 2 /5, realized on prior π = ( 1 /2, 1 /2, 0).

B. Additive capacity, fixed π -L +

∀ (π, C) Cor. 18 and Thm. 17 provide two equivalent ways to calculate L + ∀ (π, C), which we illustrate using the cancer channel. Given general prior π such that π x 1 = a and π x 2 = 1-a, we use Cor. 18 to calculate L + ∀ (π, C) using the expected earth moving metric as follows. We calculate first the Y marginal probabilities: the chance of observing a positive result is a×0.9 + (1-a) × 0.07 = 0.07+0.83a, and for negative result it is 0.93-0.83a. The corresponding posterior for observing a positive result, which we denote ν p , is given by ν p

x 1 = 0.9a/(0.07+0.83a) and ν p x 2 = 0.07(1-a)/(0.07+0.83a). There is a similar calculation for the negative posterior ν n . Next Cor. 18 directs us to calculate the Manhattan distance between π and ν p and π and ν n , and then to take the expected value over the above marginal. The distance between π and ν p is (|a-ν p x 1 | + |(1-a)-ν p x 2 |)/2, which simplifies to 0.83a(1-a)/(0.07+0.83a). Similarly the distance between π and ν n is 0.83a(1-a)/(0.93-0.83a). Finally taking the expected move we obtain 2 × 0.83a(1-a) = 1.66a(1-a). For the prior with a = 1 125 this is approximately 0.0132. An alternative but equivalent way to calculate L + ∀ (π, C) is given in the proof of Thm. 17, where we construct an optimising gain function that achieves additive capacity. Working through the definitions for this example we see that W is given by the four functions X→{-1, 1}. For each such function we construct g(w, x) = [w(x)x ′ π x ′ w(x ′ )]/2+1. Two of the four possibilities result in constants for g(w, x) (e.g. assigning 1 everywhere as x varies), and this corresponds to an overall additive leakage of 0. Hence only two functions from W correspond to options that participate in maximising over all leakage calculations. One maps x 1 to 1 and x 2 to -1, and the other is its "reflection" (multiply by -1). For the first, we see that g(w, x 1 ) = 2-a, and g(w, x 2 ) = 1-a. We summarise the situation by the following matrix: g cancer no cancer don't treat a a+1 treat 2-a 1-a One possible operational interpretation for this gain function is as follows. The result of the cancer test provides information for the health practitioner and the patient in order to make an informed decision about the best treatment plan. In this case the plan would normally consist of whether to recommend some form of direct medical intervention. The two gain strategies can therefore be thought of as putting a "cost" on either treating, or not treating the patient; that cost has either a high-or low gain for the patient depending on whether cancer is actually present. In the scenario where the patient is given direct medical intervention (row labelled "treat" in the matrix) there is therefore a strong positive gain for the patient who does have cancer, but relatively a low gain for the patient who does not have cancer but is given treatment anyway. Similarly in the scenario corresponding to deciding not to intervene (row labelled "don't treat"), there is a relatively low gain for the patient who does have cancer, but a positive gain for the patient who does not. With this interpretation, the additive capacity of 1.66a(1-a) gives the expected overall gain for the patient, and corresponds to the strategy of always offering treatment whenever the test is positive, but never when the test is negative.

We note that this gain function is 1-spanning and nonnegative; in a more realistic costing the difference between treating and not-treating would be obtained by shifting and scaling (see §IV), with the former having the option to assign negative gains in the case of no treatment being given when in fact the cancer is present.

C. General additive capacity -L +

∀ (∀, C) Computing the general additive capacity L + ∀ (∀, C) involves solving the optimisation problem set out at §VII-C. For |X|=2, this problem can be solved exactly and indeed the optimal prior is always uniform. This can be seen directly in the cancer channel above, where the capacity is the maximum value of 1.66a(1-a), where 0≤a≤1, giving a value of 1.66/4 = 0.415. When |X|>2, however, the optimal prior does not seem to be uniform in all cases: a graph plotted for the channel C y 1 y 2 y 3 x 1 0.4 0.5 0.1 x 2 0.6 0.1 0.3 x 3 0.2 0.2 0.6 shows that the optimal additive capacity occurs at approximately (0.44, 0.09, 0.47).

Finally, let C be the identity matrix on X (i.e. a perfect channel). Given prior π: DX, the hyper [π, C] produced by C consists of point distributions [x], each one with probability π x . Now for any x: X the earth-moving distance between π and [x] is 1-π x , since all of the mass of π needs to be moved onto x, except for what is already there. Hence the overall earth-moving distance, obtained by considering all x's in X, is 2 , and that is maximized by a uniform π, giving just 1-1 /|X|. (Interestingly, this is also the maximum additive leakage with respect to g id .) IX. Bounding "Dalenius" Leakage Here we consider the "Dalenius" scenario described in §V-C, establishing bounds on the leakage of a secret X that may be caused by a channel C from Y to Z, no matter what correlations may exist between X and Y. Our results, given in Cor. [START_REF] Köpf | Automatic quantification of cache side-channels[END_REF] and Cor. 23 below, follow from general results that we now develop for capacities of cascades of channels.

x (amount moved to [x])(distance moved to [x]) = x π x (1-π x ) = 1 -x (π x )
In the following lemmas etc. we assume that channel R: X→Z is a cascade of channels S : X→Y and T : Y→Z. The proofs will be presented for additive capacity; but, once established additively, the results hold easily for multiplicative capacity as well (Cor. 23).

Lemma 19: Left-capacity bound for cascade

For any prior ρ: DX and gain function g on X we have the inequality L + g (ρ, R) ≤ L + g (ρ, S ). Proof: This is a direct consequence of properties of a relation comparing information-flow between channels, described in recent and related work [START_REF] Mciver | Compositional closure for Bayes risk in probabilistic noninterference[END_REF], [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF], [START_REF] Mciver | Abstract channels and their robust information-leakage ordering[END_REF], [START_REF] Mciver | A Kantorovich-monadic powerdomain for information hiding, with probability and nondeterminism[END_REF]; it is a partial order which here we will call "secures." 14 The order has the property that, for any two channels C, C ′ , whenever C ′ secures C, we have L + g (π, C ′ )≤L + g (π, C) for all π, g (a corollary of [11, Thm. 6.2 generalised] and of [START_REF] Mciver | A Kantorovich-monadic powerdomain for information hiding, with probability and nondeterminism[END_REF]Thm. 8]). Furthermore, and conveniently for our purposes here, one of several (equivalent) presentations of that order [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF] is as follows:

C ′ secures C just when for some conformal channel M we have C ′ =CM (with the juxtaposition representing matrix multiplication, i.e. channel cascade).

Thus we can calculate

R = S T ⇒ R secures S "definition of information-flow order [11]" ⇒ V g [ρ, R] ≤ V g [ρ, S ] " [11, Thm. 6.2], above" ⇒ V g [ρ, R]-V g [ρ] ≤ V g [ρ, S ]-V g [ρ] ⇒ L + g (ρ, R) ≤ L + g (ρ, S ) . "definition L + ∀ (∀, )"
Lemma 20: Right-capacity bound for cascade For any prior ρ: DX we have L + ∀ (ρ, R) ≤ L + ∀ (τ, T ), where distribution τ: DY is the distribution of outputs in Y produced by channel S with prior ρ.

Proof: Let gain function g on X be arbitrary. We calculate

V g [ρ, R] . = z max w x ρ x R x,z g(w, x) "definition V" = z max w x ρ x ( y S x,y T y,z )g(w, x) "R = S T " = z max w y T y,z x ρ x S x,y g(w, x) " x y = x,y " = z max w y T y,z τ y h(w, y) "define τ, h so that τ y h(w, y) = x ρ x S x,y g(w, x)" = V h [τ, T ] . "definition V"
The key move obviously is the definition of τ, h in terms of ρ, g. We use a "temporary" Π: D(X×Y) like this: Π x,y = ρ x S x,y then τ y = x Π x.y and h(w, y) = x Π x,y g(w, x)/τ y .

Note that we have that h is 1-spanning, because g is. For each w there are L w , H w with H w -L w ≤1 and L w ≤g(w, x)≤H w for all

x, so that L w = x Π x,y L w /τ y ≤ h(w, y) ≤ x Π x,y H w /τ y = H w , from the definition of τ y . Now if you set T =O in the above, 15 then R=S O=O also, and you get

V g [ρ] = V g [ρ, O] = V h [τ, O] = V h [τ] ,
so that for any ρ, g there are τ, h with L + g (ρ, R) = L + h (τ, T ). And so L + ∀ (ρ, R) ≤ L + ∀ (τ, T ) as claimed. Those two lemmas give us this theorem about cascades:

Theorem 21: Capacity of cascades

If R: X→Z is a cascade of channels S : X→Y and T : Y→Z (as above) then

L + ∀ (∀, R) ≤ L + ∀ (∀, S ) min L + ∀ (∀, T )
, where we recall that L + ∀ (∀, •) is a supremum over all priors and all (1-spanning) gain-functions.

Proof: The result follows directly from Lemmas 19,20: simply take suprema on both sides to give L + ∀ (∀, R) ≤ L + ∀ (∀, S ) and L + ∀ (∀, R) ≤ L + ∀ (∀, T ) respectively. Now we can use Lem. 20 to give a bound on any "collateral" Dalenius leakage about some other X even when there is no direct link between C and X, i.e. if we are given only that there is some interesting joint distribution on X and Y that is somehow known to the observer.

Corollary 22: Dalenius bound

Consider as above a channel C: Y→Z and let π: DY a prior for C. Assume further that there is some other space X and a known joint distribution Π: D(X×Y) describing a correlation between X and Y. Note that π must in that case be the Y-marginal of Π.

Imagine an extended channel C * from X×Y to Z defined by C * (x,y),z = C y,z . Then (addressing the concern raised in §V-C) the "collateral leakage" that the imaginary C * causes wrt. the arbitrary X can be bounded independendently of X and the joint distribution Π it shares with Y. The bound depends only on C and π: we have L + ∀ (Π, C * ) ≤ L + ∀ (π, C), where the righthand side -the upper bound-does not depend on X and its relationship with Y beyond the (necessary) fact that π is the Y-marginal of Π.

Proof: Construct a deterministic "projection channel" P: X×Y → Y so that P (x,y),y ′ = (1 if y=y ′ else 0). Observe then that C * =PC, that π is the Y-output of C * wrt. prior Π, and apply Lem. 20.

Note from our conclusion L

+ ∀ (Π, C * ) ≤ L + ∀ (π, C)
we have in particular, for any "Y-ignoring" g * (w, (x, y)) = g(w, x) encoding an attacker's interest in X alone (i.e. not in Y at all), that the bound L + g * (Π, C * ) ≤ L + ∀ (π, C) applies. Finally, we note that the same results hold for multiplicative capacities:

Corollary 23:

For channels R: X→Z and S : X→Y and T : Y→Z, with R=S T , we have

Left-capacity bound L g (ρ, R) ≤ L g (ρ, S ) Right-capacity bound L ∀ (ρ, R) ≤ L ∀ (τ, S ) Capacity of cascades L ∀ (∀, R) ≤ L ∀ (∀, S ) min L ∀ (∀, T ) Dalenius bound L ∀ (Π, C * ) ≤ L ∀ (π, C) ,
where g, ρ, τ, C * , Π, π are as defined above.

Proof: The proofs of Lems. 19,20, of Thm. 21 and of Cor. 22 hold mutatis mutandis for multiplicative capacities. 16

X. Related work

As early as the 1950's, Shannon himself observed [START_REF] Shannon | The lattice theory of information[END_REF] that "[i]t is hardly expected that a single concept of information would satisfactorily account for the numerous possible applications of [information theory]." In the 90's, Cachin advocated [START_REF] Cachin | Entropy measures and unconditional security in cryptography[END_REF] that information metrics for security, or entropies, not only include a way to calculate some numeric value but also offer an operational interpretation, which describes what aspect of interest is being quantified. In recent years various metrics have been proposed for capturing the leakage of information in different operational scenarios. Work has been done on Shannon entropy [START_REF] Clark | Quantitative information flow, relations and polymorphic types[END_REF], [START_REF] Malacaria | Assessing security threats of looping constructs[END_REF], [START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF]- [START_REF] Alvim | Quantitative information flow in interactive systems[END_REF] guessing entropy [START_REF] Massey | Guessing and entropy[END_REF], [START_REF] Malacaria | Algebraic foundations for information theoretical, probabilistic and guessability measures of information flow[END_REF] and vulnerability or Bayes risk [START_REF] Smith | On the foundations of quantitative information flow[END_REF], [START_REF] Mciver | Compositional closure for Bayes risk in probabilistic noninterference[END_REF], [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF]. This plurality of metrics motivated researchers to look for some essential notion of information that would permeate all the various notions of entropy. Originally proposed by Landauer and Redmond [START_REF] Landauer | A lattice of information[END_REF], the Lattice of Information has been studied as an underlying algebraic structure for deterministic channels. And indeed, for deterministic channels, Yasuoka and Terauchi [START_REF] Yasuoka | Quantitative information flow -verification hardness and possibilities[END_REF] showed that the orderings on induced by Shannon entropy, guessing entropy, and vulnerability are all equivalent, and Malacaria [START_REF] Malacaria | Algebraic foundations for information theoretical, probabilistic and guessability measures of information flow[END_REF] showed that they coincide with the partition-refinement order in the lattice of partitions induced by such channels. However meaningful, these traditional entropies fail to capture a range of other relevant scenarios of interest, and the g-leakage framework proposed by Alvim et al. [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF], and McIver el al. [START_REF] Mciver | Compositional closure for Bayes risk in probabilistic noninterference[END_REF], models the operational scenario in which the channel executes by means of gain-functions. Given the wide range of possible gain functions and contexts, a robust comparison between channels is made via a strong g-leakage pre-order, which requires a channel never leak more than another, for any prior and gain function. It was shown in [START_REF] Mciver | Compositional closure for Bayes risk in probabilistic noninterference[END_REF], [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF] that composition refinement is a sufficient condition for the strong g-leakage pre-order in probabilistic channels. The converse was proved by McIver et al. [START_REF] Mciver | Compositional closure for Bayes risk in probabilistic noninterference[END_REF], [START_REF] Mciver | Abstract channels and their robust information-leakage ordering[END_REF], so establishing the complete coincidence between composition refinement and the strong g-leakage pre-order. Hence that ordering is a compelling generalization to probabilistic channels of the partition refinement on deterministic channels. Furthermore, [START_REF] Mciver | Abstract channels and their robust information-leakage ordering[END_REF] introduces abstract channels, which quotient over the abstract redundancies of the traditional channel representations. The authors show that composition refinement is a partial order on abstract channels, but not on channel matrices, and hence that the abstraction provides a more adequate representation for probabilistic systems in general.

Finally, Braun, Chatzikokolakis, and Palamidessi [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF] show that multiplicative and additive min-entropy leakage orderings are equivalent when comparing two channels on a given prior. However, when channels are compared with respect to their capacity (over all priors), multiplicative and additive leakage can produce inconsistent results. 16 In fact the capacity of cascades in the multiplicative case also follows directly from Theorem 6 of [START_REF] Espinoza | Min-entropy as a resource[END_REF] and the Miracle Theorem.

XI. Conclusions and future work

We have studied robustness for leakage measurements by defining additive-and multiplicative capacities; and we have argued that both play an important role in assessing the severity of information flows. Our definitions are based on the relatively new approach of gain functions, which have been shown to capture a surprisingly wide range of attacker scenarios; and the corresponding capacity measurements thus apply automatically to all of those. Further, we have argued that robustness of leakage measurements is especially useful when our knowledge is limited, either about the prior or about the cost/benefit scenarios of an attacker, or both. Surprisingly, even in the case of unknown and essentially unpredictable correlations with apparently unrelated data -the "Dalenius" scenario-we have been able to contribute novel limits on the information flow that can result.

Our current definitions of additive capacity use 1-spanning gain functions; this is primarily due to a 1-Lipschitz condition associated with the Kantorovich metric [START_REF] Deng | The Kantorovich Metric in computer science: A brief survey[END_REF], [START_REF] Mciver | A Kantorovich-monadic powerdomain for information hiding, with probability and nondeterminism[END_REF] and is what enables our connection of the latter with the additive gcapacity. In future work we plan to investigate other metrics which would yield similarly efficient algorithms for computing capacity, but which could express more conveniently other notions of leakage (such as that based on Shannon). Finally we plan to investigate approximation algorithms for L + ∀ (∀, C).

Fix π, π ′ : DX; define X + ={x: X | π x ≥ π ′ x } and X -=X \ X + . From π = π ′ = 1 we have

x: X + (π x -π ′ x ) = x: X -(π ′ x -π x ) = 1 /2 x |π x -π ′ x | = K DX (π, π ′ ). ( 10
)
Given a guess w: W, we define g(w, ⊤) = max ≤ K DX (π, π ′ ) .

"g is 1-spanning Def. 3"

Now we recall that V g [π] = sup w f w (π), and so it remains only to show that the supremum preserves the 1-Lipschitz property.

So let F be a set of functions A→R that are 1-Lipschitz wrt some metric d on A. We show that F(a) = sup f : F f (a) is also 1-Lipschitz. Fixing a, a ′ : A, assume wlog that F(a)≥F(a ′ ); we have

|F(a) -F(a ′ )| = sup f f (a) -sup f f (a ′ ) "definition F; F(a) ≥ F(a ′ )" ≤ sup f ( f (a) -f (a ′ )) "-sup f ′ f ′ (a ′ ) ≤ -f (a ′ )" ≤ sup f | f (a) -f (a ′ )| ≤ sup f d(a, a ′ ) " f is 1-Lipschitz wrt d" = d(a, a ′ ) .

B. Calculation of Kantorovich distance from [π] to [π, C] (from §VII-C)

The Manhattan distance between two vectors of equal dimension (e.g. distributions in DX) is the sum of the nonnegative differences between them in each dimension, by analogy with the distance needed to travel between two intersections in a city of regular blocks (like Manhattan). Thus we have

C. Existence of g-function for Thm. 17 (from §VII-B)

Here we show that the g-function quoted in the proof of Thm. 17 has the property claimed:

x τ x g(w, x) =

x τ x (1 + (w(x)x ′ π x ′ w(x ′ ))/2) "definition g" = ( x τ x w(x)x τ x x ′ π x ′ w(x ′ ))/2 + 1 " x τ x = 1" = ( x τ x w(x)x ′ π x ′ w(x ′ ))/2 + 1 " x τ x = 1" = x (τ x -π x )w(x)/2 + 1 .

"rename x ′ to x"

  between [π] and [π, C]. Remarkably, this insight enables us to compute L + ∀ (π, C) in time linear in the size of C.

  x g(w, x) and g(w, ⊥) = min x g(w, x) , and then define the function f w : DX→R asf w (π) = E π g(w, •) =x π x g(w, x) . We first show that f w is 1-Lipschitz, as follows:| f w (π)f w (π ′ )| = | x (π x -π ′ x )g(w, x)| "definition of f w " = | x: X + (π x -π ′ x )g(w, x)x: X -(π ′ x -π x )g(w, x)| "rewrite sum" ≤ | x: X + (π x -π ′ x )g(w, ⊤)x: X -(π ′ x -π x )g(w, ⊥)|"definition g(w, ⊤), g(w, ⊥) above"= K DX (π, π ′ ) |g(w, ⊤)g(w, ⊥)| " (10) "

K D 2 X

 2 ([π], [π, C]) = 1/2 y p(y)(Manhattan distance from p X to p X|y ) = 1/2 y p(y) x |p X (x)p X|y (x)| = 1/2 y p(y) x |π xp(x, y)/p(y)| = 1/2 x,y |π x p(y)p(x, y)| = 1/2 x,y π x |p(y) -C x,y | = 1/2 x,y π x |C x,yx ′ π x ′ C x ′ ,y | .

Where the upper-case Greek-and Roman letters are the same, we will write the Greek in sans-serif: thus upper-case τ would be T.

Note that the characteristic function of the support set is indeed the ceiling of the distribution as a function.

We write lg for log 2 (Knuth).

The more usual notation for these quantities is H(X), H(X|Y), and I(X; Y). We explain at the end of §II why we use brackets[•].

For Shannon entropy, this follows from a result by Massey[START_REF] Massey | Guessing and entropy[END_REF].

There might be fewer posteriors in the support of hyper [π, C] than there are columns in the joint distribution Π from which it derives, because if several columns of Π normalise to the same posterior then the hyper will automatically coalesce them[START_REF] Mciver | Abstract channels and their robust information-leakage ordering[END_REF]: columns y 2 and y 3 were coalesced in this case.

On the other hand, increasing vulnerability from 0.000001 to 0.300001 is far more significant than increasing it from 0.4 to 0.7, even though both give additive leakage of 0.3. Perhaps we could say, roughly speaking, that leakage is 'significant' only if both the multiplicative-and additive leakage are 'large'.

Theorem 4.1 of[START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF] says that we always have V g (π, C) ≥ V g (π). It remains true even if gain values are allowed to be negative, which means that additive leakage will always be non-negative.

It is worth noting that this theorem is fundamentally different from the intractability results of[START_REF] Yasuoka | Quantitative information flow -verification hardness and possibilities[END_REF]-those results assume that the channel is represented as a program, which inevitably leads to intractability of analysis. In contrast, our theorem is based on the channel matrix, which gives the channel's behaviour explicitly.

Note that if ∅ ∈ U, we do not actually get a channel matrix, since ∅ leads to an all-zero row. But in this case notice that U contains k pairwise disjoint sets iff U-{∅} contains k-1 pairwise disjoint sets.

In fact, the Set-Packing problem remains NP-complete even if all sets in U have cardinality at most 3 [34, p. 221].

We write O because it is a right-zero of channel cascading.

In[START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF],[START_REF] Mciver | Abstract channels and their robust information-leakage ordering[END_REF] we wrote more-secure ⊑ • less-secure, by analogy with refinement of partitions making them less secure. In[START_REF] Mciver | Compositional closure for Bayes risk in probabilistic noninterference[END_REF],[START_REF] Mciver | A Kantorovich-monadic powerdomain for information hiding, with probability and nondeterminism[END_REF] we wrote less-secure ⊑ more-secure, since refinement of programs makes them more secure. This unlucky opposition is why we just call it "secures" here.

Acknowledgments Geoffrey Smith was partially supported by the National Science Foundation under grant CNS-1116318. McIver and Morgan were supported by the Australian Research Council under grant DP120101413. NICTA is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program. Also, the authors are grateful for support from Digiteo and the INRIA équipe associée Princess.

Appendix

A. Technical lemmas on gain functions (from §IV and §VII)

Lem. [START_REF] Dalenius | Towards a methodology for statistical disclosure control[END_REF] shows how to express the vulnerability as a standard expected value of a function over a hyper, and is a general result we use repeatedly.

Lemma 24:

Let C: X×Y→R be a channel, and g a gain function and π a prior. Then we have

Proof:

The left-hand side just above is interpreted at (4) as an expected value on the distribution p Y of a random variable F: Y→R defined F(y) = V g (p X|y ), where the joint distribution Π wrt. which p Y , p X|y are defined is the usual one induced by channel C's action on the prior π.

We want to establish that the construction can equally well be interpreted as acting on a hyper directly: the [π, C] on the right-hand side just above is the hyper defined by Π, and one way of formulating that hyper is as the push forward of a function G(y) = p X|y acting on p Y , typically written G * (p Y ). And then the entire right-hand side is the expected value

Once we observe that F is the functional composition V g •G, the result follows from a general equality relating expected value and push-forward, that

Further details about hypers and their relation to joint distributions can be found at [START_REF] Mciver | Compositional closure for Bayes risk in probabilistic noninterference[END_REF], [START_REF] Mciver | Abstract channels and their robust information-leakage ordering[END_REF], [START_REF] Mciver | A Kantorovich-monadic powerdomain for information hiding, with probability and nondeterminism[END_REF]. Now we can use standard properties of expected values to verify our gain function algebra.

Lemma 25: Gain function algebra ( §IV) Recall the definitions from ( 5) and ( 6) in §IV:

The general proof strategy for these properties is to use distribution of addition and multiplication through the expectation operator. Note however that this expectation operator acts at the level of hypers and therefore most of the proofs are concerned with translating V g [π, C] into that form.

We use 0 in gain function expressions to represent the gain function that returns the value 0 for all values of w, x. This allows us to write V g +k@x ′ as V g + V 0 +k@x ′ , because the modification of g to g +k@x ′ does not affect the (maximising) choice of w. Our three proofs are now as follows:

x-Shift:

Global Shift: This follows from the proof of x-Shift since a global shift is simply an x-shift for each value of x in X.

Scaling: This follows from observing that V g ×k = kV g when k>0, and then using the fact that multiplication distributes through the expectation operator.

The next result Lem. 26 is used for Lem. 14 from §VII.

Lemma 26: 1-spanning implies 1-Lipschitz If g is 1-spanning then V g is 1-Lipschitz (wrt K DX ), considered as a function DX→R.

Proof: (Note that the proof does not assume a finite W.)