Leakage and Protocol Composition in a
Game-Theoretic Perspective
1

2

3Mário S. Alvim , Konstantinos Chatzikokolakis , Yusuke Kawamoto , and4
Catuscia Palamidessi
1

Universidade Federal de Minas Gerais, Belo Horizonte, Brazil
2
CNRS and École Polytechnique, Palaiseau, France
3
AIST, Tsukuba, Japan
4
INRIA and École Polytechnique, Palaiseau, France

Abstract. In the inference attacks studied in Quantitative Information
Flow (QIF), the adversary typically tries to interfere with the system in
the attempt to increase its leakage of secret information. The defender,
on the other hand, typically tries to decrease leakage by introducing some
controlled noise. This noise introduction can be modeled as a type of protocol composition, i.e., a probabilistic choice among different protocols,and its effect on the amount of leakage depends heavily on whether or
not this choice is visible to the adversary. In this work we consider operators for modeling visible and invisible choice in protocol composition,
and we study their algebraic properties. We then formalize the interplay
between defender and adversary in a game-theoretic framework adapted
to the specific issues of QIF, where the payoff is information leakage. We
consider various kinds of leakage games, depending on whether players
act simultaneously or sequentially, and on whether or not the choices ofthe defender are visible to the adversary. Finally, we establish a hierarchy of these games in terms of their information leakage, and provide
methods for finding optimal strategies (at the points of equilibrium) for
both attacker and defender in the various cases.

1

Introduction

A fundamental problem in computer security is the leakage of sensitive information due to correlation of secret values with observables—i.e., any information
accessible to the attacker, such as, for instance, the system’s outputs or execution time. The typical defense consists in reducing this correlation, which canbe done in, essentially, two ways. The first, applicable when the correspondence
secret-observable is deterministic, consists in coarsening the equivalence classesof secrets that give rise to the same observables. This can be achieved with
post-processing, i.e., sequentially composing the original system with a programthat removes information from observables. For example, a typical attack on encrypted web traffic consists on the analysis of the packets’ length, and a typicaldefense consists in padding extra bits so to diminish the length variety [28].

The second kind of defense, on which we focus in this work, consists in adding
controlled noise to the observables produced by the system. This can be usuallyseen as a composition of different protocols via probabilistic choice.
Example 1 (Differential privacy). Consider a counting query f , namely a function that, applied to a dataset x, returns the number of individuals in x thatsatisfy a given property. A way to implement differential privacy [12] is to add
geometrical noise to the result of f , so to obtain a probability distribution P on
∣z−f (x)∣integers of the form P (z) = c e, where c is a normalization factor. The
resulting mechanism can be interpreted as a probabilistic choice on protocols of
the form f (x), f (x)+1, f (x)+2, . . . , f (x)−1, f (x)−2, . . ., where the probability
assigned to f (x) + n and to f (x) − n decreases exponentially with n.
Example 2 (Dining cryptographers). Consider two agents running the dining
cryptographers protocol [11], which consists in tossing a fair binary coin andthen declaring the exclusive or ⊕ of their secret value x and the result of thecoin. The protocol can be thought as the fair probabilistic choice of two protocols, one consisting simply of declaring x, and the other declaring x ⊕ 1.
Most of the work in the literature of quantitative information flow (QIF)
considers passive attacks, in which the adversary only observes the system. Notable exceptions are the works [8,21,4], which consider attackers who interact
with and influence the system, possibly in an adaptive way, with the purpose of
maximizing the leakage of information.
Example 3 (CRIME attack). Compression Ratio Info-leak Made Easy (CRIME)[25] is a security exploit against secret web cookies over connections using the
HTTPS and SPDY protocols and data compression. The idea is that the attacker
can inject some content a in the communication of the secret x from the target
site to the server. The server then compresses and encrypts the data, including
both a and x, and sends back the result. By observing the length of the result,the attacker can then infer information about x. To mitigate the leakage, one
possible defense would consist in transmitting, along with x, also an encryption
method f selected randomly from a set F . Again, the resulting protocol can beseen as a composition, using probabilistic choice, of the protocols in the set F .
In all examples above the main use of the probabilistic choice is to obfuscate
the relation between secrets and observables, thus reducing their correlation—
and, hence, the information leakage. To achieve this goal, it is essential that theattacker never comes to know the result of the choice. In the CRIME example, however, if f and a are chosen independently, then (in general) it is still
better to choose f probabilistically, even if the adversary will come to know,
afterwards, the choice of f . In fact, this is true also for the attacker: his best
strategies (in general) are to chose a according to some probability distribution.
Indeed, suppose that F = {f1 , f2 } are the defender’s choices and A = {a1 , a2 }are the attacker’s, and that f1 (⋅, a1 ) leaks more than f1 (⋅, a2 ), while f2 (⋅, a1 )leaks less than f2 (⋅, a2 ). This is a scenario like the matching pennies in game2

theory: if one player selects an action deterministically, the other player may
exploit this choice and get an advantage. For each player the optimal strategy
is to play probabilistically, using a distribution that maximizes his own gain for
all possible actions of the adversary. In zero-sum games, in which the gain of
one player coincides with the loss of the other, the optimal pair of distributions
always exists, and it is called saddle point. It also coincides with the Nash equilibrium, which is defined as the point in which neither of the two players getsany advantage in changing unilaterally his strategy.
Motivated by these examples, this paper investigates the two kinds of choice,visible and hidden (to the attacker), in a game-theoretic setting. Looking atthem as language operators, we study their algebraic properties, which will help
reason about their behavior in games. We consider zero-sum games, in which thegain (for the attacker) is represented by the leakage. While for visible choice it
is appropriate to use the “classic” game-theoretic framework, for hidden choice
we need to adopt the more general framework of the information leakage games
proposed in [4]. This happens because, in contrast with standard game theory,in games with hidden choice the utility of a mixed strategy is a convex function of the distribution on the defender’s pure actions, rather than simply the
expected value of their utilities. We will consider both simultaneous games—in
which each player chooses independently—and sequential games— in which one
player chooses his action first. We aim at comparing all these situations, and at
identifying the precise advantage of the hidden choice over the visible one.
To measure leakage we use the well-known information-theoretic model. A
central notion in this model is that of entropy, but here we use its converse, vulnerability, which represents the magnitude of the threat. In order to derive results
as general as possible, we adopt the very comprehensive notion of vulnerability
as any convex and continuous function, as used in [8] and [5]. This notion has
been shown [5] to subsume most information measures, including Bayes vulnerability (aka min-vulnerability, aka (the converse of) Bayes risk) [27,10], Shannon
entropy [26], guessing entropy [22], and g-vulnerability [6].
The main contributions of this paper are:
– We present a general framework for reasoning about information leakage ina game-theoretic setting, extending the notion of information leakage games
proposed in [4] to both simultaneous and sequential games, with either hidden or visible choice.
– We present a rigorous compositional way, using visible and hidden choice
operators, for representing adversary and defender’s actions in information
leakage games. In particular, we study the algebraic properties of visible andhidden choice on channels, and compare the two kinds of choice with respect
to the capability of reducing leakage, in presence of an adaptive attacker.
– We provide a taxonomy of the various scenarios (simultaneous and sequential) showing when randomization is necessary, for either attacker or defender, to achieve optimality. Although it is well-known in information flowthat the defender’s best strategy is usually randomized, only recently it has
3been shown that when defender and adversary act simultaneously, the adversary’s optimal strategy also requires randomization [4].
– We use our framework in a detailed case study of a password-checking protocol. The naive program, which checks the password bit by bit and stops
when it finds a mismatch, is clearly very insecure, because it reveals at eachattempt the maximum correct prefix. On the other hand, if we continue
checking until the end of the string (time padding), the program becomesvery inefficient. We show that, by using probabilistic choice instead, we canobtain a good trade-off between security and efficiency.
Plan of the paper. The remaining of the paper is organized as follows. In Section 2
we review some basic notions of game theory and quantitative information flow.
In Section 3 we introduce our running example. In Section 4 we define the visible and hidden choice operators and demonstrate their algebraic properties. In
Section 5, the core of the paper, we examine various scenarios for leakage games.
In Section 6 we show an application of our framework to a password checker. In
Section 7 we discuss related work and, finally, in Section 8 we conclude.

2

Preliminaries

In this section we review some basic notions from game theory and quantitative
information flow. We use the following notation: Given a set I, we denote by
DI the set of all probability distributions over I. Given µ ∈ DI, its support
def
supp(µ) = {i ∈ I ∶ µ(i) > 0} is the set of its elements with positive probability.
We use i←µ to indicate that a value i∈I is sampled from a distribution µ on I.
2.1

Basic concepts from game theory

Two-player games Two-player games are a model for reasoning about the
behavior of two players. In a game, each player has at its disposal a set ofactions that he can perform, and he obtains some gain or loss depending on theactions chosen by both players. Gains and losses are defined using a real-valued
payoff function. Each player is assumed to be rational, i.e., his choice is driven by
the attempt to maximize his own expected payoff. We also assume that the set of
possible actions and the payoff functions of both players are common knowledge.
In this paper we only consider finite games, in which the set of actions available to the players are finite. Next we introduce an important distinction between
simultaneous and sequential games. In the following, we will call the two players
defender and attacker.
Simultaneous games In a simultaneous game, each player chooses his action
without knowing the action chosen by the other. The term “simultaneous” here
does not mean that the players’ actions are chosen at the same time, but only4

5

that they are chosen independently. Formally, such a game is defined as a tuple(D, A, ud , ua ), where D is a nonempty set of defender’s actions, A is a nonempty
set of attacker’s actions, ud ∶ D × A → R is the defender’s payoff function, andua ∶ D × A → R is the attacker’s payoff function.
Each player may choose an action deterministically or probabilistically. A
pure strategy of the defender (resp. attacker) is a deterministic choice of an action, i.e., an element d ∈ D (resp. a ∈ A). A pair (d, a) is called pure strategy
profile, and ud (d, a), ua (d, a) represent the defender’s and the attacker’s payoffs,
respectively. A mixed strategy of the defender (resp. attacker) is a probabilistic choice of an action, defined as a probability distribution δ ∈ DD (resp.
α ∈ DA). A pair (δ, α) is called mixed strategy profile. The defender’s andthe attacker’s expected payoff functions for mixed strategies are defined, respecdef
deftively, as: Ud (δ, α) = E d←δ ud (d, a) = ∑d∈D δ(d)α(a)ud (d, a) and Ua (δ, α) =a←αE d←δ ua (d, a) = ∑d∈D δ(d)α(a)ua (d, a).
a←α

a∈A

a∈A

