11institutetext: Universidade Federal de Minas Gerais, Belo Horizonte, Brazil
22institutetext: CNRS and École Polytechnique, Palaiseau, France
33institutetext: AIST, Tsukuba, Japan 44institutetext: INRIA and École
Polytechnique, Palaiseau, France

Authors’ Instructions

# Leakage and Protocol Composition in a Game-Theoretic Perspective††thanks:
This version corresponds to the paper published in the POST 2018 conference
proceedings. We suggest the reader to read instead the full version of this
paper, available at [5], also because in this version there are some minor
mistakes, which have been corrected in the full version.

Mário S. Alvim 11 Konstantinos Chatzikokolakis 22 Yusuke Kawamoto 33 Catuscia
Palamidessi 44

###### 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 of the 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. The full
version of this paper can be found in https://arxiv.org/abs/1803.10042

##  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 can be done in, essentially, two ways. The first,
applicable when the correspondence secret-observable is deterministic,
consists in coarsening the equivalence classes of secrets that give rise to
the same observables. This can be achieved with post-processing, i.e.,
sequentially composing the original system with a program that removes
information from observables. For example, a typical attack on encrypted web
traffic consists on the analysis of the packets’ length, and a typical defense
consists in padding extra bits so to diminish the length variety [29].

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
usually seen 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$ that satisfy a given property. A
way to implement differential privacy [13] is to add geometrical noise to the
result of $f$, so to obtain a probability distribution $P$ on integers of the
form $P(z)=c\,e^{|z-f(x)|}$, 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,\ldots,f(x)-1,f(x)-2,\ldots$, 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 [12], which
consists in tossing a fair binary coin and then declaring the exclusive or
$\oplus$ of their secret value $x$ and the result of the coin. The protocol
can be thought as the fair probabilistic choice of two protocols, one
consisting simply of declaring $x$, and the other declaring $x\oplus 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 [9, 22, 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) [26] 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
be seen 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 the attacker 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=\\{f_{1},f_{2}\\}$ are the defender’s choices and $A=\\{a_{1},a_{2}\\}$ are
the attacker’s, and that $f_{1}(\cdot,a_{1})$ leaks more than
$f_{1}(\cdot,a_{2})$, while $f_{2}(\cdot,a_{1})$ leaks less than
$f_{2}(\cdot,a_{2})$. This is a scenario like _the matching pennies_ in game
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 gets any 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 at
them as language operators, we study their algebraic properties, which will
help reason about their behavior in games. We consider zero-sum games, in
which the gain (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 [9] and [6]. This notion has been shown [6] to subsume most
information measures, including _Bayes vulnerability_ (aka min-vulnerability,
aka (the converse of) Bayes risk) [28, 11], _Shannon entropy_ [27], _guessing
entropy_ [23], and _$g$ -vulnerability_ [7].

The main contributions of this paper are:

  * •

We present a general framework for reasoning about information leakage in a
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 and
hidden 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 flow that the
defender’s best strategy is usually randomized, only recently it has 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 each attempt
the maximum correct prefix. On the other hand, if we continue checking until
the end of the string (time padding), the program becomes very inefficient. We
show that, by using probabilistic choice instead, we can obtain 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 $\mathcal{I}$, we
denote by $\mathbb{D}\mathcal{I}$ the _set of all probability distributions_
over $\mathcal{I}$. Given $\mu\in\mathbb{D}\mathcal{I}$, its _support_ ${\sf
supp}(\mu)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{i\in\mathcal{I}:\mu(i)>0\\}$
is the set of its elements with positive probability. We use
$i{\leftarrow}\mu$ to indicate that a value $i{\in}\mathcal{I}$ is sampled
from a distribution $\mu$ on $\mathcal{I}$.

###  2.1 Basic concepts from game theory

####  2.1.1 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 of _actions_ that he
can perform, and he obtains some gain or loss depending on the actions 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_.

####  2.1.2 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 only that they are
chosen independently. Formally, such a game is defined as a tuple111Following
the convention of _security games_ , we set the first player to be the
defender. $(\mathcal{D},\,\mathcal{A},\,\mathit{u_{\sf d}},\mathit{u_{\sf
a}})$, where $\mathcal{D}$ is a nonempty set of _defender’s actions_ ,
$\mathcal{A}$ is a nonempty set of _attacker’s actions_ , $\mathit{u_{\sf
d}}:\mathcal{D}\times\mathcal{A}\rightarrow\mathbb{R}$ is the _defender’s
payoff function_ , and $\mathit{u_{\sf
a}}:\mathcal{D}\times\mathcal{A}\rightarrow\mathbb{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\in\mathcal{D}$ (resp. $a\in\mathcal{A}$). A
pair $(d,a)$ is called _pure strategy profile_ , and $\mathit{u_{\sf
d}}(d,a)$, $\mathit{u_{\sf a}}(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 $\delta\in\mathbb{D}\mathcal{D}$ (resp.
$\alpha\in\mathbb{D}\mathcal{A}$). A pair $(\delta,\alpha)$ is called _mixed
strategy profile_. The defender’s and the attacker’s _expected payoff
functions_ for mixed strategies are defined, respectively, as: $\mathit{U_{\sf
d}}(\delta,\alpha)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}{\operatornamewithlimits{\displaystyle\mathbb{E}}_{\begin{subarray}{c}d\leftarrow\delta\\\
a\leftarrow\alpha\end{subarray}}\mathit{u_{\sf
d}}(d,a)}=\sum_{\begin{subarray}{c}d\in\mathcal{D}\\\
a\in\mathcal{A}\end{subarray}}\delta(d)\alpha(a)\mathit{u_{\sf d}}(d,a)$ and
$\mathit{U_{\sf
a}}(\delta,\alpha)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}{\operatornamewithlimits{\displaystyle\mathbb{E}}_{\begin{subarray}{c}d\leftarrow\delta\\\
a\leftarrow\alpha\end{subarray}}\mathit{u_{\sf
a}}(d,a)}=\sum_{\begin{subarray}{c}d\in\mathcal{D}\\\
a\in\mathcal{A}\end{subarray}}\delta(d)\alpha(a)\mathit{u_{\sf a}}(d,a)$.

A defender’s mixed strategy $\delta\in\mathbb{D}\mathcal{D}$ is a _best
response_ to an attacker’s mixed strategy $\alpha\in\mathbb{D}\mathcal{A}$ if
$\mathit{U_{\sf
d}}(\delta,\alpha)=\max_{\delta^{\prime}\in\mathbb{D}\mathcal{D}}\mathit{U_{\sf
d}}(\delta^{\prime},\alpha)$. Symmetrically, $\alpha\in\mathbb{D}\mathcal{A}$
is a _best response_ to $\delta\in\mathbb{D}\mathcal{D}$ if $\mathit{U_{\sf
a}}(\delta,\alpha)=\max_{\alpha^{\prime}\in\mathbb{D}\mathcal{A}}\mathit{U_{\sf
d}}(\delta,\alpha^{\prime})$. A _mixed-strategy Nash equilibrium_ is a profile
$(\delta^{*},\alpha^{*})$ such that $\delta^{*}$ is the best response to
$\alpha^{*}$ and vice versa. This means that in a Nash equilibrium, no
unilateral deviation by any single player provides better payoff to that
player. If $\delta^{*}$ and $\alpha^{*}$ are point distributions concentrated
on some $d^{*}\in\mathcal{D}$ and $a^{*}\in\mathcal{A}$ respectively, then
$(\delta^{*},\alpha^{*})$ 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 game has a mixed strategy Nash equilibrium.

####  2.1.3 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
$(\mathcal{D},\,\allowbreak\mathcal{D}\,{\rightarrow}\,\mathcal{A},\,\allowbreak\mathit{u_{\sf
d}},\allowbreak\mathit{u_{\sf a}})$ where $\mathcal{D}$, $\mathcal{A}$,
$\mathit{u_{\sf d}}$ and $\mathit{u_{\sf a}}$ are defined as in simultaneous
games. Also the strategies of the defender (the leader) are defined as in
simultaneous games: an action $d\in\mathcal{D}$ for the pure case, and a
distribution $\delta\in\mathbb{D}\mathcal{D}$ for the mixed one. On the other
hand, a pure strategy for the attacker is a function $\mathit{s_{\sf
a}}:\mathcal{D}\,{\rightarrow}\,\mathcal{A}$, which represents the fact that
his choice of an action $\mathit{s_{\sf a}}$ in $\mathcal{A}$ depends on the
defender’s choice $d$. An attacker’s mixed strategy is a probability
distribution $\mathit{\sigma_{\sf
a}}\in\mathbb{D}(\mathcal{D}\,{\rightarrow}\,\mathcal{A})$ over his pure
strategies.222The definition of the mixed strategies as
$\mathbb{D}(\mathcal{D}\rightarrow\mathcal{A})$ means that the attacker draws
a function $\mathit{s_{\sf a}}:\mathcal{D}\,{\rightarrow}\,\mathcal{A}$
_before_ he knows the choice of the defender. In contrast, the so-called
_behavioral strategies_ are defined as functions
$\mathcal{D}\rightarrow\mathbb{D}\mathcal{A}$, and formalize the idea that the
draw is made after the attacker knows such choice. In our setting, these two
definitions are equivalent, in the sense that they yield the same payoff.  The
defender’s and the attacker’s _expected payoff functions_ for mixed strategies
are defined, respectively, as $\mathit{U_{\sf d}}(\delta,\mathit{\sigma_{\sf
a}})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}{\operatornamewithlimits{\displaystyle\mathbb{E}}_{\begin{subarray}{c}d\leftarrow\delta\\\
\mathit{s_{\sf a}}\leftarrow\mathit{\sigma_{\sf
a}}\end{subarray}}\mathit{u_{\sf d}}(d,\mathit{s_{\sf
a}}(d))}=\sum_{\begin{subarray}{c}d\in\mathcal{D}\\\ \mathit{s_{\sf
a}}:\mathcal{D}\,{\rightarrow}\,\mathcal{A}\end{subarray}}\delta(d)\mathit{\sigma_{\sf
a}}(\mathit{s_{\sf a}})\mathit{u_{\sf d}}(d,\mathit{s_{\sf a}}(d))$ and
$\mathit{U_{\sf a}}(\delta,\mathit{\sigma_{\sf
a}})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}{\operatornamewithlimits{\displaystyle\mathbb{E}}_{\begin{subarray}{c}d\leftarrow\delta\\\
\mathit{s_{\sf a}}\leftarrow\mathit{\sigma_{\sf
a}}\end{subarray}}\mathit{u_{\sf a}}(d,\mathit{s_{\sf
a}}(d))}=\sum_{\begin{subarray}{c}d\in\mathcal{D}\\\ \mathit{s_{\sf
a}}:\mathcal{D}\,{\rightarrow}\,\mathcal{A}\end{subarray}}\delta(d)\mathit{\sigma_{\sf
a}}(\mathit{s_{\sf a}})\mathit{u_{\sf a}}(d,\mathit{s_{\sf a}}(d))$.

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 the actions belonging to the same equivalence class. The pure
strategies of the followers, therefore, are functions from the set of the
equivalence classes on the actions of the leader to his own actions. Formally,
a _defender-first sequential game with imperfect information_ is a tuple
$(\mathcal{D},\,\mathit{K}_{\mathsf{a}}\rightarrow\mathcal{A},\,\mathit{u_{\sf
d}},\mathit{u_{\sf a}})$ where $\mathcal{D}$, $\mathcal{A}$, $\mathit{u_{\sf
d}}$ and $\mathit{u_{\sf a}}$ are defined as in simultaneous games, and
$\mathit{K}_{\mathsf{a}}$ is a partition of $\mathcal{D}$. The _expected
payoff functions_ are defined as before, except that now the argument of
$\mathit{s_{\sf a}}$ is the equivalence class of $d$. Note that in the case in
which all defender’s actions are indistinguishable from each other at the eyes
of the attacker (_totally imperfect information_), we have
$\mathit{K}_{\mathsf{a}}=\\{\mathcal{D}\\}$ and the expected payoff functions
coincide with those of the simultaneous games.

####  2.1.4 Zero-sum games and Minimax Theorem

A game $(\mathcal{D},\,\mathcal{A},\,\mathit{u_{\sf d}},\mathit{u_{\sf a}})$
is _zero-sum_ if for any $d\in\mathcal{D}$ and any $a\in\mathcal{A}$, the
defender’s loss is equivalent to the attacker’s gain, i.e., $\mathit{u_{\sf
d}}(d,a)=-\mathit{u_{\sf a}}(d,a)$. For brevity, in zero-sum games we denote
by $u$ the attacker’s payoff function $\mathit{u_{\sf a}}$, and by $U$ the
attacker’s expected payoff $\mathit{U_{\sf a}}$.333Conventionally 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 line with
the definition of payoff as vulnerability. Consequently, the goal of the
defender is to minimize $U$, and the goal of the attacker 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 $(\delta^{*},\alpha^{*})$ such that
$U(\delta^{*},\alpha^{*})=\min_{\delta}\max_{\alpha}U(\delta,\alpha)$. The von
Neumann’s minimax theorem, in fact, ensures that such solution (which always
exists) is stable.

######  Theorem 1 (von Neumann’s minimax theorem)

