Information Leakage Games
Mário S. Alvim1 , Konstantinos Chatzikokolakis2 , Yusuke Kawamoto3 , andCatuscia Palamidessi4
1

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

Abstract. We consider a game-theoretic setting to model the interplay
between attacker and defender in the context of information flow, andto reason about their optimal strategies. In contrast with standard gametheory, in our games the utility of a mixed strategy is a convex functionof the distribution on the defender’s pure actions, rather than the expected value of their utilities. Nevertheless, the important properties ofgame theory, notably the existence of a Nash equilibrium, still hold forour (zero-sum) leakage games, and we provide algorithms to compute thecorresponding optimal strategies. As typical in (simultaneous) game theory, the optimal strategy is usually mixed, i.e., probabilistic, for both theattacker and the defender. From the point of view of information flow,
this was to be expected in the case of the defender, since it is well known
that randomization at the level of the system design may help to reduce
information leaks. Regarding the attacker, however, this seems the firstwork (w.r.t. the literature in information flow) proving formally that incertain cases the optimal attack strategy is necessarily probabilistic.

1

Introduction

A fundamental problem in computer security is the leakage of sensitive information due to correlation of secret information with observable information publicly
available, or in some way accessible, to the attacker. Correlation in fact allows
for the use of Bayesian inference to guessing the value of the secret. Typicalexamples are side channels attacks, in which (observable) physical aspects of thesystem, such as the execution time of a decryption algorithm, may be exploitedby the attacker to restrict the range of the possible (secret) encryption keys. The
branch of security that studies the amount of information leaked by a system
is called Quantitative Information Flow (QIF), and it has seen growing interest
over the past decade. See for instance [10,15,27,3,4], just to mention a few.
In general, it has been recognized that randomization can be very useful toobfuscate the link between secrets and observables. Examples include various
anonymity protocols (for instance, the dining cryptographers [9] and Crowds[23]), and the renown framework of differential privacy [11]. The defender (thesystem designer, or the user) is, therefore, typically probabilistic. As for theattacker, most works in the literature consider only passive attacks, limited to2Alvim et al.

observing the system’s behavior. Notable exceptions are the works of Borealeand Pampaloni [4], and of Mardziel et al. [18], which consider adaptive attackers
who interact with and influence the system. We note that, however, [4] does
not consider probabilistic strategies for the attacker. As for [18], although theirmodel allows them, none of their extensive case-studies needs probabilistic attack
strategies to maximize leakage. This may seem surprising, since, as mentioned
before, randomization is known to be useful (and, in general, crucial) for the
defender to undermine the attack and protect the secret. Thus there seems to
be an asymmetry between attacker and defender w.r.t. probabilistic strategies
in QIF. Our thesis is that there is indeed an asymmetry, but this does not meanthat the attacker has nothing to gain from randomization: when the defendercan change his own strategy according to the attacker’s actions, it becomes
advantageous for the attacker to try to be unpredictable and, consequently, adopt
a probabilistic strategy. For the defender, while randomization is useful for thesame reason, it is also useful because it reduces the information leakage, and since
information leakage constitutes the gain of the attacker, this reduction influences
his strategy. This latter aspect introduces the asymmetry mentioned above.
In the present work, we consider scenarios in which both attacker and defender can make choices that influence the system during the attack. We aim,in particular, at analyzing the attacker’s strategies that can maximize information leakage, and the defender’s most appropriate strategies to counterattackand keep the system as secure as possible. As argued before, randomization canhelp both attacker and defender make their moves unpredictable. The most suitable framework for analyzing this kind of interplay is, naturally, game theory,
where the use of randomization can be modeled by the notion of mixed strategies, and where the interplay between attacker and defender, and their struggle
to achieve the best result for themselves, can be modeled in terms of optimal
strategies and Nash equilibrium. It is important to note, however, that one of thetwo advantages that randomization has for the defender, namely the reductionof information leakage, has no counterpart in standard game theory. Indeed, we
demonstrate that this property makes the utility of a mixed strategy be a convex
function of the distribution of the defender. In contrast, in standard game theory
the utility of a mixed strategy is the expectation of the utility of the pure strategies of each player, and therefore it is an affine function on each of the players’
distributions. As a consequence, we need to consider a new kind of games, which
we call information leakage games, where the utility of a mixed strategy is afunction affine on the attacker’s strategy, and convex on the defender’s. Nevertheless, the fundamental results of game theory, notably the minimax theorem
and the existence of Nash equilibria, still hold for our zero-sum leakage games.
We also propose algorithms to compute the optimal strategy, namely, the strategies for the attacker and the defender that lead to a Nash equilibrium, where noplayer has anything to gain by unilaterally changing his own strategy.
For reasoning about information leakage, we employ the well-establishedinformation-theoretic framework, which is by far the most used in QIF. A central notion in this model is that of vulnerability, which intuitively measures how

Information Leakage Games3

easily the secret can be discovered (and exploited) by the attacker. For the sakeof generality, we adopt the notion of vulnerability as any convex and continuousfunction [4,2], which has been shown to subsume most previous measures of the
QIF literature [2], including Bayes vulnerability (a.k.a. min-vulnerability [27,8]),
Shannon entropy [25], guessing entropy [19], and g-vulnerability [3].
We note that vulnerability is an expectation measure over the secrets. In thispaper we assume the utility to be such average measure, but, in some cases, it
could be advantageous for the defender to adopt different strategies dependingon the value of the secret. We leave this refinement for future work.
The main contributions of this paper are the following:– We define a general framework of information leakage games to reason about
the interplay between attacker and defender in QIF scenarios.
– We prove that, in our framework, the utility is a convex function of the mixed
strategy of the defender. To the best of our knowledge, this is a novelty w.r.t.
traditional game theory, where the utility of a mixed strategy is defined as
expectation of the utilities of the pure strategies.
– We provide methods for finding the solution and the equilibria of leakage
games by solving a convex optimization problem.
– We show examples in which Nash equilibria require a mixed strategy. Thisis, to the best of our knowledge, the first proof in QIF that in some cases
the optimal strategy of the attacker must be probabilistic.
– As a case study, we consider the Crowds protocol in a MANET (Mobile Adhoc NETwork). We study the case in which the attacker can add a corrupted
node as an attack, the defender can add an honest node as a countermeasure,and we compute the defender component of the Nash equilibrium.
Plan of the paper In Section 2 we review the basic notions of game theory
and QIF. In Section 3 we introduce some motivating examples. In section 4 wediscuss the difference of our leakage games from those of standard game theory.
In Section 5 we prove the convexity of the utility of the defender. In Section 6 we
present algorithms for computing the Nash equilibria and optimal strategies forleakage games. In Section 7 we apply our framework to a version of the Crowds
protocol. In Section 8 we discuss related work. Section 9 concludes.

2

Preliminaries

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