A defender’s mixed strategy δ ∈ DD is a best response to an attacker’s mixed′
strategy α ∈ DA if Ud (δ, α) = maxδ′ ∈DD Ud (δ , α). Symmetrically, α ∈ DA is′a best response to δ ∈ DD if Ua (δ, α) = maxα′ ∈DA Ud (δ, α ). A mixed-strategy∗∗∗∗
Nash equilibrium is a profile (δ , α ) such that δ is the best response to α
and vice versa. This means that in a Nash equilibrium, no unilateral deviation∗∗
by any single player provides better payoff to that player. If δ and α are∗∗point distributions concentrated on some d ∈ D and a ∈ A respectively, then∗∗∗ ∗(δ , α ) is a pure-strategy Nash equilibrium, and will be denoted by (d , a ).
While not all games have a pure strategy Nash equilibrium, every finite gamehas a mixed strategy Nash equilibrium.

Sequential games In a sequential game players may take turns in choosing
their actions. In this paper, we only consider the case in which each player
moves only once, in such a way that one of the players (the leader ) chooses his
action first, and commits to it, before the other player (the follower ) makes his
choice. The follower may have total knowledge of the choice made by the leader,or only partial. We refer to the two scenarios by the terms perfect and imperfect
information, respectively.
We now give the precise definitions assuming that the leader is the defender.
The case in which the leader is the attacker is similar.
A defender-first sequential game with perfect information is a tuple (D,D → A, ud , ua ) where D, A, ud and ua are defined as in simultaneous games.
Also the strategies of the defender (the leader) are defined as in simultaneous games: an action d ∈ D for the pure case, and a distribution δ ∈ DD forthe mixed one. On the other hand, a pure strategy for the attacker is a function sa ∶ D → A, which represents the fact that his choice of an action sa in A
depends on the defender’s choice d. An attacker’s mixed strategy is a probabil5

Following the convention of security games, we set the first player to be the defender.

5

6

ity distribution σa ∈ D(D → A) over his pure strategies. The defender’s andthe attacker’s expected payoff functions for mixed strategies are defined, respecdef
tively, as Ud (δ, σa ) = E d←δ ud (d, sa (d)) = ∑ d∈D δ(d)σa (sa )ud (d, sa (d)) andsa ∶D → Asa ←σadef

Ua (δ, σa ) = E d←δ ua (d, sa (d)) = ∑sa ←σad∈D δ(d)σa (sa )ua (d, sa (d)).
sa ∶D → A

The case of imperfect information is typically formalized by assuming an
indistinguishability (equivalence) relation over the actions chosen by the leader,
representing a scenario in which the follower cannot distinguish between theactions belonging to the same equivalence class. The pure strategies of the followers, therefore, are functions from the set of the equivalence classes on theactions of the leader to his own actions. Formally, a defender-first sequential
game with imperfect information is a tuple (D, Ka → A, ud , ua ) where D, A,
ud and ua are defined as in simultaneous games, and Ka is a partition of D. The
expected payoff functions are defined as before, except that now the argumentof sa is the equivalence class of d. Note that in the case in which all defender’sactions are indistinguishable from each other at the eyes of the attacker (totallyimperfect information), we have Ka = {D} and the expected payoff functions
coincide with those of the simultaneous games.
Zero-sum games and Minimax Theorem A game (D, A, ud , ua ) is zero-sum
if for any d ∈ D and any a ∈ A, the defender’s loss is equivalent to the attacker’s
gain, i.e., ud (d, a) = −ua (d, a). For brevity, in zero-sum games we denote by u7
the attacker’s payoff function ua , and by U the attacker’s expected payoff Ua .
Consequently, the goal of the defender is to minimize U , and the goal of theattacker is to maximize it.
In simultaneous zero-sum games the Nash equilibrium corresponds to the solution of the minimax problem (or equivalently, the maximin problem), namely,∗∗∗∗
the strategy profile (δ , α ) such that U (δ , α ) = minδ maxα U (δ, α). The von
Neumann’s minimax theorem, in fact, ensures that such solution (which always
exists) is stable.
m

Theorem 1 (von Neumann’s minimax theorem) Let X ⊂ R and Y ⊂nR be compact convex sets, and U ∶ X × Y → R be a continuous function suchthat U (x, y) is a convex function in x ∈ X and a concave function in y ∈ Y.
Then minx∈X maxy∈Y U (x, y) = maxy∈Y minx∈X U (x, y).
A related property is that, under the conditions of Theorem 1, there exists a
∗ ∗
∗
∗ ∗
∗
saddle point (x , y ) s.t., for all x∈X and y∈Y: U (x , y)≤U (x , y )≤U (x, y ).
6

The definition of the mixed strategies as D(D → A) means that the attacker draws
a function sa ∶ D → A before he knows the choice of the defender. In contrast, theso-called behavioral strategies are defined as functions D → DA, and formalize theidea that the draw is made after the attacker knows such choice. In our setting, thesetwo definitions are equivalent, in the sense that they yield the same payoff.
7
Conventionally in game theory the payoff u is set to be that of the first player, but
we prefer to look at the payoff from the point of view of the attacker to be in linewith the definition of payoff as vulnerability.

6

The solution of the minimax problem can be obtained by using convex optimization techniques. In case U (x, y) is affine in x and in y, we can also use
linear optimization.
In case D and A contain two elements each, there is a closed form for thesolution. Let D = {d0 , d1 } and A = {a0 , a1 } respectively. Let uij be the utility of∗∗∗the defender on di , aj . Then the Nash equilibrium (δ , α ) is given by: δ (d0 ) =∗(u11 −u10 )/(u00 −u01 −u10 +u11 ) and α (a ) = (u11 −u01 )/(u00 −u01 −u10 +u11 ) if these values0∗
are in [0, 1]. Note that, since there are only two elements, the strategy δ is∗completely specified by its value in d0 , and analogously for α .
2.2

Quantitative information flow

Finally, we briefly review the standard framework of quantitative information
flow, which is concerned with measuring the amount of information leakage in a(computational) system.
Secrets and vulnerability A secret is some piece of sensitive information the
defender wants to protect, such as a user’s password, social security number, or
current location. The attacker usually only has some partial knowledge about
the value of a secret, represented as a probability distribution on secrets calleda prior. We denote by X the set of possible secrets, and we typically use π todenote a prior belonging to the set DX of probability distributions over X .
The vulnerability of a secret is a measure of the utility that it represents forthe attacker. In this paper we consider a very general notion of vulnerability,
following [5], and we define a vulnerability V to be any continuous and convex
function of type DX → R. It has been shown in [5] that these functions coincidewith the set of g-vulnerabilities, and are, in a precise sense, the most general
8
information measures w.r.t. a set of basic axioms.
Channels, posterior vulnerability, and leakage Computational systems can bemodeled as information theoretic channels. A channel C ∶ X × Y → R is afunction in which X is a set of input values, Y is a set of output values, andC(x, y) represents the conditional probability of the channel producing outputy ∈ Y when input x ∈ X is provided. Every channel C satisfies 0 ≤ C(x, y) ≤ 1
for all x ∈ X and y ∈ Y, and ∑y∈Y C(x, y) = 1 for all x ∈ X .
A distribution π ∈ DX and a channel C with inputs X and outputs Y
induce a joint distribution p(x, y) = π(x)C(x, y) on X × Y, producing joint
random variables X, Y with marginal probabilities p(x) = ∑y p(x, y) and p(y) =∑x p(x, y), and conditional probabilities p(x∣y) = p(x,y)/p(y) if p(y) ≠ 0. For agiven y (s.t. p(y) ≠ 0), the conditional probabilities p(x∣y) for each x ∈ X form
the posterior distribution pX∣y .
8More precisely, if posterior vulnerability is defined as the expectation of the vulnerability of posterior distributions, the measure respects the data-processing inequality
and always yields non-negative leakage iff vulnerability is convex.

7

A channel C in which X is a set of secret values and Y is a set of observablevalues produced by a system can be used to model computations on secrets.
Assuming the attacker has prior knowledge π about the secret value, knows
how a channel C works, and can observe the channel’s outputs, the effect of thechannel is to update the attacker’s knowledge from π to a collection of posteriorspX∣y , each occurring with probability p(y).
Given a vulnerability V, a prior π, and a channel C, the posterior vulnerability
V [π, C] is the vulnerability of the secret after the attacker has observed thedefoutput of the channel C. Formally: V [π, C] = ∑y∈Y p(y)V [pX∣y ].
It is known from the literature [5] that the posterior vulnerability is a convex
function of π. Namely, for any channel C, any family of distributions {πi }, andany set of convex coefficients {ci }, we have: V [∑i ci πi , C] ≤ ∑i ci V [πi , C].
The (information) leakage of channel C under prior π is a comparison between the vulnerability of the secret before the system was run—called priorvulnerability—and the posterior vulnerability of the secret. Leakage reflects by
how much the observation of the system’s outputs increases the attacker’s information about the secret. It can be defined either additively (V [π, C] − V [π]),or multiplicatively (V[π,C]/V[π]).

3An illustrative example

We introduce an example which will serve as run- Program 0ning example through the paper. Although admit- High Input: x ∈ {0, 1}
tedly contrived, this example is simple and yet pro- Low Input: a ∈ {0, 1}
duces different leakage measures for all different com- Output: y ∈ {0, 1}
binations of visible/invisible choice and simultane- y = x ⋅ aous/sequential games, thus providing a way to com- return ypare all different scenarios we are interested in.
Program 1
Consider that a binary secret must be processedby a program. As usual, a defender wants to protect High Input: x ∈ {0, 1}
Low Input: a ∈ {0, 1}
the secret value, whereas an attacker wants to infer
Output: y ∈ {0, 1}
it by observing the system’s output. Assume the dec ← flip coin with bias a/3
fender can choose which among two alternative ver- if c = heads {y = x}sions of the program to run. Both programs take the else {y = x̄}secret value x as high input, and a binary low input return ya whose value is chosen by the attacker. They bothFig. 1. Running example.
9
return the output in a low variable y. Program 0
returns the binary product of x and a, whereas Program 1 flips a coin with bias
a/3 (i.e., a coin which returns heads with probability a/3) and returns x if theresult is heads, and the complement x̄ of x otherwise. The two programs are
represented in Figure 1.
9

We adopt the usual convention in QIF of referring to secret variables, inputs andoutputs in programs as high, and to their observable counterparts as low.

8

The combined choices of the defender’s and of the attacker’s determine how
the system behaves. Let D={0, 1} represent the set of the defender’s choices—
i.e., the index of the program to use—, and A = {0, 1} represent the set ofthe attacker’s choices—i.e., the value of the low input a. We shall refer to theelements of D and A as actions. For each possible combination of actions d ∈ D
and a ∈ A, we can construct a channel Cda modeling how the resulting systembehaves. Each channel Cda is a function of type X × Y → R, where X = {0, 1}
is the set of possible high input values for the system, and Y = {0, 1} is the setof possible output values from the system. Intuitively, each channel provides theprobability that the system (which was fixed by the defender) produces outputy ∈ Y given that the high input is x ∈ X (and that the low input was fixed by
the attacker). The four possible channels are depicted as matrices below.
C00 y = 0 y = 1
x=0 1
0
x=1 1
0

