Konstantinos Chatzikokolakis

Catuscia Palamidessi
email: catuscia@lix.polytechnique.fr

Prakash Panangaden
email: prakash@cs.mcgill.ca

On the Bayes Risk in Information-Hiding Protocols *

Randomized protocols for hiding private information can be regarded as noisy channels in the information-theoretic sense, and the inference of the concealed information can be regarded as a hypothesis-testing problem. We consider the Bayesian approach to the problem, and investigate the probability of error associated to the MAP (Maximum Aposteriori Probability) inference rule. Our main result is a constructive characterization of a convex base of the probability of error, which allows us to compute its maximum value (over all possible input distributions), and to identify upper bounds for it in terms of simple functions. As a side result, we are able to improve the Hellman-Raviv and the Santhi-Vardy bounds expressed in terms of conditional entropy. We then discuss an application of our methodology to the Crowds protocol, and in particular we show how to compute the bounds on the probability that an adversary break anonymity.

Introduction

Information-hiding protocols try to hide the relation between certain facts, that we wish to maintain hidden, and the observable consequences of these facts. Example of such protocols are anonymity protocols like Crowds [START_REF] Michael | Crowds: anonymity for Web transactions[END_REF], Onion Routing [START_REF] Syverson | Anonymous connections and onion routing[END_REF], and Freenet [START_REF] Clarke | Freenet: A distributed anonymous information storage and retrieval system. In Designing Privacy Enhancing Technologies[END_REF]. Often these protocols use randomization to obfuscate the link between the information that we wish to keep hidden and the observed events. Crowds, for instance, tries to conceal the identity of the originator of a message by forwarding the message randomly until it reaches its destination, so that if an attacker intercepts the message, it cannot be sure whether the sender is the originator or just a forwarder.

In most cases, protocols like the ones above can be regarded as informationtheoretic channels, where the inputs are the facts to keep hidden and the outputs are the observables. In information theory channels are typically noisy, which means that for a given input we may obtain several different outputs, each with a certain probability. A channel is then characterized by what is called transfer matrix, whose elements are the conditional probabilities of obtaining a certain output given a certain input. In our case, the matrix represents the correlation between the facts and the observables. An adversary can try to infer the facts from the observables using the Bayesian method for hypothesis testing, which is based on the principle of assuming an a priori probability distribution on the hidden facts (hypotheses), and deriving from that (and from the matrix) the a posteriori distribution after a certain event has been observed. It is well known that the best strategy is to apply the MAP (Maximum Aposteriori Probability) criterion, which, as the name says, dictates that one should choose the hypothesis with the maximum a posteriori probability given the observation. "Best" means that this strategy induces the smallest probability of guessing the wrong hypothesis. The probability of error, in this case, is also called Bayes risk.

Intuitively, the Bayes risk is maximum when the rows of the channel's matrix are all the same; this case corresponds indeed to capacity 0, which means that the input and the output are independent, i.e. we do not learn anything about the inputs by observing the outputs. This is the ideal situation, from the point of view of information-hiding protocols. In practice, however, it is difficult to achieve such degree of privacy. We are then interested in maximizing the Bayes risk, so to characterize quantitatively the protection offered by the protocol. The interest in finding good bounds for the probability of error is motivated also by the fact that in some case the decision region can have a complicated geometry, or the decision function can be very sensitive to small variations in the input distribution, thus making it difficult to compute the probability of error. Some examples of such situations are illustrated in [START_REF] Santhi | On an improvement over Rényi's equivocation bound[END_REF]. Good bounds based on "easy" functions (i.e. functions easy to compute, and not too sensitive to computational errors) are therefore very useful in such situations as they can be used as an approximation of the probability of error. It is particularly nice to have convex bounds since they bound any estimate based on linear interpolation.

The main purpose of this paper is to investigate the Bayes risk, in relation to the channel's matrix, and to produce tight bounds on it.

There are many bounds known in literature for the Bayes risk. One of these is the equivocation bound, due to Rényi [START_REF] Rényi | On the amount of missing information and the Neyman-Pearson lemma[END_REF], which states that the probability of error is bounded by the conditional entropy of the channel's input given the output. Later, Hellman and Raviv improved this bound by half [START_REF] Hellman | Probability of error, equivocation, and the chernoff bound[END_REF]. Recently, Santhi and Vardy have proposed a new bound, that depends exponentially on the (opposite of the) conditional entropy, and which considerably improves the Hellman-Raviv bound in the case of multi-hypothesis testing [START_REF] Santhi | On an improvement over Rényi's equivocation bound[END_REF]. The latter is better, however, in the case of binary hypothesis testing.

The Bayes approach to hypothesis testing is often criticized because it assumes the knowledge of the a priori distribution, or at least of a good approximation of it, which is often an unjustified assumption. However, even if the adversary does not know the a priori distribution, the method is still valid asymptotically, under the condition that the matrix's rows are all pairwise distinguished. Under such condition indeed, as shown in [START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF], by repeating the experiment the contribution of the a priori probability becomes less and less relevant for the computation of the Bayesian risk, and it "washes out" in the limit. Furthermore, the Bayesian risk converges to 0. At the other extreme, when the rows are all equal, the Bayes risk does not converge to 0 and its limit is bound from below by a constant that depends on the input distribution. In the present paper we continue this investigation by considering what happens in the intermediate case when some of the rows (not necessarily all) are equal.

Contribution

The main contributions of this paper are the following:

1. We consider what we call "the corner points" of a piecewise linear function, and we propose criteria to compute the maximum of the function, and to identify concave functions that are upper bounds for the given piecewise linear function, based on the analysis of its corner points only.

2. We consider the hypothesis testing problem in relation to an informationtheoretic channel. In this context, we show that the probability of error associated to the MAP rule is piecewise linear, and we give a constructive characterization of a set of corner points, which turns out to be finite.

Together with the results of the previous paragraph, this leads to algorithms to compute the maximum Bayes risk over all the channel's input distributions, and to a method to improve functional upper bounds of the error probability. The improved functions are tight at at least one point.

3. By using the above results about concave functions and corner points, we give an alternative proof of the Hellman-Raviv and the Santhi-Vardy bounds on the Bayes risk in terms of conditional entropy. Our proof is intuitive and works exactly in the same way for both bounds, which were proven using different techniques in the corresponding papers.

4. Thanks to our characterization of the maximum Bayes risk, we are able to improve on the Hellman-Raviv and the Santhi-Vardy bounds. These two bounds are tight (i.e. coincide with the Bayes risk) on the corner points only for channels of capacity 0. Our improved bounds are tight at at least one corner point for every channel.

5. We consider the case of protocol re-execution, and we show that in the intermediate case in which at least two rows are equal the Bayes risk does not converge to 0. Furthermore we give a precise lower bound for the limit of the Bayes risk.

6. We show how to apply the above results to randomized protocols for information hiding. In particular, we present an analysis of Crowds using two different network topologies, and derive the maximum Bayes risk for an adversary who tries to break anonymity, and improved bounds on this probability in terms of conditional entropy, for any input distribution.

Related work

Probabilistic notions of anonymity and information-hiding have been explored in [START_REF] Chaum | The dining cryptographers problem: Unconditional sender and recipient untraceability[END_REF][START_REF] Halpern | Anonymity and information hiding in multiagent systems[END_REF][START_REF] Bhargava | Probabilistic anonymity[END_REF][START_REF] Chatzikokolakis | Probable innocence revisited[END_REF]. We discuss the relation with these works in detail in Section 5.

Several authors have considered the idea of using information theory to analyze anonymity. A recent line of work is due to [START_REF] Serjantov | Towards an information theoretic metric for anonymity[END_REF][START_REF] Díaz | Towards measuring anonymity[END_REF]. The main difference with our approach is that in these works the anonymity degree is expressed in terms of input entropy, rather than conditional entropy. More precisely, the emphasis is on the lack of information of the attacker about the distribution of the inputs, rather than on the capability of the protocol to prevent the attacker from determining this information from a statistical analysis of the observables which are visible to the attacker. Moreover, a uniform input distribution is assumed, while in this paper we abstract from the input distribution.

In [START_REF] Moskowitz | Covert channels and anonymizing networks[END_REF][START_REF] Moskowitz | Quasianonymous channels[END_REF] the ability to have covert communication as a result of non-perfect anonymity is explored. These papers focus on the possibility of constructing covert channels by the users of the protocol, using the protocol mechanisms, and on measuring the amount of information that can be transferred through these channels. In [START_REF] Moskowitz | Quasianonymous channels[END_REF] the authors also suggest that the channel's capacity can be used as an asymptotic measure of the worst-case information leakage. Note that in [START_REF] Moskowitz | Quasianonymous channels[END_REF] the authors warn that in certain cases the notion of capacity might be too strong a measure to compare systems with, because the holes in the anonymity of a system might not behave like text book discrete memoryless channels.

Another information-theoretical approach is the one of [START_REF] Deng | Measuring anonymity with relative entropy[END_REF]. The authors propose a probabilistic process calculus to describe protocols for ensuring anonymity, and use the Kullback-Leibler distance (aka relative entropy) to measure the degree of anonymity these protocols can guarantee. More precisely, the degree of anonymity is defined as the distance between the distributions on the observable traces produced by the original runs of the protocol, and those produced by the runs after permuting the identities of he users. Furthermore, they prove that the operators in the probabilistic process calculus are non-expansive with respect to the Kullback-Leibler distance.

A different approach, still using the Kullback-Leibler distance, is taken in [START_REF] Michael | Belief in information flow[END_REF]. In this paper, the authors define as information leakage the difference between the a priori accuracy of the guess of the attacker, and the a posteriori one, after the attacker has made his observation. The accuracy of the guess is defined as the Kullback-Leibler distance between the belief (which is a weight attributed by the attacker to each input hypothesis) and the true distribution on the hypotheses.