Two-player, simultaneous games

We review basic definitions from two-player games, a model for reasoning about
the behavior of strategic players. We refer to [22] for more details.

4

Alvim et al.

In a game, each player has at its disposal a set of actions that he can perform,
and obtains some payoff (gain or loss) depending on the outcome of the actions
chosen by both players. The payoff’s value to each player is evaluated using autility function. Each player is assumed to be rational, i.e., his choice is driven by
the attempt to maximize his own utility. We also assume that the set of possible
actions and the utility functions of both players are common knowledge.
In this paper we only consider finite games, namely the cases in which theset of actions available to each player is finite. Furthermore, we only consider
simultaneous games, meaning that each player chooses actions without knowing
the actions chosen by the other. Formally, such a game is defined as a tuple5(D, A, ud , ua ), where D is a nonempty set of defender’s actions, A is a nonempty
set of attacker’s actions, ud : D × A → R is the defender’s utility function, andua : D × A → R is the attacker’s utility function.
Each player may choose an action deterministically or probabilistically. A
pure strategy of the defender (resp. attacker) is a deterministic choice of anaction, i.e., an element d ∈ D (resp. a ∈ A). A pair (d, a) is a pure strategy
profile, and ud (d, a), ua (d, a) represent the defender’s and the attacker’s utilities.
A mixed strategy of the defender (resp. attacker) is a probabilistic choice ofan action, defined as a probability distribution δ ∈ DD (resp. α ∈ DA). A pair(δ, α) is called a mixed strategy profile. The defender’s and the attacker’s expectedutility functions for mixed strategies are defined, respectively, as:def

Ud (δ, α) = E ud (d, a) =
d←δ
a←α

def

Ua (δ, α) = E ua (d, a) =
d←δ
a←α

X

δ(d)α(a)ud (d, a)

d∈D
a∈A

X

δ(d)α(a)ua (d, a)

d∈D
a∈A

A defender’s mixed strategy δ ∈ DD is a best response to an attacker’s mixed
strategy α ∈ DA if Ud (δ, α) = maxδ0 ∈DD Ud (δ 0 , α). Symmetrically, α ∈ DA is abest response to δ ∈ DD if Ua (δ, α) = maxα0 ∈DA Ud (δ, α0 ). A mixed-strategy Nashequilibrium is a profile (δ ∗ , α∗ ) such that δ ∗ is a best response to α∗ and viceversa. Namely, no unilateral deviation by any single player provides better utility
to that player. If δ ∗ and α∗ are point distributions concentrated on some d∗ ∈ D
and a∗ ∈ A, respectively, then (δ ∗ , α∗ ) is a pure-strategy Nash equilibrium, andwill be denoted by (d∗ , a∗ ). While not all games have a pure strategy Nashequilibrium, every finite game has a mixed strategy Nash equilibrium.
2.2

Zero-sum games and Minimax Theorem

A game (D, A, ud , ua ) is zero-sum if for any d ∈ D and any a ∈ A, ud (d, a) =−ua (d, a), i.e., the defender’s loss is equivalent to the attacker’s gain. For brevity,
in zero-sum games we denote by u the attacker’s utility function ua , and by U
5

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

Information Leakage Games5

the attacker’s expected utility Ua .6 Consequently, the goal of the defender is tominimize 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 profile (δ ∗ , α∗ ) such that U (δ ∗ , α∗ ) = minδ maxα U (δ, α). The von Neumann’s
minimax theorem ensures that such solution (which always exists) is stable:
Theorem 1 (von Neumann’s minimax theorem). Let X ⊂ Rm and Y ⊂Rn be compact convex sets, and U : X × Y → R be a continuous function suchthat U (x, y) is convex in x ∈ X and concave in y ∈ Y. Then it is the case thatminx∈X maxy∈Y U (x, y) = maxy∈Y minx∈X U (x, y).
A related property is that, under the conditions of Theorem 1, there exists a
saddle point (x∗ , y ∗ ) s.t., for all x ∈ X and y ∈ Y, U (x∗ , y)≤U (x∗ , y ∗ )≤U (x, y ∗ ).
2.3

Quantitative information flow

Finally, we briefly review the standard framework of quantitative information
flow, which is used to measure the amount of information leakage in a system.
Secrets and vulnerability A secret is some piece of sensitive information the
defender wants to protect, such as a user’s password, social security number, or
current location. The attacker usually only has some partial knowledge about
the value of a secret, represented as a probability distribution on secrets calleda prior. We denote by X the set of possible secrets, and we typically use π todenote a prior belonging to the set DX of probability distributions over X .
The vulnerability of a secret is a measure of the utility of the attacker’s
knowledge about the secret. In this paper we consider a very general notion ofvulnerability, following [2], and define a vulnerability V to be any continuous andconvex function of type DX → R. It has been shown in [2] that these functions
coincide with the set of g-vulnerabilities, and are, in a precise sense, the mostgeneral information measures w.r.t. a set of basic axioms. 7
Channels, posterior vulnerability, and leakage Systems can be modeled as information theoretic channels. A channel C : X × Y → R is a function in which
X is a set of input values, Y is a set of output values, and C(x, y) represents
the conditional probability of the channel producing output y ∈ Y when inputx ∈ X is provided.
Every channel C satisfies 0 ≤ C(x, y) ≤ 1 for all x ∈ X andPy ∈ Y, and y∈Y C(x, y) = 1 for all x ∈ X .
6

Conventionally in game theory the utility u is set to be that of the first player, but
we prefer to look at the utility from the point of view of the attacker to be in linewith the definition of utility as vulnerability, as we will introduce in Section 2.3.
7
More precisely, if posterior vulnerability is defined as the expectation of the vulnerability of posterior distributions, the measure respects the data-processing inequality
and yields non-negative leakage iff vulnerability is convex.

6

Alvim et al.

A distribution π ∈ DX and a channel C with inputs X and outputs Y inducea joint distributionp(x, y) = π(x)C(x,y) on X × Y, with marginal probabilities
PP
p(x) = y p(x, y) and p(y) = x p(x, y), and conditional probabilities p(x|y) =p(x,y)/p(y) if p(y) 6= 0. For a given y (s.t. p(y) 6= 0), the conditional probabilities
p(x|y) for each x ∈ X form the posterior distribution pX|y .
A channel C in which X is a set of secret values and Y is a set of observablevalues produced by a system can be used to model computations on secrets.
Assuming the attacker has prior knowledge π about the secret value, knows how
a channel C works, and can observe the channel’s outputs, the effect of thechannel is to update the attacker’s knowledge from a prior π to a collection ofposteriors pX|y , each occurring with probability p(y).
Given a vulnerability V, a prior π, and a channel C, the posterior vulnerability
V[π, C] is the vulnerability of the secret after the attacker has observed the