C01 y = 0 y = 1
x=0 1
0
x=1 0
1

C10 y = 0 y = 1
x=0 0
1
x=1 1
0

C11 y = 0 y = 1
x = 0 1/3 2/3
x = 1 2/3 1/3

Note that channel C00 does not leak any information about the input x (i.e., it
is non-interferent), whereas channels C01 and C10 completely reveal x. Channel
C11 is an intermediate case: it leaks some information about x, but not all.
We want to investigate how the defender’s and the attacker’s choices influence
the leakage of the system. For that we can just consider the (simpler) notion ofposterior vulnerability, since in order to make the comparison fair we need toassume that the prior is always the same in the various scenarios, and this
implies that the leakage is in a one-to-one correspondence with the posterior
vulnerability (this happens for both additive and multiplicative leakage).
For this example, assume we are interV a=0a=1
ested in Bayes vulnerability [10,27], definedd = 0 1/2
1
as V(π) = maxx π(x) for every π ∈ DX .
2/3
d=1 1
Assume for simplicity that the prior is theuniform prior πu . In this case we know from
Table 1. Vulnerability of each chan[9] that the posterior Bayes vulnerability of nel C in the running example.
daa channel is the sum of the greatest elementsof each column, divided by the total number of inputs. Table 1 provides the Bayesdefvulnerability Vda = V [πu , Cda ] of each channel considered above.
Naturally, the attacker aims at maximizing the vulnerability of the system,
while the defender tries to minimize it. The resulting vulnerability will depend
on various factors, in particular on whether the two players make their choicesimultaneously (i.e. without knowing the choice of the opponent) or sequentially.
Clearly, if the choice of a player who moves first is known by an opponent whomoves second, the opponent will be in advantage. In the above example, forinstance, if the defender knows the choice a of the attacker, the most convenient
choice for him is to set d = a, and the vulnerability will be at most 2/3 . Viceversa, if the attacker knows the choice d of the defender, the most convenient
choice for him is to set a ≠ d. The vulnerability in this case will be 1.
Things become more complicated when players make choices simultaneously.
None of the pure choices of d and a are the best for the corresponding player,
9because the vulnerability of the system depends also on the (unknown) choiceof the other player. Yet there is a strategy leading to the best possible situation
for both players (the Nash equilibrium), but it is mixed (i.e., probabilistic), inthat the players randomize their choices according to some precise distribution.
Another factor that affects vulnerability is whether or not the defender’schoice is known to the attacker at the moment in which he observes the outputof the channel. Obviously, this corresponds to whether or not the attacker knows
what channel he is observing. Both cases are plausible: naturally the defender
has all the interest in keeping his choice (and, hence, the channel used) secret,since then the attack will be less effective (i.e., leakage will be smaller). On theother hand, the attacker may be able to identify the channel used anyway, forinstance because the two programs have different running times. We will callthese two cases hidden and visible choice, respectively.
It is possible to model players’ strategies, as well as hidden and visible choices,
as operations on channels. This means that we can look at the whole system as
if it were a single channel, which will turn out to be useful for some proofs of ourtechnical results. Next section is dedicated to the definition of these operators.
We will calculate the exact values for our example in Section 5.

4

Visible and hidden choice operators on channels

In this section we define matrices and some basic operations on them. Sincechannels are a particular kind of matrix, we use these matrix operations todefine the operations of visible and hidden choice among channels, and to prove
important properties of these channel operations.

4.1

Matrices, and their basic operators

Given two sets X and Y, a matrix is a total function of type X × Y → R.
Two matrices M1 ∶ X1 × Y1 → R and M2 ∶ X2 × Y2 → R are said to becompatible if X1 = X2 . If it is also the case that Y1 = Y2 , we say that thematrices have the same type. The scalar multiplication r⋅M between a scalar r
and a matrix M is defined as usual, and so is the summation (∑i∈I Mi ) (x, y) =Mi1 (x, y) + . . . + Min (x, y) of a family {Mi }i∈I of matrices all of a same type.
Given a family {Mi }i∈I of compatible matrices s.t. each Mi has type X ×Yi →R, their concatenation ◇i∈I is the matrix having all columns of every matrix inthe family, in such a way that every column is tagged with the matrix it camefrom. Formally, (◇i∈I Mi ) (x, (y, j)) = Mj (x, y), if y ∈ Yj , and the resulting
10
matrix has type X × (⨆i∈I Yi ) → R.
When the family {Mi } has only twoelements we may use the binary version ⋄ of the concatenation operator. The
10⨆i∈I Yi = Yi1 ⊔ Yi2 ⊔ . . . ⊔ Yin denotes the disjoint union {(y, i) ∣ y ∈ Yi , i ∈ I} of
the sets Yi1 , Yi2 , . . ., Yin .

10following depicts the concatenation of two matrices M1 and M2 in tabular form.
M1 y1 y2
M2 y1 y2 y3
M1 ⋄ M2 (y1 , 1) (y2 , 1) (y1 , 2) (y2 , 2) (y3 , 2)
x1 1 2 ⋄ x1 5 6 7 =
x1
1
2
5
6
7
x2 3 4x2 8 9 10
x2
3
4
8
9
10

4.2

Channels, and their hidden and visible choice operators

A channel is a stochastic matrix, i.e., all elements are non-negative, and all rows
sum up to 1. Here we will define two operators specific for channels. In thefollowing, for any real value 0 ≤ p ≤ 1, we denote by p̄ the value 1 − p.
Hidden choice The first operator models a hidden probabilistic choice amongchannels. Consider a family {Ci }i∈I of channels of a same type. Let µ ∈ DI bea probability distribution on the elements of the index set I. Consider an input
x is fed to one of the channels in {Ci }i∈I , where the channel is randomly pickedaccording to µ. More precisely, an index i ∈ I is sampled with probability µ(i),then the input x is fed to channel Ci , and the output y produced by the channel
is then made visible, but not the index i of the channel that was used. Note that
we consider hidden choice only among channels of a same type: if the sets of
outputs were not identical, the produced output might implicitly reveal whichchannel was used.
Formally, given a family {Ci }i∈I of channels s.t. each Ci has same type X ×
Y → R, the hidden choice operator ⨊i←µ is defined as ⨊i←µ Ci = ∑i∈I µ(i) Ci .
Proposition 2 Given a family {Ci }i∈I of channels of type X × Y → R, and a
distribution µ on I, the hidden choice ⨊i←µ Ci is a channel of type X × Y → R.
In the particular case in which the family {Ci } has only two elements Ci1and Ci2 , the distribution µ on indexes is completely determined by a real value
0 ≤ p ≤ 1 s.t. µ(i1 ) = p and µ(i2 ) = p̄. In this case we may use the binary versionp ⊕ of the hidden choice operator: Ci1 p ⊕ Ci2 = p Ci1 +p̄ Ci2 . The example below
depicts the hidden choice between channels C1 and C2 , with probability p=1/3.
C1 y1 y2
C2 y1 y2
C1 1/3 ⊕ C2 y1 y2
7/18 11/18
x1 1/2 1/2 1/3 ⊕ x1 1/3 2/3 =x1
4/9 5/9
x2 1/3 2/3
x2 1/2 1/2
x2

Visible choice The second operator models a visible probabilistic choice amongchannels. Consider a family {Ci }i∈I of compatible channels. Let µ ∈ DI be aprobability distribution on the elements of the index set I. Consider an input x
is fed to one of the channels in {Ci }i∈I , where the channel is randomly pickedaccording to µ. More precisely, an index i ∈ I is sampled with probability µ(i),then the input x is fed to channel Ci , and the output y produced by the channel
is then made visible, along with the index i of the channel that was used. Note
11

that visible choice makes sense only between compatible channels, but it is not
required that the output set of each channel be the same.
Formally, given {Ci }i∈I of compatible channels s.t. each Ci has type X ×Yi →R, and a distribution µ on I, the visible choice operator &i←µ is defined as&i←µ Ci = ◇i∈I µ(i) Ci .
Proposition 3 Given a family {Ci }i∈I of compatible channels s.t. each Ci has
type X × Yi → R, and a distribution µ on I, the result of the visible choice&i←µ Ci is a channel of type X × (⨆i∈I Yi ) → R.
In the particular case the family {Ci } has only two elements Ci1 and Ci2 ,the distribution µ on indexes is completely determined by a real value 0 ≤ p ≤ 1
s.t. µ(i1 ) = p and µ(i2 ) = p̄. In this case we may use the binary version p H of
the visible choice operator: Ci1 p H Ci2 = p Ci1 ⋄ p̄ Ci2 . The following depicts thevisible choice betwee channels C1 and C3 , with probability p=1/3.
C1 y1 y2
C3 y1 y3
C1 1/3 H C3 (y1 , 1) (y2 , 1) (y1 , 3) (y3 , 3)
1/6
1/6
2/9
4/9
x1 1/2 1/2 1/3 H x1 1/3 2/3 =
x1
1/9
2/9
1/3
1/3
x2 1/3 2/3
x2 1/2 1/2
x2

4.3

Properties of hidden and visible choice operators

We now prove algebraic properties of channel operators. These properties will be
useful when we model a (more complex) protocol as the composition of smaller
channels via hidden or visible choice.
Whereas the properties of hidden choice hold generally with equality, thoseof visible choice are subtler. For instance, visible choice is not idempotent, sincein general C p H C ≠ C. (In fact if C has type X × Y → R, C p H C has type
X × (Y ⊔ Y) → R.) However, idempotency and other properties involving visible
choice hold if we replace the notion of equality with the more relaxed notion of“equivalence” between channels. Intuitively, two channels are equivalent if they
have the same input space and yield the same value of vulnerability for every
prior and every vulnerability function.
Definition 4 (Equivalence of channels) Two compatible channels C1 andC2 with domain X are equivalent, denoted by C1 ≈ C2 , if for every prior π ∈ DX
and every posterior vulnerability V we have V [π, C1 ] = V [π, C2 ].
Two equivalent channels are indistinguishable from the point of view of information leakage, and in most cases we can just identify them. Indeed, nowadays
there is a tendency to use abstract channels [23,5], which capture exactly theimportant behavior with respect to any form of leakage. In this paper, however,
we cannot use abstract channels because the hidden choice operator needs a
concrete representation in order to be defined unambiguously.
The first properties we prove regard idempotency of operators, which can beused do simplify the representation of some protocols.
12