In the field of information flow and non-interference there is a line of research which is related to ours. There have been various papers [START_REF] Mclean | Security models and information flow[END_REF][START_REF] Gray | Toward a mathematical foundation for information flow security[END_REF][START_REF] Clark | Quantitative analysis of the leakage of confidential data[END_REF][START_REF] Clark | Quantified interference for a while language[END_REF][START_REF] Lowe | Quantifying information flow[END_REF] in which the so-called high information and the low information are seen as the input and output respectively of a channel. The idea is that "high" information is meant to be kept secret and the "low" information is visible; the point is to prevent the high information from being deduced by observing the low information. From an abstract point of view, the setting is very similar; technically it does not matter what kind of information one is trying to conceal, what is relevant for the analysis is only the probabilistic relation between the input and the output information. We believe that our results are applicable also to the field of non-interference.

The connection between the adversary's goal of inferring a secret from the observables, and the field of hypothesis testing, has been explored in other papers in literature, see in particular [START_REF] Ueli | Authentication theory and hypothesis testing[END_REF][START_REF] Di Pierro | Approximate non-interference[END_REF][START_REF] Di Pierro | Measuring the confinement of probabilistic systems[END_REF][START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF]. To our knowledge, however, [START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF] is the only work exploring the Bayes risk in connection to the channel associated to an information-hiding protocol. More precisely, [START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF] considers a framework in which anonymity protocols are interpreted as particular kinds of channels, and the degree of anonymity provided by the protocol as the converse of the channel's capacity (an idea already suggested in [START_REF] Moskowitz | Quasianonymous channels[END_REF]). Then, [START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF] considers a scenario in which the adversary can enforce the re-execution of the protocol with the same input, and studies the Bayes risk on the statistics of the repeated experiment. The question is how the adversary can approximate the MAP rule when the a priori distribution is not known, and the main results of [START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF] on this topic is that the approximation is possible when the rows of the matrix are pairwise different, and impossible when they are all equal (case of capacity 0). Furthermore, in the first case the Bayes risk converges to 0, while in the second case it does not. In the present paper the main focus is on the Bayes risk as a function of the a priori distribution, and on the computation of its bounds. However we also continue the investigation of [START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF] on the protocol re-execution, and we give a lower bound to the limit of the Bayes risk in the intermediate case in which some of the rows (not necessarily all) coincide.

Part of the results of this paper were presented (without proofs) in [START_REF] Chatzikokolakis | Probability of error in information-hiding protocols[END_REF].

Plan of the paper

Next section recalls some basic notions about information theory, hypothesis testing and the probability of error. Section 3 proposes some methods to identify bounds for a function that is generated by a set of corner points; these bounds are tight on at least one corner point. Section 4 presents the main result of our work, namely a constructive characterization of the corner points of Bayes risk.

In Section 5 we discuss the relation with some probabilistic information-hiding notions in literature. Section 6 illustrates an application of our results to the anonymity protocol Crowds. In Section 7 we study the convergence of the Bayes risk in the case of protocol re-execution. Section 8 concludes.

Information theory, hypothesis testing and the probability of error

In this section we briefly review some basic notions in information theory and hypothesis testing that will be used throughout the paper. We refer to [START_REF] Cover | Elements of Information Theory[END_REF] for more details.

A channel is a tuple (A, O, p(•|•)) where A, O are the sets of input and output values respectively and p(o|a) is the conditional probability of observing output o ∈ O when a ∈ A is the input. In this paper, we assume that both A and O are finite with cardinality n and m respectively. We will also sometimes use indices to represent their elements: A = {a 1 , a 2 , . . . , a n } and O = {o 1 , o 2 , . . . , o m }. The p(o|a)'s constitute the transfer matrix (which we will simply call matrix ) of the channel. The usual convention is to arrange the a's by rows and the o's by columns.

In general, we consider the input of a channel as hidden information, and the output as observable information. The set of input values can also be regarded as a set of mutually exclusive (hidden) facts or hypotheses. A probability distribution p(•) over A is called a priori probability, and it induces a probability distribution over O called the marginal probability of O. In fact,

p(o) = a p(a, o) = a p(o|a) p(a)
where p(a, o) represents the joint probability of a and o, and we use its definition p(a, o) = p(o|a)p(a).

When we observe an output o, the probability that the corresponding input has been a certain a is given by the conditional probability p(a|o), also called a posteriori probability of a given o, which in general is different from p(a). This difference can be interpreted as the fact that observing o gives us evidence that changes our degree of belief in the hypothesis a. The a priori and the a posteriori probabilities of a are related by Bayes' theorem:

p(a|o) = p(o|a) p(a) p(o)
In hypothesis testing we try to infer the true hypothesis (i.e. the input fact that really took place) from the observed output. In general, it is not possible to determine the right hypothesis with certainty. We are interested in minimizing the probability of error, i.e. the probability of making the wrong guess. Formally, the probability of error is defined as follows. Given the decision function f : O → A adopted by the observer to infer the hypothesis, let E f : A → 2 O be the function that gives the error region of f when a ∈ A has occurred, namely:

E f (a) = {o ∈ O | f (o) = a} Let η f : A → [0, 1]
be the function that associates to each a ∈ A the probability that f gives the wrong input when a ∈ A has occurred, namely:

η f (a) = o∈E f (a) p(o|a)
The probability of error for f is then obtained as the sum of the probability of error for each possible input, averaged over the probability of the input:

P f = a p(a) η f (a)
In the Bayesian framework, the best possible decision function f B , namely the decision function that minimizes the probability of error, is obtained by applying the MAP (Maximum Aposteriori Probability) criterion, that chooses an input a with a maximum p(a|o). Formally:

f B (o) = a ⇒ ∀a ′ p(a|o) ≥ p(a ′ |o)
The probability of error associated with f B , also called the Bayes risk, is then given by (we will use the notation P e instead than P f B for simplicity)

P e = 1 - o p(o) max a p(a|o) = 1 - o max a p(o|a) p(a)
Note that f B , and the Bayes risk, depend on the inputs' a priori probability. The input distributions can be represented as the elements x = (x 1 , x 2 , . . . , x n ) of the domain D (n) defined as

D (n) = { x ∈ R n | i x i = 1 and ∀i x i ≥ 0}
(also called an (n -1)-simplex) where the correspondence is given by x i = p(a i ) for all i's. In the rest of the paper we will take the MAP rule as decision function and view the Bayes risk as a function P e : D (n) → [0, 1] defined by

P e ( x) = 1 - i max j p(o i |a j )x j (1)
We will identify probability distributions and their vector representation freely throughout the paper. There are some notable results in literature relating the Bayes risk to the information-theoretic notion of conditional entropy, also called equivocation. Let us first recall the concept of random variable and its entropy. A random variable A is determined by a set of values A and a probability distribution p(•) over A. The entropy of A, H(A), is given by

H(A) = - a p(a) log p(a)
The entropy measures the uncertainty of a random variable. It takes its maximum value log n when A's distribution is uniform and its minimum value 0 when A is constant. We usually consider the logarithm in base 2 and thus measure entropy in bits.

I(A; O) = H(A) -H(A|O)
Mutual information measures the amount of information that one random variable contains about another random variable. In other words, it measures the amount of uncertainty about A that we lose when observing O. It can be shown that it is symmetric (I(A; O) = I(O; A)) and that 0 ≤ I(A; O) ≤ H(A). The maximum mutual information between A and O over all possible input distributions p(•) is known as the channel's capacity:

C = max p(•) I(A; O)
The capacity of a channel gives the maximum rate at which information can be transmitted using this channel without distortion.

Given a channel, let x be the a priori distribution on the inputs. Recall that x also determines a probability distribution on the outputs. Let A and O be the random variables associated to the inputs and outputs respectively. The Bayes risk is related to H(A|O) by the Hellman-Raviv bound [START_REF] Hellman | Probability of error, equivocation, and the chernoff bound[END_REF]:

P e ( x) ≤ 1 2 H(A|O) (2)
and by the Santhi-Vardy bound [START_REF] Santhi | On an improvement over Rényi's equivocation bound[END_REF]:

P e ( x) ≤ 1 -2 -H(A|O) (3)
We remark that, while the bound (2) is tighter than (3) in case of binary hypothesis testing, i.e. when n = 2, (3) gives a much better bound when n becomes larger. In particular the bound in (3) is always limited by 1, which is not the case for (2).

Convexly generated functions and their bounds

In this section we characterize a special class of functions on probability distributions, and we present various results regarding their bounds which lead to methods to compute their maximum, to prove that a concave function is an upper bound, and to derive an upper bound from a concave function. The interest of this study is that the probability of error will turn out to be a function in this class. We start by recalling some basic notions of convexity: let R be the set of real numbers. The elements λ 1 , λ 2 , . . . , λ k ∈ R constitute a set of convex coefficients iff ∀i λ i ≥ 0 and i λ i = 1. Given a vector space V , a convex combination of x 1 , x 2 , . . . , x k ∈ V is any vector of the form i λ i x i where the λ i 's are convex coefficients. A subset S of V is convex if and only if every convex combination of vectors in S is also in S. It is easy to see that for any n the domain D (n) of probability distributions of dimension n is convex. Given a subset S of V , the convex hull of S, which we will denote by ch(S), is the smallest convex set containing S. Since the intersection of convex sets is convex, it is clear that ch(S) always exists.

We now introduce (with a slight abuse of terminology) the concept of convex base: Intuitively, a convex base of a set S is a subset of S whose convex hull contains S. Definition 3.1. Given the vector sets S, U , we say that U is a convex base for S if and only if U ⊆ S and S ⊆ ch(U ).

In the following, given a vector x = (x 1 , x 2 , . . . , x n ), and a function f from n-dimensional vectors to reals, we will use the notation ( x, f ( x)) to denote the (n + 1)-dimensional vector (x 1 , x 2 , . . . , x n , f ( x)). Similarly, given a vector set S in a n-dimensional space, we will use the notation (S, f (S)) to represent the set of vectors {( x, f ( x)) | x ∈ S} in a (n + 1)-dimensional space. The notation f (S) represents the image of S under f , i.e. f (S) = {f ( x) | x ∈ S}.

We are now ready to introduce the class of functions that we mentioned at the beginning of this section: Definition 3.2. Given a vector set S, a convex base U of S, and a function f : S → R, we say that (U, f (U )) is a set of corner points of f if and only if (U, f (U )) is a convex base for (S, f (S)). We also say that f is convexly generated by (U, f (U )).