def P
output of C. Formally: V[π, C] = y∈Y p(y)V pX|y .
The information leakage of a channel C under a prior π is a comparison
between the vulnerability of the secret before the system was run—called theprior vulnerability—and the posterior vulnerability of the secret. The leakage
reflects by how much the observation of the system’s outputs increases the utilityof the attacker’s knowledge about the secret. It can be defined either additively(V[π, C] − V[π]), or multiplicatively (V[π,C]/V[π]).

3A motivating example

We present some simple examples to motivate our information leakage games.
3.1

The two-millionaires problem

The “two-millionaires problem” was introduced by Yao in [33]. In the original
formulation, there are two “millionaires”, Alice and Don, who want to discover
who is the richest among them, but neither wants to reveal to the other theamount of money that he or she has.
We consider a (conceptually) asymmetric variant of this problem, where Aliceis the attacker and Don is the defender. Don wants to learn whether or not he isricher than Alice, but does not want Alice to learn anything about the amountx of money he has. To this purpose, Don sends x to a trusted server Jeeves, whoin turn asks Alice, privately, what is her amount a of money. Jeeves then checks
which among x and a is greater, and sends the result y back to Don.8 However,Don is worried that Alice may intercept Jeeves’ message containing the result of
the comparison, and exploit it to learn more accurate information about x bytuning her answer a appropriately (since, given y, Alice can deduce whether a isan upper or lower bound on x). We assume that Alice may get to know Jeeves’
reply, but not the messages from Don to Jeeves.
8

The reason to involve Jeeves is that Alice may not want to reveal a to Don, either.

Information Leakage Games7

We will use the following information-flow terminology: the information thatshould remain secret (to the attacker) is called high, and what is visible to (andpossibly controllable by) the attacker is called low. Hence, in the program run
by Jeeves a is a low input and x is a high input. The result y of the comparison(since it may be intercepted by the attacker) is a low output. The problem is to
avoid the flow of information from x to y (given a).
One way to mitigate this problem is to use randomization. Assume that
Jeeves provides two different programs to ensure the service. Then, when Don
sends his request to Jeeves, he can make a random choice d among the two
programs 0 and 1, sending d to Jeeves along with the value x. Now if Aliceintercepts the result y, it will be less useful to her since she does not know whichof the two programs has been run. As Don of course knows which program wasrun, the result y will still be just as useful to him. 9
In order to determine the best probabilistic strategy that Don should apply to
select the program, we analyze the problem from a game-theoretic perspective.
For simplicity, we assume that x and a both range in {0, 1}. The two alternative
programs that Jeeves can run are shown in Table 1.
Program 0

Program 1

High Input: x ∈ {0, 1}
Low Input: a ∈ {0, 1}
Output: y ∈ {T, F }High Input: x ∈ {0, 1}
Low Input: a ∈ {0, 1}
Output: y ∈ {T, F }return x ≤ areturn x ≥ aTable 1. The two programs run by Jeeves.

The combined choices of Alice and Don determine how the system behaves.
Let D = {0, 1} represent Don’s possible choices, i.e., the program to run, and
A = {0, 1} represent Alice’s possible choices, i.e., the value of the low input a. We
shall refer to the elements of D and A as actions. For each possible combinationof actions d and a, we can construct a channel Cda with inputs X = {0, 1} (theset of possible high input values) and outputs Y = {T, F } (the set of possible
low output values), modeling the behavior of the system from the point of viewof the attacker. Intuitively, each channel entry Cda (x, y) is the probability thatthe program run by Jeeves (which is determined by d) produces output y ∈ Ygiven that the high input is x ∈ X and that the low input is a. The resulting
four channel matrices are represented in Table 2. Note that channels C01 and C10
do not leak any information about the input x (output y is constant), whereas
channels C00 and C11 completely reveal x (output y is in a bijection with x).
We want to investigate how the defender’s and the attacker’s strategies influence the leakage of the system. For that we can consider the (simpler) notionof posterior vulnerability, since, for a given prior, the value of leakage is in a9Note that d should not be revealed to the attacker: although d is not sensitive
information in itself, knowing it would help the attacker figure out the value of x.

8Alvim et al.
a=0

a=1

d = 0 (x ≤ a?)

C00 y = T y = F
x=0 1
0
x=1 0
1

C01 y = T y = F
x=0 1
0
x=1 1
0

d = 1 (x ≥ a?)

C10 y = T y = F
x=0 1
0
x=1 1
0

C11 y = T y = F
x=0 0
1
x=1 1
0

Table 2. The two-millionaires system, from the point of view of the attacker.

one-to-one (monotonic) correspondence with the value of posterior vulnerability. For this P
example, we consider posterior Bayes vulnerability [8,27], definedas V[π, C] = y maxx C(x, y)π(x). Intuitively, Bayes vulnerability measures theprobability of the adversary guessing the secret correctly in one try, and it canbe shown that V[π, C] coincides with the converse of the Bayes error.
For simplicity, we assume a uniform prior distribution πu . It has been shown
that, in this case, the posterior Bayes vulnerability of a channel C can be computed as the sum of the greatest elements of eachcolumn of C, divided by thePhigh input-domain size [7]. Namely, V[πu , C] = y maxx C(x,y)/|X |. It is easy to
see that we have V[πu , C00 ] = V[πu , C11 ] = 1 and V[πu , C01 ] = V[πu , C10 ] = 1/2.
Thus we obtain the utility table shown in Table 3, which is similar to that of
the well-known “matching-pennies” game.
As in standard game theory, there may not
V a=0a=1
exist an optimal pure strategy profile. The de1/2
d=0 1
fender as well as the attacker can then try tominimize/maximize the system’s vulnerability by
d = 1 1/2
1adopting a mixed strategy δ and α, respectively.
A crucial task is evaluating the vulnerability of the Table 3. Utility table for thesystem under such mixed strategies. This evalua- two-millionaires game.
tion is naturally performed from the point of viewof the attacker, who knows his own choice a, but not the defender’s choiced. As aPconsequence, the attacker sees the system as the convex combinationCδa = d δ(d) Cad , i.e., a probabilistic choice between the channels representing the defender’s actions. Hence, the overall vulnerability of the system will begiven by the vulnerability of Cδa , averaged over all attacker’s actions.
We now define formally the ideas illustrated above.
Definition 1. An information-leakage game is a tuple (D, A, C) where D, A
are the sets of actions of the attacker and the defender, respectively, and C ={Cda }da is a family of channel matrices indexed on pairs of actions d ∈ D, a ∈ A.
For a given vulnerability V and prior π, the utility of a pure strategy (d, a) is
given by V[π, Cda ]. The utility V(δ, α) of a mixed strategy (δ, α) is defined as:
P
def
def P
V(δ, α) = E V[π, Cδa ] = a α(a) V[π, Cδa ] where Cδa = d δ(d) Cada←α