Proposition 5 (Idempotency) Given a family {Ci }i∈I of channels s.t. Ci =C for all i ∈ I, and a distribution µ on I, then: (a) ⨊i←µ Ci = C; and (b)&i←µ Ci ≈ C.
The following properties regard the reorganization of operators, and they
will be essential in some technical results in which we invert the order in whichhidden and visible choice are applied in a protocol.
Proposition 6 (“Reorganization of operators”) Given a family {Cij }i∈I,j∈J
of channels indexed by sets I and J , a distribution µ on I, and a distribution
η on J :(a) ⨊i←µ ⨊j ←η Cij = ⨊i←µ Cij , if all Ci ’s have the same type;j ←η(b) &i←µ &j ←η Cij ≈ &i←µ Cij , if all Ci ’s are compatible; andj ←η(c) ⨊i←µ &j ←η Cij ≈ &j ←η ⨊i←µ Cij , if, for each i, all Cij ’s have same type
X ×Yj →R.

4.4

Properties of vulnerability w.r.t. channel operators

We now derive some relevant properties of vulnerability w.r.t. our channel operators, which will be later used to obtain the Nash equilibria in information
leakage games with different choice operations.
The first result states that posterior vulnerability is convex w.r.t. hidden
choice (this result was already presented in [4]), and linear w.r.t. to visible choice.
Theorem 7 Let {Ci }i∈I be a family of channels, and µ be a distribution on I.
Then, for every distribution π on X , and every vulnerability V:(a) posterior vulnerability is convex w.r.t. to hidden choice: V [π, ⨊i←µ Ci ] ≤∑i∈I µ(i) V [π, Ci ] if all Ci ’s have the same type.
(b) posterior vulnerability is linear w.r.t. to visible choice: V [π, &i←µ Ci ] =∑i∈I µ(i) V [π, Ci ] if all Ci ’s are compatible.
The next result is concerned with posterior vulnerability under the composition of channels using both operators.
Corollary 8 Let {Cij }i∈I,j∈J be a family of channels, all with domain X andwith the same type, and let π ∈ DX , and V be any vulnerability. Define U ∶def
DI × DJ → R as follows: U (µ, η) = V [π, ⨊i←µ &j ←η Cij ]. Then U is convex
on µ and linear on η.
13

5

Information leakage games

In this section we present our framework for reasoning about information leakage,extending the notion of information leakage games proposed in [4] from only
simultaneous games with hidden choice to both simultaneous and sequential
games, with either hidden or visible choice.
In an information leakage game the defender tries to minimize the leakage of
information from the system, while the attacker tries to maximize it. In this basic
scenario, their goals are just opposite (zero-sum). Both of them can influence theexecution and the observable behavior of the system via a specific set of actions.
We assume players to be rational (i.e., they are able to figure out what is thebest strategy to maximize their expected payoff), and that the set of actions andthe payoff function are common knowledge.
Players choose their own strategy, which in general may be mixed (i.e. probabilistic), and choose their action by a random draw according to that strategy.
After both players have performed their actions, the system runs and producessome output value which is visible to the attacker and may leak some information about the secret. The amount of leakage constitutes the attacker’s gain, andthe defender’s loss.
To quantify the leakage we model the system as an information-theoretic
channel (cf. Section 2.2). We recall that leakage is defined as the difference(additive leakage) or the ratio (multiplicative leakage) between posterior andprior vulnerability. Since we are only interested in comparing the leakage ofdifferent channels for a given prior, we will define the payoff just as the posterior
vulnerability, as the value of prior vulnerability will be the same for every channel.
5.1

Defining information leakage games

An (information) leakage game consists of: (1) two nonempty sets D, A of defender’s and attacker’s actions respectively, (2) a function C ∶ D×A → (X ×Y →R) that associates to each pair of actions (d, a) ∈ D×A a channel Cda ∶ X ×Y →R, (3) a prior π ∈ DX on secrets, and (4) a vulnerability measure V. The payoff
deffunction u ∶ D×A → R for pure strategies is defined as u(d, a) = V [π, Cda ].
We have only one payoff function because the game is zero-sum.
Like in traditional game theory, the order of actions and the extent by whicha player knows the move performed by the opponent play a critical role in deciding strategies and determining the payoff. In security, however, knowledge ofthe opponent’s move affects the game in yet another way: the effectiveness of theattack, i.e., the amount of leakage, depends crucially on whether or not the attacker knows what channel is being used. It is therefore convenient to distinguish
two phases in the leakage game:
Phase 1: Each player determines the most convenient strategy (which in general is mixed) for himself, and draws his action accordingly. One of theplayers may commit first to his action, and his choice may or may not be14

revealed to the follower. In general, knowledge of the leader’s action may
help the follower choose a more advantageous strategy.
Phase 2: The attacker observes the output of the selected channel Cda andperforms his attack on the secret. In case he knows the defender’s action,
he is able to determine the exact channel Cda being used (since, of course,
the attacker knows his own action), and his payoff will be the posterior vulnerability V [π, Cda ]. However, if the attacker does not know exactly whichchannel has been used, then his payoff will be smaller.
Note that the issues raised in Phase 2 are typical of leakage games; they do
not have a correspondence (to the best of our knowledge) in traditional gametheory. On the other hand, these issues are central to security, as they reflect
the principle of preventing the attacker from inferring the secret by obfuscating
the link between secret and observables.
Following the above discussion, we consider various possible scenarios forgames, along two lines of classification. First, there are three possible orders forthe two players’ actions.
Simultaneous: The players choose (draw) their actions in parallel, each without knowing the choice of the other.
Sequential, defender-first: The defender draws an action, and commits to it,
before the attacker does.
Sequential, attacker-first: The attacker draws an action, and commits to it,
before the defender does.
Note that these sequential games may present imperfect information (i.e., thefollower may not know the leader’s action).
Second, the visibility of the defender’s action during the attack may vary:
Visible choice: The attacker knows the defender’s action when he observes theoutput of the channel, and therefore he knows which channel is being used.
Visible choice is modeled by the operator &.
Hidden choice: The attacker does not know the defender’s action when heobserves the output of the channel, and therefore in general he does notexactly know which channel is used (although in some special cases he may
infer it from the output). Hidden choice is modeled by the operator ⨊.
Note that the distinction between sequential and simultaneous games is orthogonal to that between visible and hidden choice. Sequential and simultaneousgames model whether or not, respectively, the follower’s choice can be affectedby knowledge of the leader’s action. This dichotomy captures how knowledge
about the other player’s actions can help a player choose his own action. On theother hand, visible and hidden choice capture whether or not, respectively, theattacker is able to fully determine the channel representing the system, once defender and attacker’s actions have already been fixed. This dichotomy reflects thedifferent amounts of information leaked by the system as viewed by the adversary. For instance, in a simultaneous game neither player can choose his action15

Order of action
simultaneous defender 1
Defender’s visible &choice hidden ⨊stst

attacker 1

Game I

Game II

Game III

Game IV

Game V

Game VI

Table 2. Kinds of games we consider. All sequential games have perfect information,
except for game V.

based on the choice of the other. However, depending on whether or not thedefender’s choice is visible, the adversary will or will not, respectively, be able
to completely recover the channel used, which will affect the amount of leakage.
If we consider also the subdivision of sequential games into perfect and imperfect information, there are 10 possible different combinations. Some, however,make little sense. For instance, defender-first sequential game with perfect information (by the attacker) does not combine naturally with hidden choice ⨊,since that would mean that the attacker knows the action of the defender andchoses his strategy accordingly, but forgets it at the moment of the attack. (Weassume perfect recall, i.e., the players never forget what they have learned.) Yet
other combinations are not interesting, such as the attacker-first sequential gamewith (totally) imperfect information (by the defender), since it coincides withthe simultaneous-game case. Note that attacker and defender are not symmetricwith respect to hiding/revealing their actions a and d, since the knowledge of aaffects the game only in the usual sense of game theory, while the knowledge ofd also affects the computation of the payoff (cf. “Phase 2” above).
Table 2 lists the meaningful and interesting combinations. In Game V weassume imperfect information: the attacker does not know the action chosen
by the defender. In all the other sequential games we assume that the follower
has perfect information. In the remaining of this section, we discuss each gameindividually, using the example of Section 3 as running example.
Game I (simultaneous with visible choice) This simultaneous game canbe represented by a tuple (D, A, u). As in all games with visible choice &,the expected payoff U of a mixed strategy profile (δ, α) is defined to be thedef

expected value of u, as in traditional game theory: U (δ, α) = E d←δ u(d, a) =∑d∈D δ(d) α(a) u(d, a), where we recall that u(d, a) = V [π, Cda ].

a←α

a∈A

From Theorem 7(b) we derive: U (δ, α) = V [π, & d←δ Cda ]. hence the wholea←αsystem can be equivalently regarded as the channel & d←δ Cda . Still from Thea←αorem 7(b) we can derive that U (δ, α) is linear in δ and α. Therefore the Nashequilibrium can be computed using the minimax method (cf. Section 2.1).
Example 9 Consider the example of Section 3 in the setting of Game I. The∗∗
Nash equilibrium (δ , α ) can be obtained using the closed formula from Section∗∗
2.1, and it is given by δ (0) = α (0) = (2/3−1)/(1/2−1−1+2/3) = 2/5. The correspond∗∗
ing payoff is U (δ , α ) = 2/5 2/5 1/2 + 2/5 3/5 + 3/5 2/5 + 3/5 3/5 2/3 = 4/5.
16

stGame II (defender 1 with visible choice) This defender-first sequential
game can be represented by a tuple (D, D → A, u). A mixed strategy profile isof the form (δ, σa ), with δ ∈ DD and σa ∈ D(D → A), and the correspondingdef

payoff is U (δ, σa ) = E d←δ u(d, sa (d)) = ∑d∈D δ(d) σa (sa ) u(d, sa (d)), wheresa ∶D → Asa ←σau(d, sa (d)) = V [π, Cdsa (d) ].

Again, from Theorem 7(b) we derive: U (δ, σa ) = V [π, & d←δ Cdsa (d) ] andsa ←σahence the system can be expressed as channel & d←δ Cdsa (d) . From the samesa ←σaTheorem we also derive that U (δ, σa ) is linear in δ and σa , so the mutually
optimal strategies can be obtained again by solving the minimax problem. In
this case, however, the solution is particularly simple, because it is known that
there are optimal strategies which are deterministic. Hence it is sufficient for the
defender to find the action d which minimizes maxa u(d, a).
Example 10 Consider the example of Section 3 in the setting of Game II. If
the defender chooses 0 then the attacker chooses 1. If the defender chooses 1 thenthe attacker chooses 0. In both cases, the payoff is 1. The game has therefore twosolutions, (0, 1) and (1, 0).
stGame III (attacker 1 with visible choice) This game is also a sequential
game, but with the attacker as the leader. Therefore it can be represented as tupleof the form (A → D, A, u). It is the same as Game II, except that the roles of theattacker and the defender are inverted. In particular, the payoff of a mixed stratdef
egy profile (σd , α) ∈ D(A → D)×DA is given by U (σd , α) = Esa←αd ←σd u(sd (a), a) =∑sd ∶A → D σd (sd ) α(a) u(sd (a), a) = V [π, &sd ←σd Csd (a)a ], and the whole system
a←α