Let $\mathcal{X}\subset\mathbb{R}^{m}$ and $\mathcal{Y}\subset\mathbb{R}^{n}$
be compact convex sets, and
$\mathit{U}:\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$ be a continuous
function such that $\mathit{U}(x,y)$ is a convex function in $x\in\mathcal{X}$
and a concave function in $y\in\mathcal{Y}$. Then
$\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}}\mathit{U}(x,y)=\max_{y\in\mathcal{Y}}\min_{x\in\mathcal{X}}\mathit{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{\in}\mathcal{X}$ and
$y{\in}\mathcal{Y}$:
$\mathit{U}(x^{*},y){\leq}\mathit{U}(x^{*},y^{*}){\leq}\mathit{U}(x,y^{*})$.

The solution of the minimax problem can be obtained by using convex
optimization techniques. In case $\mathit{U}(x,y)$ is affine in $x$ and in
$y$, we can also use linear optimization.

In case $\mathcal{D}$ and $\mathcal{A}$ contain two elements each, there is a
closed form for the solution. Let $\mathcal{D}=\\{d_{0},d_{1}\\}$ and
$\mathcal{A}=\\{a_{0},a_{1}\\}$ respectively. Let $u_{ij}$ be the utility of
the defender on $d_{i},a_{j}$. Then the Nash equilibrium
$(\delta^{*},\alpha^{*})$ is given by:
$\delta^{*}(d_{0})=\nicefrac{{(u_{11}-u_{10})}}{{(u_{00}-u_{01}-u_{10}+u_{11})}}$
and
$\alpha^{*}(a_{0})=\nicefrac{{(u_{11}-u_{01})}}{{(u_{00}-u_{01}-u_{10}+u_{11})}}$
if these values are in $[0,1]$. Note that, since there are only two elements,
the strategy $\delta^{*}$ is completely specified by its value in $d_{0}$, and
analogously for $\alpha^{*}$.

###  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 called a
_prior_. We denote by $\mathcal{X}$ the set of possible secrets, and we
typically use $\pi$ to denote a prior belonging to the set
$\mathbb{D}{\mathcal{X}}$ of probability distributions over $\mathcal{X}$.

The _vulnerability_ of a secret is a measure of the utility that it represents
for the attacker. In this paper we consider a very general notion of
vulnerability, following [6], and we define a vulnerability $\mathbb{V}$ to be
any continuous and convex function of type
$\mathbb{D}{\mathcal{X}}\rightarrow\mathbb{R}$. It has been shown in [6] that
these functions coincide with the set of $g$-vulnerabilities, and are, in a
precise sense, the most general information measures w.r.t. a set of basic
axioms. 444More 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.

##### Channels, posterior vulnerability, and leakage

Computational systems can be modeled as information theoretic channels. A
_channel_ $C:\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$ is a function
in which $\mathcal{X}$ is a set of _input values_ , $\mathcal{Y}$ is a set of
_output values_ , and $C(x,y)$ represents the conditional probability of the
channel producing output $y\in\mathcal{Y}$ when input $x\in\mathcal{X}$ is
provided. Every channel $C$ satisfies $0\leq C(x,y)\leq 1$ for all
$x\in\mathcal{X}$ and $y\in\mathcal{Y}$, and $\sum_{y\in\mathcal{Y}}C(x,y)=1$
for all $x\in\mathcal{X}$.

A distribution $\pi\in\mathbb{D}{\mathcal{X}}$ and a channel $C$ with inputs
$\mathcal{X}$ and outputs $\mathcal{Y}$ induce a joint distribution
$p(x,y)=\pi(x)C({x,y})$ on $\mathcal{X}\times\mathcal{Y}$, producing joint
random variables $X,Y$ with marginal probabilities $p(x)=\sum_{y}p(x,y)$ and
$p(y)=\sum_{x}p(x,y)$, and conditional probabilities
$p(x{\mid}y)=\nicefrac{{p(x,y)}}{{p(y)}}$ if $p(y)\neq 0$. For a given $y$
(s.t. $p(y)\neq 0$), the conditional probabilities $p(x{\mid}y)$ for each
$x\in\mathcal{X}$ form the _posterior distribution $p_{X\mid y}$_.

A channel $C$ in which $\mathcal{X}$ is a set of secret values and
$\mathcal{Y}$ is a set of observable values produced by a system can be used
to model computations on secrets. Assuming the attacker has prior knowledge
$\pi$ about the secret value, knows how a channel $C$ works, and can observe
the channel’s outputs, the effect of the channel is to update the attacker’s
knowledge from $\pi$ to a collection of posteriors $p_{X\mid y}$, each
occurring with probability $p(y)$.

Given a vulnerability $\mathbb{V}$, a prior $\pi$, and a channel $C$, the
_posterior vulnerability_ $\mathbb{V}\left[\pi,C\right]$ is the vulnerability
of the secret after the attacker has observed the output of the channel $C$.
Formally:
$\mathbb{V}\left[\pi,C\right]\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{y\in\mathcal{Y}}p(y)\mathbb{V}\left[p_{X\mid
y}\right]$.

It is known from the literature [6] that the posterior vulnerability is a
convex function of $\pi$. Namely, for any channel $C$, any family of
distributions $\\{\pi_{i}\\}$, and any set of convex coefficients
$\\{c_{i}\\}$, we have:
$\mathbb{V}\left[\sum_{i}c_{i}\pi_{i},C\right]\leq\sum_{i}c_{i}\mathbb{V}\left[\pi_{i},C\right]$.

The _(information) leakage_ of channel $C$ under prior $\pi$ is a comparison
between the vulnerability of the secret before the system was run—called
_prior vulnerability_ —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_
($\mathbb{V}\left[\pi,C\right]-\mathbb{V}\left[\pi\right]$), or
_multiplicatively_
($\nicefrac{{\mathbb{V}\left[\pi,C\right]}}{{\mathbb{V}\left[\pi\right]}}$).

##  3 An illustrative example

Program 0
High Input: $x\in\\{0,1\\}$
Low Input: $a\in\\{0,1\\}$
Output: $y\in\\{0,1\\}$
$y=x\cdot a$
return $y$
Program 1
High Input: $x\in\\{0,1\\}$
Low Input: $a\in\\{0,1\\}$
Output: $y\in\\{0,1\\}$
$c\leftarrow{\text{flip coin with bias $\nicefrac{{a}}{{3}}$}}$
if $c=\mathit{heads}$ {$y=x$}
else {$y=\bar{x}$}
return $y$

Figure 1: Running example.

We introduce an example which will serve as running example through the paper.
Although admittedly contrived, this example is simple and yet produces
different leakage measures for all different combinations of visible/invisible
choice and simultaneous/sequential games, thus providing a way to compare all
different scenarios we are interested in.

Consider that a binary secret must be processed by a program. As usual, a
defender wants to protect the secret value, whereas an attacker wants to infer
it by observing the system’s output. Assume the defender can choose which
among two alternative versions of the program to run. Both programs take the
secret value $x$ as high input, and a binary low input $a$ whose value is
chosen by the attacker. They both return the output in a low variable $y$.
555We adopt the usual convention in QIF of referring to secret variables,
inputs and outputs in programs as _high_ , and to their observable
counterparts as _low_. Program 0 returns the binary product of $x$ and $a$,
whereas Program 1 flips a coin with bias $\nicefrac{{a}}{{3}}$ (i.e., a coin
which returns heads with probability $\nicefrac{{a}}{{3}}$) and returns $x$ if
the result is heads, and the complement $\bar{x}$ of $x$ otherwise. The two
programs are represented in Figure 1.

The combined choices of the defender’s and of the attacker’s determine how the
system behaves. Let $\mathcal{D}{=}\\{0,1\\}$ represent the set of the
defender’s choices—i.e., the index of the program to use—, and
$\mathcal{A}=\\{0,1\\}$ represent the set of the attacker’s choices—i.e., the
value of the low input $a$. We shall refer to the elements of $\mathcal{D}$
and $\mathcal{A}$ as _actions_. For each possible combination of actions
$d\in\mathcal{D}$ and $a\in\mathcal{A}$, we can construct a channel $C_{da}$
modeling how the resulting system behaves. Each channel $C_{da}$ is a function
of type $\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$, where
$\mathcal{X}=\\{0,1\\}$ is the set of possible high input values for the
system, and $\mathcal{Y}=\\{0,1\\}$ is the set of possible output values from
the system. Intuitively, each channel provides the probability that the system
(which was fixed by the defender) produces output $y\in\mathcal{Y}$ given that
the high input is $x\in\mathcal{X}$ (and that the low input was fixed by the
attacker). The four possible channels are depicted as matrices below.

$\displaystyle\begin{array}[]{|c|c|c|}\hline\cr C_{00}&y=0&y=1\\\ \hline\cr
x=0&1&0\\\ x=1&1&0\\\
\hline\cr\end{array}\quad\begin{array}[]{|c|c|c|}\hline\cr C_{01}&y=0&y=1\\\
\hline\cr x=0&1&0\\\ x=1&0&1\\\
\hline\cr\end{array}\quad\begin{array}[]{|c|c|c|}\hline\cr C_{10}&y=0&y=1\\\
\hline\cr x=0&0&1\\\ x=1&1&0\\\
\hline\cr\end{array}\quad\begin{array}[]{|c|c|c|}\hline\cr C_{11}&y=0&y=1\\\
\hline\cr x=0&\nicefrac{{1}}{{3}}&\nicefrac{{2}}{{3}}\\\
x=1&\nicefrac{{2}}{{3}}&\nicefrac{{1}}{{3}}\\\ \hline\cr\end{array}$

Note that channel $C_{00}$ does not leak any information about the input $x$
(i.e., it is _non-interferent_), whereas channels $C_{01}$ and $C_{10}$
completely reveal $x$. Channel $C_{11}$ 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
of posterior vulnerability, since in order to make the comparison fair we need
to assume 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).

$\begin{array}[]{|c|c|c|}\hline\cr\mathbb{V}&a=0&a=1\\\ \hline\cr
d=0&\nicefrac{{1}}{{2}}&1\\\ \hline\cr d=1&1&\nicefrac{{2}}{{3}}\\\
\hline\cr\end{array}$ Table 1: Vulnerability of each channel $C_{da}$ in the
running example.

For this example, assume we are interested in Bayes vulnerability [11, 28],
defined as $\mathbb{V}(\pi)=\max_{x}\pi(x)$ for every
$\pi\in\mathbb{D}{\mathcal{X}}$. Assume for simplicity that the prior is the
uniform prior $\pi_{u}$. In this case we know from [10] that the posterior
Bayes vulnerability of a channel is the sum of the greatest elements of each
column, divided by the total number of inputs. Table 1 provides the Bayes
vulnerability
$\mathbb{V}_{da}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathbb{V}\left[\pi_{u},C_{da}\right]$
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
choice _simultaneously_ (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 who moves second, the opponent will be in advantage. In the above
example, for instance, 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 $\nicefrac{{2}}{{3}}$ . Vice versa, if the attacker knows the
choice $d$ of the defender, the most convenient choice for him is to set
$a\neq 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,
because the vulnerability of the system depends also on the (unknown) choice
of 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), in that the players randomize their choices according to some
precise distribution.

Another factor that affects vulnerability is whether or not the defender’s
choice is known to the attacker at the moment in which he observes the output
of 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 the other hand, the attacker may be able to identify the
channel used anyway, for instance because the two programs have different
running times. We will call these 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 our technical 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. Since
channels are a particular kind of matrix, we use these matrix operations to
define 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 $\mathcal{X}$ and $\mathcal{Y}$, a _matrix_ is a total function
of type $\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$. Two matrices
$M_{1}:\mathcal{X}_{1}\times\mathcal{Y}_{1}\rightarrow\mathbb{R}$ and
$M_{2}:\mathcal{X}_{2}\times\mathcal{Y}_{2}\rightarrow\mathbb{R}$ are said to
be _compatible_ if $\mathcal{X}_{1}=\mathcal{X}_{2}$. If it is also the case
that $\mathcal{Y}_{1}=\mathcal{Y}_{2}$, we say that the matrices _have the
same type_. The _scalar multiplication_ $r{\cdot}M$ between a scalar $r$ and a
matrix $M$ is defined as usual, and so is the _summation_
$\left(\sum_{i\in\mathcal{I}}M_{i}\right)(x,y)=M_{i_{1}}(x,y)\operatorname{+}\ldots\operatorname{+}M_{i_{n}}(x,y)$
of a family $\\{M_{i}\\}_{i\in\mathcal{I}}$ of matrices all of a same type.

Given a family $\\{M_{i}\\}_{i\in\mathcal{I}}$ of compatible matrices s.t.
each $M_{i}$ has type $\mathcal{X}\times\mathcal{Y}_{i}\rightarrow\mathbb{R}$,
their _concatenation_ $\meddiamond_{i\in\mathcal{I}}$ is the matrix having all
columns of every matrix in the family, in such a way that every column is
tagged with the matrix it came from. Formally,
$\left(\meddiamond_{i\in\mathcal{I}}M_{i}\right)(x,(y,j))=\,M_{j}(x,y)$, if
$y\in\mathcal{Y}_{j}$, and the resulting matrix has type
$\mathcal{X}\times\left(\bigsqcup_{i\in\mathcal{I}}\mathcal{Y}_{i}\right)\rightarrow\mathbb{R}$.
666$\bigsqcup_{i\in\mathcal{I}}\mathcal{Y}_{i}=\mathcal{Y}_{i_{1}}\sqcup\mathcal{Y}_{i_{2}}\sqcup\ldots\sqcup\mathcal{Y}_{i_{n}}$
denotes the _disjoint union_ $\\{(y,i)\mid
y\in\mathcal{Y}_{i},i\in\mathcal{I}\\}$ of the sets $\mathcal{Y}_{i_{1}}$,
$\mathcal{Y}_{i_{2}}$, $\ldots$, $\mathcal{Y}_{i_{n}}$.  When the family
$\\{M_{i}\\}$ has only two elements we may use the _binary_ version $\diamond$
of the concatenation operator. The following depicts the concatenation of two
matrices $M_{1}$ and $M_{2}$ in tabular form.