In our example, δ is represented by a single number p: the probability that thedefender chooses d = 0 (i.e., Program 0). From the point of view of the attacker,

Information Leakage Games
Utility table for a = 0

Utility table for a = 1

Cp0 y = T
x=0 1
x=1 1−p

Cp1 y = T
x=0 p
x=1 1

y=F
0
p

9

y=F
1−p
0

Table 4. The two-millionaires mixed strategy of the defender, from the point of viewof the attacker, where p is the probability the defender picks action d = 0.

once he has chosen a, the system will look like a channel Cpa = p C0a +(1−p) C1a .
For instance, in the case a = 0, if x is 0 Jeeves will send T with probability 1,
but, if x is 1, Jeeves will send F with probability p and T with probability
1 − p. Similarly for a = 1. Table 4 summarizes the various channels modellingthe attacker’s point of view. It is easy to see that V[πu , Cp0 ] = (1+p)/2 andV[πu , Cp1 ] = (2−p)/2. In this case V[πu , Cpa ] coincides with the expected utility
with respect to p, i.e., V[πu , Cpa ] = p V[πu , C0a ] + (1 − p) V[πu , C1a ].
Assume now that the attacker choses a = 0 with probability q and a = 1
with probability 1 − q. The utility is obtained as expectation with respect to thestrategy of the attacker, hence the total utility is: V(p, q) = q (1+p)/2+(1−p) (2−p)/2,
which is affine in both p and q. By applying standard game-theoretic techniques,
we derive that the optimal strategy is (p∗ , q ∗ ) = (1/2, 1/2).
In the above example, things work just like in standard game theory. However,in the next section we will show an example that fully exposes the difference ofour games with respect to those of standard game theory.
3.2

Binary sum

The previous example is an instance of a general scenario in which a user, Don,delegates to a server, Jeeves, a certain computation that requires also some input
from other users. Here we will consider another instance, in which the function
to be computed is the binary sum ⊕. We assume Jeeves provides the programsin Table 5. The resulting channel matrices are represented in Table 6.
Program 0

Program 1

High Input: x ∈ {0, 1}
Low Input: a ∈ {0, 1}
Output: y ∈ {0, 1}
return x ⊕ aHigh Input: x ∈ {0, 1}
Low Input: a ∈ {0, 1}
Output: y ∈ {0, 1}
return x ⊕ a ⊕ 1

Table 5. The two programs for ⊕ and its complement.

We consider again Bayes posterior vulnerability as utility. It is easy to seethat we have V[πu , C00 ] = V[πu , C11 ] = V[πu , C01 ] = V[πu , C10 ] = 1. Thus forthe pure strategies we obtain the utility table shown in Table 7. This meansthat all pure strategies have the same utility 1 and therefore they are all equivalent. In standard game theory this would mean that also the mixed strategies have the same utility 1, since they are defined as expectation. In ourcase, however, the utility of a mixed strategy of the defender is convex on the

10Alvim et al.
a=0

a=1

d = 0 (x ⊕ a)

C00 y = 0 y = 1
x=0 1
0
x=1 0
1

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

d = 1 (x ⊕ a ⊕ 1)

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

C11 y = 0 y = 1
x=0 1
0
x=1 0
1

Table 6. The binary-sum system, from the point of view of the attacker.

distribution, so it may be convenient for the deV a=0a=1
fender to adopt a mixed strategy. Let p, 1 − p be
d
=
0 1
1
the probabilities of the defender choosing Program
d=1 1
10 and Program 1, respectively. From the point ofview of the attacher, for each of his choices of a,the system will appear as the probabilistic channel Table 7. Utility table for thebinary-sum game.
Cpa represented in Table 8.
a=0

a=1

Cp0 y = T y = F
x=0 p
1−p
x=1 1−pp

Cp1 y = T y = F
x=0 1−p
p
x=1 p
1−p

Table 8. The binary-sum mixed strategy of the defender, from the point of view of
the attacker, where p is the probability the defender picks action d = 0.

It is easy to see that V[πu , Cp0 ] = V[πu , Cp1 ] = 1 − p if p ≤ 1/2, andV[πu , Cp0 ] = V[πu , Cp1 ] = p if p ≥ 1/2. On the other hand, with respect to amixed strategy of the attacker the utility is still defined as expectation. Since inthis case the utility is the same for a = 0 and a = 1, it remains the same for any
strategy of the attacker. Formally, V(p, q) = q V[πu , Cp0 ] + (1 − q) V[πu , Cp1 ] =V[πu , Cp0 ], which does not depend on q and it is minimum for p = 1/2. We
conclude that the point of equilibrium is (p∗ , q ∗ ) = (1/2, q ∗ ) for any value of q ∗ .

4Leakage games vs. standard game theory models

In this section we explain the differences between our information leakage games
and standard approaches to game theory. We discuss: (1) why the use of vulnerability as a utility function makes our games non-standard w.r.t. von NeumannMorgenstern’s treatment of utility, (2) why the use of concave utility functions
to model risk-averse players does not capture the behavior of the attacker in ourgames, and (3) how our games differ from traditional convex-concave games.

Information Leakage Games

4.1

11

The von Neumann-Morgenstern’s treatment of utility

In their treatment of utility, von Neumann and Morgenstern [29] demonstrated
that the utility of a mixed strategy equals the expected utility of the corresponding pure strategies when a set of axioms is satisfied for player’s preferences overprobability distributions (a.k.a. lotteries) on payoffs. Since in our leakage games
the utility of a mixed strategy is not the expected utility of the corresponding
pure strategies, it is relevant to identify how exactly our framework fails to meetvon Neumann and Morgenstern (vNM) axioms.
Let us first introduce some notation. Given two mixed strategies σ, σ 0 for aplayer, we write σ  σ 0 (or σ 0  σ) when the player prefers σ 0 over σ, and σ ∼ σ 0when the player is indifferent between σ and σ 0 . Then, the vNM axioms can beformulated as follows [24]. For every mixed strategies σ, σ 0 and σ 00 :A1 Completeness: it is either the case that σ  σ 0 , σ  σ 0 , or σ ∼ σ 0 .
A2 Transitivity: if σ  σ 0 and σ 0  σ 00 , then σ  σ 00 .
A3 Continuity: if σ  σ 0  σ 00 , then there exist p ∈ [0, 1] s.t. p σ+(1−p) σ 00 ∼ σ 0 .
A4 Independence: if σ  σ 0 then for any σ 00 and p ∈ [0, 1] we have p σ + (1 −p) σ 00  p σ 0 + (1 − p) σ 00 .
For any fixed prior π on secrets, the utility function u(C) = V[π, C] is a total
function on C ranging over the reals, and therefore it satisfies axioms A1, A2 andA3 above. However, u(C) does not satisfy A4, as the next example illustrates.
Example 1. Consider the following three channel matrices from input set X ={0, 1} to output set Y = {0, 1}, where  is a small positive constant:
C1 y = 0 y = 1
x=0 1− 
x=1  1−C2 y = 0 y = 1
x=0 1
0
x=1 0
1