a∈A

can be equivalently regarded as channel &sd ←σd Csd (a)a . Obviously, also in thisa←αcase the minimax problem has a deterministic solution.
In summary, in the sequential case, whether the leader is the defender or theattacker (Games II and III, respectively), the minimax problem has always adeterministic solution [24].
Theorem 11 In a defender-first sequential game with visible choice, there existd ∈ D and a ∈ A such that, for every δ ∈ DD and σa ∈ D(D → A) we have:
U (d, σa ) ≤ u(d, a) ≤ U (δ, a). Similarly, in an attacker-first sequential game withvisible choice, there exist d ∈ D and a ∈ A such that, for every σd ∈ D(A → D)and α ∈ DA we have: U (d, α) ≤ u(d, a) ≤ U (σd , a).
Example 12 Consider now the example of Section 3 in the setting of Game III.
If the attacker chooses 0 then the defender chooses 0 and the payoff is 1/2. If theattacker chooses 1 then the defender chooses 1 and the payoff is 2/3. The lattercase is more convenient for the attacker, hence the solution of the game is thestrategy profile (1, 1).
17

Game IV (simultaneous with hidden choice) This game is a tuple (D, A, u).
However, it is not an ordinary game in the sense that the payoff a mixed strategy
profile cannot be defined by averaging the payoff of the corresponding pure strategies. More precisely, the payoff of a mixed profile is defined by averaging on thestrategy of the attacker, but not on that of the defender. In fact, when hidden
choice is used, there is an additional level of uncertainty in the relation between
the observables and the secret from the point of view of the attacker, since heis not sure about which channel is producing those observables. A mixed strategy δ for the defender produces a convex combination of channels (the channels
associated to the pure strategies) with the same coefficients, and we know fromprevious sections that the vulnerability is a convex function of the channel, andin general is not linear.
In order to define the payoff of a mixed strategy profile (δ, α), we need therefore to consider the channel that the attacker perceives given his limited knowledge. Let us assume that the action that the attacker draws from α is a. He
does not know the action of the defender, but we can assume that he knows his
strategy (each player can derive the optimal strategy of the opponent, under theassumption of common knowledge and rational players).
The channel the attacker will see is ⨊d←δ Cda , obtaining a corresponding
payoff of V [π, ⨊d←δ Cda ]. By averaging on the strategy of the attacker we obdef

tain U (δ, α) = Ea←α V [π, ⨊d←δ Cda ] = ∑a∈A α(a) V [π, ⨊d←δ Cda ]. From Theorem 7(b) we derive: U (δ, α) = V [π, &a←α ⨊d←δ Cda ] and hence the wholesystem can be equivalently regarded as channel &a←α ⨊d←δ Cda . Note that, by
Proposition 6(c), the order of the operators is interchangeable, and the system
can be equivalently regarded as ⨊d←δ &a←α Cda . This shows the robustness of
this model.
From Corollary 8 we derive that U (δ, α) is convex in δ and linear in η, hence
we can compute the Nash equilibrium by the minimax method.
Example 13 Consider now the example of Section 3 in the setting of Game
IV. For δ ∈ DD and α ∈ DA, let p = δ(0) and q = α(0). The system can be
represented by the channel (C00 p ⊕ C10 ) q H (C01 p ⊕ C11 ) represented below.
C00 p ⊕ C10 y = 0 y = 1
x=0
p
p̄
x=1
1
0

q

H

C01 p ⊕ C11 y = 0
y=1
1/3 + 2/3 p 2/3 − 2/3 px=0
2/3 − 2/3 p 1/3 + 2/3 p
x=1

For uniform π, we have V [π, C00 p ⊕ C10 ] =1 − 1/2; and V [π, C10 p ⊕ C11 ] isequal to 2/3 − 2/3 p if p ≤ 1/4, and equal to 1/3 + 2/3 p if p > 1/4. Hence the payoff,
expressed in terms of p and q, is U (p, q) = q(1 − 1/2) + q̄(2/3 − 2/3 p) if p ≤ 1/4,
∗ ∗and U (p, q) = q(1 − 1/2) + q̄(1/3 + 2/3 p) if p > 1/4. The Nash equilibrium (p , q )∗∗is given by p = argminp maxq U (p, q) and q = argmaxq minp U (p, q), and by∗∗solving the above, we obtain p = q = 4/7.
stGame V (defender 1 with hidden choice) This is a defender-first sequential game with imperfect information, hence it can be represented as a tuple of18

the form (D, Ka → A, ud , ua ), where Ka is a partition of D. Since we are assuming perfect recall, and the attacker does not know anything about the action
chosen by the defender in Phase 2, i.e., at the moment of the attack (except theprobability distribution determined by his strategy), we must assume that theattacker does not know anything in Phase 1 either. Hence the indistinguishability relation must be total, i.e., Ka = {D}. But {D} → A is equivalent to A,
hence this kind of game is equivalent to Game IV.
It is also a well known fact in Game theory that when in a sequential gamethe follower does not know the leader’s move before making his choice, the game11
is equivalent to a simultaneous game.
st

Game VI (attacker 1 with hidden choice) This game is also a sequential game with the attacker as the leader, hence it is a tuple of the form
(A → D, A, u). It is similar to Game III, except that the payoff is convex on
the strategy of the defender, instead of linear. The payoff of the mixed strategy
def
profile (σd , α) ∈ D(A → D) × DA is U (σd , α) = Ea←α V [π, ⨊sd ←σd Csd (a)a ] =V [π, ⨊a←α &sd ←σd Csd (a)a ], so the whole system can be equivalently regarded
as channel ⨊a←α &sd ←σd Csd (a)a . Also in this case the minimax problem has adeterministic solution, but only for the attacker.
Theorem 14 In an attacker-first sequential game with hidden choice, there exista ∈ A and δ ∈ DD such that, for every α ∈ DA and σd ∈ D(A → D) we havethat U (δ, α) ≤ U (δ, a) ≤ U (σd , a).
Example 15 Consider again the example of Section 3, this time in the settingof Game VI. Consider also the calculations made in Example 13, we will use
the same results and notation here. In this setting, the attacker is obliged tomake its choice first. If he chooses 0, which corresponds to committing to thesystem C00 p ⊕ C10 , then the defender will choose p = 1/4, which minimizes its
vulnerability. If he chooses 1, which corresponds to committing to the system
C01 p ⊕ C11 , the defender will choose p = 1, which minimizes its vulnerabilityof the above channel. In both cases, the leakage is p = 1/2, hence both thesestrategies are solutions to the minimax. Note that in the first case the strategyof the defender is mixed, while that of the attacker is always pure.
5.2

Comparing the games

If we look at the various payoffs obtained for the running example in the various
games, we obtain the following values (listed in decreasing order): II ∶ 1; I ∶ 4/5;
III ∶ 2/3; IV ∶ 4/7; V ∶ 4/7; VI ∶ 1/2.
11

However, one could argue that, since the defender has already committed, the attacker does not need to perform the action corresponding to the Nash equilibrium,
any payoff-maximizing solution would be equally good for him.

19

This order is not accidental: for any vulnerability
function, and for any prior, the various games are ordered, with respect to the payoff, as shown in Figure 2.
The relations between II, I, and III, and between IV-V
and VI come from the fact that, in any zero-sum sequential game the leader’s payoff will be less or equal
to his payoff in the corresponding simultaneous game.
We think this result is well-known in game theory, but
we give the hint of the proof nevertheless, for the sakeof clarity.

Fig. 2. Order of games
w.r.t.
payoff.
Gameshigher in the lattice havelarger payoff.

Theorem 16 It is the case that:(a) minδ maxσa V [π, & d←δ Cdsa (d) ] ≥ minδ maxα V [π, & d←δ Cda ]sa ←σaa←α≥ maxα minσd V [π, &sd ←σd Csd (a)a ]a←α(b) minδ maxα V [π, &a←α ⨊d←δ Cda ] ≥ maxα minσd V [π, ⨊a←α &sd ←σd Csd (a)a ]Proof. We prove the first inequality in (a). Independently of δ, consider theattacker strategy τa that assigns probability 1 to the function sa defined assa (d) = argmaxa V [π, Cda ]. Then we have that
⎤
⎡
⎤
⎡
⎢
⎥
⎢
⎥
⎥
⎢
⎥
⎢
⎥
⎢
⎥
⎢
⎥
⎢
⎥
⎢
⎥
⎢
⎥
⎢
π,
'
C
≥
min
V
π,
'
C
min max V ⎢
⎥
⎢
⎥
ds
(d)
ds
(d)
a
a
⎥
⎢
⎥
⎢
σa
δ
δ
⎥
⎢
⎥
⎢
⎥
⎢
⎥
⎢
d←δ
d←δ
⎥
⎢
⎥
⎢
⎦
⎣ sa ←τa⎦⎣ sa ←σa
⎤
⎡
⎥
⎢
⎥
⎢
⎥
⎢
⎥
⎢
⎥
π,
'
C
≥ min max V ⎢
da
⎥
⎢
⎥
⎢
α
δ
⎥
⎢
d←δ
⎥
⎢
⎦
⎣
a←α

Note that the strategy τa is optimal for the adversary, so the first of the above
inequalities is actually an equality. All other cases can be proved with an analogous reasoning.
⊔⊓
Concerning III and IV-V: these are not related. In the running example thepayoff for III is higher than for IV-V, but it is easy to find other cases in which
the situation is reversed. For instance, if in the running example we set C11 tobe the same as C00 , the payoff for III will be 1/2, and that for IV-V will be 2/3.
Finally, the relation between III and VI comes from the fact that they areboth attacker-first sequential games, and the only difference is the way in which
the payoff is defined. Then, just observe that in general we have, for every a ∈ A
and every δ ∈ DD: V [π, ⨊d←δ Cda ] ≤ V [π, &d←δ Cda ].
The relations in Figure 2 can be used by the defender as guidelines to better
protect the system, if he has some control over the rules of the game. Obviously,
for the defender the games lower in the ordering are to be preferred.
20

6Case study: a safer, faster password-checker