Of particular interest are the functions that are convexly generated by a finite number of corner points. This is true for piecewise linear functions in which S can be decomposed into finitely many convex polytopes (n-dimensional polygons) and f is equal to a linear function on each of them. Such functions are convexly generated by the finite set of vertices of these polytopes.

We now give a criterion for computing the maximum of a convexly generated function.

Proposition 3.3. Let U be a convex base of S and let f : S → R be convexly generated by (U, f (U )). If f (U ) has a maximum element b, then b is the maximum value of f on S.

Proof. Let b be the maximum of f (U ). Then for every u ∈ U we have that f ( u) ≤ b. Consider now a vector x ∈ S. Since f is convexly generated by

(U, f (U )), there exist u 1 , u 2 , . . . , u k in U such that f ( x) is obtained by convex combination from f ( u 1 ), f ( u 2 ), . . . , f ( u k ) via some convex coefficients λ 1 , λ 2 , . . . , λ k . Hence: f ( x) = i λ i f ( u i ) ≤ i λ i b since f ( u i ) ≤ b = b λ i 's being convex coefficients
Note that if U is finite then f (U ) always has a maximum element.

Next, we propose a method for establishing functional upper bounds for f , when they are in the form of concave functions.

We recall that, given a vector set S, a function g : S → R is concave if and only if for any x 1 , x 2 , . . . , x k ∈ S and any set of convex coefficients

λ 1 , λ 2 , . . . , λ k ∈ R we have i λ i g( x i ) ≤ g( i λ i x i ) Proposition 3.4.
Let U be a convex base of S, let f : S → R be convexly generated by (U, f (U )), and let g : S → R be concave. Assume that for all u ∈ U f ( u) ≤ g( u) holds. Then we have that g is an upper bound for f , i.e.

∀ x ∈ S f ( x) ≤ g( x)
Proof. Let x be an element of S. Since f is convexly generated, there exist

u 1 , u 2 , . . . , u k in U such that ( x, f ( x)) is obtained by convex combination from ( u 1 , f ( u 1 )), ( u 2 , f ( u 2 )), . . . , ( u k , f ( u k )) via some convex coefficients λ 1 , λ 2 , . . . , λ k . Hence: f ( x) = i λ i f ( u i ) ≤ i λ i g( u i ) since f ( u i ) ≤ g( u i ) ≤ g( i λ i u i ) by the concavity of g = g( x)
We also give a method to obtain functional upper bounds, that are tight on at least one corner point, from concave functions. Proposition 3.5. Let U be a convex base of S, let f : S → R be convexly generated by (U, f (U )), and let g : S → R be concave and non-negative. Let

R = {c | ∃ u ∈ U : f ( u) ≥ c g( u)}. If R has an upper bound c o , then the function c o g is a functional upper bound for f satisfying ∀ x ∈ S f ( x) ≤ c o g( x)
Furthermore, if c o ∈ R then f and c o g coincide at least at one point.

Proof. We first show that f ( u) ≤ c o g( u) for all u ∈ U . Suppose, by contradiction, that this is not the case. Then there exists u ∈ U such that f ( u) > c o g( u). If g( u) = 0 then for all c ∈ R : f ( u) > c g( u) = 0 so the set R is not bounded, which is a contradiction. Considering the case g( u) > 0 (g is assumed to be non-negative), let c = f ( u) g( u) . Then c > c o and again we have a contradiction since c ∈ R and c o is an upper bound of R . Hence by Proposition 3.4 we have that c o g is an upper bound for f . Furthermore, if

c o ∈ R then there exists u ∈ U such that f ( u) ≥ c o g( u), so f ( u) = c o g( u)
and the bound is tight as this point.

Corollary 3.6. If U is finite and ∀ u ∈ U : g( u) = 0 ⇒ f ( u) ≤ 0, then the maximum element of R always exists and is equal to max u∈U,g( u)>0 f ( u) g( u)
Finally, we develop a proof technique that will allow us to prove that a certain set is a set of corner points of a function f . Let S be a set of vectors. The extreme points of S, denoted by extr(S), is the set of points of S that cannot be expressed as the convex combination of two distinct elements of S. A subset of R n is called compact if it is closed and bounded. Our proof technique uses the Krein-Milman theorem which relates a compact convex set to its extreme points.

Theorem 3.7 (Krein-Milman). A compact and convex vector set is equal to the convex hull of its extreme points.

We refer to [START_REF] Royden | Real Analysis[END_REF] for the proof. Now since the extreme points of S are enough to generate S, to show that a given set (U, f (U )) is a set of corner points, it suffices to show that it includes all its extreme points. Proposition 3.8. Let S be a compact vector set, U be a convex base of S and f : S → R be a continuous function. Let T = S \ U . If all elements of (T, f (T )) can be written as the convex combination of two distinct elements of (S, f (S)) then (U, f (U )) is a set of corner points of f . Proof. Let S f = (S, f (S)) and U f = (U, f (U )). Since S is compact and continuous maps preserve compactness then S f is also compact, and since the convex hull of a compact set is compact then ch(S f ) is also compact (note that we did not require S to be convex). Then ch(S f ) satisfies the requirements of the Krein-Milman theorem, and since the extreme points of ch(S f ) are clearly the same as those of S f , we have

ch(extr(ch(S f ))) = ch(S f ) ⇒ ch(extr(S f )) = ch(S f ) (4)
Now all points in S f \ U f can be written as convex combinations of other (distinct) points, so they are not extreme. Thus all extreme points are contained in U f , that is extr(S f ) ⊆ U f , and since ch(•) is monotone with respect to set inclusion, we have

ch(extr(S f )) ⊆ ch(U f )
and by ( 4),

S f ⊆ ch(S f ) ⊆ ch(U f ) which means that U f is a set of corner points of f .
The advantage of the above proposition is that it only requires to express points outside U as convex combinations of any other points, not necessarily of points in U (as a direct application of the definition of corner points would require).

An alternative proof for the Hellman-Raviv and Santhi-Vardy bounds

Using Proposition 3.4 we can give an alternative, simpler proof for the bounds in ( 2) and (3). Let f : D (n) → R be the function f ( y) = 1max j y j . We start by identifying a set of corner points of f , using Proposition 3.8 to prove that they are indeed corner points.

Proposition 3.9. The function f defined above is convexly generated by (U, f (U )) with U = U 1 ∪ U 2 ∪ . . . ∪ U n where, for each k, U k is the set of all vectors that have value 1/k in exactly k components, and 0 everywhere else.

Proof. We have to show that for any point x in D (n) \U , ( x, f ( x)) can be written as a convex combination of two points in (D (n) , f (D (n) )). Let w = max i x i . Since x / ∈ U then there is at least one element of x that is neither w nor 0, let x i be that element. Let k the number of elements equal to w. We create two vectors y, z ∈ D (n) as follows

y j =      x i + ǫ if i = j w -ǫ k if x j = w x j otherwise z j =      x i -ǫ if i = j w + ǫ k if x j = w x j otherwise
where ǫ is a small positive number, such that y j , z j ∈ [0, 1] for all j, and such that w-ǫ k , w+ ǫ k are "still" the maximum elements of y, z respectively1 . Clearly

x = 1 2 y + 1 2 z and since f ( x) = 1 -w, f ( y) = 1 -w + ǫ k and f ( y) = 1 -w -ǫ k we have f ( x) = 1 2 f ( y) + 1 2 f ( z).
Since f is continuous and D (n) is compact, the result follows from Proposition 3.8.

Consider now the functions g, h : D (n) → R defined as

g( y) = 1 2 H( y) and h( y) = 1 -2 -H( y)
where (with a slight abuse of notation) H represents the entropy of the distribution y, i.e. H( y) =j y j log y j . From the concavity of H( y) ( [START_REF] Cover | Elements of Information Theory[END_REF]) follows that both g, h are concave. We now compare g, h withf ( y) = 1max j y j on the corner points on f . A corner point u k ∈ U k (defined in Proposition 3.9) has k elements equal to 1/k and the rest equal to 0. So H( u k ) = log k and

f ( u k ) = 1 - 1 k g( u k ) = 1 2 log k h( u) = 1 -2 -log k = 1 - 1 k So f ( u 1 ) = 0 = g( u 1 ), f ( u 2 ) = 1/2 = g( u 2 ), and for k > 2, f ( u k ) < g( u k ). On the other hand, f ( u k ) = h( u k ), for all k.
Thus, both g and h are greater or equal than f on all its corner points, and since they are concave, from Proposition 3.4 we have

∀ y ∈ D (n) f ( y) ≤ g( y) and f ( y) ≤ h( y) (5)
The rest of the proof proceeds as in [START_REF] Hellman | Probability of error, equivocation, and the chernoff bound[END_REF] and [START_REF] Santhi | On an improvement over Rényi's equivocation bound[END_REF]: Let x represent an a priori distribution on A and let the above y denote the a posteriori probabilities on A with respect to a certain observable o, i.e. y j = p(a j |o) = (p(o|a j )/p(o)) x j . Then P e ( x) = o p(o)f ( y), so from (5) we obtain

P e ( x) ≤ o p(o) 1 2 H( y) = 1 2 H(A|O) (6)
and

P e ( x) ≤ o p(o)(1 -2 -H( y) ) ≤ 1 -2 -H(A|O) (7)
where the last step in ( 7) is obtained by observing that 1 -2 x is concave and applying Jensen's inequality. This concludes the alternative proof of ( 2) and (3). We end this section with two remarks. First, we note that g coincides with f only on the points of U 1 and U 2 , whereas h coincides with f on all U . This explains, intuitively, why (3) is a better bound than (2) for dimensions higher than 2.

Second, we observe that, although h is a good bound for f in the sense that they coincide in all corner points of f , 1 -2 -H(A|O) is not necessarily a tight bound for P e ( x). This is due to the averaging of h, f over the outputs to obtain o p(o)(1 -2 -H( y) ) and P e ( x) respectively, and also due to the application of the Jensen's inequality. In fact, we always loosen the bound unless the channel has capacity 0 (maximally noisy channel), as we will see in some examples later. In the general case of non-zero capacity, however, this means that if we want to obtain a better bound we need to follow a different strategy. In particular, we need to find directly the corner points of P e instead than those of the f defined above. This is what we are going to do in the next section.