C3 y = 0 y = 1
x=0 0
1
x=1 1
0

If we focus on Bayes vulnerability, it is clear that an attacker would prefer C2
over C1 , i.e., C1  C2 . However, for the probability p = 1/2 we would have:p C1 + (1 − p) C3 y = 0 y = 1(1−)/2 (1+)/2
x=0(1+)/2 (1−)/2
x=1

and

p C2 + (1 − p) C3 y = 0 y = 1
1/2
1/2
x=0
1/2
1/2
x=1

Since channel p C1 +(1−p) C3 clearly reveals no less information about the secretthan channel p C2 + (1 − p) C3 , we have that p C1 + (1 − p) C3  p C2 + (1 − p) C3 ,and the axiom of independence is not satisfied.
It is actually quite natural that vulnerability does not satisfy independence: aconvex combination of two “leaky” channels (i.e., high-utility outcomes) can
produce a “non-leaky” channel (i.e., a low-utility outcome). As a consequence,
the traditional game-theoretic approach to the utility of mixed strategies does
not apply to our information leakage games. However the existence of Nashequilibria is still granted, as we will see in Section 5, Corollary 1.

12

Alvim et al.

4.2

Risk functions

At a first glance, it may seem that our information leakage games could be
expressed with some clever use of the concept of risk-averse players (in our case,the attacker), which is also based on convex utility functions (cf. [22]). Thereis, however, a crucial difference: in the models of risk-averse players, the utility
function is convex on the payoff of an outcome of the game, but the utility of amixed strategy is still the expectation of the utilities of the pure strategies, i.e., it
is linear on the distributions. On the other hand, the utility of mixed strategies
in our information leakage games is convex on the distribution of the defender.
This difference arises precisely because in our games utility is defined as thevulnerability of the channel perceived by the attacker, and, as we discussed, thiscreates an extra layer of uncertainty for the attacker.
4.3

Convex-concave games

Another well-known model from standard game-theory is that of convex-concave
games, in which each of two players can choose among a continuous set of actions
yielding convex utility for one player, and concave for the other. In this kind ofgame the Nash equilibria are given by pure strategies for each player.
A natural question would be why not represent our systems as convex-concave
games in which the pure actions of players are the mixed strategies of our leakage
games. Namely, the real values p and q that uniquely determine the defender’sand the attacker’s mixed strategies, respectively, in the two-millionaires game ofSection 3, could be taken to be the choices of pure strategies in a convex-concave
game in which the set of actions for each player is the real interval [0, 1].
This mapping from our games to convex-concave games, however, would
not be natural. One reason is that utility is still defined as expectation in thestandard convex-concave games, in contrast to our games. Consider two strategies p1 and p2 with utilities u1 and u2 , respectively. If we mix them using thecoefficient q ∈ [0, 1], the resulting strategy q p1 + (1 − q) p2 will have utilityu = q u1 + (1 − q) u2 in the standard convex-concave game, while in our case theutility would in general be strictly smaller than u. The second reason is that apure action corresponding to a mixed strategy may not always be realizable. To
illustrate this point, consider again the two-millionaires game, and the defender’s
mixed strategy consisting in choosing Program 0 with probability p and Program
1 with probability 1−p. The requirement that the defender has a pure action corresponding to p implies the existence of a program (on Jeeves’ side) that makes
internally a probabilistic choice with bias p and, depending on the outcome, executes Program 0 or Program 1. However, it is not granted that Jeeves disposesof such a program. Furthermore, Don would not know what choice has actually
been made, and thus the program would not achieve the same functionality, i.e.,
let Don know who is the richest. (Note that Jeeves should not communicate to
Don the result of the choice, because of the risk that Alice intercepts it.) Thislatter consideration underlines a key practical aspect of leakage games, namely,
the defender’s advantage over the attacker due to his knowledge of the result ofInformation Leakage Games13

his own random choice (in a mixed strategy). This advantage would be lost in
a convex-concave representation of the game since the random choice would be“frozen” in its representation as a pure action.

5

Convexity of vulnerability w.r.t. channel composition

In this section we show that posterior vulnerability is a convex function of thestrategy of the defender. In other words, given a set of channels, and a probability
distribution over them, the vulnerability of the composition of these channels
according to the distribution is smaller than or equal to the composition of theirvulnerabilities. As a consequence, we derive the existence of the Nash equilibria.
In order to state this result formally, we introduce the following notation:
given a channel matrix C and a scalar a, a C is the matrix obtained by multiplying every element of C by a. Given two compatible channel matrices C1 andC2 , namely matrices with the same indices of rows and columns10 , C1 + C2 isobtained by adding the cells of C1 andP C2 with same indices. Note that if µ is a
probability distribution on I, then i∈I µ(i) Ci is a channel matrix.
Theorem 2 (Convexity of vulnerability w.r.t. channel composition).
Let {Ci }i∈I be a family of compatible channels, and µ be a distribution on I.
Then, for every prior distribution π, and every vulnerability V, the corresponding
posterior vulnerability is convex w.r.t. to channel
P composition.
P Namely, for any
probability distribution µ on I, we have V[π, i µ(i) Ci ] ≤ i µ(i) V[π, Ci ].
P
P
Proof. Define p(y) = x π(x) i µ(i) Ci (x, y). Then:
i
h
P
P
P
π(·)
i µ(i) Ci (·,y)(by def. of posterior V)
V[π, i µ(i) Ci ] =
p(y)
V
y
p(y)
i
h
P
P
π(·) Ci (·,y)=
y p(y) Vi µ(i)p(y)ihPPπ(·) Ci (·,y)≤(*)
y p(y)i µ(i) V
p(y)
i
h
P
P
π(·) Ci (·,y)=
i µ(i)y p(y) V
p(y)
P
=
µ(i)
V[π,
C
]
(by def. of posterior V)iiwhere (*) follows from the convexity of V w.r.t. the prior (cf. Section 2.3).

tu

The existence of Nash equilibria immediately follows from the above theorem:
Corollary 1. For any (zero-sum) information-leakage game there exist a Nashequilibrium, which in general is given by a mixed strategy.
Proof. Given a mixed strategy (δ, α), the utility V(δ, α) given in Definition 1 isaffine (hence concave) on α. Furthermore, by Theorem 2, V(δ, α) is convex on δ.
Hence we can apply the von Neumann’s minimax theorem (Section 2.2), which
ensures the existence of a saddle point, i.e., a Nash equilibrium.
tu
10Note that two channel matrices with different column indices can always be madecompatible by adding appropriate columns with 0-valued cells in each of them.

14

6

Alvim et al.

Computing equilibria of information leakage games