$\small\begin{array}[]{|c|cc|}\hline\cr M_{1}&y_{1}&y_{2}\\\ \hline\cr
x_{1}&1&2\\\ x_{2}&3&4\\\
\hline\cr\end{array}\diamond\begin{array}[]{|c|ccc|}\hline\cr
M_{2}&y_{1}&y_{2}&y_{3}\\\ \hline\cr x_{1}&5&6&7\\\ x_{2}&8&9&10\\\
\hline\cr\end{array}\;=\;\begin{array}[]{|c|ccccc|}\hline\cr M_{1}\diamond
M_{2}&(y_{1},1)&(y_{2},1)&(y_{1},2)&(y_{2},2)&(y_{3},2)\\\ \hline\cr
x_{1}&1&2&5&6&7\\\ x_{2}&3&4&8&9&10\\\ \hline\cr\end{array}$

###  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 the following, for any real value $0\leq p\leq 1$, we denote by $\bar{p}$
the value $1-p$.

####  4.2.1 Hidden choice

The first operator models a hidden probabilistic choice among channels.
Consider a family $\left\\{C_{i}\right\\}_{i\in\mathcal{I}}$ of channels of a
same type. Let $\mu\in\mathbb{D}{\mathcal{I}}$ be a probability distribution
on the elements of the index set $\mathcal{I}$. Consider an input $x$ is fed
to one of the channels in $\left\\{C_{i}\right\\}_{i\in\mathcal{I}}$, where
the channel is randomly picked according to $\mu$. More precisely, an index
$i\in\mathcal{I}$ is sampled with probability $\mu(i)$, then the input $x$ is
fed to channel $C_{i}$, 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 which
channel was used.

Formally, given a family $\\{C_{i}\\}_{i\in\mathcal{I}}$ of channels s.t. each
$C_{i}$ has same type $\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$, the
_hidden choice operator_ ${\osum_{\mathit{i}\leftarrow\mathit{\mu}}}$ is
defined as
${\osum_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}=\sum_{i\in\mathcal{I}}\mu(i)\,C_{i}$.

###### Proposition 2

Given a family $\\{C_{i}\\}_{i\in\mathcal{I}}$ of channels of type
$\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$, and a distribution $\mu$
on $\mathcal{I}$, the hidden choice
${\osum_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}$ is a channel of type
$\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$.

In the particular case in which the family $\\{C_{i}\\}$ has only two elements
$C_{i_{1}}$ and $C_{i_{2}}$, the distribution $\mu$ on indexes is completely
determined by a real value $0\leq p\leq 1$ s.t. $\mu(i_{1})=p$ and
$\mu(i_{2})=\bar{p}$. In this case we may use the _binary_ version
$\;{{}_{\mathit{p}}{{{\oplus}}}}\;$ of the hidden choice operator:
$C_{i_{1}}{\;{{}_{\mathit{p}}{{{\oplus}}}}\;}C_{i_{2}}=p\,C_{i_{1}}{+}\bar{p}\,C_{i_{2}}$.
The example below depicts the hidden choice between channels $C_{1}$ and
$C_{2}$, with probability $p{=}\nicefrac{{1}}{{3}}$.

$\small\begin{array}[]{|c|cc|}\hline\cr C_{1}&y_{1}&y_{2}\\\ \hline\cr
x_{1}&\nicefrac{{1}}{{2}}&\nicefrac{{1}}{{2}}\\\
x_{2}&\nicefrac{{1}}{{3}}&\nicefrac{{2}}{{3}}\\\
\hline\cr\end{array}\;{{}_{\mathit{\nicefrac{{1}}{{3}}}}{{{\oplus}}}}\;\begin{array}[]{|c|cc|}\hline\cr
C_{2}&y_{1}&y_{2}\\\ \hline\cr
x_{1}&\nicefrac{{1}}{{3}}&\nicefrac{{2}}{{3}}\\\
x_{2}&\nicefrac{{1}}{{2}}&\nicefrac{{1}}{{2}}\\\
\hline\cr\end{array}\;=\;\begin{array}[]{|c|cc|}\hline\cr
C_{1}\;{{}_{\mathit{\nicefrac{{1}}{{3}}}}{{{\oplus}}}}\;C_{2}&y_{1}&y_{2}\\\
\hline\cr x_{1}&\nicefrac{{7}}{{18}}&\nicefrac{{11}}{{18}}\\\
x_{2}&\nicefrac{{4}}{{9}}&\nicefrac{{5}}{{9}}\\\ \hline\cr\end{array}$

####  4.2.2 Visible choice

The second operator models a visible probabilistic choice among channels.
Consider a family $\left\\{C_{i}\right\\}_{i\in\mathcal{I}}$ of compatible
channels. Let $\mu\in\mathbb{D}{\mathcal{I}}$ be a probability distribution on
the elements of the index set $\mathcal{I}$. Consider an input $x$ is fed to
one of the channels in $\left\\{C_{i}\right\\}_{i\in\mathcal{I}}$, where the
channel is randomly picked according to $\mu$. More precisely, an index
$i\in\mathcal{I}$ is sampled with probability $\mu(i)$, then the input $x$ is
fed to channel $C_{i}$, and the output $y$ produced by the channel is then
made visible, along with the index $i$ of the channel that was used. Note 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 $\\{C_{i}\\}_{i\in\mathcal{I}}$ of compatible channels s.t.
each $C_{i}$ has type $\mathcal{X}\times\mathcal{Y}_{i}\rightarrow\mathbb{R}$,
and a distribution $\mu$ on $\mathcal{I}$, the _visible choice operator_
${\bigsqcupdot_{\mathit{i}\leftarrow\mathit{\mu}}}$ is defined as
${\bigsqcupdot_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}=\meddiamond_{i\in\mathcal{I}}\;\mu(i)\,C_{i}$.

###### Proposition 3

Given a family $\\{C_{i}\\}_{i\in\mathcal{I}}$ of compatible channels s.t.
each $C_{i}$ has type $\mathcal{X}\times\mathcal{Y}_{i}\rightarrow\mathbb{R}$,
and a distribution $\mu$ on $\mathcal{I}$, the result of the visible choice
${\bigsqcupdot_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}$ is a channel of type
$\mathcal{X}\times\left(\bigsqcup_{i\in\mathcal{I}}\mathcal{Y}_{i}\right)\rightarrow\mathbb{R}$.

In the particular case the family $\\{C_{i}\\}$ has only two elements
$C_{i_{1}}$ and $C_{i_{2}}$, the distribution $\mu$ on indexes is completely
determined by a real value $0\leq p\leq 1$ s.t. $\mu(i_{1})=p$ and
$\mu(i_{2})=\bar{p}$. In this case we may use the _binary_ version
$\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;$ of the visible choice operator:
$C_{i_{1}}\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;C_{i_{2}}=p\,C_{i_{1}}\diamond\bar{p}\,C_{i_{2}}$.
The following depicts the visible choice betwee channels $C_{1}$ and $C_{3}$,
with probability $p{=}\nicefrac{{1}}{{3}}$.

$\small\begin{array}[]{|c|cc|}\hline\cr C_{1}&y_{1}&y_{2}\\\ \hline\cr
x_{1}&\nicefrac{{1}}{{2}}&\nicefrac{{1}}{{2}}\\\
x_{2}&\nicefrac{{1}}{{3}}&\nicefrac{{2}}{{3}}\\\
\hline\cr\end{array}\;{{}_{\mathit{\nicefrac{{1}}{{3}}}}{{{\sqcupdot}}}}\;\begin{array}[]{|c|cc|}\hline\cr
C_{3}&y_{1}&y_{3}\\\ \hline\cr
x_{1}&\nicefrac{{1}}{{3}}&\nicefrac{{2}}{{3}}\\\
x_{2}&\nicefrac{{1}}{{2}}&\nicefrac{{1}}{{2}}\\\
\hline\cr\end{array}\;=\;\begin{array}[]{|c|cccc|}\hline\cr
C_{1}\;{{}_{\mathit{\nicefrac{{1}}{{3}}}}{{{\sqcupdot}}}}\;C_{3}&(y_{1},1)&(y_{2},1)&(y_{1},3)&(y_{3},3)\\\
\hline\cr
x_{1}&\nicefrac{{1}}{{6}}&\nicefrac{{1}}{{6}}&\nicefrac{{2}}{{9}}&\nicefrac{{4}}{{9}}\\\
x_{2}&\nicefrac{{1}}{{9}}&\nicefrac{{2}}{{9}}&\nicefrac{{1}}{{3}}&\nicefrac{{1}}{{3}}\\\
\hline\cr\end{array}$