The corner points of the Bayes risk

In this section we present our main contribution, namely we show that P e is convexly generated by (U, P e (U )) for a finite U , and we give a constructive characterization of U , so that we can apply the results of the previous section to compute tight bounds on P e .

The idea behind the construction of such U is the following: recall that the Bayes risk is given by P e ( x) = 1i max j p(o i |a j )x j . Intuitively, this function is linear as long as, for each i, the j which gives the maximum p(o i |a j )x j remains the same while we vary x. When, for some i and k, the maximum becomes p(o i |a k )x k , the function changes its inclination and then it becomes linear again. The exact point in which the inclination changes is a solution of the equation p(o i |a j )x j = p(o i |a k )x k . This equation actually represents a hyperplane (a space in n -1 dimensions, where n is the cardinality of A) and the inclination of P e changes in all its points for which p(o i |a j )x j is maximum, i.e. it satisfies the inequality p(o i |a j )x j ≥ p(o i |a ℓ )x ℓ for each ℓ. The intersection of n -1 hyperplanes of this kind, and of the one determined by the equation

j x j = 1, is a vertex v such that ( v, P e ( v)
p(o i1 |a j1 )x j1 = p(o i1 |a j2 )x j2 p(o i2 |a j3 )x j3 = p(o i2 |a j4 )x j4 . . . p(o ir |a j2r-1 )x j2r-1 = p(o ir |a j2r )x j2r x j = 0 for j ∈ {j 1 , j 2 , . . . , j 2r } x 1 + x 2 + . . . + x n = 1 p(o i h |a j 2h )x j 2h ≥ p(o i h |a ℓ )x ℓ for 1 ≤ h ≤ r and 1 ≤ ℓ ≤ n
such that all the coefficients p(o i h |a j 2h-1 ), p(o i h |a j 2h ) are strictly positive (1 ≤ h ≤ r), and the equational part has exactly one solution. Here n is the cardinality of A, and r ranges between 0 and n -1.

The variables of the above systems of inequalities are x 1 , . . . , x n . Note that for r = 0 the system consists only of n -1 equations of the form x j = 0, plus the equation

x 1 + x 2 + . . . + x n = 1. A system is called solvable if it has solutions.
By definition, a system of the kind considered in the above definition has at most one solution.

The condition on the uniqueness of solution requires to (attempt to) solve more systems than they are actually solvable. Since the number of systems of equations of the form given in Definition 4.1 increases very fast with n, it is reasonable to raise the question of the effectiveness of our method. Fortunately, we will see that the uniqueness of solution can be characterized by a simpler condition (cf. Proposition 4.7), however still producing a huge number of systems. We will investigate the complexity of our method in Section 4.1.

We are now ready to state our main result:

Theorem 4.2. Given a channel C, the Bayes risk P e associated with C is convexly generated by (U, P e (U )), where U is the set of solutions to all solvable systems in S(C).

Proof. We need to prove that, for every u ∈ D (n) , there exist u 1 , u 2 , . . . , u t ∈ U , and convex coefficients λ 1 , λ 2 , . . . , λ t such that

u = i λ i u i and P e ( u) = i λ i P e ( u i )
Let us consider a particular u ∈ D (n) . In the following, for each i, we will use j i to denote the index j for which p(o i |a j )u j is maximum. Hence, we can rewrite P e ( u) as

P e ( u) = 1 - i p(o i |a ji )u ji (8)
We proceed by induction on n. All conditional probabilities p(o i |a j ) that appear in the proof are assumed to be strictly positive: we do not need to consider the ones which are zero, because we are interested in maximizing the terms of the form p(o i |a j )x j .

Base case (n = 2) In this case U is the set of solutions of all the systems of the form

{p(o i |a 1 )x 1 = p(o i |a 2 )x 2 , x 1 + x 2 = 1} or {x j = 0 , x 1 + x 2 = 1}
and u ∈ D (2) . Let c be the minimum x ≥ 0 such that

p(o i |a 1 )(u 1 -x) = p(o i |a 2 )(u 2 + x) for some i or let c be u 1 if such x does not exist. Analogously, let d be the minimum x ≥ 0 such that p(o i |a 2 )(u 2 -x) = p(o i |a 1 )(u 1 + x) for some i or let d be u 2 if such x does not exist. Note that p(o i |a 2 )(u 2 + c) ≥ 0, hence u 1 -c ≥ 0 and consequently u 2 + c ≤ 1. Analogously, u 2 -d ≥ 0 and u 1 + d ≤ 1. Let us define v, w (the corner points of interest) as v = (u 1 -c, u 2 + c) w = (u 1 + d, u 2 -d)
Consider the convex coefficients

λ = d c + d µ = c c + d A simple calculation shows that u = λ v + µ w It remains to prove that P e ( u) = λP e ( v) + µP e ( w) (9)
To this end, it is sufficient to show that P e is defined in v and w by the same formula as (8), i.e. that P e ( v), P e ( w) and P e ( u) are obtained as values, in v, w and u, respectively, of the same linear function. This amounts to show that the coefficients are the same, i.e. that for each i and k the inequality p(o i |a ji )v ji ≥ p(o i |a k )v k holds, and similarly for w.

Let i and k be given. If j i = 1, and consequently k = 2, we have that

p(o i |a 1 )u 1 ≥ p(o i |a 2 )u 2 holds. Hence for some x ≥ 0 the equality p(o i |a 1 )(u 1 - x) = p(o i |a 2 )(u 2 + x) holds. Therefore: p(o i |a 1 )v 1 = p(o i |a 1 )(u 1 -c) by definition of v ≥ p(o i |a 1 )(u 1 -x) since c ≤ x = p(o i |a 2 )(u 2 + x) by definition of x ≥ p(o i |a 2 )(u 2 + c) since c ≤ x = p(o i |a 1 )v 2 by definition of v
If, on the other hand, j i = 2, and consequently k = 1, we have:

p(o i |a 2 )v 2 = p(o i |a 2 )(u 2 + c) by definition of v ≥ p(o i |a 2 )u 2 since c ≥ 0 ≥ p(o i |a 1 )u 1 since j i = 2 ≥ p(o i |a 1 )(u 1 -c) since c ≥ 0 = p(o i |a 1 )v 1 by definition of v
The proof that for each i and k the inequality p(o i |a ji )w ji ≥ p(o i |a k )w k holds is analogous. Hence we have proved that

P e ( v) = 1 - i p(o i |a ji )v ji and P e ( w) = 1 - i p(o i |a ji )w ji
and a simple calculation shows that (9) holds.

Inductive case Let u ∈ D (n) . Let c be the minimum x ≥ 0 such that for some i and k

p(o i |a ji )(u ji -x) = p(o i |a n )(u n + x) j i = n -1 or p(o i |a ji )(u ji -x) = p(o i |a k )u k j i = n -1 and k = n or p(o i |a ji )u ji = p(o i |a n )(u n + x) j i = n -1
or let c be u n-1 if such x does not exist. Analogously, let d be the minimum x ≥ 0 such that for some i and k

p(o i |a ji )(u ji -x) = p(o i |a n-1 )(u n-1 + x) j i = n or p(o i |a ji )(u ji -x) = p(o i |a k )u k j i = n and k = n -1 or p(o i |a ji )u ji = p(o i |a n-1 )(u n-1 + x) j i = n
or let d be u n if such x does not exist. Similarly to the base case, define v, w as

v = (u 1 , u 2 , . . . , u n-2 , u n-1 -c, u n + c) and w = (u 1 , u 2 , . . . , u n-2 , u n-1 + d, u n -d)
and consider the same convex coefficients

λ = d c + d µ = c c + d Again, we have u = λ v + µ w.
By case analysis, and following the analogous proof given for n = 2, we can prove that for each i and k the inequalities p(o i |a ji )v ji ≥ p(o i |a k )v k and p(o i |a ji )w ji ≥ p(o i |a k )w k hold, hence, following the same lines as in the base case, we derive P e ( u) = λP e ( v) + µP e ( w)

We now prove that v and w can be obtained as convex combinations of corner points of P e in the hyperplanes (instances of D (n-1) ) defined by the equations that give, respectively, the c and d above. More precisely, if c = u n-1 the equation is x n-1 = 0. Otherwise, the equation is of the form

p(o i |a k )x k = p(o i |a ℓ )x ℓ
and analogously for d. We develop the proof for w; the case of v is analogous.

If d = u n , then the hyperplane is defined by the equation x n = 0, and it consists of the set of vectors of the form (x 1 , x 2 , . . . , x n-1 ). The Bayes risk is defined in this hyperplane exactly in the same way as P e (since the contribution of x n is null) and therefore the corner points are the same. By inductive hypothesis, those corner points are given by the solutions to the set of inequalities of the form given in Definition 4.1. To obtain the corner points in D (n) it is sufficient to add the equation x n = 0.

Assume now that d is given by one of the other equations. Let us consider the first one, the cases of the other two are analogous. Let us consider, therefore, the hyperplane H (instance of D (n-1) ) defined by the equation

p(o i |a n )x n = p(o i |a n-1 )x n-1 (10)
It is convenient to perform a transformation of coordinates. Namely, represent the elements of H as vectors y with

y j = x j 1 ≤ j ≤ n -2 x n-1 + x n j = n -1 (11)
Consider the channel

C ′ = A ′ , O, p ′ (•|•)
with A ′ = {a 1 , a 2 , . . . , a n-1 }, and

p ′ (o k |a j ) = p(o k |a j ) 1 ≤ j ≤ n -2 max{p 1 (k), p 2 (k)} j = n -1
where

p 1 (k) = p(o k |a n-1 ) p(o i |a n ) p(o i |a n-1 ) + p(o i |a n ) (p(o i |a n ) and p(o i |a n-1
) are from (10)), and

p 2 (k) = p(o k |a n ) p(o i |a n-1 ) p(o i |a n-1 ) + p(o i |a n )
The Bayes risk in H is defined by

P e ( y) = k max 1≤j≤n-1 p ′ (o k |a j )y j
and a simple calculation shows that P e ( y) = P e ( x) whenever x satisfies (10) and y and x are related by [START_REF] Deng | Measuring anonymity with relative entropy[END_REF]. Hence the corner points of P e ( x) over H can be obtained from those of P e ( y).

The systems in S(C) are obtained from those in S(C ′ ) in the following way. For each system in S(C ′ ), replace the equation y 1 +y 2 +. . .+y n-1 = 1 by x 1 +x 2 + . . . + x n-1 + x n = 1, and replace, in each equation, every occurrence of y j by x j , for j from 1 to n -2. Furthermore, if y n-1 occurs in an equation E of the form y n-1 = 0, then replace E by the equations x n-1 = 0 and x n = 0. Otherwise, it must be the case that for some k 1 , k 2 , p ′ (o k1 |a n-1 )y n-1 and p ′ (o k2 |a n-1 )y n-1 occur in two of the other equations. In that case, replace p ′ (o k1 |a n-1 )y n-1 by p(o k1 |a n-1 )x n-1 if p 1 (k 1 ) ≥ p 2 (k 1 ), and by p(o k1 |a n )x n otherwise. Analogously for p ′ (o k2 |a n-1 )y n-1 . Finally, add the equation p(o i |a n )x n = p(o i |a n-1 )x n-1 . It is easy to see that the uniqueness of solution is preserved by this transformation. The conversions to apply on the inequality part are trivial.

Note that S(C) is finite, hence the U in Theorem 4.2 is finite as well.

An alternative characterization of the corner points

In this section we give an alternative characterization of the corner points of the Bayes risk. The reason is that the new characterization considers only systems of equations that are guaranteed to have a unique solution (for the equational part). As a consequence, we need to solve much less systems than those of Definition 4.1. We characterize these systems in terms of graphs. Definition 4.3. A labeled undirected multigraph is a tuple G = (V, L, E) where V is a set of vertices, L is a set of labels and E ⊆ {({v, u}, l) | v, u ∈ V, l ∈ L} is a set of labeled edges (note that multiple edges are allowed between the same vertices). A graph is connected iff there is a path between any two vertices. A tree is a connected graph without cycles. We say that a tree

T = (V T , L T , E T ) is a tree of G iff V T ⊆ V, L T ⊆ L, E T ⊆ E.
p(o i |a j )x j = p(o i |a k )x k p(o i |a j )x j ≥ p(o i |a l )x l ∀ 1 ≤ l ≤ n
for all edges ({a j , a k }, o i ) ∈ E T , plus the equalities

x j = 0 ∀a j / ∈ V T x 1 + . . . + x n = 1
Let T(C) be the set of systems generated by all trees of G(C).

An advantage of this characterization is that it allows an alternative, simpler proof of Theorem 4.2. The two proofs differ substantially. Indeed, the new one is non-inductive and uses the proof technique of Proposition 3.8. Theorem 4.6. Given a channel C, the Bayes risk P e associated to C is convexly generated by (U, P e (U )), where U is the set of solutions to all solvable systems in T(C). The probability of error can be written as

P e ( x) = 1 - i∈I p(o i |a j( x,i) )x j( x,i) where j( x, i) = min Φ( x, i) (12)
We now fix a point x / ∈ U and we are going to show that there exist y, z ∈ D (n) different than x such that ( x, P e ( x)) = t( y, P e ( y)) + t( z, P e ( z)). Let M ( x) be the indexes of the non-zero elements of x, that is M ( x) = {j ∈ J | x j > 0} (we will simply write M if x is clear from the context. The idea is that we will "slightly" modify some elements in M without affecting any of the sets Φ( x, i). We first define a relation ∼ on the set M as

j ∼ k iff ∃i ∈ Ψ( x) : j, k ∈ Φ( x, i)
and take ≈ as the reflexive and transitive closure of ∼ (≈ is an equivalence relation). Now assume that ≈ has only one equivalence class, equal to M . Then we can create a tree T as follows: we start from a single vertex a j , j ∈ M . At each step, we find a vertex a j in the current tree such that j ∼ k for some k ∈ M where a k is not yet in the tree (such a vertex always exist since M is an equivalence class of ≈). Then we add a vertex a k and an edge ({a j , a k }, o i ) where i is the one from the definition of ∼. Note that since i ∈ Ψ( x) we have that p(o i |a j ), p(o i |a k ) are positive so this edge also belongs to G(C). Repeating this procedure creates a tree of G(C) such that x is a solution to its corresponding system of inequalities, which is a contradiction since x / ∈ U . So we conclude that ≈ has at least two equivalence classes, say C, D. The idea is that we will add/subtract an ǫ from all elements of the class simultaneously, while preserving the relative ratio of the elements. We choose an ǫ > 0 small enough such that 0 < x jǫ and x j + ǫ < 1 for all j ∈ M and such that subtracting it from any element does not affect the relative order of the quantities p(o i |a j )x j , that is

p(o i |a j )x j > p(o i |a k )x k ⇒ p(o i |a j )(x j -ǫ) > p(o i |a k )(x k + ǫ) (13)
for all i ∈ I, j, k ∈ M . 2 Then we create two points y, z ∈ D (n) as follows:

y j =      x j -x j ǫ 1 if j ∈ C x j + x j ǫ 2 if j ∈ D x j otherwise z j =      x j + x j ǫ 1 if j ∈ C x j -x j ǫ 2 if j ∈ D x j otherwise
where ǫ 1 = ǫ/ j∈C x j and ǫ 2 = ǫ/ j∈D x j (note that x j ǫ 1 , x j ǫ 2 ≤ ǫ) . It is easy to see that x = 1 2 y + 1 2 z, it remains to show that P e ( x) = 1 2 P e ( y) + 1 2 P e ( z). We notice that M ( x) = M ( y) = M ( z) and Ψ( x) = Ψ( y) = Ψ( z) since x j > 0 iff y j > 0, z j > 0. We now compare Φ( x, i) and Φ( y, i).

If i / ∈ Ψ( x) then p(o i |a k ) = 0, ∀k ∈ M so Φ( x, i) = Φ( y, i) = J. Assuming i ∈ Ψ( x), we first show that p(o i |a j )x j > p(o i |a k )x k implies p(o i |a j )y j > p(o i |a k )y k . This follows from (13) since p(o i |a j )y j ≥ p(o i |a j )(x j -ǫ) > p(o i |a k )(x k + ǫ) ≥ p(o i |a k )y k This means that k / ∈ Φ( x, i) ⇒ k / ∈ Φ( y, i), in other words Φ( x, i) ⊇ Φ( y, i) (14)
Now we show that k ∈ Φ( x, i) ⇒ k ∈ Φ( y, i). Assume k ∈ Φ( x, i) and let j ∈ Φ( y, i) (note that Φ( y, i) = ∅). By ( 14) we have j ∈ Φ( x, i) which means that p(o i |a k )x k = p(o i |a j )x j . Moreover, since i ∈ Ψ( x) we have that j, k belong to the same equivalence class of ≈.

If j, k ∈ C then p(o i |a k )y k = p(o i |a k )(x k -x k ǫ 1 ) = p(o i |a j )(x j -x j ǫ 1 ) p(o i |a k )x k = p(o i |a j )x j = p(o i |a j )y j which means that k ∈ Φ( y, i). Similarly for j, k ∈ D. If j, k / ∈ C ∪ D then x k = y k , x j = y j
and the same result is immediate. So we have Φ( x, i) = Φ( y, i), ∀i ∈ I. And symmetrically we can show that Φ( x, i) = Φ( z, i). This implies that j( x, i) = j( y, i) = j( z, i) (see [START_REF] Díaz | Towards measuring anonymity[END_REF]) so we finally have

1 2 P e ( y) + 1 2 P e ( z) = 1 2 1 - i∈I p(o i |a j( y,i) )y j( y,i) + 1 - i∈I p(o i |a j( z,i) )z j( z,i) = 1 - i∈I p(o i |a j( x,i) )( 1 2 y j( x,i) + 1 2 z j( x,i) ) = P e ( x)
Applying Proposition 3.8 completes the proof.

We now show that both characterizations give the same systems of equations, that is S(C) = T(C). Proposition 4.7. Consider a system of inequalities of the form given in Definition 4.1. Then, the equational part has a unique solution if and only if the system is generated by a tree of G(C).

Proof. if ) Assume that the system is generated by a tree of G(C). Consider the variable corresponding to the root, say x 1 . Express its children x 2 , . . . , x k in terms of x 1 . That is to say that, if the equation is ax 1 = bx 2 , then we express x 2 as a/bx 1 . At the next step, we express the children of x 2 in terms of x 2 an hence in terms of x 1 , . . . etc. Finally, we replace all x ′ i s by their expressions in terms of x 1 in the equation i x i = 1. This has exactly one solution.

only if ) Assume by contradiction that the system is not generated by a tree.