Our goal is to solve information leakage games, in which the success of an attacka and a defence d is measured by a vulnerability measure V. The attack/defence
combination is a pure strategy profile (d, a) in this game, and is associated witha channel Cda modeling the behavior of the system. The attacker clearly knows
his own choice a, whereas the defender’s choice is assumed to be hidden. Hencethe utilty of a mixed strategy profile (δ, α) will be given by Definition 1, that is:V(δ, α) =Pa α(a) V[π,Pd δ(d) Cda ]Note that V(δ, α) is convex on δ and affine on α, hence Theorem 1 guarantees
the existence of an equilibrium (i.e. a saddle-point) (δ ∗ , α∗ ) which is a solutionof both the minimax and the maximin problems. The goal in this section is tocompute a) a δ ∗ that is part of an equilibrium, which is important in order to
optimize the defence, and b) the utility V(δ ∗ , α∗ ), which is important to provide
an upper bound on the effectiveness of an attack when δ ∗ is applied.
This is a convex-concave optimization problem for which various methods
have been proposed in the literature. If V is twice differentiable (and satisfies
a few extra conditions) then the Newton method can be applied [6]; however,many such measures, most notably Bayes-vulnerability, our main vulnerability
measure of interest, are not differentiable. For non-differentiable functions, [21]proposes a subgradient method that iterates on both δ, α at each step. We haveapplied this method and it does indeed converge to V(δ ∗ , α∗ ), with one importantcaveat: the solution δ that it produces is not necessarily an equilibrium (note that
V(δ, α) = V(δ ∗ , α∗ ) does not guarantee that (δ, α) is a saddle point). Producing
an optimal δ ∗ is of vital importance in our case.
The method we propose is based on the idea of solving the minimax problem
δ̂ = argminδ maxα V(δ, α), since its solution is guaranteed to be part of an equilibrium.11 To solve this problem, we exploit the
P fact that V(δ,P α) is affine on α
(not just concave). For a fixed δ, maximizing P a α(a) V[π, d δ(d) Cda ] simply
involves picking the a with the highest V[π, d δ(d) Cda ] and assigning probability 1 to it. Hence, ourPminimax problem is equivalent to δ̂ = argminδ f (δ)
where f (δ) = maxa V[π, d δ(d) Cda ]; that is, we have to minimize the max offinitely many convex functions, with δ being the only variables.
For this problem we can employ the projected subgradient method, given by:δ (k+1) = P (δ (k) − αk g (k) )where g (k) is any subgradient of f on δ (k) [5]. Note that the subgradient of afinite max is simply a subgradient of any branch that gives the max at thatpoint. P (x) is the projection of x on the domain of f ; in our case the domain is
the probability simplex, for which there exist efficient algorithms for computing
11

Note that this is true only for δ, the α-solution of the minimax problem is notnecessarily part of an equilibrium; we need to solve the maximin problem for this.

Information Leakage Games15

the projection [30]. Finally αk is a step-size, for which various
choices guarantee√
convergence [5]. In our experiments we found αk = 0.1/ k to perform well.
As the starting point δ (1) we take the uniform distribution; moreover thesolution can be approximated to within an arbitrary  > 0 by using the stopping
criterion of [5, Section 3.4]. Note that the obtained δ̂ approximates the equilibrium strategy δ ∗ , while f (δ̂) approximates V(δ ∗ , α∗ ). Hence we achieve bothdesired goals, as formally stated in the following result.
Proposition 1. If V is Lipschitz then the subgradient method discussed in thissection converges to a δ ∗ that is part of an equilibrium of the game. Moreover, letδ̂ be the solution computed within a given  > 0, and let (δ ∗ , α∗ ) be an equilibrium.
Then it holds that:V(δ̂, α) −  ≤ V(δ̂, α∗ ) ≤ V(δ, α∗ ) + ∀δ, αwhich also implies that f (δ̂) − V(δ ∗ , α∗ ) ≤ .
Proof. (Sketch) argminδ f (δ) is equivalent to the minimax problem whose δsolution is guaranteed to be part of an equilibrium. Convergence is ensured by
the subgradient method under the Lipschitz condition, and given that ||δ (1) −δ ∗ ||is bounded by the distance between the uniform and a point distribution.
tuFinally, ofPparticular interest is the Bayes-vulnerability measure [8,27], givenby V[π, C] = y maxx π(x) C(x, y), since it is widely used to provide an upperbound to all other measures of information leakage [3]. For this measure, V isP(k)
Lipschitz and the subgradient vector g (k) is given by gd = y π(x∗y ) Cda∗ (x∗y , y)where a∗ , x∗y are the ones giving the max in the branches of f (δ (k) ). Note also
that, since f is piecewise linear, the convex optimization problem can be transformed into a linear one using a standard technique, and then solved by linear
programming. However, due to the large number of max branches of V, thisconversion can be a problem with a huge number of constraints. In our experiments we found that the subgradient method described above is significantly
more efficient than linear programming.
Note also that, although the subgradient method is general, it might be
impractical in applications where the number of attacker or defender actions
is very large. Application-specific methods could offer better scalability in suchcases, we leave the development of such methods as future work.

7

Case study

In this section, we apply our game-theoretic analysis to the case of anonymous
communication on a mobile ad-hoc network (MANET). In such a network, nodes
can move in space and communicate with other nearby nodes. We assume that
nodes can also access some global (wide area) network, but such connections
are neither anonymous nor trusted. Consider, for instance, smartphone users
who can access the cellular network, but do not trust the network provider. The

16

Alvim et al.

goal is to send a message on the global network without revealing the sender’sidentity to the provider. For that, users can form a MANET using some shortrange communication method (e.g., bluetooth), and take advantage of the local
network to achieve anonymity on the global one.
Crowds [23] is a protocol for anonymous communication that can be employedon a MANET for this purpose. Note that, although more advanced systems foranonymous communication exist (e.g. Onion Routing), the simplicity of Crowds
makes it particularly appeling for MANETs. The protocol works as follows: theinitiator (i.e., the node who wants to send the message) selects some other nodeconnected to him (with uniform probability) and forwards the request to him.
A forwarder, upon receiving the message, performs a probabilistic choice: withprobability pf he keeps forwarding the message (again, by selecting uniformly auser among the ones connected to him), while with probability 1 − pf he delivers
the message on the global network. Replies, if any, can be routed back to theinitiator following the same path in reverse order.
Anonymity comes from the fact that the detected node (the last in the path)
is most likely not the initiator. Even if the attacker knows the network topology, he can infer that the initiator is most likely a node close to the detected
one, but if there are enough nodes we can achieve some reasonable anonymity
guarantees. However, the attacker can gain an important advantage by deploying a node himself and participating to the MANET. When a node forwards a
message to this corrupted node, this action is observed by the attacker andincreases the probability of that node being the initiator. Nevertheless, thenode can still claim that he was only forwarding the request for someone else,
hence we still provide some level of anonymity. By modeling the system asa channel, and computing its posterior Bayes
vulnerability [27], we get the probability thatthe attacker guesses correctly the identity of theinitiator, after performing his observation.
In this section we study a scenario of 30
nodes deployed in an area of 1km×1km, in thelocations illustrated in Fig. 1. Each node cancommunicate with others up to a distance of 250
meters, forming the network topology shown in
the graph. To compromise the anonymity of thesystem, the attacker plans to deploy a corrupted
node in the network; the question is which is
the optimal location for such a node. The an- Fig. 1. A MANET with 30 users
swer is far from trivial: on the one side being in a 1km×1km area.
connected to many nodes is beneficial, but at
the same time these nodes need to be “vulnerable”, being close to a highly connected clique might not be optimal. At the same time, the administrator of the
network is suspecting that the attacker is about to deploy a corrupted node.
Since this action cannot be avoided (the network is ad-hoc), a countermeasure
is to deploy a deliverer node at a location that is most vulnerable. Such a nodeInformation Leakage Games