###  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, those of
visible choice are subtler. For instance, visible choice is not idempotent,
since in general $C{\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;}C\neq C$. (In fact if
$C$ has type $\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$,
$C{\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;}C$ has type
$\mathcal{X}\times(\mathcal{Y}\sqcup\mathcal{Y})\rightarrow\mathbb{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 $C_{1}$ and $C_{2}$ with domain $\mathcal{X}$ are
_equivalent_ , denoted by $C_{1}\approx C_{2}$, if for every prior
$\pi\in\mathbb{D}{\mathcal{X}}$ and every posterior vulnerability $\mathbb{V}$
we have $\mathbb{V}\left[\pi,C_{1}\right]=\mathbb{V}\left[\pi,C_{2}\right]$.

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_ [24, 6], which capture
exactly the important 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 be
used do simplify the representation of some protocols.

######  Proposition 5 (Idempotency)

Given a family $\\{C_{i}\\}_{i\in\mathcal{I}}$ of channels s.t. $C_{i}=C$ for
all $i\in\mathcal{I}$, and a distribution $\mu$ on $\mathcal{I}$, then: (a)
${{\osum_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}=C}$; and (b)
${{\bigsqcupdot_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}\approx 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 which
hidden and visible choice are applied in a protocol.

######  Proposition 6 (“Reorganization of operators”)

Given a family $\\{C_{ij}\\}_{i\in\mathcal{I},j\in\mathcal{J}}$ of channels
indexed by sets $\mathcal{I}$ and $\mathcal{J}$, a distribution $\mu$ on
$\mathcal{I}$, and a distribution $\eta$ on $\mathcal{J}$:

  1. (a)

${{\osum_{\mathit{i}\leftarrow\mathit{\mu}}}\;{\osum_{\mathit{j}\leftarrow\mathit{\eta}}}C_{ij}={\osum_{\begin{subarray}{c}\mathit{i}\leftarrow\mathit{\mu}\\\
\mathit{j}\leftarrow\mathit{\eta}\end{subarray}}}C_{ij}}$, if all $C_{i}$’s
have the same type;

  2. (b)

${{\bigsqcupdot_{\mathit{i}\leftarrow\mathit{\mu}}}\;{\bigsqcupdot_{\mathit{j}\leftarrow\mathit{\eta}}}C_{ij}\approx{\bigsqcupdot_{\begin{subarray}{c}\mathit{i}\leftarrow\mathit{\mu}\\\
\mathit{j}\leftarrow\mathit{\eta}\end{subarray}}}C_{ij}}$, if all $C_{i}$’s
are compatible; and

  3. (c)

${{\osum_{\mathit{i}\leftarrow\mathit{\mu}}}\;{\bigsqcupdot_{\mathit{j}\leftarrow\mathit{\eta}}}C_{ij}\approx{\bigsqcupdot_{\mathit{j}\leftarrow\mathit{\eta}}}\;{\osum_{\mathit{i}\leftarrow\mathit{\mu}}}C_{ij}}$,
if, for each $i$, all $C_{ij}$’s have same type
$\mathcal{X}{\times}\mathcal{Y}_{j}{\rightarrow}\mathbb{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 $\\{C_{i}\\}_{i\in\mathcal{I}}$ be a family of channels, and $\mu$ be a
distribution on $\mathcal{I}$. Then, for every distribution $\pi$ on
$\mathcal{X}$, and every vulnerability $\mathbb{V}$:

  1. (a)

posterior vulnerability is convex w.r.t. to hidden choice:
$\mathbb{V}\left[\pi,{\osum_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}\right]\leq\sum_{i\in\mathcal{I}}\mu(i)\,\mathbb{V}\left[\pi,C_{i}\right]$
if all $C_{i}$’s have the same type.

  2. (b)

posterior vulnerability is linear w.r.t. to visible choice:
$\mathbb{V}\left[\pi,{\bigsqcupdot_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}\right]=\sum_{i\in\mathcal{I}}\mu(i)\,\mathbb{V}\left[\pi,C_{i}\right]$
if all $C_{i}$’s are compatible.

The next result is concerned with posterior vulnerability under the
composition of channels using both operators.

###### Corollary 8

Let $\\{C_{ij}\\}_{i\in\mathcal{I},j\in\mathcal{J}}$ be a family of channels,
all with domain $\mathcal{X}$ and with the same type, and let
$\pi\in\mathbb{D}\mathcal{X}$, and $\mathbb{V}$ be any vulnerability. Define
$\mathit{U}:\mathbb{D}\mathcal{I}\times\mathbb{D}\mathcal{J}\rightarrow\mathbb{R}$
as follows:
$\mathit{U}(\mu,\eta)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathbb{V}\left[\pi,{\osum_{\mathit{i}\leftarrow\mathit{\mu}}}\;{\bigsqcupdot_{\mathit{j}\leftarrow\mathit{\eta}}}\;C_{ij}\right]$.
Then $\mathit{U}$ is convex on $\mu$ and linear on $\eta$.

##  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 the execution 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 the best strategy to maximize their expected payoff),
and that the set of actions and the 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
produces some 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, and the 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 and
prior vulnerability. Since we are only interested in comparing the leakage of
different 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
$\mathcal{D}$, $\mathcal{A}$ of defender’s and attacker’s actions
respectively, (2) a function
$C:\mathcal{D}{\times}\mathcal{A}\rightarrow(\mathcal{X}{\times}\mathcal{Y}\rightarrow\mathbb{R})$
that associates to each pair of actions
$(d,a)\in\mathcal{D}{\times}\mathcal{A}$ a channel
$C_{da}:\mathcal{X}{\times}\mathcal{Y}\rightarrow\mathbb{R}$, (3) a prior
$\pi\in\mathbb{D}{\mathcal{X}}$ on secrets, and (4) a vulnerability measure
$\mathbb{V}$. The payoff function
$u:\mathcal{D}{\times}\mathcal{A}\rightarrow\mathbb{R}$ for pure strategies is
defined as
$u(d,a)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathbb{V}\left[\pi,C_{da}\right]$.
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 which
a player knows the move performed by the opponent play a critical role in
deciding strategies and determining the payoff. In security, however,
knowledge of the opponent’s move affects the game in yet another way: the
effectiveness of the attack, 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 the players may
commit first to his action, and his choice may or may not be 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 $C_{da}$ and performs
his attack on the secret. In case he knows the defender’s action, he is able
to determine the exact channel $C_{da}$ being used (since, of course, the
attacker knows his own action), and his payoff will be the posterior
vulnerability $\mathbb{V}\left[\pi,C_{da}\right]$. However, if the attacker
does not know exactly which channel 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 game
theory. 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 for
games, along two lines of classification. First, there are three possible
orders for the 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., the
follower 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 the output of the
channel, and therefore he knows which channel is being used. Visible choice is
modeled by the operator $\bigsqcupdot$.

Hidden choice:

The attacker does not know the defender’s action when he observes the output
of the channel, and therefore in general he does not exactly know which
channel is used (although in some special cases he may infer it from the
output). Hidden choice is modeled by the operator $\osum$.

Note that the distinction between sequential and simultaneous games is
orthogonal to that between visible and hidden choice. Sequential and
simultaneous games model whether or not, respectively, the follower’s choice
can be affected by 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 the other hand, visible and hidden choice capture whether or
not, respectively, the attacker is able to fully determine the channel
representing the system, _once defender and attacker’s actions have already
been fixed_. This dichotomy reflects the different _amounts of information
leaked_ by the system as viewed by the adversary. For instance, in a
simultaneous game neither player can choose his action based on the choice of
the other. However, depending on whether or not the defender’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 $\osum$, since that would mean that the attacker knows the action of
the defender and choses his strategy accordingly, but forgets it at the moment
of the attack. (We assume _perfect recall_ , i.e., the players never forget
what they have learned.) Yet other combinations are not interesting, such as
the attacker-first sequential game with (totally) imperfect information (by
the defender), since it coincides with the simultaneous-game case. Note that
attacker and defender are not symmetric with respect to hiding/revealing their
actions $a$ and $d$, since the knowledge of $a$ affects the game only in the
usual sense of game theory, while the knowledge of $d$ also affects the
computation of the payoff (cf. “Phase 2” above).

Table 2 lists the meaningful and interesting combinations. In Game V we assume
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 game
individually, using the example of Section 3 as running example.

| Order of action
---|---
| simultaneous | defender 1st | attacker 1st
Defender’schoice | visible $\bigsqcupdot$ | Game I | Game II | Game III
hidden $\osum$ | Game IV | Game V | Game VI
Table 2: Kinds of games we consider. All sequential games have perfect
information, except for game V.

####  5.1.1 Game I (simultaneous with visible choice)

This simultaneous game can be represented by a tuple
$(\mathcal{D},\,\mathcal{A},\,\mathit{u})$. As in all games with visible
choice $\bigsqcupdot$, the expected payoff $\mathit{U}$ of a mixed strategy
profile $(\delta,\alpha)$ is defined to be the expected value of $u$, as in
traditional game theory:
$\mathit{U}(\delta,\alpha)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}{\operatornamewithlimits{\displaystyle\mathbb{E}}_{\begin{subarray}{c}d\leftarrow\delta\\\
a\leftarrow\alpha\end{subarray}}\mathit{u}(d,a)}=\sum_{\begin{subarray}{c}d\in\mathcal{D}\\\
a\in\mathcal{A}\end{subarray}}\delta(d)\,\alpha(a)\,\mathit{u}(d,a)$, where we
recall that $\mathit{u}(d,a)=\mathbb{V}\left[\pi,C_{da}\right]$.

From Theorem 7(b) we derive:
$\mathit{U}(\delta,\alpha)=\mathbb{V}\left[\pi,{\bigsqcupdot_{\begin{subarray}{c}\mathit{d}\leftarrow\mathit{\delta}\\\
\mathit{a}\leftarrow\mathit{\alpha}\end{subarray}}}C_{da}\right]$. hence the
whole system can be equivalently regarded as the channel
${\bigsqcupdot_{\begin{subarray}{c}\mathit{d}\leftarrow\mathit{\delta}\\\
\mathit{a}\leftarrow\mathit{\alpha}\end{subarray}}}C_{da}$. Still from Theorem
7(b) we can derive that $\mathit{U}(\delta,\alpha)$ is linear in $\delta$ and
$\alpha$. Therefore the Nash equilibrium 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 $(\delta^{*},\alpha^{*})$ can be obtained using the closed formula
from Section 2.1, and it is given by
$\delta^{*}(0)=\alpha^{*}(0)=\nicefrac{{(\nicefrac{{2}}{{3}}-1)}}{{(\nicefrac{{1}}{{2}}-1-1+\nicefrac{{2}}{{3}})}}=\nicefrac{{2}}{{5}}.$
The corresponding payoff is
$\mathit{U}(\delta^{*},\alpha^{*})=\nicefrac{{2}}{{5}}\,\nicefrac{{2}}{{5}}\,\nicefrac{{1}}{{2}}+\nicefrac{{2}}{{5}}\,\nicefrac{{3}}{{5}}+\nicefrac{{3}}{{5}}\,\nicefrac{{2}}{{5}}+\nicefrac{{3}}{{5}}\,\nicefrac{{3}}{{5}}\,\nicefrac{{2}}{{3}}=\nicefrac{{4}}{{5}}$.

####  5.1.2 Game II (defender 1st with visible choice)

This defender-first sequential game can be represented by a tuple
$(\mathcal{D},\,\mathcal{D}\,{\rightarrow}\,\mathcal{A},\,\mathit{u})$. A
mixed strategy profile is of the form $(\delta,\mathit{\sigma_{\sf a}})$, with
$\delta\in\mathbb{D}\mathcal{D}$ and $\mathit{\sigma_{\sf
a}}\in\mathbb{D}(\mathcal{D}\,{\rightarrow}\,\mathcal{A})$, and the
corresponding payoff is $\mathit{U}(\delta,\mathit{\sigma_{\sf
a}})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}{\operatornamewithlimits{\displaystyle\mathbb{E}}_{\begin{subarray}{c}d\leftarrow\delta\\\
\mathit{s_{\sf a}}\leftarrow\mathit{\sigma_{\sf
a}}\end{subarray}}\mathit{u}(d,\mathit{s_{\sf
a}}(d))}\allowbreak=\allowbreak\sum_{\begin{subarray}{c}d\in\mathcal{D}\\\
\mathit{s_{\sf
a}}:\mathcal{D}\,{\rightarrow}\,\mathcal{A}\end{subarray}}\delta(d)\,\mathit{\sigma_{\sf
a}}(\mathit{s_{\sf a}})\,\mathit{u}(d,\mathit{s_{\sf a}}(d))$, where
$\mathit{u}(d,\mathit{s_{\sf a}}(d))=\mathbb{V}\left[\pi,C_{d\mathit{s_{\sf
a}}(d)}\right]$.

Again, from Theorem 7(b) we derive:
$\textstyle\mathit{U}(\delta,\mathit{\sigma_{\sf
a}})=\mathbb{V}\left[\pi,{\bigsqcupdot_{\begin{subarray}{c}\mathit{d}\leftarrow\mathit{\delta}\\\
\mathit{\mathit{s_{\sf a}}}\leftarrow\mathit{\mathit{\sigma_{\sf
a}}}\end{subarray}}}C_{d\mathit{s_{\sf a}}(d)}\right]$ and hence the system
can be expressed as channel
$\textstyle{\bigsqcupdot_{\begin{subarray}{c}\mathit{d}\leftarrow\mathit{\delta}\\\
\mathit{\mathit{s_{\sf a}}}\leftarrow\mathit{\mathit{\sigma_{\sf
a}}}\end{subarray}}}C_{d\mathit{s_{\sf a}}(d)}$. From the same Theorem we also
derive that $\mathit{U}(\delta,\mathit{\sigma_{\sf a}})$ is linear in $\delta$
and $\mathit{\sigma_{\sf 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 $\max_{a}\mathit{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$ then
the attacker chooses $0$. In both cases, the payoff is $1$. The game has
therefore two solutions, $(0,1)$ and $(1,0)$.

####  5.1.3 Game III (attacker 1st with visible choice)

This game is also a sequential game, but with the attacker as the leader.
Therefore it can be represented as tuple of the form
$(\mathcal{A}\,{\rightarrow}\,\mathcal{D},\,\mathcal{A},\,\mathit{u})$. It is
the same as Game II, except that the roles of the attacker and the defender
are inverted. In particular, the payoff of a mixed strategy profile
$(\mathit{\sigma_{\sf
d}},\alpha)\in\mathbb{D}(\mathcal{A}\,{\rightarrow}\,\mathcal{D})\times\mathbb{D}\mathcal{A}$
is given by $\mathit{U}(\mathit{\sigma_{\sf
d}},\alpha)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}{\operatornamewithlimits{\displaystyle\mathbb{E}}_{\begin{subarray}{c}\mathit{s_{\sf
d}}\leftarrow\mathit{\sigma_{\sf d}}\\\
a\leftarrow\alpha\end{subarray}}\mathit{u}(\mathit{s_{\sf
d}}(a),a)}={\sum_{\begin{subarray}{c}\mathit{s_{\sf
d}}:\mathcal{A}\,{\rightarrow}\,\mathcal{D}\\\
a\in\mathcal{A}\end{subarray}}}\mathit{\sigma_{\sf d}}(\mathit{s_{\sf
d}})\,\alpha(a)\,\mathit{u}(\mathit{s_{\sf
d}}(a),a)\allowbreak=\allowbreak{\mathbb{V}\left[\pi,{\bigsqcupdot_{\begin{subarray}{c}\mathit{\mathit{s_{\sf
d}}}\leftarrow\mathit{\mathit{\sigma_{\sf d}}}\\\
\mathit{a}\leftarrow\mathit{\alpha}\end{subarray}}}C_{\mathit{s_{\sf
d}}(a)a}\right]}$, and the whole system can be equivalently regarded as
channel ${\bigsqcupdot_{\begin{subarray}{c}\mathit{\mathit{s_{\sf
d}}}\leftarrow\mathit{\mathit{\sigma_{\sf d}}}\\\
\mathit{a}\leftarrow\mathit{\alpha}\end{subarray}}}C_{\mathit{s_{\sf
d}}(a)a}$. Obviously, also in this case the minimax problem has a
deterministic solution.

In summary, in the sequential case, whether the leader is the defender or the
attacker (Games II and III, respectively), the minimax problem has always a
deterministic solution [25].

###### Theorem 11

In a defender-first sequential game with visible choice, there exist
$d\in\mathcal{D}$ and $a\in\mathcal{A}$ such that, for every
$\delta\in\mathbb{D}\mathcal{D}$ and $\mathit{\sigma_{\sf
a}}\in\mathbb{D}(\mathcal{D}\,{\rightarrow}\,\mathcal{A})$ we have:
$\mathit{U}(d,\mathit{\sigma_{\sf
a}})\leq\mathit{u}(d,a)\leq\mathit{U}(\delta,a)$. Similarly, in an attacker-
first sequential game with visible choice, there exist $d\in\mathcal{D}$ and
$a\in\mathcal{A}$ such that, for every $\mathit{\sigma_{\sf
d}}\in\mathbb{D}(\mathcal{A}\,{\rightarrow}\,\mathcal{D})$ and
$\alpha\in\mathbb{D}\mathcal{A}$ we have:
$\mathit{U}(d,\alpha)\leq\mathit{u}(d,a)\leq\mathit{U}(\mathit{\sigma_{\sf
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
$\nicefrac{{1}}{{2}}$. If the attacker chooses $1$ then the defender chooses
$1$ and the payoff is $\nicefrac{{2}}{{3}}$. The latter case is more
convenient for the attacker, hence the solution of the game is the strategy
profile $(1,1)$.

####  5.1.4 Game IV (simultaneous with hidden choice)

This game is a tuple $(\mathcal{D},\mathcal{A},\mathit{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 the strategy 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 he is not sure about which channel is producing those
observables. A mixed strategy $\delta$ for the defender produces a convex
combination of channels (the channels associated to the pure strategies) with
the same coefficients, and we know from previous sections that the
vulnerability is a convex function of the channel, and in general is not
linear.

In order to define the payoff of a mixed strategy profile $(\delta,\alpha)$,
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 $\alpha$ 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 the assumption of common knowledge and rational
players).

The channel the attacker will see is
${\osum_{\mathit{d}\leftarrow\mathit{\delta}}}C_{da}$, obtaining a
corresponding payoff of
$\mathbb{V}\left[\pi,{{\osum_{\mathit{d}\leftarrow\mathit{\delta}}}}{C_{da}}\right]$.
By averaging on the strategy of the attacker we obtain
$\mathit{U}(\delta,\alpha)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}{\operatornamewithlimits{\displaystyle\mathbb{E}}_{\begin{subarray}{c}a\leftarrow\alpha\\\
\end{subarray}}\;\mathbb{V}\left[\pi,{{\osum_{\mathit{d}\leftarrow\mathit{\delta}}}}{C_{da}}\right]}=\sum_{a\in\mathcal{A}}\,\alpha(a)\,\mathbb{V}\left[\pi,{{\osum_{\mathit{d}\leftarrow\mathit{\delta}}}}{C_{da}}\right]$.
From Theorem 7(b) we derive:
$\mathit{U}(\delta,\alpha)=\mathbb{V}\left[\pi,{\bigsqcupdot_{\mathit{a}\leftarrow\mathit{\alpha}}}\,{{\osum_{\mathit{d}\leftarrow\mathit{\delta}}}}{C_{da}}\right]$
and hence the whole system can be equivalently regarded as channel
${{\bigsqcupdot_{\mathit{a}\leftarrow\mathit{\alpha}}}\,{{\osum_{\mathit{d}\leftarrow\mathit{\delta}}}}{C_{da}}}$.
Note that, by Proposition 6(c), the order of the operators is interchangeable,
and the system can be equivalently regarded as
${{\osum_{\mathit{d}\leftarrow\mathit{\delta}}}}\,{{\bigsqcupdot_{\mathit{a}\leftarrow\mathit{\alpha}}}{C_{da}}}$.
This shows the robustness of this model.

From Corollary 8 we derive that $\mathit{U}(\delta,\alpha)$ is convex in
$\delta$ and linear in $\eta$, 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
$\delta\in\mathbb{D}\mathcal{D}$ and $\alpha\in\mathbb{D}\mathcal{A}$, let
$p=\delta(0)$ and $q=\alpha(0)$. The system can be represented by the channel
$(C_{00}\;{{}_{\mathit{p}}{{{\oplus}}}}\;C_{10})\;{{}_{\mathit{q}}{{{\sqcupdot}}}}\;(C_{01}\;{{}_{\mathit{p}}{{{\oplus}}}}\;C_{11})$
represented below.

$\displaystyle\small\begin{array}[]{|c|c|c|}\hline\cr
C_{00}\;{{}_{\mathit{p}}{{{\oplus}}}}\;C_{10}&y=0&y=1\\\ \hline\cr
x=0&p&\bar{p}\\\ x=1&1&0\\\
\hline\cr\end{array}\quad\;{{}_{\mathit{q}}{{{\sqcupdot}}}}\;\quad\begin{array}[]{|c|c|c|}\hline\cr
C_{01}\;{{}_{\mathit{p}}{{{\oplus}}}}\;C_{11}&y=0&y=1\\\ \hline\cr
x=0&\nicefrac{{1}}{{3}}+\nicefrac{{2}}{{3}}\;p&\nicefrac{{2}}{{3}}-\nicefrac{{2}}{{3}}\;p\\\
x=1&\nicefrac{{2}}{{3}}-\nicefrac{{2}}{{3}}\;p&\nicefrac{{1}}{{3}}+\nicefrac{{2}}{{3}}\,p\\\
\hline\cr\end{array}$

For uniform $\pi$, we have
$\mathbb{V}\left[\pi,C_{00}\;{{}_{\mathit{p}}{{{\oplus}}}}\;C_{10}\right]{=}1-\nicefrac{{1}}{{2}}$;
and $\mathbb{V}\left[\pi,C_{10}\;{{}_{\mathit{p}}{{{\oplus}}}}\;C_{11}\right]$
is equal to $\nicefrac{{2}}{{3}}-\nicefrac{{2}}{{3}}\;p$ if
$p\leq\nicefrac{{1}}{{4}}$, and equal to
$\nicefrac{{1}}{{3}}+\nicefrac{{2}}{{3}}\;p$ if $p>\nicefrac{{1}}{{4}}$. Hence
the payoff, expressed in terms of $p$ and $q$, is
$\mathit{U}(p,q)=q(1-\nicefrac{{1}}{{2}})+\bar{q}(\nicefrac{{2}}{{3}}-\nicefrac{{2}}{{3}}\;p)$
if $p\leq\nicefrac{{1}}{{4}}$, and
$\mathit{U}(p,q)=q(1-\nicefrac{{1}}{{2}})+\bar{q}(\nicefrac{{1}}{{3}}+\nicefrac{{2}}{{3}}\;p)$
if $p>\nicefrac{{1}}{{4}}$. The Nash equilibrium $(p^{*},q^{*})$ is given by
$p^{*}=\operatornamewithlimits{argmin}_{p}\max_{q}\mathit{U}(p,q)$ and
$q^{*}=\operatornamewithlimits{argmax}_{q}\min_{p}\mathit{U}(p,q)$, and by
solving the above, we obtain $p^{*}=q^{*}=\nicefrac{{4}}{{7}}$.

####  5.1.5 Game V (defender 1st with hidden choice)

This is a defender-first sequential game with imperfect information, hence it
can be represented as a tuple of the form
$(\mathcal{D},\,\mathit{K}_{\mathsf{a}}\rightarrow\mathcal{A},\,\mathit{u_{\sf
d}},\mathit{u_{\sf a}})$, where $\mathit{K}_{\mathsf{a}}$ is a partition of
$\mathcal{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 the probability distribution determined by his
strategy), we must assume that the attacker does not know anything in Phase 1
either. Hence the indistinguishability relation must be total, i.e.,
$\mathit{K}_{\mathsf{a}}=\\{\mathcal{D}\\}$. But
$\\{\mathcal{D}\\}\rightarrow\mathcal{A}$ is equivalent to $\mathcal{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 game the
follower does not know the leader’s move before making his choice, the game is
equivalent to a simultaneous game.777However, 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.

####  5.1.6 Game VI (attacker 1st with hidden choice)

This game is also a sequential game with the attacker as the leader, hence it
is a tuple of the form
$(\mathcal{A}\,{\rightarrow}\,\mathcal{D},\,\mathcal{A},\,\mathit{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 profile
$(\mathit{\sigma_{\sf
d}},\alpha)\in\mathbb{D}(\mathcal{A}\,{\rightarrow}\,\mathcal{D})\times\mathbb{D}\mathcal{A}$
is $\mathit{U}(\mathit{\sigma_{\sf
d}},\alpha)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}{\operatornamewithlimits{\displaystyle\mathbb{E}}_{\begin{subarray}{c}a\leftarrow\alpha\\\
\end{subarray}}\;\mathbb{V}\left[\pi,{{\osum_{\mathit{\mathit{s_{\sf
d}}}\leftarrow\mathit{\mathit{\sigma_{\sf d}}}}}}{C_{\mathit{s_{\sf
d}}(a)a}}\right]}={\mathbb{V}\left[\pi,{\bigsqcupdot_{\mathit{a}\leftarrow\mathit{\alpha}}}\;{\osum_{\mathit{\mathit{s_{\sf
d}}}\leftarrow\mathit{\mathit{\sigma_{\sf d}}}}}C_{\mathit{s_{\sf
d}}(a)a}\right]}$, so the whole system can be equivalently regarded as channel
${\bigsqcupdot_{\mathit{a}\leftarrow\mathit{\alpha}}}\;{\osum_{\mathit{\mathit{s_{\sf
d}}}\leftarrow\mathit{\mathit{\sigma_{\sf d}}}}}C_{\mathit{s_{\sf d}}(a)a}$.
Also in this case the minimax problem has a deterministic solution, but only
for the attacker.

###### Theorem 14

In an attacker-first sequential game with hidden choice, there exist
$a\in\mathcal{A}$ and $\delta\in\mathbb{D}\mathcal{D}$ such that, for every
$\alpha\in\mathbb{D}\mathcal{A}$ and $\mathit{\sigma_{\sf
d}}\in\mathbb{D}(\mathcal{A}\,{\rightarrow}\,\mathcal{D})$ we have that
$\mathit{U}(\delta,\alpha)\leq\mathit{U}(\delta,a)\leq\mathit{U}(\mathit{\sigma_{\sf
d}},a)$.

###### Example 15

Consider again the example of Section 3, this time in the setting of 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 to make
its choice first. If he chooses $0$, which corresponds to committing to the
system $C_{00}\;{{}_{\mathit{p}}{{{\oplus}}}}\;C_{10}$, then the defender will
choose $p=\nicefrac{{1}}{{4}}$, which minimizes its vulnerability. If he
chooses $1$, which corresponds to committing to the system
$C_{01}\;{{}_{\mathit{p}}{{{\oplus}}}}\;C_{11}$, the defender will choose
$p=1$, which minimizes its vulnerability of the above channel. In both cases,
the leakage is $p=\nicefrac{{1}}{{2}}$, hence both these strategies are
solutions to the minimax. Note that in the first case the strategy of 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):
${\rm II:}\,1;\,\allowbreak{\rm I:}\,\nicefrac{{4}}{{5}};\,\allowbreak{\rm
III:}\,\nicefrac{{2}}{{3}};\,\allowbreak{\rm
IV:}\,\nicefrac{{4}}{{7}};\,\allowbreak{\rm
V:}\,\nicefrac{{4}}{{7}};\,\allowbreak{\rm
VI:}\,\nicefrac{{1}}{{2}}\allowbreak$.

Figure 2: Order of games w.r.t. payoff. Games higher in the lattice have
larger payoff.

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 sake of clarity.

###### Theorem 16

It is the case that:

  1. (a)

$\begin{array}[t]{lll}\min_{\delta}\max_{\mathit{\sigma_{\sf
a}}}\mathbb{V}\left[\pi,{\bigsqcupdot_{\begin{subarray}{c}\mathit{d}\leftarrow\mathit{\delta}\\\
\mathit{\mathit{s_{\sf a}}}\leftarrow\mathit{\mathit{\sigma_{\sf
a}}}\end{subarray}}}C_{d\mathit{s_{\sf
a}}(d)}\right]&\geq&\min_{\delta}\max_{\alpha}\mathbb{V}\left[\pi,{\bigsqcupdot_{\begin{subarray}{c}\mathit{d}\leftarrow\mathit{\delta}\\\
\mathit{a}\leftarrow\mathit{\alpha}\end{subarray}}}C_{da}\right]\\\
&\geq&\max_{\alpha}\min_{\mathit{\sigma_{\sf
d}}}{\mathbb{V}\left[\pi,{\bigsqcupdot_{\begin{subarray}{c}\mathit{\mathit{s_{\sf
d}}}\leftarrow\mathit{\mathit{\sigma_{\sf d}}}\\\
\mathit{a}\leftarrow\mathit{\alpha}\end{subarray}}}C_{\mathit{s_{\sf
d}}(a)a}\right]}\end{array}$

  2. (b)

$\min_{\delta}\max_{\alpha}\mathbb{V}\left[\pi,{\bigsqcupdot_{\mathit{a}\leftarrow\mathit{\alpha}}}\,{{\osum_{\mathit{d}\leftarrow\mathit{\delta}}}}{C_{da}}\right]\geq\max_{\alpha}\min_{\mathit{\sigma_{\sf
d}}}{\mathbb{V}\left[\pi,{\osum_{\mathit{a}\leftarrow\mathit{\alpha}}}\;{\bigsqcupdot_{\mathit{\mathit{s_{\sf
d}}}\leftarrow\mathit{\mathit{\sigma_{\sf d}}}}}C_{\mathit{s_{\sf
d}}(a)a}\right]}$

###### Proof

We prove the first inequality in (a). Independently of $\delta$, consider the
attacker strategy $\tau_{a}$ that assigns probability $1$ to the function
$\mathit{s_{\sf a}}$ defined as $\mathit{s_{\sf
a}}(d)=\operatornamewithlimits{argmax}_{a}\mathbb{V}\left[\pi,C_{da}\right]$.
Then we have that

$\displaystyle\min_{\delta}\max_{\mathit{\sigma_{\sf
a}}}\mathbb{V}\left[\pi,{\bigsqcupdot_{\begin{subarray}{c}\mathit{d}\leftarrow\mathit{\delta}\\\
\mathit{\mathit{s_{\sf a}}}\leftarrow\mathit{\mathit{\sigma_{\sf
a}}}\end{subarray}}}C_{d\mathit{s_{\sf a}}(d)}\right]\geq$
$\displaystyle\,\,\min_{\delta}\mathbb{V}\left[\pi,{\bigsqcupdot_{\begin{subarray}{c}\mathit{d}\leftarrow\mathit{\delta}\\\
\mathit{\mathit{s_{\sf
a}}}\leftarrow\mathit{\tau_{a}}\end{subarray}}}C_{d\mathit{s_{\sf
a}}(d)}\right]$ $\displaystyle\geq$
$\displaystyle\,\,\min_{\delta}\max_{\alpha}\mathbb{V}\left[\pi,{\bigsqcupdot_{\begin{subarray}{c}\mathit{d}\leftarrow\mathit{\delta}\\\
\mathit{a}\leftarrow\mathit{\alpha}\end{subarray}}}C_{da}\right]$

Note that the strategy $\tau_{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 the
payoff 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 $C_{11}$ to be the same as $C_{00}$, the payoff for III will be
$\nicefrac{{1}}{{2}}$, and that for IV-V will be $\nicefrac{{2}}{{3}}$.

Finally, the relation between III and VI comes from the fact that they are
both 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\in\mathcal{A}$ and every $\delta\in\mathbb{D}\mathcal{D}$:
$\mathbb{V}\left[\pi,{{\osum_{\mathit{d}\leftarrow\mathit{\delta}}}}{C_{da}}\right]\leq\mathbb{V}\left[\pi,{{\bigsqcupdot_{\mathit{d}\leftarrow\mathit{\delta}}}}{C_{da}}\right]$.

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.

##  6 Case study: a safer, faster password-checker

Program PWD123
High Input: $x\in\\{000,001,\ldots,111\\}$
Low Input: $a\in\\{000,001,\ldots,111\\}$
Output: $y\in\\{T,F\\}$
accept $:=T$
for $i=1,2,3$ do
if $a_{i}\neq x_{i}$ then
accept $:=F$
break
end if
end for
return accept

Figure 3: Password-checker algorithm.

In this section we apply our game-theoretic, compositional approach to show
how a defender can mitigate an attacker’s typical timing side-channel attack
while avoiding the usual burden imposed on the password-checker’s efficiency.

Consider the password-checker PWD123 of Figure 3, which performs a bitwise-
check of a 3-bit low-input $a{=}a_{1}a_{2}a_{3}$, provided by the attacker,
against a 3-bit secret password $x{=}x_{1}x_{2}x_{3}$. The low-input is
rejected as soon as it mismatches the secret, and is accepted otherwise.

The attacker can choose low-inputs to try 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 low-input is rejected, there
is some leakage of information: from the duration of the execution 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 $\mathcal{X}=\\{000,001,\ldots,111\\}$ be the set
of all possible 3-bit passwords, and
$\mathcal{Y}=\\{(F,1),(F,2),\allowbreak(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 $C_{123,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_ [28]. The
_prior Bayes vulnerability_ of a distribution
$\pi{\in}\mathbb{D}{\mathcal{X}}$ is defined as
$V_{g}\left[\pi\right]{=}\max_{x\in\mathcal{X}}\pi_{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
$\hat{\pi}=(0.0137,0.0548,0.2191,\allowbreak 0.4382,\allowbreak
0.0002,\allowbreak 0.0002,\allowbreak 0.0548,\allowbreak 0.2191)$, its prior
Bayes vulnerability is $\mathbb{V}\left[\hat{\pi}\right]{=}0.4382$.

The _posterior Bayes vulnerability_ of a prior $\pi$ and a channel
$C{:}\mathcal{X}{\times}\mathcal{Y}{\rightarrow}\mathbb{R}$ is defined as
$\mathbb{V}\left[\pi,C\right]{=}\sum_{y\in\mathcal{Y}}\max_{x\in\mathcal{X}}\pi_{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 $\hat{\pi}$ above, the posterior Bayes vulnerability of
channel $C_{123,101}$ is
$\mathbb{V}\left[\hat{\pi},C_{123,101}\right]{=}0.6577$ (which represents an
increase 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 $C_{\text{cons},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 vulnerability is
$\mathbb{V}\left[\hat{\pi},C_{123,101}\right]{=}0.4384$, which brings the
multiplicative Bayes leakage down to an increase of only about $0.05\%$.
However, the expected running time goes up to $3$ iterations (an increase of
about $135\%$ w.r.t. that of $C_{123,101}$).

$\begin{array}[]{|c|c|c|c|c|}\hline\cr\hbox{\multirowsetup$C_{123,101}$}&y{=}&y{=}&y{=}&y{=}\\\
&(F,1)&(F,2)&(F,3)&(T,3)\\\ \hline\cr x{=}000&1&0&0&0\\\ x{=}001&1&0&0&0\\\
x{=}010&1&0&0&0\\\ x{=}011&1&0&0&0\\\ x{=}100&0&0&1&0\\\ x{=}101&0&0&0&1\\\
x{=}110&0&1&0&0\\\ x{=}111&0&1&0&0\\\ \hline\cr\end{array}$
$\begin{array}[]{|c|c|c|}\hline\cr\hbox{\multirowsetup$C_{\text{cons},101}$}&y{=}&y{=}\\\
&(F,3)&(T,3)\\\ \hline\cr x{=}000&1&0\\\ x{=}001&1&0\\\ x{=}010&1&0\\\
x{=}011&1&0\\\ x{=}100&1&0\\\ x{=}101&0&1\\\ x{=}110&1&0\\\ x{=}111&1&0\\\
\hline\cr\end{array}$

Figure 4: Channels $C_{da}$ modeling the password checker for defender’s
action $d$ and attacker’s action $a$.

Seeking some compromise between security and efficiency, assume that the
defender can employ password-checkers that perform the bitwise comparison
among low-input $a$ and secret password $x$ in different orders. More
precisely, there is one version of the checker for every 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
$\mathcal{A}=\\{000,001,\ldots,111\\}$ are all possible low-inputs to the
checker, and the defender’s $\mathcal{D}=\\{123,\allowbreak 132,\allowbreak
213,\allowbreak 231,\allowbreak 312,\allowbreak 321\\}$ are all orders to
perform the comparison. Hence, there is a total of $48$ possible channels
$C_{ad}{:}\mathcal{X}{\times}\mathcal{Y}{\rightarrow}\mathbb{R}$, one for each
combination of $d{\in}\mathcal{D}$, $a{\in}\mathcal{A}$.

In our framework, the utility of a mixed strategy profile $(\delta,\alpha)$ is
given by
$\mathit{U}(\delta,\alpha)\allowbreak=\allowbreak\operatornamewithlimits{\displaystyle\mathbb{E}}_{\begin{subarray}{c}a\leftarrow\alpha\\\
\end{subarray}}\;\mathbb{V}\left[\pi,{{\osum_{\mathit{d}\leftarrow\mathit{\delta}}}}{C_{da}}\right]$.
For each pure strategy profile $(d,a)$, the payoff of the game will be the
posterior Bayes vulnerability of the resulting channel $C_{da}$ (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
techniques from [4], we can compute the best (mixed) strategy for the defender
in this game, which turns out to be
$\delta^{*}=(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 the attacker 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

$\begin{array}[]{c|c||c|c|c|c|c|c|c|c|}\lx@intercol\hfil\hfil\lx@intercol&\lx@intercol\hfil\textbf{Attacker's
action $a$}\hfil\lx@intercol\\\
\cline{2-10}\cr&U(d,a)&000&001&010&011&100&101&110&111\\\
\cline{2-10}\cr\cline{2-10}\cr\hbox{\multirowsetup\rotatebox[origin={c}]{90.0}{\stackanchor{{Defender's}}{{action
$d$}}}}&123&0.7257&0.7257&0.9311&0.9311&0.6577&0.6577&0.7122&0.7122\\\
\cline{2-10}\cr&132&0.8900&0.9311&0.8900&0.9311&0.7122&0.7122&0.7122&0.7122\\\
\cline{2-10}\cr&213&0.5068&0.5068&0.9311&0.9311&0.4934&0.4934&0.7668&0.7668\\\
\cline{2-10}\cr&231&0.5068&0.5068&0.7668&0.9311&0.5068&0.5068&0.7668&0.9311\\\
\cline{2-10}\cr&312&0.7257&0.9311&0.7257&0.9311&0.7122&0.8766&0.7122&0.8766\\\
\cline{2-10}\cr&321&0.6712&0.7122&0.7257&0.9311&0.6712&0.7122&0.7257&0.9311\\\
\cline{2-10}\cr\end{array}$

Table 3: Utility for each pure strategy profile.

$2.3922$ iterations (an increase of only $87\%$ w.r.t. the channel PWD123),
which is below the worst possible expected $3$ iterations of the constant-time
password checker.

##  7 Related work

Many studies have applied game theory to analyses of security and privacy in
networks [8, 15, 3], cryptography [16], anonymity [1], location privacy [14],
and intrusion detection [31], to cite a few. See [21] for a survey.

In the context of quantitative information flow, most works consider only
passive attackers. Boreale and Pampaloni [9] 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. [22] propose a model for
both adaptive attackers and defenders, but in none of their extensive case-
studies the attacker needs a probabilistic strategy to maximize leakage. In
this paper we characterize when randomization is necessary, for either
attacker or defender, to achieve 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. [20] theoretically analyze security games and study the relationships
between Stackelberg and Nash Equilibria under various forms of imperfect
information. Khouzani and Malacaria [19] 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 with hidden 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’s secrets. Then they present how the leakage on the defender’s
secrets gives influences on the defender’s optimal strategy. More recently, Xu
et al. [30] 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., [18]), but we are unaware of any explicit definition
and investigation of hidden and visible choice operators. Although Kawamoto et
al. [17] implicitly use the hidden choice to model a probabilistic system as
the weighted 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. More
precisely, we formalized visible and hidden probabilistic choices of different
protocols. We then formalized 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 considered various kinds of leakage games,
depending on whether players act simultaneously or sequentially, and whether
the choices of the defender are visible or not to the adversary. We
established a hierarchy of 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 the
system 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
not equivalent, 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 the Japan-
France AYAME Program, and by the project Epistemic Interactive Concurrency
(EPIC) from the STIC AmSud Program. Má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] Má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] Mário S. Alvim, Konstantinos Chatzikokolakis, Yusuke Kawamoto, and Catuscia Palamidessi.  A Game-Theoretic Approach to Information-Flow Control via Protocol Composition.  arXiv preprint arXiv:1803.10042, 2018.  https://arxiv.org/abs/1803.10042.
  * [6] Má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.
  * [7] Má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.
  * [8] Tamer Basar.  The gaussian test channel with an intelligent jammer.  IEEE Trans. Information Theory, 29(1):152–157, 1983.
  * [9] Michele Boreale and Francesca Pampaloni.  Quantitative information flow under generic leakage functions and adaptive adversaries.  Logical Methods in Computer Science, 11(4), 2015.
  * [10] 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.
  * [11] Konstantinos Chatzikokolakis, Catuscia Palamidessi, and Prakash Panangaden.  On the Bayes risk in information-hiding protocols.  J. of Comp. Security, 16(5):531–571, 2008.
  * [12] David Chaum.  The dining cryptographers problem: Unconditional sender and recipient untraceability.  Journal of Cryptology, 1:65–75, 1988.
  * [13] 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.
  * [14] Julien Freudiger, Mohammad Hossein Manshaei, Jean-Pierre Hubaux, and David C. Parkes.  On non-cooperative location privacy: A game-theoretic analysis.  In Proc. of CCS, pages 324–337, 2009.
  * [15] Jens Grossklags, Nicolas Christin, and John Chuang.  Secure or insure?: A game-theoretic analysis of information security games.  In Proc. of WWW, pages 209–218, 2008.
  * [16] Jonathan Katz.  Bridging game theory and cryptography: Recent results and future directions.  In Proc. of TCC, pages 251–272, 2008.
  * [17] Yusuke Kawamoto, Fabrizio Biondi, and Axel Legay.  Hybrid statistical estimation of mutual information for quantifying information flow.  In Proc. of FM 2016, pages 406–425, 2016.
  * [18] 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.
  * [19] M. H. R. Khouzani and P. Malacaria.  Relative perfect secrecy: Universally optimal strategies and channel design.  In Proc. of CSF, pages 61–76, 2016.
  * [20] Dmytro Korzhyk, Zhengyu Yin, Christopher Kiekintveld, Vincent Conitzer, and Milind Tambe.  Stackelberg vs. nash in security games: An extended investigation of interchangeability, equivalence, and uniqueness.  J. Artif. Intell. Res., 41:297–327, 2011.
  * [21] Mohammad Hossein Manshaei, Quanyan Zhu, Tansu Alpcan, Tamer Bacşar, and Jean-Pierre Hubaux.  Game theory meets network security and privacy.  ACM Comput. Surv., 45(3):25:1–25:39, 2013.
  * [22] Piotr Mardziel, Má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.
  * [23] Massey.  Guessing and entropy.  In Proceedings of the IEEE Int. Symposium on Information Theory, page 204. IEEE, 1994.
  * [24] 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.
  * [25] Martin J. Osborne and Ariel Rubinstein.  A Course in Game Theory.  The MIT Press, 1994.
  * [26] Juliano Rizzo and Thai Duong.  The CRIME attack, 2012.
  * [27] Claude E. Shannon.  A mathematical theory of communication.  Bell System Technical Journal, 27:379–423, 625–56, 1948.
  * [28] Geoffrey Smith.  On the foundations of quantitative information flow.  In Proc. of FOSSACS, volume 5504 of LNCS, pages 288–302. Springer, 2009.
  * [29] 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.
  * [30] Haifeng Xu, Albert Xin Jiang, Arunesh Sinha, Zinovi Rabinovich, Shaddin Dughmi, and Milind Tambe.  Security games with information leakage: Modeling and computation.  In Proc. of IJCAI, pages 674–680, 2015.
  * [31] Quanyan Zhu, Carol J. Fung, Raouf Boutaba, and Tamer Basar.  A game-theoretical approach to incentive design in collaborative intrusion detection networks.  In Proc. of GAMENETS, pages 384–392. IEEE, 2009.

##  Appendix 0.A Proofs of Technical Results

In this section we provide proofs for our technical results.

###  0.A.1 Preliminaries for proofs

We start by providing some necessary background for the subsequent technical
proofs.

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 prior
and 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 channel $C$ of type
$\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$, its _zero-column
extension_ $C^{0}$ is the channel of type
$\mathcal{X}\times\left(\mathcal{Y}\cup\\{y_{0}\\}\right)\rightarrow\mathbb{R}$,
with $y_{0}\notin\mathcal{Y}$, s.t. $C^{0}(x,y)=C(x,y)$ for all
$x\in\mathcal{X}$, $y\in\mathcal{Y}$, and $C^{0}(x,y_{0})=0$ for all
$x\in\mathcal{X}$.

######  Lemma 17 (Characterization of channel equivalence [7, 24])

Two channels $C_{1}$ and $C_{2}$ are equivalent iff every column of $C_{1}$ is
a convex combination of columns of $C_{2}^{0}$, and every column of $C_{2}$ is
a convex combination of columns of $C_{1}^{0}$.

Note that the result above implies that for being equivalent, any two channels
must be compatible.

###  0.A.2 Proofs of Section 4

See 2

###### Proof

Since hidden choice is defined as a summation of matrices, the type of
${\osum_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}$ is the same as the type of
every $C_{i}$ in the family.

To see that ${\osum_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}$ is a channel
(i.e., all of its entries are non-negative, and all of its rows sum up to 1),
first note that, since each $C_{i}$ in the family is a channel matrix,
$C_{i}(x,y)$ lies in the interval $[0,1]$ for all $x\in\mathcal{X}$,
$y\in\mathcal{Y}$. Since $\mu$ is a set of convex coefficients, from the
definition of hidden choice it follows that also
$\sum_{i\in\mathcal{I}}\mu(i)C_{i}(x,y)$ must lie in the interval $[0,1]$ for
every $x,y$.

Second, note that for all $x\in\mathcal{X}$:

$\displaystyle\sum_{y\in\mathcal{Y}}\left({\osum_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}\right)(x,y)=$
$\displaystyle\,\sum_{y\in\mathcal{Y}}\sum_{i\in\mathcal{I}}\mu(i)C_{i}(x,y)$
(def. of hidden choice) $\displaystyle=$
$\displaystyle\,\sum_{i\in\mathcal{I}}\mu(i)\sum_{y\in\mathcal{Y}}C_{i}(x,y)$
$\displaystyle=$ $\displaystyle\,\sum_{i\in\mathcal{I}}\mu(i)\cdot 1$
($C_{i}{:}\mathcal{X}{\times}\mathcal{Y}{\rightarrow}\mathbb{R}$ are channels)
$\displaystyle=$ $\displaystyle\,1$ ($\mu$ is a prob. dist.)

See 3

###### Proof

Visible choice applied to a family $\\{C_{i}\\}$ of channels scales each
matrix $C_{i}$ by a factor $\mu(i)$, which preserves the type
$\mathcal{X}\times\mathcal{Y}_{i}\rightarrow\mathbb{R}$ of each matrix, and
then concatenates all the matrices so produced, yielding a result of type
$\mathcal{X}\times\left(\bigsqcup_{i\in\mathcal{I}}\mathcal{Y}_{i}\right)\rightarrow\mathbb{R}$.

To see that ${\bigsqcupdot_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}$ 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
$\\{C_{i}\\}$ can be denoted by
$\left({\bigsqcupdot_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}\right)(x,(y,j))$,
where $x\in\mathcal{X}$, $j\in\mathcal{I}$, and $y\in\mathcal{Y}_{j}$. Then,
note that for all $x\in\mathcal{X}$, $j\in\mathcal{I}$, and
$y\in\mathcal{Y}_{j}$:

$\displaystyle\left({\bigsqcupdot_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}\right)(x,(y,j))=$
$\displaystyle\,\left(\meddiamond_{i\in\mathcal{I}}\mu(i)C_{i}\right)(x,(y,j))$
(def. of visible choice) $\displaystyle=$
$\displaystyle\,\left(\mu(j)C_{j}\right)(x,y)$ (def. of concatenation)
$\displaystyle=$ $\displaystyle\,\mu(j)C_{j}(x,y)$ (def. of scalar mult.) (1)

which is a non-negative value, since, both $\mu(j)$ and $C_{j}(x,y)$ are non-
negative.

Finally, note that for all $x\in\mathcal{X}$:

$\displaystyle\sum_{\begin{subarray}{c}j\in\mathcal{I}\\\
y\in\mathcal{Y}_{j}\end{subarray}}\left({\bigsqcupdot_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}\right)(x,(y,j))=$
$\displaystyle\,\sum_{\begin{subarray}{c}j\in\mathcal{I}\\\
y\in\mathcal{Y}_{j}\end{subarray}}\mu(j)C_{j}(x,y)$ (by Eq. (0.A.2))
$\displaystyle=$
$\displaystyle\,\sum_{j\in\mathcal{I}}\mu(j)\sum_{y\in\mathcal{Y}_{j}}C_{j}(x,y)$
$\displaystyle=$ $\displaystyle\,\sum_{j\in\mathcal{I}}\mu(j)\cdot 1$
($C_{j}{:}\mathcal{X}{\times}\mathcal{Y}_{j}{\rightarrow}\mathbb{R}$ are
channels) $\displaystyle=$ $\displaystyle\,1$ ($\mu$ is a prob. dist.)

See 5

###### Proof

  1. a)

Idempotency of hidden choice:

$\displaystyle{\osum_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}=$
$\displaystyle\,\sum_{i}\mu(i)C_{i}$ (def. of hidden choice) $\displaystyle=$
$\displaystyle\,\sum_{i}\mu(i)C$ (since every $C_{i}=C$) $\displaystyle=$
$\displaystyle\,C\sum_{i}\mu(i)$ $\displaystyle=$ $\displaystyle\,C$ (since
$\mu$ is a prob. dist.)

  2. b)

Idempotency of visible choice:

$\displaystyle{\bigsqcupdot_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}=$
$\displaystyle\,\meddiamond_{i}\mu(i)C_{i}$ (def. of visible choice)
$\displaystyle=$ $\displaystyle\,\meddiamond_{i}\mu(i)C$ (since every
$C_{i}=C$) $\displaystyle\approx$ $\displaystyle\,C$ (by Lemma 17)

In the above derivation, we can apply Lemma 17 because 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 the other side.

See 6

###### Proof

  1. a)

$\displaystyle{\osum_{\mathit{i}\leftarrow\mathit{\mu}}}{\osum_{\mathit{j}\leftarrow\mathit{\eta}}}C_{ij}=$
$\displaystyle\,{\osum_{\mathit{i}\leftarrow\mathit{\mu}}}\left(\sum_{j}\eta(j)C_{ij}\right)$
(def. of hidden choice) $\displaystyle=$
$\displaystyle\,\sum_{i}\mu(i)\left(\sum_{j}\eta(j)C_{ij}\right)$ (def. of
hidden choice) $\displaystyle=$
$\displaystyle\,\sum_{i,j}\eta(i)\eta(j)C_{ij}$ (reorganizing the sums)
$\displaystyle=$
$\displaystyle\,{\osum_{\begin{subarray}{c}\mathit{i}\leftarrow\mathit{\mu}\\\
\mathit{j}\leftarrow\mathit{\eta}\end{subarray}}}C_{ij}$ (def. of hidden
choice)

  2. b)

$\displaystyle{\bigsqcupdot_{\mathit{i}\leftarrow\mathit{\mu}}}{\bigsqcupdot_{\mathit{j}\leftarrow\mathit{\eta}}}C_{ij}=$
$\displaystyle\,{\bigsqcupdot_{\mathit{i}\leftarrow\mathit{\mu}}}\left(\meddiamond_{j}C_{ij}\right)$
(def. of visible choice) $\displaystyle=$
$\displaystyle\,\meddiamond_{i}\mu(i)\left(\meddiamond_{j}\eta(j)C_{ij}\right)$
(def. of visible choice) $\displaystyle\approx$
$\displaystyle\meddiamond_{ij}\mu(i)\eta(j)C_{ij}$ (by Lemma 17)
$\displaystyle=$
$\displaystyle\,{\bigsqcupdot_{\begin{subarray}{c}\mathit{i}\leftarrow\mathit{\mu}\\\
\mathit{j}\leftarrow\mathit{\eta}\end{subarray}}}C_{ij}$ (def. of visible
choice)

In the above derivation, we can apply Lemma 17 because 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 the other side.

  3. c)

$\displaystyle{\osum_{\mathit{i}\leftarrow\mathit{\mu}}}{\bigsqcupdot_{\mathit{j}\leftarrow\mathit{\eta}}}C_{ij}=$
$\displaystyle\,{\osum_{\mathit{i}\leftarrow\mathit{\mu}}}\left(\meddiamond_{j}C_{ij}\right)$
(def. of visible choice) $\displaystyle=$
$\displaystyle\,\sum_{i}\mu(i)\left(\meddiamond_{j}\eta(j)C_{ij}\right)$ (def.
of hidden choice) $\displaystyle\approx$
$\displaystyle\,\meddiamond_{j}\eta(j)\left(\sum_{i}\eta(i)C_{ij}\right)$ (by
Lemma 17) $\displaystyle=$
$\displaystyle\,{\bigsqcupdot_{\mathit{j}\leftarrow\mathit{\eta}}}{\osum_{\mathit{i}\leftarrow\mathit{\mu}}}C_{ij}$
(def. of operators)

In the above derivation, we can apply Lemma 17 because 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 the other side.

See 7

###### Proof

  1. a)

Let us call $\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$ the type of
each channel $C_{i}$ in the family $\\{C_{i}\\}$. Then:

$\displaystyle\mathbb{V}\left[\pi,{\osum_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}\right]=$
$\displaystyle\,\mathbb{V}\left[\pi,\operatorname{\sum}_{i}\mu(i)C_{i}\right]$
(def. of hidden choice) $\displaystyle=$
$\displaystyle\,\sum_{y\in\mathcal{Y}}p(y)\cdot\mathbb{V}\left[\frac{\pi(\cdot)\sum_{i}\mu(i)C_{i}(\cdot,y)}{p(y)}\right]$
(def. of posterior $\mathbb{V}$) $\displaystyle=$
$\displaystyle\,\sum_{y\in\mathcal{Y}}p(y)\cdot\mathbb{V}\left[\sum_{i}\mu(i)\frac{\pi(\cdot)C_{i}(\cdot,y)}{p(y)}\right]$
$\displaystyle\leq$
$\displaystyle\,\sum_{y\in\mathcal{Y}}p(y)\cdot\sum_{i}\mu(i)\mathbb{V}\left[\frac{\pi(\cdot)C_{i}(\cdot,y)}{p(y)}\right]$
(by convexity of $\mathbb{V}$) $\displaystyle=$
$\displaystyle\,\sum_{i}\mu(i)\sum_{y\in\mathcal{Y}}p(y)\mathbb{V}\left[\frac{\pi(\cdot)C_{i}(\cdot,y)}{p(y)}\right]$
$\displaystyle=$
$\displaystyle\,\sum_{i}\mu(i)\mathbb{V}\left[\pi,C_{i}\right]$

where $p(y)=\sum_{x\in\mathcal{X}}\pi(x)\sum_{i}\mu(i)C_{i}(x,y)$.

  2. b)

Let us call $\mathcal{X}\times\mathcal{Y}_{i}\rightarrow\mathbb{R}$ the type
of each channel $C_{i}$ in the family $\\{C_{i}\\}$. Then:

$\displaystyle\mathbb{V}\left[\pi,{\bigsqcupdot_{\mathit{i}\leftarrow\mathit{\mu}}}C_{i}\right]=$
$\displaystyle\,\mathbb{V}\left[\pi,\meddiamond_{i}\mu(i)C_{i}\right]$ (def.
of visible choice) $\displaystyle=$
$\displaystyle\,\sum_{y\in\mathcal{Y}}p(y)\cdot\mathbb{V}\left[\frac{\pi(\cdot)\meddiamond_{i}\mu(i)C_{i}(\cdot,y)}{p(y)}\right]$
(def. of posterior $\mathbb{V}$) $\displaystyle=$
$\displaystyle\,\sum_{y\in\mathcal{Y}}p(y)\cdot\mathbb{V}\left[\meddiamond_{i}\mu(i)\frac{\pi(\cdot)C_{i}(\cdot,y)}{p(y)}\right]$
$\displaystyle=$
$\displaystyle\,\sum_{y\in\mathcal{Y}}p(y)\cdot\sum_{i}\mu(i)\mathbb{V}\left[\frac{\pi(\cdot)C_{i}(\cdot,y)}{p(y)}\right]$
(see (*) below) $\displaystyle=$
$\displaystyle\,\sum_{i}\mu(i)\sum_{y\in\mathcal{Y}}p(y)\mathbb{V}\left[\frac{\pi(\cdot)C_{i}(\cdot,y)}{p(y)}\right]$
$\displaystyle=$
$\displaystyle\,\sum_{i}\mu(i)\mathbb{V}\left[\pi,C_{i}\right]$

where $p(y)=\sum_{x\in\mathcal{X}}\pi(x)\sum_{i}\mu(i)C_{i}(x,y)$, and step
(*) holds because in the vulnerability 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.

See 8

###### Proof

To see that $U(\mu,\eta)$ is convex on $\mu$, note that:

$\displaystyle U(\mu,\eta)=$
$\displaystyle\,\mathbb{V}\left[\pi,{\osum_{\mathit{i}\leftarrow\mathit{\mu}}}\;{\bigsqcupdot_{\mathit{j}\leftarrow\mathit{\eta}}}\;C_{ij}\right]$
(by definition) $\displaystyle\leq$
$\displaystyle\,\sum_{i}\mu(i)\;\mathbb{V}\left[\pi,{\bigsqcupdot_{\mathit{j}\leftarrow\mathit{\eta}}}\;C_{ij}\right]$
(by Theorem 7)

To see that $U(\mu,\eta)$ is linear on $\eta$, note that:

$\displaystyle U(\mu,\eta)=$
$\displaystyle\,\mathbb{V}\left[\pi,{\osum_{\mathit{i}\leftarrow\mathit{\mu}}}\;{\bigsqcupdot_{\mathit{j}\leftarrow\mathit{\eta}}}\;C_{ij}\right]$
(by definition) $\displaystyle=$
$\displaystyle\,\mathbb{V}\left[\pi,{\bigsqcupdot_{\mathit{j}\leftarrow\mathit{\eta}}}\;{\osum_{\mathit{i}\leftarrow\mathit{\mu}}}\;C_{ij}\right]$
(by Prop. 6) $\displaystyle=$
$\displaystyle\,\sum_{j}\eta(j)\;\mathbb{V}\left[\pi,{\osum_{\mathit{i}\leftarrow\mathit{\mu}}}\;C_{ij}\right]$
(by Theorem. 7)

##  Appendix 0.B Properties of binary versions of channel operators

In this section we derive some relevant properties of the binary versions of
the hidden and visible choice operators. We start with results regarding each
operator individually.

######  Proposition 18 (Properties of the binary hidden choice)

For any channels $C_{1}$ and $C_{2}$ of the same type, and any values $0\leq
p,q\leq 1$, the binary hidden choice operator satisfies the following
properties:

  1. a)

_Idempotency_ : $C_{1}\;{{}_{\mathit{p}}{{{\oplus}}}}\;C_{1}=C_{1}$

  2. b)

_Commutativity_ :
$C_{1}\;{{}_{\mathit{p}}{{{\oplus}}}}\;C_{2}=C_{2}\;{{}_{\mathit{\bar{p}}}{{{\oplus}}}}\;C_{1}$

  3. c)

_Associativity_ :

$C_{1}\;{{}_{\mathit{p}}{{{\oplus}}}}\;(C_{2}\;{{}_{\mathit{q}}{{{\oplus}}}}\;C_{3})=(\nicefrac{{1}}{{q}}\cdot
C_{1}\;{{}_{\mathit{p}}{{{\oplus}}}}\;C_{2})\;{{}_{\mathit{q}}{{{\oplus}}}}\;\bar{p}\cdot
C_{3}$

if $q\neq 0$.

  4. d)

_Absorption_ :

$(C_{1}\;{{}_{\mathit{p}}{{{\oplus}}}}\;C_{2})\;{{}_{\mathit{q}}{{{\oplus}}}}\;(C_{1}\;{{}_{\mathit{r}}{{{\oplus}}}}\;C_{2})=C_{1}\;{{}_{\mathit{(pq+\bar{q}r)}}{{{\oplus}}}}\;C_{2}.$

###### Proof

We will prove each property separately.

  1. a)

_Idempotency_ :

$\displaystyle C_{1}\;{{}_{\mathit{p}}{{{\oplus}}}}\;C_{1}=$
$\displaystyle\,p\cdot C_{1}+\bar{p}\cdot C_{1}$ (def. of hidden choice)
$\displaystyle=$ $\displaystyle\,(p+\bar{p})\cdot C_{1}$ $\displaystyle=$
$\displaystyle\,C_{1}$ ($p+\bar{p}=1$)

  2. b)

_Commutativity_ :

$\displaystyle C_{1}\;{{}_{\mathit{p}}{{{\oplus}}}}\;C_{2}=$
$\displaystyle\,p\cdot C_{1}+\bar{p}\cdot C_{2}$ (def. of hidden choice)
$\displaystyle=$ $\displaystyle\,\bar{p}\cdot C_{2}+p\cdot C_{1}$
$\displaystyle=$
$\displaystyle\,C_{2}\;{{}_{\mathit{\bar{p}}}{{{\oplus}}}}\;C_{1}$ (def. of
hidden choice)

  3. c)

_Associativity_ :

$\displaystyle\,C_{1}\;{{}_{\mathit{p}}{{{\oplus}}}}\;(C_{2}\;{{}_{\mathit{q}}{{{\oplus}}}}\;C_{3})$
$\displaystyle=$ $\displaystyle\,p\cdot C_{1}+\bar{p}(q\cdot
C_{2}+\bar{q}\cdot C_{3})$ (def. of hidden choice) $\displaystyle=$
$\displaystyle\,p\cdot C_{1}+\bar{p}q\cdot C_{2}+\bar{p}\bar{q}\cdot C_{3}$
$\displaystyle=$ $\displaystyle\,q(p(\nicefrac{{1}}{{q}}\cdot
C_{1})+\bar{p}\cdot C_{2})+\bar{q}(\bar{p}\cdot C_{3})$ $\displaystyle=$
$\displaystyle\,(\nicefrac{{1}}{{q}}\cdot
C_{1}\;{{}_{\mathit{p}}{{{\oplus}}}}\;C_{2})\;{{}_{\mathit{q}}{{{\oplus}}}}\;\bar{p}\cdot
C_{3}$ (def. of hidden choice)

  4. d)