In this section we apply our game- Program PWD123
theoretic, compositional approach to show High Input: x ∈ {000, 001, . . . , 111}
how a defender can mitigate an attacker’s Low Input: a ∈ {000, 001, . . . , 111}
typical timing side-channel attack while Output: y ∈ {T, F }avoiding the usual burden imposed on the accept ∶= T
password-checker’s efficiency.
for i = 1, 2, 3 do
Consider the password-checker PWD123
if ai ≠ xi thenaccept ∶= F
of Figure 3, which performs a bitwise-checkbreakof a 3-bit low-input a=a1 a2 a3 , provided by
end ifthe attacker, against a 3-bit secret password x=x1 x2 x3 . The low-input is rejected end foras soon as it mismatches the secret, and is return accept
Fig. 3. Password-checker algorithm.
accepted otherwise.
The attacker can choose low-inputs totry to gain information about the password. Obviously, in case PWD123 accepts the
low-input, the attacker learns the password value is a=x. Yet, even when the lowinput is rejected, there is some leakage of information: from the duration of theexecution the attacker can estimate how many iterations have been performed
before the low-input was rejected, thus inferring a prefix of the secret password.
To model this scenario, let X = {000, 001, . . . , 111} be the set of all possible
3-bit passwords, and Y = {(F, 1), (F, 2), (F, 3), (T, 3)} be the set of observables
produced by the system. Each observable is an ordered pair whose first element
indicates whether the password was accepted (T or F ), and the second element
indicates the duration of the computation (1, 2, or 3 iterations). For instance,channel C123,101 in Figure 4 models PWD123 ’s behavior when the attacker provides
low-input a=101.
We will adopt as a measure of information Bayes vulnerability [27]. The prior
Bayes vulnerability of a distribution π∈DX is defined as Vg [π] = maxx∈X πx ,and represents the probability that the attacker guesses correctly the password
in one try. For instance, if the distribution on all possible 3-bit passwords isπ̂ = (0.0137, 0.0548, 0.2191, 0.4382, 0.0002, 0.0002, 0.0548, 0.2191), its prior Bayes
vulnerability is V [π̂] =0.4382.
The posterior Bayes vulnerability of a prior π and a channel C∶X ×Y→R isdefined as V [π, C] = ∑y∈Y maxx∈X πx C(x, y), and it represents the probability
that the attacker guesses correctly the password in one try, after he observes
the output of the channel (i.e., after he has measured the time needed for the
checker to accept or reject the low-input). For prior π̂ above, the posterior Bayes
vulnerability of channel C123,101 is V [π̂, C123,101 ] =0.6577 (which represents anincrease in Bayes vulnerability of about 50%), and the expected running time
for this checker is of 1.2747 iterations.
A way to mitigate this timing side-channel is to make the checker’s execution
time independent of the secret. Channel Ccons,101 from Figure 4 models a checker
that does that (by eliminating the break command within the loop in PWD123 )when the attacker’s low-input is a=101. This channel’s posterior Bayes vulner21

ability is V [π̂, C123,101 ] =0.4384, which brings the multiplicative Bayes leakage
down to an increase of only about 0.05%. However, the expected running timegoes up to 3 iterations (an increase of about 135% w.r.t. that of C123,101 ).
y=
y=
y=
y=
y=
y=
Seeking some compro- C
Ccons,101
123,101(F, 1) (F, 2) (F, 3) (T, 3)(F, 3) (T, 3)
mise between security and efx=000
1
0
0
0
x=000
1
0
ficiency, assume that the dex=001
1
0
0
0
x=001
1
0
x=010
1
0
0
0
x=010
1
0
fender can employ passwordx=011
1
0
0
0
x=011
1
0
checkers that perform the
x=100
0
0
1
0
x=100
1
0
x=101
0
0
0
1
x=101
0
1
bitwise comparison among
x=110
0
1
0
0
x=110
1
0
low-input a and secret passx=111
0
1
0
0
x=111
1
0
word x in different orders.
More precisely, there is one Fig. 4. Channels Cda modeling the password checker
version of the checker for ev- for defender’s action d and attacker’s action a.
ery possible order in which the index i ranges in the control of the loop. For
instance, while PWD123 checks the bits in the order 1, 2, 3, the alternative algorithm PWD231 uses the order 2, 3, 1.

To determine a defender’s best choice of which versions of the checker to run,
we model this problem as game. The attacker’s actions A = {000, 001, . . . , 111}
are all possible low-inputs to the checker, and the defender’s D = {123, 132, 213,
231, 312, 321} are all orders to perform the comparison. Hence, there is a totalof 48 possible channels Cad ∶X ×Y→R, one for each combination of d∈D, a∈A.

Defender’saction d

In our framework, the utility of a mixed strategy profile (δ, α) is given by
U (δ, α) = Ea←α V [π, ⨊d←δ Cda ]. For each pure strategy profile (d, a), the payoffof the game will be the posterior Bayes vulnerability of the resulting channel
Cda (since, if we measuring leakage, the prior vulnerability is the same for every
channel once the prior is fixed). Table 3 depicts such payoffs. Note that the attacker’s and defender’s actions substantially affect the effectiveness of the attack:vulnerability ranges between 0.4934 and 0.9311 (and so multiplicative leakage
is in the range between an increase of 12% and one of 112%). Using techniquesfrom [4], we can compute the best (mixed) strategy for the defender in this∗game, which turns out to be δ = (0.1667, 0.1667, 0.1667, 0.1667, 0.1667, 0.1667).
This strategy is part of an equilibrium and guarantees that for any choice of theattacker the posterior Bayes vulnerability is at most 0.6573 (so the multiplicative leakage is bounded by 50%, an intermediate value between the minimum of
about 12% and the maximum of about 112%). It is interesting to note that the
expected running time, for any action of the attacker, is bounded by at most
Attacker’s action a
2.3922 iterations (anU (d, a) 000
001
010
011
100
101
110
111
increase of only 87%
123
0.7257 0.7257 0.9311 0.9311 0.6577 0.6577 0.7122 0.7122
132
0.8900 0.9311 0.8900 0.9311 0.7122 0.7122 0.7122 0.7122
w.r.t. the channel
213
0.5068 0.5068 0.9311 0.9311 0.4934 0.4934 0.7668 0.7668
PWD123 ), which is be231
0.5068 0.5068 0.7668 0.9311 0.5068 0.5068 0.7668 0.9311
312
0.7257 0.9311 0.7257 0.9311 0.7122 0.8766 0.7122 0.8766
low the worst possi321
0.6712 0.7122 0.7257 0.9311 0.6712 0.7122 0.7257 0.9311
ble expected 3 iteraTable 3. Utility for each pure strategy profile.
tions of the constanttime password checker.
22

7

Related work

Many studies have applied game theory to analyses of security and privacy innetworks [7,14,3], cryptography [15], anonymity [1], location privacy [13], andintrusion detection [30], to cite a few. See [20] for a survey.
In the context of quantitative information flow, most works consider only
passive attackers. Boreale and Pampaloni [8] consider adaptive attackers, but
not adaptive defenders, and show that in this case the adversary’s optimal strategy can be always deterministic. Mardziel et al. [21] propose a model for both
adaptive attackers and defenders, but in none of their extensive case-studies theattacker needs a probabilistic strategy to maximize leakage. In this paper wecharacterize when randomization is necessary, for either attacker or defender, toachieve optimality in our general information leakage games.
Security games have been employed to model and analyze payoffs between
interacting agents, especially between a defender and an attacker. Korzhyk et
al. [19] theoretically analyze security games and study the relationships between
Stackelberg and Nash Equilibria under various forms of imperfect information.
Khouzani and Malacaria [18] study leakage properties when perfect secrecy is
not achievable due to constraints on the allowable size of the conflating sets,
and provide universally optimal strategies for a wide class of entropy measures,and for g-entropies. These works, contrarily to ours, do not consider games withhidden choice, in which optimal strategies differ from traditional game-theory.
Several security games have modeled leakage when the sensitive information are the defender’s choices themselves, rather than a system’s high input.
For instance, Alon et al. [2] propose zero-sum games in which a defender chooses
probabilities of secrets and an attacker chooses and learns some of the defender’ssecrets. Then they present how the leakage on the defender’s secrets gives influences on the defender’s optimal strategy. More recently, Xu et al. [29] show
zero-sum games in which the attacker obtains partial knowledge on the security
resources that the defender protects, and provide the defender’s optimal strategy
under the attacker’s such knowledge.
Regarding channel operators, sequential and parallel composition of channels
have been studied (e.g., [17]), but we are unaware of any explicit definition andinvestigation of hidden and visible choice operators. Although Kawamoto etal. [16] implicitly use the hidden choice to model a probabilistic system as theweighted sum of systems, they do not derive the set of algebraic properties we
do for this operator, and for its interaction with the visible choice operator.

8

Conclusion and future work

In this paper we used protocol composition to model the introduction of noise
performed by the defender to prevent leakage of sensitive information. Moreprecisely, we formalized visible and hidden probabilistic choices of different protocols. We then formalized the interplay between defender and adversary in agame-theoretic framework adapted to the specific issues of QIF, where the payoff23

is information leakage. We considered various kinds of leakage games, dependingon whether players act simultaneously or sequentially, and whether the choicesof the defender are visible or not to the adversary. We established a hierarchyof these games, and provided methods for finding the optimal strategies (at the
points of equilibrium) in the various cases.
As future research, we would like to extend leakage games to the case of
repeated observations, i.e., when the attacker can observe the outcomes of thesystem in successive runs, under the assumption that both attacker and defender
may change the channel in each run. We would also like to extend our framework to non zero-sum games, in which the costs of attack and defense are notequivalent, and to analyze differentially-private mechanisms.
Acknowledgments The authors are thankful to anonymous reviewers for helpful comments. This work was supported by JSPS and Inria under the project LOGIS of theJapan-France AYAME Program, and by the project Epistemic Interactive Concurrency (EPIC) from the STIC AmSud Program. Mário S. Alvim was supported by
CNPq, CAPES, and FAPEMIG. Yusuke Kawamoto was supported by JSPS KAKENHI Grant Number JP17K12667.