17

Defender’s action

directly delivers all messages forwarded to it on the global network; since itnever generates messages its own anonymity is not an issue, it only improves
the anonymity of the other nodes. Moreover, since it never communicates in thelocal network its operation is invisible to the attacker. But again, the optimal
location for the new deliverer node is not obvious, and most importantly, thechoice depends on the choice of the attacker.
To answer these questions, we model the system as a game where the actions of attacker and defender are the locations of newly deployed corrupted andhonest nodes, respectively. We assume that the possible locations for new nodes
are the nine ones shown in Fig. 1. For each pure strategy profile (d, a), we construct the corresponding network and use the PRISM model checker to construct
the corresponding channel Cda , using a model similar to the one of [26]. Notethat the computation considers the specific network topology of Fig. 1, whichreflects the positions of each node at the time when the attack takes place; thecorresponding channels need to be recomputed if the network changes in the future. As leakage measure we use the posterior Bayes vulnerability (with uniform
prior π), which is the attacker’s probability of correctly guessing the initiator
given his observation in the protocol. According to Definition 1, for a mixed
strategy profile (δ, α) the utility
Attacker’s actionis V(δ, α) = Ea←αV[π, Cδa ].
1
2
3
4
5
6
7
8
9
The utilities (posterior Bayes
1 7.38 6.88 6.45 6.23 7.92 6.45 9.32 7.11 6.45
vulnerability %) for each pure
2 9.47 6.12 6.39 6.29 7.93 6.45 9.32 7.11 6.45
profile are displayed in Table 9.
3 9.50 6.84 5.46 6.29 7.94 6.45 9.32 7.11 6.45
4 9.44 6.92 6.45 5.60 7.73 6.45 9.03 7.11 6.45
Note that the attacker and de5 9.48 6.91 6.45 6.09 6.90 6.13 9.32 6.92 6.44
fender actions substantialy affect
6 9.50 6.92 6.45 6.29 7.61 5.67 9.32 7.11 6.24
the effectiveness of the attack,
7 9.50 6.92 6.45 5.97 7.94 6.45 7.84 7.10 6.45
with the probability of a correct
8 9.50 6.92 6.45 6.29 7.75 6.45 9.32 6.24 6.45
9 9.50 6.92 6.45 6.29 7.92 6.24 9.32 7.11 5.68
guess ranging between 5.46% and9.5%. Based on the results of Sec- Table 9. Utility for each pure strategy profile.
tion 6, we can then compute thebest strategy for the defender,
which turns out to be (probabilities expressed as %):δ ∗ = (34.59, 3.48, 3.00, 10.52, 3.32, 2.99, 35.93, 3.19, 2.99)
This strategy is part of an equilibrium and guarantees that for any choice of theattacker the vulnerability is at most 8.76%, and is substantially better that thebest pure strategy (location 1) which leads to a worst vulnerability of 9.32%.
As expected, δ ∗ selects the most vulnerable locations (1 and 7) with the highest
probability. Still, the other locations are selected with non-negligible probability,
which is important for maximizing the attacker’s uncertainty about the defense.

8

Related work

There is an extensive literature on game theory models for security and privacy incomputer systems, including network security, vehicular networks, cryptography,
anonymity, location privacy, and intrusion detection. See [17] for a survey.

18

Alvim et al.

In many studies, security games have been used to model and analyze utilities
between interacting agents, especially an attacker and a defender. In particular,
Korzhyk et al. [16] present a theoretical analysis of security games and investigate
the relation between Stackelberg and simultaneous games under various forms
of uncertainty. In application to network security, Venkitasubramaniam [28] investigates anonymous wireless networking, which they formalize as a zero-sum
game between the network designer and the attacker. The task of the attacker is
to choose a subset of nodes to monitor so that anonymity of routes is minimum
whereas the task of the designer is to maximize anonymity by choosing nodes toevade flow detection by generating independent transmission schedules.
Khouzani et al. [14] present a framework for analyzing a trade-off between
usability and security. They analyze guessing attacks and derive the optimal policies for secret picking as Nash/Stackelberg equilibria. Khouzani and Malacaria[13] investigate properties of leakage when perfect secrecy is not achievable dueto the limit on the allowable size of the conflating sets, and show the existenceof universally optimal strategies for a wide class of entropy measures, and for gentropies (the dual of g-vulnerabilities). In particular, they show that designinga channel with minimum leakage is equivalent to Nash equilibria in a corresponding two-player zero-sum games of incomplete information for a range of entropy
measures.
Concerning costs of security, Yang et al. [32] propose a framework to analyze
user behavior in anonymity networks. Utility is modeled as a combination ofweighted cost and anonymity utility. They also consider incentives and theirimpact on users’ cooperation.
Some security games have considered leakage of information about the defender’s choices. For example, Alon et al. [1] present two-player zero-sum games
where a defender chooses probabilities of secrets while an attacker chooses andlearns some of the defender’s secrets. Then they show how the leakage on the defender’s secrets influences the defender’s optimal strategy. Xu et al. [31] present
zero-sum security games where the attacker acquires partial knowledge on the
security resources the defender is protecting, and show the defender’s optimal
strategy under such attacker’s knowledge. More recently, Farhang et al. [12]present two-player games where utilities are defined taking account of information leakage, although the defender’s goal is different from our setting. They
consider a model where the attacker incrementally and stealthily obtains partial
information on a secret, while the defender periodically changes the secret aftersome time to prevent a complete compromise of the system. In particular, thedefender is not attempting to minimize the leak of a certain secret, but only
to make it useless (for the attacker). Hence their model of defender and utility
is totally different from ours. To the best of our knowledge there have been noworks exploring games with utilities defined as information-leakage measures.
Finally, in game theory Matsui [20] uses the term “information leakage game”
with a meaning different than ours, namely, as a game in which (part of) thestrategy of one player may be leaked in advance to the other player, and thelatter may revise his strategy based on this knowledge.