_Absorption_ : First note that:

$\displaystyle\,(C_{1}\;{{}_{\mathit{p}}{{{\oplus}}}}\;C_{2})\;{{}_{\mathit{q}}{{{\oplus}}}}\;(C_{1}\;{{}_{\mathit{r}}{{{\oplus}}}}\;C_{2})$
$\displaystyle=$
$\displaystyle\,q(pC_{1}+\bar{p}C_{2})+\bar{q}(rC_{1}+\bar{r}C_{2})$ (def. of
hidden choice) $\displaystyle=$
$\displaystyle\,pqC_{1}+\bar{p}qC_{2}+\bar{q}rC_{1}+\bar{q}\bar{r}C_{2}$
$\displaystyle=$
$\displaystyle\,(pq+\bar{q}r)C_{1}+(\bar{p}q+\bar{q}\bar{r})C_{2}$
$\displaystyle=$
$\displaystyle\,C_{1}\;{{}_{\mathit{(pq+\bar{q}r)}}{{{\oplus}}}}\;C_{2}$ (*)

To complete the proof, note that in step (*) above, $pq+\bar{q}r$ and
$\bar{p}q+\bar{q}\bar{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 $C_{1}$ and $C_{2}$, and any values $0\leq p,q\leq
1$, the visible choice operator satisfies the following properties:

  1. a)