Then we we can divide the variables in at least two equivalence classes with respect to the equivalence relation ≈ defined in the proof of Theorem 4.6, and we can define the same y defined a few paragraphs later. This y is a different solution of the same system (also for the inequalities).

The advantage of Definition 4.5 is that it constructs directly solvable systems, in contrast to Definition 4.1 which would oblige us to solve all systems of the given form and keep only the solvable ones. We finally give the complexity of computing the corner points of P e using the tree characterization, which involves counting the number of trees of G(C). Proof. To compute the set of corner points of P e we need to solve all the systems of inequalities in T(C). Each of those is produced by a tree of G(C). In the worst case, the matrix of the channel is non-zero everywhere, in which case G(C) is the complete multigraph K m n of n vertices, each pair of which is connected by exactly m edges. Let K 1 n be the complete graph of n vertices (without multiple edges). Cayley's formula ([?]) gives its number σ(K 1 n ) of spanning trees:

σ(K 1 n ) = n n-2 (15)
We now want to compute the total number τ (K 1 n ) of trees of K 1 n . To create a tree of k vertices, we have n k ways to select k out of the n vertices of K 1 n and σ(K 1 k ) ways to form a tree with them. Thus

τ (K 1 n ) = n k=1 n k σ(K 1 k ) = n k=1 n! k!(n -k)! k k-2 (15) = n k=1 1 (n -k)! (k + 1) • . . . • n • k k-2 ≤ n k=1 1 (n -k)! n n-k • n k-2 k + i ≤ n = n n-2 n-1 l=0 1 l! set l = n -k ≤ e • n n-2 since ∞ l=0 1 l! = e thus τ (K 1 n ) ∈ O(n n-2
). Each tree of K m n can be produced by a tree of K 1 n by exchanging the edge between two vertices with any of the m available edges in K m n . Since a tree of K m n has at most n -1 edges, for each tree of K 1 n we can produce at most m n-1 trees of K m n . Thus