References
1. Alessandro Acquisti, Roger Dingledine, and Paul F. Syverson. On the economics
of anonymity. In Proc. of FC, pages 84–102, 2003.
2. Noga Alon, Yuval Emek, Michal Feldman, and Moshe Tennenholtz. Adversarial
leakage in games. SIAM J. Discrete Math., 27(1):363–385, 2013.
3. Tansu Alpcan and Sonja Buchegger. Security games for vehicular networks. IEEE
Trans. Mob. Comput., 10(2):280–290, 2011.
4. Mário S. Alvim, Konstantinos Chatzikokolakis, Yusuke Kawamoto, and Catuscia
Palamidessi. Information leakage games. In Proc. of GameSec, volume 10575 of
LNCS, pages 437–457. Springer, 2017.
5. Mário S. Alvim, Konstantinos Chatzikokolakis, Annabelle McIver, Carroll Morgan,
Catuscia Palamidessi, and Geoffrey Smith. Axioms for information leakage. In
Proc. of CSF, pages 77–92, 2016.
6. Mário S. Alvim, Konstantinos Chatzikokolakis, Catuscia Palamidessi, and Geoffrey
Smith. Measuring information leakage using generalized gain functions. In Proc.
of CSF, pages 265–279, 2012.
7. Tamer Basar. The gaussian test channel with an intelligent jammer. IEEE Trans.
Information Theory, 29(1):152–157, 1983.
8. Michele Boreale and Francesca Pampaloni. Quantitative information flow undergeneric leakage functions and adaptive adversaries. Logical Methods in Computer
Science, 11(4), 2015.
9. Christelle Braun, Konstantinos Chatzikokolakis, and Catuscia Palamidessi. Quantitative notions of leakage for one-try attacks. In Proc. of MFPS, volume 249 of
ENTCS, pages 75–91. Elsevier, 2009.
10. Konstantinos Chatzikokolakis, Catuscia Palamidessi, and Prakash Panangaden. On
the Bayes risk in information-hiding protocols. J. of Comp. Security, 16(5):531–
571, 2008.

24

11. David Chaum. The dining cryptographers problem: Unconditional sender andrecipient untraceability. Journal of Cryptology, 1:65–75, 1988.
12. Cynthia Dwork, Frank Mcsherry, Kobbi Nissim, and Adam Smith. Calibrating
noise to sensitivity in private data analysis. In Proc. of TCC, volume 3876 of
LNCS, pages 265–284. Springer, 2006.
13. Julien Freudiger, Mohammad Hossein Manshaei, Jean-Pierre Hubaux, andDavid C. Parkes. On non-cooperative location privacy: A game-theoretic analysis. In Proc. of CCS, pages 324–337, 2009.
14. Jens Grossklags, Nicolas Christin, and John Chuang. Secure or insure?: A gametheoretic analysis of information security games. In Proc. of WWW, pages 209–218,
2008.
15. Jonathan Katz. Bridging game theory and cryptography: Recent results and future
directions. In Proc. of TCC, pages 251–272, 2008.
16. Yusuke Kawamoto, Fabrizio Biondi, and Axel Legay. Hybrid statistical estimationof mutual information for quantifying information flow. In Proc. of FM 2016, pages
406–425, 2016.
17. Yusuke Kawamoto, Konstantinos Chatzikokolakis, and Catuscia Palamidessi. On
the compositionality of quantitative information flow. Logical Methods in Computer
Science, 13(3:11):1–31, 2017.
18. M. H. R. Khouzani and P. Malacaria. Relative perfect secrecy: Universally optimal
strategies and channel design. In Proc. of CSF, pages 61–76, 2016.
19. Dmytro Korzhyk, Zhengyu Yin, Christopher Kiekintveld, Vincent Conitzer, andMilind Tambe. Stackelberg vs. nash in security games: An extended investigation ofinterchangeability, equivalence, and uniqueness. J. Artif. Intell. Res., 41:297–327,
2011.
20. Mohammad Hossein Manshaei, Quanyan Zhu, Tansu Alpcan, Tamer Bacşar, andJean-Pierre Hubaux. Game theory meets network security and privacy. ACM
Comput. Surv., 45(3):25:1–25:39, 2013.
21. Piotr Mardziel, Mário S. Alvim, Michael W. Hicks, and Michael R. Clarkson. Quantifying information flow for dynamic secrets. In Proc. of S&P, pages 540–555, 2014.
22. Massey. Guessing and entropy. In Proceedings of the IEEE Int. Symposium on
Information Theory, page 204. IEEE, 1994.
23. Annabelle McIver, Carroll Morgan, Geoffrey Smith, Barbara Espinoza, and Larissa
Meinicke. Abstract channels and their robust information-leakage ordering. In
Proc. of POST, volume 8414 of LNCS, pages 83–102. Springer, 2014.
24. Martin J. Osborne and Ariel Rubinstein. A Course in Game Theory. The MIT
Press, 1994.
25. Juliano Rizzo and Thai Duong. The CRIME attack, 2012.
26. Claude E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27:379–423, 625–56, 1948.
27. Geoffrey Smith. On the foundations of quantitative information flow. In Proc. of
FOSSACS, volume 5504 of LNCS, pages 288–302. Springer, 2009.
28. Qixiang Sun, Daniel R Simon, Yi-Min Wang, Wilf Russell, Venkata N Padmanabhan, and Lili Qiu. Statistical identification of encrypted web browsing traffic. In
Proc. of S&P, pages 19–30. IEEE, 2002.
29. Haifeng Xu, Albert Xin Jiang, Arunesh Sinha, Zinovi Rabinovich, Shaddin
Dughmi, and Milind Tambe. Security games with information leakage: Modelingand computation. In Proc. of IJCAI, pages 674–680, 2015.
30. Quanyan Zhu, Carol J. Fung, Raouf Boutaba, and Tamer Basar. A gametheoretical approach to incentive design in collaborative intrusion detection networks. In Proc. of GAMENETS, pages 384–392. IEEE, 2009.

25

A

Proofs of Technical Results

In this section we provide proofs for our technical results.
A.1

Preliminaries for proofs

We start by providing some necessary background for the subsequent technicalproofs.
Definition 4 states that two compatible channels (i.e., with the same input
space) are equivalent if yield the same value of vulnerability for every priorand every vulnerability function. The result below, from the literature, provides
necessary and sufficient conditions for two channels being equivalent. The result
employs the extension of channels with an all-zero column as follows. For any
0channel C of type X × Y → R, its zero-column extension C is the channel of0type X × (Y ∪ {y0 }) → R, with y0 ∉ Y, s.t. C (x, y) = C(x, y) for all x ∈ X ,0y ∈ Y, and C (x, y0 ) = 0 for all x ∈ X .
Lemma 17 (Characterization of channel equivalence [6,23]) Two channels C1 and C2 are equivalent iff every column of C1 is a convex combination of0
columns of C2 , and every column of C2 is a convex combination of columns of0
C1 .
Note that the result above implies that for being equivalent, any two channels
must be compatible.
A.2

Proofs of Section 4

Proposition 2 Given a family {Ci }i∈I of channels of type X × Y → R, and a
distribution µ on I, the hidden choice ⨊i←µ Ci is a channel of type X × Y → R.
Proof. Since hidden choice is defined as a summation of matrices, the type of⨊i←µ Ci is the same as the type of every Ci in the family.
To see that ⨊i←µ Ci is a channel (i.e., all of its entries are non-negative, andall of its rows sum up to 1), first note that, since each Ci in the family is achannel matrix, Ci (x, y) lies in the interval [0, 1] for all x ∈ X , y ∈ Y. Since µ
is a set of convex coefficients, from the definition of hidden choice it follows that
also ∑i∈I µ(i)Ci (x, y) must lie in the interval [0, 1] for every x, y.
Second, note that for all x ∈ X :∑ ( ⨊ Ci ) (x, y) = ∑ ∑ µ(i)Ci (x, y)
y∈Y

i←µ

(def. of hidden choice)y∈Y i∈I= ∑ µ(i) ∑ Ci (x, y)
i∈I

y∈Y

= ∑ µ(i) ⋅ 1(Ci ∶X ×Y→R are channels)

i∈I

=1

(µ is a prob. dist.)26

Proposition 3 Given a family {Ci }i∈I of compatible channels s.t. each Ci has
type X × Yi → R, and a distribution µ on I, the result of the visible choice&i←µ Ci is a channel of type X × (⨆i∈I Yi ) → R.
Proof. Visible choice applied to a family {Ci } of channels scales each matrix
Ci by a factor µ(i), which preserves the type X × Yi → R of each matrix,
and then concatenates all the matrices so produced, yielding a result of type
X × (⨆i∈I Yi ) → R.
To see that &i←µ Ci is a channel (i.e., that all of its entries are non-negative,
and that all rows sum-up to 1), note that each element of the visible choice on
the family {Ci } can be denoted by (&i←µ Ci ) (x, (y, j)), where x ∈ X , j ∈ I,
and y ∈ Yj . Then, note that for all x ∈ X , j ∈ I, and y ∈ Yj :( ' Ci ) (x, (y, j)) = (◇i∈I µ(i)Ci ) (x, (y, j))(def. of visible choice)i←µ= (µ(j)Cj ) (x, y)(def. of concatenation)= µ(j)Cj (x, y)(def. of scalar mult.)(1)which is a non-negative value, since, both µ(j) and Cj (x, y) are non-negative.
Finally, note that for all x ∈ X :∑ ( ' Ci ) (x, (y, j)) = ∑ µ(j)Cj (x, y)
j∈I
y∈Yj

i←µ

(by Eq. (1))

j∈I
y∈Yj

= ∑ µ(j) ∑ Cj (x, y)
j∈I

y∈Yj

= ∑ µ(j) ⋅ 1(Cj ∶X ×Yj →R are channels)

j∈I

=1

(µ is a prob. dist.)

Proposition 5 (Idempotency) Given a family {Ci }i∈I of channels s.t. Ci =C for all i ∈ I, and a distribution µ on I, then: (a) ⨊i←µ Ci = C; and (b)&i←µ Ci ≈ C.
Proof. a) Idempotency of hidden choice:⨊ Ci = ∑ µ(i)Cii←µ(def. of hidden choice)i= ∑ µ(i)C(since every Ci = C)i

= C ∑ µ(i)i=C(since µ is a prob. dist.)27b) Idempotency of visible choice:' Ci = ◇i µ(i)Ci(def. of visible choice)i←µ= ◇i µ(i)C(since every Ci = C)≈C

(by Lemma 17)

In the above derivation, we can apply Lemma 17 because every column ofthe channel on each side of the equivalence can be written as a convex combination of the zero-column extension of the channel on the other side.
Proposition 6 (“Reorganization of operators”) Given a family {Cij }i∈I,j∈J
of channels indexed by sets I and J , a distribution µ on I, and a distribution
η on J :(a) ⨊i←µ ⨊j ←η Cij = ⨊i←µ Cij , if all Ci ’s have the same type;j ←η(b) &i←µ &j ←η Cij ≈ &i←µ Cij , if all Ci ’s are compatible; andj ←η(c) ⨊i←µ &j ←η Cij ≈ &j ←η ⨊i←µ Cij , if, for each i, all Cij ’s have same type
X ×Yj →R.
Proof. a)⨊ ⨊ Cij = ⨊ (∑ η(j)Cij )i←µj ←ηi←µ(def. of hidden choice)j= ∑ µ(i) (∑ η(j)Cij )i(def. of hidden choice)j= ∑ η(i)η(j)Cij(reorganizing the sums)i,j= ⨊ Cij(def. of hidden choice)

i←µ
j ←η