_Idempotency_ : $C_{1}\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;C_{1}\approx C_{1}$

  2. b)

_Commutativity_ : $C_{1}\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;C_{2}\approx
C_{2}\;{{}_{\mathit{\bar{p}}}{{{\sqcupdot}}}}\;C_{1}$

  3. c)

_Associativity_ :
$C_{1}\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;(C_{2}\;{{}_{\mathit{q}}{{{\sqcupdot}}}}\;C_{3})\approx(\nicefrac{{1}}{{q}}\cdot
C_{1}\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;C_{2})\;{{}_{\mathit{q}}{{{\sqcupdot}}}}\;\bar{p}\cdot
C_{3}$ if $q\neq 0$.

###### Proof

We will prove each property separately.

  1. a)

_Idempotency_ : $C_{1}\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;C_{1}\approx C_{1}$,
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 the other side.

  2. b)

_Commutativity_ :

$\displaystyle C_{1}\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;C_{2}=$
$\displaystyle\,p\cdot C_{1}\diamond\bar{p}\cdot C_{2}$ (def. of visible
choice) $\displaystyle\approx$ $\displaystyle\ \bar{p}\cdot C_{2}\diamond
p\cdot C_{1}$ (by Lemma 17) $\displaystyle=$ $\displaystyle\
C_{2}\;{{}_{\mathit{\bar{p}}}{{{\sqcupdot}}}}\;C_{1}$ (def. of visible
choice).