τ (K m n ) ≤ m n-1 τ (K 1 n ) ∈ O(m n-1 n n-2 )
Finally, for each tree we have to solve the corresponding system of inequalities.

Due to the form of this system, computing the solution can be done in O(n) time by expressing all variables x i in terms of the root of the tree, and then replace them in the equation i x i = 1. On the other hand, for each solution we have to verify as many as n(n -1) inequalities, so in total the solution can be found in O(n 2 ) time. Thus, computing all corner points takes O(n 2 m n-1 n n-2 ) = O(n(nm) n-1 ) time.

Note that, to improve a bound using Proposition 3.5, we need to compute the maximum ratio f ( u)/g( u) of all corner points u. Thus, we need only to compute these points, not to store them. Still, as shown in the above proposition, the number of the systems we need to solve in the general case is huge. However, as we will see in Section 6.1, in certain cases of symmetric channel matrices the complexity can be severely reduced to even polynomial time.

Examples

Example 4.9 (Binary hypothesis testing). The case n = 2 is particularly simple: the systems generated by C are all those of the form

{p(o i |a 1 )x 1 = p(o i |a 2 )x 2 , x 1 + x 2 = 1}
plus the two systems

{x 1 = 0 , x 1 + x 2 = 1} {x 2 = 0 , x 1 + x 2 = 1}
These systems are always solvable, hence we have m + 2 corner points, where we recall that m is the cardinality of O.

Let us illustrate this case with a concrete example: let C be the channel determined by the following matrix: The systems generated by C are:

o 1 o 2 o 3 a 1 1/2 1/3 1/6 a 2 1
{x 1 = 0 , x 1 + x 2 = 1} { 1 2 x 1 = 1 6 x 2 , x 1 + x 2 = 1} { 1 3 x 1 = 1 2 x 2 , x 1 + x 2 = 1} { 1 6 x 1 = 1 3 x 2 , x 1 + x 2 = 1} {x 1 = 0 , x 1 + x 2 = 1}
The solutions of these systems are: (0, 1), (1/4, 3/4), (3/5, 2/5), (2/3, 1/3), and (1, 0), respectively. The value of P e on these points is 0, 1/4, 3/10 (maximum), 1/3, and 0 respectively, and P e is piecewise linear between these points, i.e. it can be generated by convex combination of these points and its value on them. Its graph is illustrated in Figure 1, where x 1 is represented by x and x 2 by 1x. The following is an example of a solvable system generated by C:

2 3 x 1 = 1 8 x 2 1 8 x 2 = 4 5 x 3 x 1 + x 2 + x 3 = 1 2 3 x 1 ≥ 1 10 x 3 1 8 x 2 ≥ 1 6 x 1
Another example is

1 6 x 1 = 3 4 x 2 x 3 = 0 x 1 + x 2 + x 3 = 1
The graph of P e is depicted in Figure 2, where x 3 is represented by 1-x 1 -x 2 .

Maximum Bayes risk and relation with strong anonymity

In this section we discuss the Bayes risk in the extreme cases of maximum and minimum (i.e. 0) capacity, and, in the second case, we illustrate the relation with the notion of probabilistic strong anonymity existing in literature.

Maximum capacity

If the channel has no noise, which means that for each observable o there exists at most one a such that p(o|a) = 0, then the Bayes risk is 0 for every input distribution. In fact

P e ( x) = 1 -o max j p(o|a j )x j = 1 -j o p(o|a j )x j = 1 -j x j = 0

Capacity 0

The case in which the capacity of the channel is 0 is by definition obtained when I(A; O) = 0 for all possible input distributions of A. From information theory we know that this is the case iff A and O are independent (cf. [10, p.27]). Hence we have the following characterization: The condition p(o|a) = p(o|a ′ ) for all o, a, a ′ has been called strong probabilistic anonymity in [START_REF] Bhargava | Probabilistic anonymity[END_REF] and it is equivalent to the condition p(a|o) = p(a) for all o, a. The latter was considered as a definition of anonymity in [START_REF] Chaum | The dining cryptographers problem: Unconditional sender and recipient untraceability[END_REF] and it is called conditional anonymity in [START_REF] Halpern | Anonymity and information hiding in multiagent systems[END_REF].

Capacity 0 is the optimal case also with respect to the incapability of the adversary of inferring the hidden information. In fact, the Bayes risk achieves its highest possible value, for a given n (cardinality of A), when the rows of the matrix are all the same and the distribution is uniform. To prove this, let x ∈ D (n) and let x k be the maximum component of x. We have

P e ( x) = 1 -o max j p(o|a j )x j ≤ 1 -o p(o|a k )x k = 1 -x k o p(o|a k ) = 1 -x k
Now, the minimum possible value for x k is 1/n, which happens in the case of uniform input distribution. We have therefore

P e ( x) ≤ 1 - 1 n = n -1 n
namely, n -1/n is an upper bound of the probability of error. It remains to show that it is a maximum and that it is obtained when the rows are all the same (p(o|a j ) = p(o|a) for all o and j, and some a) and the input distribution is uniform. This is indeed the case, as proven by the following:

P e ( 1 n , 1 n , . . . , 1 n ) = 1 -o max j p(o|a j ) 1 n = 1 -o p(o|a) 1 n = 1 -1 n o p(o|a) = n-1 n
An example of protocol with capacity 0 is the dining cryptographers in a connected graph [START_REF] Chaum | The dining cryptographers problem: Unconditional sender and recipient untraceability[END_REF], under the assumption that the payer is always one of the cryptographers, and that the coins are fair.

Application: Crowds

In this section we show how to apply the results of the previous sections to the analysis of a security protocol, in order to obtain improved bounds on the attacker's probability of error. This involves modeling the protocol, computing its channel matrix either analytically or using model-checking tools, and using it to compute the corner points of the probability of error. We illustrate our ideas on Crowds, a well-known anonymity protocol from the literature.

In this protocol, introduced by Reiter and Rubin in [START_REF] Michael | Crowds: anonymity for Web transactions[END_REF], a user (called the initiator ) wants to send a message to a web server without revealing its identity. To achieve that, he routes the message through a crowd of users participating in the protocol. The routing is performed in the following way: in the beginning, the initiator randomly selects a user (called a forwarder ), possibly himself, and forwards the request to him. A forwarder, upon receiving a message, performs a probabilistic choice. With probability p f (a parameter of the protocol) he selects a new user and forwards once again the message. With probability 1p f he sends the message directly to the server.

It is easy to see that the initiator is strongly anonymous with respect to the server, as all users have the same probability of being the forwarder who finally delivers the message. However, the more interesting case is when the attacker is one of the users of the protocol (called a corrupted user) which uses his information to find out the identity of the initiator. A corrupted user has more information than the server since he sees other users forwarding the message through him. The initiator, being the first in the path, has greater probability of forwarding the message to the attacker than any other user, so strong anonymity cannot hold. However, under certain conditions on the number of corrupted users, Crowds can be shown to satisfy a weaker notion of anonymity called probable innocence.

In our analysis, we consider two network topologies. In the first, used in the original presentation of Crowds, all users are assumed to be able to communicate with any other user, in other words the network graph is a clique. In this case, the channel matrix is symmetric and easy to compute. Moreover, due to the symmetry of the matrix, the corner points of the probability of error are fewer in number and have a simple form.

However, having a clique network is not always feasible in practice, as it is the case for example in distributed systems. As the task of computing the matrix becomes much harder in a non-clique network, we employ model-checking tools to perform it automatically. The set of corner points, being finite, can also be computed automatically by solving the corresponding systems of inequalities.

Crowds in a clique network

We consider an instance of Crowds with m users, of which n are honest and c = mn are corrupted. To construct the matrix of the protocol, we start by identifying the set of anonymous facts, which depends on what the system is trying to hide. In protocols where one user performs an action of interest (like initiating a message in our example) and we want to protect his identity, the set A would be the set of the users of the protocol. Note that the corrupted users should not be included in this set, since we cannot expect the attacker's own actions to be hidden from him. So in our case we have A = {u 1 , . . . u n } where u i means that user i is the initiator.

The set of observables should also be defined, based on the visible actions of the protocol and on the various assumptions made about the attacker. In Crowds we assume that the attacker does not have access to the entire network (such an attacker would be too powerful for this protocol) but only to the messages that pass through a corrupted user. Each time a user i forwards the message to a corrupted user we say that he is detected which corresponds to an observable action in the protocol. Along the lines of other studies of Crowds (e.g. [START_REF] Shmatikov | Probabilistic model checking of an anonymity system[END_REF]) we suppose that an attacker will not forward a message himself, since by doing so he would not gain more information. So at each execution of the protocol there is at most one detected user and we have O = {d 1 , . . . , d n } where d j means that user j was detected. Now we need to compute the probabilities p(d j |u i ) for all 1 ≤ i, j ≤ n. We first observe some symmetries of the protocol. First, the probability of observing the initiator is the same, independently of who is the initiator. We denote this probability by α. Moreover, the probability of detecting a user other than the initiator is the same for all other users. We denote this probability by β. It can be shown ( [START_REF] Michael | Crowds: anonymity for Web transactions[END_REF]) that

α = c 1 -n-1 m p f m -np f β = α - c m
Note that there is also the possibility of not observing any user, if the message arrives to a server without passing through any corrupted user. To compute the matrix, we condition on the event that some user was observed, which is reasonable since otherwise anonymity is not an issue. Thus the conditional probabilities of the matrix are:

p(d j |u i ) = α s if i = j β s
otherwise where s = α + (n -1)β. The matrix for n = 20, c = 5, p f = 0.7 is shown in Figure 3. An advantage of the symmetry is that the corner points of the probability of error for such a matrix have a simple form. Proposition 6.1. Let (A, O, p(•|•)) be a channel. Assume that all values of the matrix p(•|•) are either α or β, with α, β > 0, and that there is at most one α per column. Then all solutions to the systems of Definition 4.5 have at most two distinct non-zero elements, equal to x and α β x for some x ∈ (0, 1]. Proof. Since all values of the matrix are either α or β, the equations of all the systems in Definition 4.5 are of the form x i = x j or α•x i = β•x j . 3 Assume that a solution of such a system has three distinct non-zero elements x 1 > x 2 > x 3 > 0. We consider the following two cases:

1. x 2 , x 3 are related to each other by an equation. Since x 2 > x 3 this equation can only be α • x 2 = β • x 3 , where p(o|a 2 ) = α for some observable o.

Since there is at most one α per column we have p(o|a 1 ) = β and thus p(o|a 1 )x 1 = β x 1 > β x 3 = α x 2 = p(o|a 2 )x 2 which violates the inequalities of Definition 4.5.

2. x 2 , x 3 are not related to each other. Thus they must be related to x 1 by two equations (assuming

α > β) β • x 1 = α • x 2 and β • x 1 = α • x 3 . This implies that x 2 = x 3 which is a contradiction.
Similarly for more than three non-zero elements.

The above proposition allows us to efficiently compute the scaling factor of Proposition 3.5 to improve the Santhi-Vardy bound. Proof. By Proposition 6.1, all corner points of P e have two distinct non-zero elements x and α β x. If we fix the number k 1 of elements equal to x and the number k 2 of elements equal to α β x then x can be uniquely computed in constant time. Due to the symmetry of the matrix, P e as well as the Santhi-Vardy bound will have the same value for all corner points with the same k 1 , k 2 . So it is sufficient to compute the ratio in only one of them. Then by varying k 1 , k 2 , we can compute the best ratio without even computing all the corner points. Note that there are O(n 2 ) possible values of k 1 , k 2 and since we need to compute one point for each of them, the total computation can be performed in O(n 2 ) time.

We can now apply the algorithm described above to compute the scaling factor c o ≤ 1. Multiplying the Santhi-Vardy bound by c o will give us an improved bound for the probability of error. The results are shown in Figure 4. We plot the obtained scaling factor while varying the number of honest users, for c = 5 and for various values of the parameter p f . A lower scaling factor means a bigger improvement with respect to the Santhi-Vardy bound. We remind that we probability of error, in this case, gives the probability that the attacker "guesses" the wrong sender. The higher it is, the more secure is the protocol. It is worth noting that the scaling factor increases when the number of honest users increases or when the probability of forwarding increases. In other words, the improvement is better when the probability of error is smaller (and the system is less anonymous). When increasing the number of users (without increasing the number c of corrupted ones), the protocol offers more anonymity and the capacity increases. In this case the Santhi-Vardy bound becomes closer to the corner points of P e and there is little room for improvement.

Crowds in a grid network

We now consider a grid-shaped network as shown in Figure 5. In this network there is a total of nine users, each of whom can only communicate with the four that are adjacent to him. We assume that the network "wraps" at the edges, so user 1 can communicate with both user 3 and user 7. Also, we assume that the only corrupted user is user 5.

In this example we have relaxed the assumption of a clique network, showing that a model-checking approach can be used to analyze more complicated network topologies (but of course is limited to specific instances). Moreover, the lack of homogeneity in this network creates a situation where the maximum probability of error is given by a non-uniform input distribution. This emphasizes the importance of abstracting from the input distribution: assuming a uniform one would be not justified in this example. Similarly to the previous example, the set of anonymous events will be A = {u 1 , u 2 , u 3 , u 4 , u 6 , u 7 , u 8 , u 9 } where u i means that user i is the initiator. For the observable events we notice that only the users 2, 4, 6 and 8 can communicate with the corrupted user. Thus we have O = {d 2 , d 4 , d 6 , d 8 } where d j means that user j was detected.

To compute the channel's matrix, we have modeled Crowds in the language of the PRISM model-checker ([?]), which is essentially a formalism to describe Markov Decision Processes. PRISM can compute the probability of reaching a specific state starting from a given one. Thus, each conditional probability p(d j |u i ) is computed as the probability of reaching a state where the attacker has detected user j, starting from the state where i is the initiator. Similarly to the previous example, we compute all probabilities conditioned on the fact that some observation was made, which corresponds to normalizing the rows of the matrix. (0.17, 0.17, 0.17, 0.17, 0.08, 0.08, 0.08, 0.08).

Protocol re-execution

In this section we consider the case in which a protocol is executed multiple times with the same input, either forced by the attacker himself or by some external factor. For instance, in Crowds users send messages along randomly selected routes. For various reasons this path might become unavailable, so the user will need to create a new one, thus re-executing the protocol. If the attacker is part of the path, he could also cause it to fail by not forwarding messages, thus obliging the sender to recreate it (unless measures are taken to prevent this, as it is done in Crowds).

From the point of view of hypothesis testing, the above scenario corresponds to repeating the experiment multiple times while the same hypothesis holds through the repetition. We assume that the the outcomes of the repeated experiments are independent. This corresponds to assuming that the protocol is memoryless, i.e. each time it is reactivated, it works according to the same probability distribution, independently from what happened in previous sessions.

The Bayesian approach to hypothesis testing requires the knowledge of the matrix of the protocol and of the a priori distribution of the hypotheses. The first assumption (knowledge of the matrix of the protocol) is usually granted in our setting, because the way the protocol works is public. The second assumption, on the contrary, is not obvious, since the attacker does not usually know the distribution of the information that is supposed to be concealed by the protocol. However it was showed in [START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF] that, under certain conditions, the a priori distribution becomes less and less relevant with the repetition of the experiment, and it "washes out" at the limit. In this section, we recall briefly the results in [START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF] and we extend them by proving a lower bound on the limit of the Bayes risk.

Let (A, O, p(•|•)) be the channel of a protocol S. The experiment obtained by re-executing the protocol n times with the same event a as input will be denoted by S n . The observables in S n are sequences o = (o 1 , . . . , o n ) of observables of S and, since we consider the repetitions to be independent, the conditional probabilities for S n will be given by4

p( o|a) = n i=1 p(o i |a) (16)
Let f n : O n → A be the decision function adopted by the adversary to infer the anonymous action from the sequence of observable. Also let E fn : A → 2 O n be the error region of f n and let η fn : A → [0, 1] be the function that associates to each a ∈ A the probability of inferring the wrong input event on the basis of f n , namely η fn (a) = o∈E fn (a) p( o|a). Then the probability of error of f n will be the expected value of η fn (a):

P fn = a∈A p(a)η fn (a)
The MAP rule and the notion of MAP decision function can be extended to the case of protocol re-execution in the obvious way. Namely a MAP decision function in the context of protocol repetition is a function f n such that for each o ∈ O n and a, a ′ ∈ A

f n ( o) = a ⇒ p( o|a)p(a) ≥ p( o|a ′ )p(a ′ )
Also in the case of protocol repetition the MAP rule gives the best possible result, namely if f n is a MAP decision function then P fn ≤ P hn for any other decision function h n .

The following definition establishes a condition on the matrix under which the knowledge of the input distribution becomes irrelevant for hypothesis testing. (A,O,p(•|•)), we say that the protocol is determinate iff all rows of the matrix p are pairwise different, i.e. the probability distributions p(•|a), p(•|a ′ ) are different for each pair a, a ′ with a = a ′ .

Definition 7.1 ([3]). Given a protocol with channel

Next proposition shows that if a protocol is determinate, then it can be approximated by a decision function which compares only the elements along the column corresponding to the observed event, without considering the input probabilities. The conditional probability p(o|a) (resp. p( o|a)) is called likelihood of a given o (resp. o). The criterion for the definition of g n used in Proposition 7.2 is to choose the a which maximizes the likelihood of o (resp. o), and it is known in literature as the Maximum Likelihood criterion (ML). This rule is quite popular in statistic, its advantage over the Bayesian approach being that it does not require any knowledge of the a priori probability on A.

When the protocol is determinate, the probability of error associated to the ML rule converges to 0, as shown by the following proposition. The same holds, of course, for the MAP rule, because of Proposition 7.2.

Proposition 7.3 ([3]

). Given a determinate protocol (A, O, p(•|•)), for any distribution p A on A and for any ǫ > 0, there exists n such that the property g n ( o) = a ⇒ p( o|a) ≥ p( o|a ′ ) ∀a ′ ∈ A determines a unique decision function g n on a set of probability greater than 1ǫ, and the probability of error P gn is smaller than ǫ.

One extreme case of determinate matrix is when the capacity is maximum. In this case the probability of error of the MAP and ML rules is always 0, independently from n. The proof is analogous to the one of Section 5.1.

Consider now the case in which determinacy does not hold, i.e. when there are at least two identical rows in the matrix, say a 1 and a 2 . In such case, for the sequences o ∈ O n such that p( o|a 1 ) (or equivalently p( o|a 2 )) is maximum, the value of a ML function g n is not uniquely determined, because we could choose either a 1 or a 2 . Hence we have more than one ML decision function.

More generally, if there are k identical rows corresponding to a 1 , a 2 , . . . , a k , the ML criterion gives k different possibilities every time we get an observable o ∈ O n for which p( o|a 1 ) is maximum. Intuitively this is a situation which may induce an error which is difficult to get rid of, even by repeating the protocol many times.

The situation is different if we know the a priori distribution and we use a MAP function f n . In this case we have to maximize p(a)p( o|a) and even in case of identical rows, the a priori knowledge can help to make a sensible guess about the most likely a.

Both in the case of the ML and of the MAP functions, however, we can show that the probability of error is bound from below by an expression that depends on the probabilities of a 1 , a 2 , . . . , a k only. In fact, we can show that this is the case for any decision function, whatever criterion they use to select the hypothesis. Note that the expression (k -1)p(a ℓ ) does not depend on n. Assuming that the a i 's have positive probability, from the above proposition we derive that the probability of error is always greater than a constant strictly greater than 0. Hence the probability of error does not converge to 0. Corollary 7.5. If there exist a 1 , a 2 , . . . , a k with positive probability, k ≥ 2, and whose corresponding rows in the matrix are identical, then for any n and any decision function h n the probability of error is bound from below by a positive constant.