Information Leakage Games

9

19

Conclusion and future work

In this paper we introduced the notion of information leakage games, in which
a defender and an attacker have opposing goals in optimizing the amount of
information leakage in a system. In contrast to standard game theory models,in our games the utility of a mixed strategy is a convex function of the distribution of the defender’s actions, rather than the expected value of the utilitiesof the pure strategies in the support. Nevertheless, the important properties ofgame theory, notably the existence of a Nash equilibrium, still hold for our zerosum leakage games, and we provided algorithms to compute the corresponding
optimal strategies for the attacker and the defender.
As future research, we would like to extend leakage games to scenarios withrepeated observations, i.e., when the attacker can repeatedly observe the outcomes of the system in successive runs, under the assumption that both theattacker and the defender may change the channel at each run. Furthermore,
we would like to consider the possibility to adapt the defender’s strategy to thesecret value, as we believe that in some cases this would provide significant advantage to the defender. We would also like to consider the cost of attack andof defense, which would lead to non-zero-sum games.
Acknowledgments The authors are thankful to Arman Khouzani and Pedro O. S. Vazde Melo for valuable discussions. 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. Mário S. Alvim was
supported by CNPq, CAPES, and FAPEMIG. Yusuke Kawamoto was supported by
JSPS KAKENHI Grant Number JP17K12667.

References
1. N. Alon, Y. Emek, M. Feldman, and M. Tennenholtz. Adversarial leakage in games.
SIAM J. Discrete Math., 27(1):363–385, 2013.
2. M. S. Alvim, K. Chatzikokolakis, A. McIver, C. Morgan, C. Palamidessi, and
G. Smith. Axioms for information leakage. In Proc. of CSF, pages 77–92, 2016.
3. M. S. Alvim, K. Chatzikokolakis, C. Palamidessi, and G. Smith. Measuring information leakage using generalized gain functions. In CSF, pages 265–279, 2012.
4. M. Boreale and F. Pampaloni. Quantitative information flow under generic leakage
functions and adaptive adversaries. Log. Meth. Comp. Sci., 11(4), 2015.
5. S. Boyd and A. Mutapcic. Subgradient methods. Lecture notes of EE364b, Stanford
University, Winter Quarter, 2007, 2006.
6. S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press,
New York, 2004.
7. C. Braun, K. Chatzikokolakis, and C. Palamidessi. Quantitative notions of leakage for one-try attacks. In Proc. of MFPS, volume 249 of ENTCS, pages 75–91.
Elsevier, 2009.
8. K. Chatzikokolakis, C. Palamidessi, and P. Panangaden. On the Bayes risk in
information-hiding protocols. J. of Comp. Security, 16(5):531–571, 2008.

20

Alvim et al.

9. D. Chaum. The dining cryptographers problem: Unconditional sender and recipient
untraceability. Journal of Cryptology, 1:65–75, 1988.
10. D. Clark, S. Hunt, and P. Malacaria. A static analysis for quantifying information
flow in a simple imperative language. J. of Comp. Security, 2007.
11. C. Dwork, F. Mcsherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity
in private data analysis. In Proc. of TCC, pages 265–284, 2006.
12. S. Farhang and J. Grossklags. Flipleakage: A game-theoretic approach to protect against stealthy attackers in the presence of information leakage. In Proc. of
GameSec, pages 195–214, 2016.
13. M. Khouzani and P. Malacaria. Relative perfect secrecy: Universally optimal
strategies and channel design. In Proc. of CSF, pages 61–76. IEEE, 2016.
14. M. H. R. Khouzani, P. Mardziel, C. Cid, and M. Srivatsa. Picking vs. guessing
secrets: A game-theoretic analysis. In Proc. of CSF, pages 243–257, 2015.
15. B. Köpf and D. A. Basin. An information-theoretic model for adaptive side-channel
attacks. In Proc. of CCS, pages 286–296. ACM, 2007.
16. D. Korzhyk, Z. Yin, C. Kiekintveld, V. Conitzer, and M. Tambe. Stackelberg vs.
nash in security games: An extended investigation of interchangeability, equivalence, and uniqueness. J. Artif. Intell. Res., 41:297–327, 2011.
17. M. H. Manshaei, Q. Zhu, T. Alpcan, T. Bacşar, and J.-P. Hubaux. Game theory
meets network security and privacy. ACM Comput. Surv., 45(3):25:1–25:39, 2013.
18. P. Mardziel, M. S. Alvim, M. W. Hicks, and M. R. Clarkson. Quantifying information flow for dynamic secrets. In Proc. of S&P, pages 540–555, 2014.
19. Massey. Guessing and entropy. In Proc. of ISIT, page 204. IEEE, 1994.
20. A. Matsui. Information leakage forces cooperation. Games and Economic Behavior,
1(1):94 – 115, 1989.
21. A. Nedić and A. Ozdaglar. Subgradient methods for saddle-point problems. Journalof optimization theory and applications, 142(1):205–228, 2009.
22. M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994.
23. M. K. Reiter and A. D. Rubin. Crowds: anonymity for Web transactions. ACM
Trans. on Information and System Security, 1(1):66–92, 1998.
24. A. Rubinstein. Lecture Notes in Microeconomic Theory. Princeton University
Press, second edition, 2012.
25. C. E. Shannon. A mathematical theory of communication. Bell System Technical
Journal, 27:379–423, 625–56, 1948.
26. V. Shmatikov. Probabilistic analysis of anonymity. In CSFW, pages 119–128, 2002.
27. G. Smith. On the foundations of quantitative information flow. In Proc. of FOSSACS, volume 5504 of LNCS, pages 288–302. Springer, 2009.
28. P. Venkitasubramaniam and L. Tong. A game-theoretic approach to anonymous
networking. IEEE/ACM Trans. Netw., 20(3):892–905, 2012.
29. J. Von Neumann and O. Morgenstern. Theory of games and economic behavior.
Princeton university press, 2007.
30. W. Wang and M. A. Carreira-Perpinán. Projection onto the probability simplex:
An efficient algorithm with a simple proof, and an application. arXiv preprint
arXiv:1309.1541, 2013.
31. H. Xu, A. X. Jiang, A. Sinha, Z. Rabinovich, S. Dughmi, and M. Tambe. Security
games with information leakage: Modeling and computation. In Proc. of IJCAI,
pages 674–680, 2015.
32. M. Yang, V. Sassone, and S. Hamadou. A game-theoretic analysis of cooperationin anonymity networks. In Proc. of POST, pages 269–289, 2012.
33. A. C. Yao. Protocols for secure computations. IEEE 54th Annual Symposium on
Foundations of Computer Science, pages 160–164, 1982.