In the above derivation, we can apply Lemma 17 because 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 the other side.

  3. c)

_Associativity_ :

$\displaystyle
C_{1}\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;(C_{2}\;{{}_{\mathit{q}}{{{\sqcupdot}}}}\;C_{3})=$
$\displaystyle\,p\cdot C_{1}\diamond\bar{p}(q\cdot C_{2}\diamond\bar{q}\cdot
C_{3})$ (def. of visible choice) $\displaystyle\approx$ $\displaystyle\,p\cdot
C_{1}\diamond\left(\bar{p}q\cdot C_{2}\diamond\bar{p}\bar{q}\cdot
C_{3}\right)$ (by Lemma 17) $\displaystyle=$
$\displaystyle\,q(p(\nicefrac{{1}}{{q}}\cdot C_{1})\diamond\bar{p}\cdot
C_{2})\diamond\bar{q}(\bar{p}\cdot C_{3})$ $\displaystyle=$
$\displaystyle\,(\nicefrac{{1}}{{q}}\cdot
C_{1}\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;C_{2})\;{{}_{\mathit{q}}{{{\sqcupdot}}}}\;\bar{p}\cdot
C_{3}$ (def. of visible choice)

In the above derivation, we can apply Lemma 17 because 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 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
$C_{1}\;{{}_{\mathit{p}}{{{\oplus}}}}\;(C_{2}\;{{}_{\mathit{q}}{{{\sqcupdot}}}}\;C_{3})$
and
$(C_{1}\;{{}_{\mathit{p}}{{{\oplus}}}}\;C_{2})\;{{}_{\mathit{q}}{{{\sqcupdot}}}}\;(C_{1}\;{{}_{\mathit{p}}{{{\oplus}}}}\;C_{3})$
cannot be both defined: if the former is defined, then $C_{1}$ must have the
same type as $C_{2}\;{{}_{\mathit{q}}{{{\sqcupdot}}}}\;C_{3}$, whereas if the
latter is defined, $C_{1}$ must have the same type as $C_{2}$, but
$C_{2}\;{{}_{\mathit{q}}{{{\sqcupdot}}}}\;C_{3}$ and $C_{2}$ do not have the
same type (they have different output sets).