Remark 7.6. In Proposition 7.4 we are allowed to consider any subset of identical rows. In general it is not necessarily the case that a larger subset gives a better bound. In fact, as the subset increases, k increases too, but the minimal p(a i ) may decrease. To find the best bound in general one has to consider all the possible subsets of identical rows.

Capacity 0 is the extreme case of identical rows: it corresponds, in fact, to the situation in which all the rows of the matrix are identical. This is, of course, the optimal case with respect to information-hiding. All the rows are the same, consequently the observations are of no use for the attacker to infer the input event, i.e. to define the "right" g n ( o), since all p( o|a) are maximum.

The probability of error of any decision function is bound from below by (|A| -1) min i p(a i ). Note that by Remark 7.6 we may get better bounds by considering subsets of the rows instead than all of them.

Conclusion and future work

In this paper we have investigated the hypothesis testing problem from the point of view of an adversary playing against an information-hiding protocol, seen as a channel in the information-theoretic sense. We have considered the Bayesian approach to hypothesis testing, and specifically the Maximum Aposteriori Probability (MAP) rule. We have shown that the function P e expressing the probability of error for the MAP rule is piecewise linear, and we have given a constructive characterization of a special set of points which allows computing the maximum P e over all probability distributions on the channel's inputs. This set of points is determined uniquely by the matrix associated to the channel. As a byproduct of this study, we have also improved both the Hellman-Raviv and the Santhi-Vardy bounds.

A common objection to the Bayesian approach to hypothesis testing is that it requires the knowledge of the input distribution (a priori probability). This is a valid criticism in our setting as well, since in general the adversary does not have a priori knowledge of the hidden information. Under certain conditions depending on the protocol's matrix, however, the adversary may be able to infer the input distribution with arbitrary precision by repeatedly observing the outcome of consecutive sessions. Our plans for future work include the investigation of the conditions under which such inference is possible, and the study of the corresponding probability of error as a function of the matrix.

  ) is a corner point of P e . Definition 4.1. Given a channel C = (A, O, p(•|•)), the family S(C) of systems generated by C is the set of all systems of inequalities of the following form:

Definition 4 . 4 .

 44 Let C = (A, O, p(•|•)) be a channel. We define its associated graph G(C) = (V, L, E) as V = A, L = O and ({a, a ′ }, o) ∈ E iff p(o|a), p(o|a ′ ) are both positive. Definition 4.5. Let C = (A, O, p(•|•)) be a channel, let n = |A| and let T = (V T , L T , E T ) be a tree of G(C). The system of inequalities generated by T is defined as

  Proof. Let J = {1, . . . , |A|}, I = {1, . . . , |O|}. We definem( x, i) = max k∈J p(o i |a k )x k Maximum for column i Ψ( x) = {i ∈ I | m( x, i) > 0}Columns with non-zero maximum Φ( x, i) = {j ∈ J | p(o i |a j )x j = m( x, i)} Rows giving the maximum for col. i

Proposition 4 . 8 .

 48 Let C = (A, O, p(•|•)) be a channel and let n = |A|, m = |O|.Computing the set of corner points of P e for C can be performed in O(n(nm) n-1 ) time.

Figure 1 :

 1 Figure1: The graph of the Bayes risk for the channel in Example 4.9 and various bounds for it. Curve 1 represents the probability of error if we ignore the observables, i.e. the function f ( x) = 1max j x j . Curve 2 represents the Bayes risk P e ( x). Curve 3 represents the Hellman-Raviv bound1 2 H(A|O). Curve 4 represents the Santhi-Vardy bound 1 -2 -H(A|O) . Finally, Curves 5 and 6 represent the improvements on 3 and 4, respectively, that we get by applying the method induced by our Proposition 3.5.

Example 4 . 10 (Figure 2 :

 4102 Figure 2: Ternary hypothesis testing. The lower curve represents the Bayes risk for the channel in Example 4.10, while the upper curve represents the Santhi-Vardy bound 1 -2 -H(A|O) .

Proposition 5 . 1 (

 51 [START_REF] Cover | Elements of Information Theory[END_REF]). The capacity of a channel (A, O, p(•|•)) is 0 iff all the rows of the matrix are the same, i.e. p(o|a) = p(o) = p(o|a ′ ) for all o ∈ O and a, a ′ ∈ A.

d 1 d 2 . . . d 20 u 1 0Figure 3 :

 122013 Figure3: The channel matrix of Crowds for n = 20, c = 5, p f = 0.7. The events u i , d j mean that user i is the initiator and user j was detected respectively.

9 Figure 4 :Proposition 6 . 2 .

 9462 Figure 4: The improvement (represented by the scaling factor) with respect to the Santhi-Vardy bound for various instances of Crowds.

Figure 5 :

 5 Figure 5: An instance of Crowds with nine users in a grid network. User 5 is the only corrupted one.

Figure 7 :

 7 Figure 7: The lower curve is the probability of error in the examined instance of Crowds. The upper two are the Santhi and Vardy's bound and its improved version.

Proposition 7 . 2 (

 72 [START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF]). Given a determinate protocol (A, O, p(•|•)), for any distribution on A, any MAP decision functions f n and any decision functiong n : O n → A such that g n ( o) = a ⇒ p( o|a) ≥ p( o|a ′ ) ∀ o ∈ O n ∀a, a ′ ∈ Awe have that g n approximates f n . Namely, for any ǫ > 0, there exists n such that the probability of the set{ o ∈ O n | f n ( o) = g n ( o)} is smaller than ǫ.

Proposition 7 . 4 . 1 -

 741 If the matrix has identical rows corresponding to a 1 , a 2 , . . . , a k then for any n and any decision function h n we have thatP hn ≥ (k -1) min 1≤i≤k {p(a i )}Proof. Assume that p(a ℓ ) = min 1≤i≤k {p(a i )}. We have:P hn = a∈A p(a)η fn (a) ≥ 1≤i≤k p(a i )η fn (a i ) ≥ 1≤i≤k p(a ℓ )η fn (a i ) (p(a ℓ ) = min 1≤i≤k {p(a i )}) ℓ ) (p( o|a i ) = p( o|a ℓ )) = p(a ℓ ) 1≤i≤k hn( o) =ai p( o|a ℓ ) = p(a ℓ ) 1≤i≤k (hn( o)=ai p( o|a ℓ ) )≥ (k -1)p(a ℓ ) ( 1≤i≤k hn( o)=ai p( o|a ℓ ) ≤ 1)

Taking ǫ = min{a, w -b}/2 is sufficient, where a is the minimum positive element of x and b is the maximum element smaller than w.

Let δ i,j,k = p(o i |a j )x j -p(o i |a k )x k . It is sufficient to take ǫ < min({ δ i,j,k p(o i |a j ) + p(o i |a j ) | δ i,j,k > 0} ∪ {x j | j ∈ M })

Note that by construction of G(C) the coefficients of all equations are non-zero, so in our case either α or β.

With a slight abuse of notations we denote by p the probability matrix of both S and S n . It will be clear from the context to which we refer to.

* This work has been partially supported by the INRIA DREI Équipe Associée PRINT-EMPS. The work of Konstantinos Chatzikokolakis and Catuscia Palamidessi has been also supported by the INRIA ARC project ProNoBiS.

d 2 d 4 d 6 d 8 u 1 0.33 0.33 0.17 0.17 u 3 0.33 0.17 0.33 0.17 u 7 0.17 0.33 0.17 0.33 u 9 0.17 0.17 0.33 0.33 u 2 0.68 0.07 0.07 0.17 u 4 0.07 0.68 0.17 0.07 u 6 0.07 0.17 0.68 0.07 u 8 0.17 0.07 0.07 0.68 Figure 6: The channel matrix of the examined instance of Crowds. The symbols u i , d j mean that user i is the initiator and user j was detected respectively.

In Figure 6 the channel matrix is displayed for the examined Crowds instance, computed using probability of forwarding p f = 0.8. We have split the users in two groups, the ones who cannot communicate directly with the corrupted user, and the ones who can. When a user of the first group, say user 1, is the initiator, there is a higher probability of detecting the users that are adjacent to him (users 2 and 4) than the other two (users 6 and 8) since the message needs two steps to arrive to the latters. So p(d 2 |u 1 ) = p(d 4 |u 1 ) = 0.33 are greater than p(d 6 |u 1 ) = p(d 8 |u 1 ) = 0.17. In the second group users have direct communication to the attacker, so when user 2 is the initiator, the probability p(d 2 |u 2 ) of detecting him is high. From the remaining three observables d 8 has higher probability since user 8 can be reached from user 2 in one step, while users 4 and 6 need two steps. Inside each group the rows are symmetric since the users behave similarly. However between the groups the rows are different which is caused by the different connectivity to the corrupted user 5.

We can now compute the probability of error for this instance of Crowds, which is displayed in the lower curve of Figure 7. Since we have eight users, to plot this function we have to map it to the three dimensions. We do this by considering the users 1, 3, 7, 9 to have the same probability x 1 , the users 2, 8 to have the same probability x 2 and the users 4, 6 to have the same probability 1x 1x 2 . Then we plot P e as a function of x 1 , x 2 in the ranges 0 ≤ x 1 ≤ 1/4, 0 ≤ x 2 ≤ 1/2. Note that when x 1 = x 2 = 0 there are still two users [START_REF] Chatzikokolakis | Probability of error in information-hiding protocols[END_REF][START_REF] Clark | Quantitative analysis of the leakage of confidential data[END_REF] among whom the probability is distributed, so P e is not 0. The upper curve of Figure 7 shows the Santhi and Vardy's bound on the probability of error. Since all the rows of the matrix are different the bound is not tight, as illustrated.

We can obtain a better bound by applying Proposition 3.5. The set of corner points, characterized by Theorem 4.2, is finite and can be automatically constructed by solving the corresponding systems of inequalities. After finding the corner points, we compute the scaling factor c o = max u P e ( u)/h( u), where h is the original bound, and take c o • h as the improved bound. In our example we found c o = 0.925 which was given for the corner point u =