b)
' ' Cij = ' (◇j Cij )i←µj ←η(def. of visible choice)i←µ= ◇i µ(i) (◇j η(j)Cij )≈ ◇ij µ(i)η(j)Cij(def. of visible choice)(by Lemma 17)= ' Cij(def. of visible choice)

i←µ
j ←η

In the above derivation, we can apply Lemma 17 because every column ofthe channel on each side of the equivalence can be written as a convex combination of the zero-column extension of the channel on the other side.
28

c)⨊ ' Cij = ⨊ (◇j Cij )i←µj ←η(def. of visible choice)i←µ= ∑ µ(i) (◇j η(j)Cij )(def. of hidden choice)i≈ ◇j η(j) (∑ η(i)Cij )(by Lemma 17)i= ' ⨊ Cij(def. of operators)j ←η i←µIn the above derivation, we can apply Lemma 17 because every column ofthe channel on each side of the equivalence can be written as a convex combination of the zero-column extension of the channel on the other side.
Theorem 7 Let {Ci }i∈I be a family of channels, and µ be a distribution on I.
Then, for every distribution π on X , and every vulnerability V:(a) posterior vulnerability is convex w.r.t. to hidden choice: V [π, ⨊i←µ Ci ] ≤∑i∈I µ(i) V [π, Ci ] if all Ci ’s have the same type.
(b) posterior vulnerability is linear w.r.t. to visible choice: V [π, &i←µ Ci ] =∑i∈I µ(i) V [π, Ci ] if all Ci ’s are compatible.
Proof. a) Let us call X × Y → R the type of each channel Ci in the family {Ci }.
Then:
V [π, ⨊ Ci ] = V [π, ∑ µ(i)Ci ](def. of hidden choice)ii←µ= ∑ p(y) ⋅ V [y∈Yπ(⋅) ∑i µ(i)Ci (⋅, y)]p(y)= ∑ p(y) ⋅ V [∑ µ(i)iy∈Y≤ ∑ p(y) ⋅ ∑ µ(i)V [iy∈Y= ∑ µ(i) ∑ p(y)V [iy∈Y(def. of posterior V)

π(⋅)Ci (⋅, y)]p(y)π(⋅)Ci (⋅, y)]p(y)π(⋅)Ci (⋅, y)]p(y)= ∑ µ(i)V [π, Ci ]iwhere p(y) = ∑x∈X π(x) ∑i µ(i)Ci (x, y).
29(by convexity of V)b) Let us call X × Yi → R the type of each channel Ci in the family {Ci }. Then:V [π, ' Ci ] = V [π, ◇i µ(i)Ci ](def. of visible choice)i←µ= ∑ p(y) ⋅ V [y∈Yπ(⋅) ◇i µ(i)Ci (⋅, y)]p(y)= ∑ p(y) ⋅ V [◇i µ(i)y∈Y= ∑ p(y) ⋅ ∑ µ(i)V [iy∈Y= ∑ µ(i) ∑ p(y)V [iy∈Y(def. of posterior V)

π(⋅)Ci (⋅, y)]p(y)π(⋅)Ci (⋅, y)]p(y)(see (*) below)π(⋅)Ci (⋅, y)]p(y)= ∑ µ(i)V [π, Ci ]iwhere p(y) = ∑x∈X π(x) ∑i µ(i)Ci (x, y), and step (*) holds because in thevulnerability of a concatenation of matrices every column will contribute to
the vulnerability in proportion to its weight in the concatenation, and hence it
is possible to break the vulnerability of a concatenated matrix as the weighted
sum of the vulnerabilities of its sub-matrices.
Corollary 8 Let {Cij }i∈I,j∈J be a family of channels, all with domain X andwith the same type, and let π ∈ DX , and V be any vulnerability. Define U ∶def
DI × DJ → R as follows: U (µ, η) = V [π, ⨊i←µ &j ←η Cij ]. Then U is convex
on µ and linear on η.
Proof. To see that U (µ, η) is convex on µ, note that:
U (µ, η) = V [π, ⨊ ' Cij ](by definition)i←µ j ←η≤ ∑ µ(i) V [π, ' Cij ](by Theorem 7)

j ←η

i

To see that U (µ, η) is linear on η, note that:
U (µ, η) = V [π, ⨊ ' Cij ](by definition)i←µ j ←η= V [π, ' ⨊ Cij ](by Prop. 6)

j ←η i←µ= ∑ η(j) V [π, ⨊ Cij ]
j

i←µ

30

(by Theorem. 7)

B

Properties of binary versions of channel operators

In this section we derive some relevant properties of the binary versions of thehidden and visible choice operators. We start with results regarding each operator individually.
Proposition 18 (Properties of the binary hidden choice) For any channels C1 and C2 of the same type, and any values 0 ≤ p, q ≤ 1, the binary hidden
choice operator satisfies the following properties:a) Idempotency: C1 p ⊕ C1 = C1b) Commutativity: C1 p ⊕ C2 = C2 p̄ ⊕ C1c) Associativity:
C1 p ⊕ (C2 q ⊕ C3 ) = (1/q ⋅ C1 p ⊕ C2 ) q ⊕ p̄ ⋅ C3
if q ≠ 0.
d) Absorption:(C1 p ⊕ C2 ) q ⊕ (C1 r ⊕ C2 ) = C1 (pq+q̄r ) ⊕ C2 .
Proof. We will prove each property separately.
a) Idempotency:
C1 p ⊕ C1 = p ⋅ C1 + p̄ ⋅ C1

(def. of hidden choice)= (p + p̄) ⋅ C1
= C1

(p + p̄ = 1)b) Commutativity:
C1 p ⊕ C2 = p ⋅ C1 + p̄ ⋅ C2

(def. of hidden choice)= p̄ ⋅ C2 + p ⋅ C1
= C2 p̄ ⊕ C1

(def. of hidden choice)c) Associativity:
C1 p ⊕ (C2 q ⊕ C3 )= p ⋅ C1 + p̄(q ⋅ C2 + q̄ ⋅ C3 )(def. of hidden choice)= p ⋅ C1 + p̄q ⋅ C2 + p̄q̄ ⋅ C3
= q(p(1/q ⋅ C1 ) + p̄ ⋅ C2 ) + q̄(p̄ ⋅ C3 )= (1/q ⋅ C1 p ⊕ C2 ) q ⊕ p̄ ⋅ C3

31

(def. of hidden choice)d) Absorption: First note that:(C1 p ⊕ C2 ) q ⊕ (C1 r ⊕ C2 )= q(pC1 + p̄C2 ) + q̄(rC1 + r̄C2 )(def. of hidden choice)= pqC1 + p̄qC2 + q̄rC1 + q̄r̄C2= (pq + q̄r)C1 + (p̄q + q̄r̄)C2= C1 (pq+q̄r ) ⊕ C2(*)

To complete the proof, note that in step (*) above, pq + q̄r and p̄q + q̄r̄ form
a valid binary probability distribution (they are both non-negative, and they
add up to 1), then apply the definition of hidden choice.
Proposition 19 (Properties of binary visible choice) For any compatible
channels C1 and C2 , and any values 0 ≤ p, q ≤ 1, the visible choice operator
satisfies the following properties:a) Idempotency: C1 p H C1 ≈ C1b) Commutativity: C1 p H C2 ≈ C2 p̄ H C1c) Associativity: C1 p H (C2 q H C3 ) ≈ (1/q ⋅ C1 p H C2 ) q H p̄ ⋅ C3 if q ≠ 0.
Proof. We will prove each property separately.
a) Idempotency: C1 p H C1 ≈ C1 , by immediate application of Lemma 17, since
every column of the channel on each side of the equivalence can be written
as a convex combination of the zero-column extension of the channel on theother side.
b) Commutativity:
C1 p H C2 = p ⋅ C1 ⋄ p̄ ⋅ C2

(def. of visible choice)≈ p̄ ⋅ C2 ⋄ p ⋅ C1

(by Lemma 17)= C2 p̄ H C1

(def. of visible choice).

In the above derivation, we can apply Lemma 17 because every column ofthe channel on each side of the equivalence can be written as a convex combination of the zero-column extension of the channel on the other side.
c) Associativity:
C1 p H (C2 q H C3 ) = p ⋅ C1 ⋄ p̄(q ⋅ C2 ⋄ q̄ ⋅ C3 )(def. of visible choice)≈ p ⋅ C1 ⋄ (p̄q ⋅ C2 ⋄ p̄q̄ ⋅ C3 )(by Lemma 17)= q(p(1/q ⋅ C1 ) ⋄ p̄ ⋅ C2 ) ⋄ q̄(p̄ ⋅ C3 )= (1/q ⋅ C1 p H C2 ) q H p̄ ⋅ C3
32

(def. of visible choice)In the above derivation, we can apply Lemma 17 because every column ofthe channel on each side of the equivalence can be written as a convex combination of the zero-column extension of the channel on the other side.
Now we turn our attention to the interaction between hidden and visible
choice operators.
A first result is that hidden choice does not distribute over visible choice. To
see why, note that C1 p ⊕ (C2 q H C3 ) and (C1 p ⊕ C2 ) q H (C1 p ⊕ C3 ) cannot
be both defined: if the former is defined, then C1 must have the same type as
C2 q H C3 , whereas if the latter is defined, C1 must have the same type as C2 ,but C2 q H C3 and C2 do not have the same type (they have different outputsets).
However, as the next result shows, visible choice distributes over hidden
choice.
Proposition 20 (Distributivity of p H over q ⊕ ) Let C1 , C2 and C3 becompatible channels, and C2 and C3 have the same type. Then, for any values
0 ≤ p, q ≤ 1:
C1 p H (C2 q ⊕ C3 ) ≈ (C1 p H C2 ) q ⊕ (C1 p H C3 ).
Proof.
C1 p H (C2 q ⊕ C3 )= (C1 q ⊕ C1 ) p H (C2 q ⊕ C3 )(idempotency of visible choice)= p(q ⋅ C1 + q̄ ⋅ C1 ) ⋄ p̄(q ⋅ C2 + q̄ ⋅ C3 )(def. of operators)= (pq ⋅ C1 + pq̄ ⋅ C1 ) ⋄ (p̄q ⋅ C2 + p̄q̄ ⋅ C3 )≈ (pq ⋅ C1 ⋄ p̄q ⋅ C2 ) + (pq̄ ⋅ C1 ⋄ p̄q̄ ⋅ C3 )(by Lemma 17)= q(p ⋅ C1 ⋄ p̄ ⋅ C2 ) + q̄(p ⋅ C1 ⋄ p̄ ⋅ C3 )= q(C1 p H C2 ) + q̄(C1 p H C3 )(def. of visible choice)= (C1 p H C2 ) q ⊕ (C1 p H C3 )(def. of hidden choice)In the above derivation, we can apply Lemma 17 because every column of thechannel on each side of the equivalence can be written as a convex combinationof the zero-column extension of the channel on the other side.

33