However, as the next result shows, visible choice distributes over hidden
choice.

######  Proposition 20 (Distributivity of
$\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;$ over
$\;{{}_{\mathit{q}}{{{\oplus}}}}\;$)

Let $C_{1}$, $C_{2}$ and $C_{3}$ be compatible channels, and $C_{2}$ and
$C_{3}$ have the same type. Then, for any values $0\leq p,q\leq 1$:

$\displaystyle
C_{1}\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;(C_{2}\;{{}_{\mathit{q}}{{{\oplus}}}}\;C_{3})\approx(C_{1}\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;C_{2})\;{{}_{\mathit{q}}{{{\oplus}}}}\;(C_{1}\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;C_{3}).$

###### Proof

$\displaystyle\,C_{1}\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;(C_{2}\;{{}_{\mathit{q}}{{{\oplus}}}}\;C_{3})$
$\displaystyle=$
$\displaystyle\,(C_{1}\;{{}_{\mathit{q}}{{{\oplus}}}}\;C_{1})\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;(C_{2}\;{{}_{\mathit{q}}{{{\oplus}}}}\;C_{3})$
(idempotency of visible choice) $\displaystyle=$ $\displaystyle\,p(q\cdot
C_{1}+\bar{q}\cdot C_{1})\diamond\bar{p}(q\cdot C_{2}+\bar{q}\cdot C_{3})$
(def. of operators) $\displaystyle=$ $\displaystyle\,(pq\cdot
C_{1}+p\bar{q}\cdot C_{1})\diamond(\bar{p}q\cdot C_{2}+\bar{p}\bar{q}\cdot
C_{3})$ $\displaystyle\approx$ $\displaystyle\,(pq\cdot
C_{1}\diamond\bar{p}q\cdot C_{2})+(p\bar{q}\cdot
C_{1}\diamond\bar{p}\bar{q}\cdot C_{3})$ (by Lemma 17) $\displaystyle=$
$\displaystyle\,q(p\cdot C_{1}\diamond\bar{p}\cdot C_{2})+\bar{q}(p\cdot
C_{1}\diamond\bar{p}\cdot C_{3})$ $\displaystyle=$
$\displaystyle\,q(C_{1}\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;C_{2})+\bar{q}(C_{1}\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;C_{3})$
(def. of visible choice) $\displaystyle=$
$\displaystyle\,(C_{1}\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;C_{2})\;{{}_{\mathit{q}}{{{\oplus}}}}\;(C_{1}\;{{}_{\mathit{p}}{{{\sqcupdot}}}}\;C_{3})$
(def. of hidden choice)

In the above derivation, we can apply Lemma 17 because 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 the other side.