Sardaouna Hamadou

Catuscia Palamidessi

Vladimiro Sassone

Quantifying Leakage in the Presence of Unreliable Sources of Information

Keywords: Information hiding, quantitative information flow, belief combination, probabilistic models, uncertainty, accuracy

Belief and min-entropy leakage are two well-known approaches to quantify information flow in security systems. Both concepts stand as alternatives to the traditional approaches founded on Shannon entropy and mutual information, which were shown to provide inadequate security guarantees. In this paper we unify the two concepts in one model so as to cope with the frequent (potentially inaccurate, misleading or outdated) attackers' side information about individuals on social networks, online forums, blogs and other forms of online communication and information sharing. To this end we propose a new metric based on min-entropy that takes into account the adversary's beliefs.

Introduction

Protecting sensitive and confidential data is becoming increasingly important in many fields of human activities, such as electronic communication, auction, payment and voting. Many protocols for protecting confidential information have been proposed in the literature. In recent years the frameworks for reasoning, designing, and verifying these protocols have considered 1 The work of Catuscia Palamidessi was partially supported by the INRIA Large Scale Initiative CAPPRIS (Collaborative Action for the Protection of Privacy Rights in the Information Society).

2 The work of Vladimiro Sassone was partially supported by the project Horizon 2020: SUNFISH probabilistic aspects and techniques for two reasons. First, the data to be protected often range in domains naturally subject to statistical considerations. Second and more important, the protocols often use randomised primitives to obfuscate the link between the information to be protected and the observable outcomes. This is the case, e.g., of the DCNets [1], Crowds [2], 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[END_REF].

From the formal point of view, the degree of protection is the converse of the leakage, i.e. the amount of information about the secrets that can be deduced from the observables. Early approaches to information hiding in literature were the so-called possibilistic approaches, in which the probabilistic aspects were abstracted away and replaced by non-determinism. Some examples of these approaches are those based on epistemic logic [START_REF] Syverson | Group principals and the formalization of anonymity[END_REF][START_REF] Halpern | Anonymity and information hiding in multiagent systems[END_REF], on function views [START_REF] Hughes | Information hiding, anonymity and privacy: a modular approach[END_REF], and on process calculi [START_REF] Schneider | CSP and anonymity[END_REF][START_REF] Ryan | Modelling and Analysis of Security Protocols[END_REF]. Subsequently, however, it has been recognised that the possibilistic view is too coarse, in that it tends to consider as equivalent randomized obfuscation methods that have very di↵erent degrees of protection.

The probabilistic approaches became therefore increasingly more popular. At the beginning they were investigated mainly at their strongest form of protection, namely to express the property that the observables reveal no (quantitative) information about the secrets (strong anonymity, no interference) [1, [START_REF] Halpern | Anonymity and information hiding in multiagent systems[END_REF][START_REF] Bhargava | Probabilistic anonymity[END_REF]. Such strong property, however, is almost never achievable in practice. Hence, weaker notions of protection started to be considered. We mention in particular Rubin and Reiter's concepts of possible innocence and of probable innocence [2] and their variants explored in [START_REF] Chatzikokolakis | Probable innocence revisited[END_REF]. These are, however, still true-or-false properties. The need to express in a quantitative way the degree of protection has then lead naturally to explore suitable notions within the well-established fields of Information Theory and of Statistics.

Concepts from Information Theory [START_REF] Cover | Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)[END_REF] have proved quite useful in this domain. In particular, the notion of noisy channel has been used to model protocols for information-hiding, and the flow of information in programs. The idea is that the input s 2 S of the channel represents the information to be kept secret, and the output o 2 O represents the observable. The noise of the channel is generated by the e↵orts of the protocol to hide the link between the secrets and the observable, usually by means of randomised mechanisms. Consequently, an input s may generate several di↵erent outputs o, according to a conditional probability distribution p(o | s). These probabilities constitute the channel matrix C. Similarly, for each output there may be several di↵erent corresponding inputs, according to the con-verse conditional probability p(s | o) which is linked to the above by the Bayes law: p(s | o) = p(o | s) p(s)/p(o). The probability p(s) is the a priori probability of s, while p(s | o) is the a posteriori probability of s, after we know that the output is o. These probability distributions determine the entropy and the conditional entropy of the input, respectively. They represent the uncertainty about the input, before and after observing the output. The di↵erence between entropy and conditional entropy is called the mutual information and expresses how much information is carried by the channel, i.e. how much uncertainty about the input we lose by observing the output (i.e., equivalently, how much information about the input we gain by observing the output).

Even though several notions of entropy have been proposed in Information Theory, Shannon's is by far the most famous of them, due to its relation with the channel's rate, i.e., the speed by which information can be transmitted accurately on a channel. Consequently, there have been various attempts to define the degree of protection by using concepts based on Shannon entropy, notably mutual information [START_REF] Zhu | Anonymity vs. information leakage in anonymity systems[END_REF][START_REF] Clark | Quantitative information flow, relations and polymorphic types[END_REF][START_REF] Malacaria | Assessing security threats of looping constructs[END_REF][START_REF] Malacaria | Lagrange multipliers and maximum information leakage in di↵erent observational models[END_REF] and the related notion of capacity, which is the supremum of the mutual information over all possible input distributions, and which therefore represents the worst case from the point of view of security [START_REF] Moskowitz | Quasi-anonymous channels[END_REF][START_REF] Moskowitz | Covert channels and anonymizing networks[END_REF][START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF].

A refinement of the above approaches came from the ideas of integrating the notions of extra knowledge and belief [START_REF] Franz | Attacking unlinkability: The importance of context[END_REF][START_REF] Clarkson | Belief in information flow[END_REF][START_REF] Clarkson | Quantifying information flow with beliefs[END_REF]. The idea is that the gain obtained by looking at the output should be relative to the possible initial knowledge or belief that an attacker may have about the secret. For instance, assume that in a parliament composed by m Labourists and n Conservatives, m members voted against a proposal to eliminate the minimum wage. Without any additional knowledge it is reasonable to believe that all Labourists voted against. If however we came to know that exactly one Conservative voted against, then it is more reasonable to believe that the most liberally-inclined Conservative voted against, and the least liberally-inclined Labourist voted in favour. In this case, the a posteriori belief is likely to be much more accurate than the a priori one, and the gain obtained using the knowledge about MPs' relative positioning on the left-to-right scale is much larger than the one computed as di↵erence of entropies. Consequently, [START_REF] Clarkson | Quantifying information flow with beliefs[END_REF] proposed to define the protection of a system in terms of the di↵erence (expressed in terms of Kullback-Leibler divergence) between the accuracy of the a posteriori belief and the accuracy of the a priori one.

Another criticism to the Shannon-entropy-based approach came from Smith, who argued that it is not very suitable to model information leakage in the typical scenario of protocol attacks, where the adversary has only a limited number of tries to guess the value of the secret [START_REF] Smith | Adversaries and information leaks (tutorial)[END_REF]. In such a scenario, the natural measure of the threat is the probability that the adversary guesses the right value. The case of "one-try only" was dubbed by Smith vulnerability of the secret. Shannon entropy, on the other hand, represents the expected number of attempts that an adversary has to make to discover the secret, assuming that there is no limit to such number, and that the adversary can narrow down the value by probing properties of the secret. Smith gave an example of two programs whose Shannon's mutual information is about the same, yet the probability of making the right guess after having observed the output is much higher in one program than in the other. In a subsequent paper [START_REF] Smith | On the foundations of quantitative information flow[END_REF], Smith proposed to define the leakage in terms of a notion of mutual information based on Rényi min-entropy (the logarithm of the vulnerability), which captures the case of an adversary disposing of one single try. Subsequent approaches going under the name of g-leakage have extended the analysis to multiple tries, and to the case in which each guess is associated with a gain (or loss) which depends on the level of approximation [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF][START_REF] Mciver | Abstract channels and their robust information-leakage ordering[END_REF][START_REF] Alvim | Additive and multiplicative notions of leakage, and their capacities[END_REF]. The min-entropy approach remains however the canonical framework, not only for its simplicity, but also because the worst-case min-leakage (aka min-capacity) has been proved to be an upper bound to the g-leakage [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF].

In [START_REF] Hamadou | Probable innocence in the presence of independent knowledge[END_REF] the authors extended the vulnerability model of [START_REF] Smith | On the foundations of quantitative information flow[END_REF] in the context of the Crowds protocol for anonymous message posting to encompass the frequent situation where attackers have extra knowledge. They pointed out that in Crowds the adversary indeed has extra information (viz., the target servers) and assumed that she knows the correlation between that and the secret (viz., the users' preferences for servers). They proved that in such scenarios anonymity is more di cult to achieve.

In our opinion, a fundamental issue remains wide open: the need to measure and account for the accuracy of the adversary's extra knowledge. Indeed, [START_REF] Hamadou | Probable innocence in the presence of independent knowledge[END_REF] assumes that the adversary's extra information is accurate, and such an assumption is generally not warranted. Inaccuracy can indeed arise, e.g. from people giving deliberately wrong information, or simply from outdated data. As already noticed in [START_REF] Clarkson | Quantifying information flow with beliefs[END_REF] there is no reason in general to assume that the probability distributions the attacker uses are correct, and therefore they must be treated as beliefs.

This paper fills this gap by generalising the model on Rényi min-entropy to cope with the presence of the attacker's beliefs. To this end we propose a new metric based on the concept of vulnerability that takes into account the adversary's beliefs. The idea is that the attacker does not know the actual probability distributions (i.e., the a priori distribution of the protocol's hidden input and its correlation with the extra information), and is assuming them. The belief-vulnerability is then the expected probability of guessing the value of the hidden input in one try given the adversary's belief. Informally, the adversary chooses the value of the secret input which has the maximum a posteriori probability according to her belief. Then the vulnerability of the secret input is expressed in terms of the actual a posteriori probabilities of the adversary's possible choices. We show the strength of our definitions both in terms of their theoretical properties and their utility by applying them to various threat scenarios and comparing the results to the previous approaches. Among its several advantages, our model allows to identify the levels of accuracy for the adversary's beliefs which are compatible with the security of a given program or protocol. This paper revises and expends an earlier version [START_REF] Hamadou | Reconciling belief and vulnerability in information flow[END_REF]. First, we have simplified the model of the adversary's belief. Indeed, in the previous model, an attacker's belief consists of a pair: an assumed prior distribution over the set of secret inputs and an external channel leaking some (potentially incorrect) information about these secret inputs to the adversary. In this exposition, we simply model the belief by a subjective probability distribution, which summarises the aggregated information about the secret initially collected by the attacker from di↵erent and potentially conflicting sources of evidence. This approach is more in line with existing models of beliefs in the literature and simplifies significantly the exposition of our results and their comparison to existing work. Our approach is motivated further in §Appendix A. The flexibility of the model is illustrated in §6, where we apply our approach to di↵erent programs under various attack scenarios. We show in particular that a program which performs better than another in one threat scenario might become worse when the threat scenario evolves. Finally, exploiting notions and techniques from Dempster-Shafer Theory [START_REF] Dempster | A generalization of bayesian inference[END_REF][START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], in §Appendix B we propose a new technique to estimate the reliability of an adversary's belief. This allows us to obtain a sound method of updating an arbitrary belief applying the Bayes' rule for updating a hypothesis.

The rest of the paper is organised as follows: in §2 we fix some basic notations and recall some fundamental notions of Information Theory; in §3 we briefly revise previous approaches to quantitative information follow; §4 and §5 deliver our core technical contribution by extending the model on Rényi min entropy to the case of attacker's beliefs and investigating its theoretical properties; in §6 we apply our approach to various threat scenarios and compare it to the previous approaches; in §7 we discuss the related work whilst §8 contains our concluding remarks.

Preliminaries

In this section we briefly revise the elements of Information Theory which underpin the work in this paper, and illustrate our conceptual framework.

Some notions of Information Theory

Being in a purely probabilistic setting gives us the ability to use tools from information theory to reason about the uncertainty of a random variable and the inaccuracy of assuming a distribution for a random variable. In particular we are interested in the following notions: entropy, mutual information, relative entropy and min-entropy. We refer the reader to [START_REF] Massey | Guessing and entropy[END_REF][START_REF] Cover | Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)[END_REF] for more details.

We use capital letters X, Y to denote discrete random variables and the corresponding small letters x, y and calligraphic letters X , Y for their values and set of values respectively. We denote by p(x), p(y) the probability of x and y respectively and by p(x, y) their joint probability.

Let X, Y be random variables. The (Shannon) entropy H(X) of X is defined as

H(X) = X x2X p(x) log p(x). (1)
The entropy measures the uncertainty of a random variable. It takes its maximum value log |X | when X is uniformly distributed and its minimum value 0 when X is a constant. We take the logarithm with a base 2 and thus measure entropy in bits. The conditional entropy

H(X|Y ) = X y2Y p(y) X x2X p(x|y) log p(x|y) (2)
measures the amount of uncertainty of X when Y is known. It can be shown that 0  H(X|Y )  H(X) with the leftmost equality holding when Y completely determines the value of X and the rightmost one when Y reveals no information about X, i.e., X and Y are independent random variables.

Comparing H(X) and H(X|Y ) give us the notion of mutual information, denoted I(X; Y ) and defined by

I(X; Y ) = H(X) H(X|Y ). (3)
It is non-negative, symmetric and bounded by H(X). In other words,

0  I(X; Y ) = I(Y ; X)  H(X).
The relative entropy or Kullback-Leibler distance between two probability distribution p and q on the same set X , denoted D(p k q), is defined as

D(p k q) = X x2X p(x) log p(x) q(x) . (4)
It is non-negative (but not symmetric) and it is 0 if and only if p = q.

The relative entropy measures the inaccuracy or information divergence of assuming that the distribution is q when the true distribution is p.

The guessing entropy G(X) is the expected number of tries required to guess the value of X optimally. The optimal strategy is to guess the values of X in decreasing order of probability. Thus if we assume that X = {x 1 , x 2 , . . . , x n } and x i 's are arranged in decreasing order of probabilities, i.e., p(x

1 ) p(x 2 ) • • • q(x n ), then G(X) = X 1in ip(x i ). (5)
The min-entropy H 1 (X) of a random variable is given by

H 1 (X) = log max x2X p(x) (6)
and measures the di culty for an attacker to correctly guess the value of X in one try (obviously using the optimal strategy above). It can be shown that H 1 (X)  H(X) with equality when X is uniformly distributed. In general, H(X) can be arbitrary higher than H 1 (X), since it can be arbitrary high even if X assumes a given value with probability close to 1.

Framework

In this paper we consider a framework similar to the probabilistic approaches to anonymity and information flow used e.g. in [START_REF] Halpern | Anonymity and information hiding in multiagent systems[END_REF][START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF][START_REF] Malacaria | Lagrange multipliers and maximum information leakage in di↵erent observational models[END_REF], and [START_REF] Smith | On the foundations of quantitative information flow[END_REF]. We restrict ourselves to total protocols and programs with one high level input A, a random variable over a finite set A, and one low level output (observable) O, a random variable over a finite set O. We represent a protocol/program by the matrix of the conditional probabilities p(o j | a i ) that the low output is o j given that the high input is a i . An adversary or eavesdropper can see the output of a protocol, but not its input, and she is interested in deriving the value of the input from the observed output in one single try.

In this paper we shall assume that the high input is generated according to an a priori probabilistic distribution p(a i ) unknown to the adversary, and we also denote by p (a i ) the subjective probability modeling the adversary's initial belief, as explained in the introduction 3 . In other words, p (a i ) is her assumed a priori distribution of A.

Example 1. Let A be a random variable with an unknown (to the adversary) a priori distribution over A = {0, 1, 2, 3}. Suppose that A is the high input of the deterministic program C1 below, whose low output is

O = ⇢ 1 if a 2 {0, 1} 2 otherwise. PROG C1: BEGIN O := b log(A + 2) c END
Now suppose that the adversary, for some reason, initially believes that A is an odd number and that 1 is more likely than 3. For example p (1) = 0.9 and p (3) = 0.1. In the case of wrong belief, i.e., when A is actually an even number, her low observation of PROG C1 does not allow her to realize that her initial belief is wrong. She will not be able to correct it and will therefore pick again the wrong value. Indeed, both observations 1 and 2 are compatible with the odd numbers. However, whereas observing O = 1

p(o | a) o 0 o 1 o 2 a 0 1 0 a 1 1 0 0 a 2 0 1 a 3 1 0 0 Table 1: Conditional probabilistic matrix of PROG C2
would strengthen her belief that A is 1, seeing a low output of 2 might raise some doubts if the adversary does not fully trust the source of her belief, as the unlikely 3 (viz., p (3) = 0.1) has happened. In Section Appendix B we present a novel technique allowing the adversary to estimate the reliability of her initial belief and to discount it accordingly. Now suppose that A is the high input of the probabilistic program C2 below, with low output O 2 { 1, 0, 2} and conditional probabilistic matrix as in Table 1.

PROG C2: BEGIN R 'sampled from {0, 2} with p(0) = and p(2) = 1 '; If A = R Then O := A Else O := 1 END
Contrary to the PROG C1, the low output of PROG C2 may allow the adversary to realize that her initial belief about the parity of A is wrong. For example if she initially believes that A is odd and then she observes that O is either 0 or 2, then she knows that her belief is wrong. But the observation O = 1 does not help her to correct her inaccurate belief, as it can be induced by both even and odd numbers.

Uncertainty vs accuracy

This section reviews the existing definitions for quantifying information leakage. We begin by quantitative approaches to information flow based on Shannon entropy and mutual information, and recall why they fail generally to give good security guarantees. We then present alternative approaches based on the adversary's beliefs initially proposed by Clarkson, Myers and Schneider [START_REF] Clarkson | Quantifying information flow with beliefs[END_REF]. We conclude the section by presenting more recent alternative approaches based on the concept of vulnerability [START_REF] Smith | On the foundations of quantitative information flow[END_REF] and Rényi min-entropy.

Shannon entropy approach

There seems to be a general consensus in the literature for using Shannon entropy to measure uncertainty and mutual information to quantify information leakage [START_REF] Köpf | An information-theoretic model for adaptive sidechannel attacks[END_REF][START_REF] Clark | A static analysis for quantifying information flow in a simple imperative language[END_REF][START_REF] Clark | Quantitative information flow, relations and polymorphic types[END_REF][START_REF] Clark | Quantitative analysis of the leakage of confidential data[END_REF][START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF]. We remind the reader that these approaches aim at quantifying information flow as a reduction of the adversary uncertainty about the high input and take no account of the adversary's initial belief. Shannon entropy H(A) as a measure of the uncertainty of A seems adequate to express the adversary's initial uncertainty about A. Similarly, as the conditional entropy H(A | O) measures the remaining amount of uncertainty of A when O is known, it seems appropriate to express the adversary's remaining uncertainty. We thus have the following definitions.

• initial uncertainty (IU): H(A)

• remaining uncertainty (RU ):

H(A | O) • information leakage (IL): IU RU = H(A) H(A | O) = I(A; O)
Nevertheless, recent work by Smith [START_REF] Smith | On the foundations of quantitative information flow[END_REF] suggests that these notions do not support security guarantees satisfactorily. In particular the remaining uncertainty is generally of little value in characterising the real threat that the adversary could guess the value of A given her low observations. Smith uses the following example to prove that.

Example 2. Consider the following programs C3 and C4, where A is a uniformly distributed 8k-bit integer, k 2, & denotes bitwise 'AND', and 0 7k 1 1 k+1 a binary constant.

PROG C3: PROG C4: BEGIN BEGIN If A mod 8 = 0 O := A & 0 7k 1 1 k+1 Then O := A END Else O := 1 END
PROG C3 reveals completely the high input when A is a multiple of 8 while it reveals nothing about A otherwise (except of course the very fact that it is not a multiple of 8). On the contrary, PROG C4 reveals always and only the last k + 1 bits of A.

According to Shannon entropy-based metrics, we have IU = 8k, RU = 7k 0.169 and IL = k + 0.169 for PROG C3, and IU = 8k, RU = 7k 1 and IL = k + 1 for PROG C4 (the reader is referred to [START_REF] Smith | On the foundations of quantitative information flow[END_REF] for the detailed calculations). So, under such definitions, PROG C4 appears actually worse than PROG C3, as 7k 1 < 7k 0.169, even though intuitively C3 leaves A highly vulnerable to being guessed (e.g., when it is a multiple of 8) while C4 does not, at least for large k.

Belief approach

Clarkson et al. [START_REF] Clarkson | Belief in information flow[END_REF][START_REF] Clarkson | Quantifying information flow with beliefs[END_REF] showed that the Shannon entropy approach is inadequate for measuring information flow when the adversary makes assumptions about the high-level secret and such assumptions might be incorrect. Based on the conviction that it is unavoidable that the attacker makes such (potentially inaccurate) assumptions, they proposed a new metric. They formalised the idea of an adversary's belief as a distribution of A assumed by the adversary: information flow is then expressed as an improvement in the accuracy of such belief. The initial accuracy is the Kullback-Leibler distance between the adversary's initial belief and the actual value of A; similarly the remaining accuracy is the Kullback-Leibler distance between the Bayesianupdated belief of the adversary after her low observation, and the actual value of A.

As already noticed by Smith [START_REF] Smith | On the foundations of quantitative information flow[END_REF], when the adversary's belief coincides with the a priori distribution of A, then the belief approach reduces again to the inadequate standard approach illustrated above.

Vulnerability approach

Having observed that both the consensus and the belief approaches fail in general to give good security guarantees, Smith [START_REF] Smith | On the foundations of quantitative information flow[END_REF] proposes a new metric for quantitative information flow based on the notions of vulnerability and min-entropy. We briefly revise these concepts here.

The vulnerability of a random variable A is the worse-case probability that an adversary could guess the value of A correctly in one try. The vulnerability of A, denoted V (A), is thus formally defined as follows.

Definition 1. V (A) = max a2A p(a).

The conditional vulnerability of a A given O measures the expected probability of guessing A in one try given O. It is denoted V (A | O) and defined as follows.

Definition 2. V (A | O) = P o2O p(o)V (A | o), where V (A | o) is max a2A p(a | o).
The initial uncertainty about A is then defined as the negative logarithm of V (A), which turns out to be the min-entropy of the random variable A -cf. ( 6) above. The remaining uncertainty about A after observing O is defined as the min-entropy of A given O. Thus we have the following vulnerabilitybased definitions:

• IU : H 1 (A) = log V (A) • RU : H 1 (A | O) = log V (A | O) • IL : IU RU = H 1 (A) H 1 (A | O)
Security guarantees of the vulnerability-based approach: by applying these definitions to the programs of Example 2, we have IU = 8k, RU = 8k 3 and IL = 3 for PROG C3, and IU = 8k, RU = 7k 1 and IL = k + 1 for PROG C4. While these quantities remain the same as in the consensus approach for PROG C4, the new metric increases the leakage ascribed to PROG C3 reflecting the fact that the low observations of PROG C3 leave the high input very vulnerable to being guessed.

Unifying Belief and Vulnerability

We now propose an alternative approach based on the vulnerability concept that takes into account the adversary's belief.

Belief-vulnerability

Let A be a random high level variable. The belief-vulnerability of A is the expected probability of guessing A in one try given the adversary's belief. The adversary will choose a value having the maximal probability according to her belief, that is a value a 0 2 , where = argmax a2A p (a). The vulnerability of A is then the real probability that the adversary's choice is correct, that is the probability p(a 0 ). As there might be many values of A in with the maximal probability, the attacker will pick uniformly at random one of them. Hence we have the following definition. Definition 3. Let A be a random variable and = argmax a2A p (a). The belief-vulnerability of A, denoted V (A), is defined as

V (A) = 1 | | X a 0 2 p(a 0 ). ( 7
)
The initial threat is the belief-uncertainty of A (viz. the belief minentropy 4 of A) given by the following definition. Definition 4. Let A be a random variable. The initial threat to A, denoted H 1 (A), is defined as

H 1 (A) = log ⇣ 1 V (A) ⌘ . ( 8
)
Note that from the above definition, the initial uncertainty may be infinite when for all a in , p(a) = 0, modelling the impossibility of a correct guess in one single try when the attacker is choosing a value having zero prior probability. However it might be very di cult to quantify the decrease in uncertainty when initially it is infinite. Therefore we will assume throughout the rest of this paper that initially every value is possible, that is p(x) > 0 for all x in X .

Example 3. Suppose that A is distributed over {0, 1, 2, 3} and the adversary's belief is about the parity of A.

Table 2 summarizes the initial uncertainty about A when the actual a priori distribution and the adversary's prebelief are p 1 and p 2 , and p 1 and p 2 respectively. The pair (p, p ) means that the actual a priori distribution of A is p while the adversary prebelief is p . Thus in (p 1 , p 1 ) the adversary believes that p 1 always uniformly produces an even number while, though it usually produces e↵ectively an even number, with probability 0.02 it also produces an odd number that fools the attacker. However in a one-time guessing attack, this slightly "inaccurate" belief does not a↵ect the vulnerability of A as knowing p 1 , the actual a priori distribution, would not change the attacker choice. In (p 2 , p 1 ), on the contrary, p 2 usually fools the attacker by producing an odd number while the attacker is always expecting an even number. This decreases very much the vulnerability of A as it is almost impossible for the attacker to guess the value of the secret in one try when her initial belief is so wrong. Hence, the increase in her initial uncertainty.

(p 1 , p 1 ) (p 1 , p 2 ) (p 2 , p 1 ) (p 2 , p 2 ) V (A) 0.
Next we show that the lower bound of the belief-uncertainty is obtained with a full knowledge of the actual a priori distribution (viz., a true and justifiable belief).

Theorem 1. H 1 (A)  H 1 (A).
Proof. Let = argmax a2A p (a) be the set of the adversary's possible choices.

V (A) = 1 | | X a2 p(a)  1 | | X a2 max a 0 2A p(a 0 ) ( since ✓ A) Therefore, V (A)  1 | | P a2 V (A) = 1 | | | |V (A) = V (A). Hence H 1 (A) H 1 (A).
The lower bound is reached if and only if all the adversary's possible choices have the actual maximum a priori probability.

Proposition 1. H 1 (A) = H 1 (A) i↵ ✓ argmax a2A p(a).
Proof. The proof in the right direction is similar to the proof of Theorem 1 where the inequality is replaced by the equality. To see why the opposite holds, it is su cient to observe that when there exists an element of that has not the maximum a priori probability then V (A) is less than V (A). Hence the uncertainty is greater than the lower-bound.

In particular when the prebelief coincides with the actual a priori distribution so are the belief min-entropy and the min-entropy.

Corollary 1. If p(a) = p (a) for all a in A, then H 1 (A) = H 1 (A).
In the vulnerability model where the adversary is supposed to know the a priori probability distribution of the high input, the minimum vulnerability, or equivalently the maximum uncertainty, is obtained using a uniform distribution. However in the presence of belief, the uncertainty can be arbitrary high. In fact we have the following upper-bound of the belief min-entropy.

Theorem 2. H 1 (A)  log ⇣ min a2A p(a) ⌘ .
Proof. Similar to the proof of Theorem 1 with max replaced by min and the inequality is reversed.

In particular the belief uncertainty hits the upper-bound when all the adversary's possible choices have the actual minimal prior probability.

Proposition 2. H 1 (A) = log ⇣ min a2A p(a)
⌘ i↵ ✓ argmin a2A p(a). The proof in the right direction is again similar to the proof of Theorem 1 where the inequality is replaced by the equality and max by min. To see why the other implication holds, it is su cient to observe that when there exists an element of that has not the minimum a priori probability then V (A) is greater than min a2A p(a). Hence the uncertainty is less than the upperbound.

We conclude this section by showing two interesting properties of the belief uncertainty. First, we show that beliefs have no e↵ect on the initial uncertainty of A when its actual a priori probability distribution is uniform. In that case, any choice of the attacker results in the same actual vulnerability and she has the same probability 1 |A| of a correct guess. Proposition 3. If A is uniformly distributed then for all initial belief p , we have

H 1 (A) = H 1 (A) = log ⇣ |A| ⌘ .
Proof. Let = argmax a2A p (a).

V (A) = 1 | | X a2 p(a) = 1 | | X a2 1 |A| = 1 | | X a2 V (A) = 1 | | | |V (A) = V (A).
Hence

H 1 (A) = H 1 (A) = log ⇣ |A| ⌘ .
Conversely, for a vacuous belief, the initial belief-uncertainty is independent of the actual a priori distribution of the high input.

Proposition 4. If the prebelief is vacuous then

H 1 (A) = log ⇣ |A| ⌘ .
Proof. If the prebelief is vacuous then its pignistic transformation p (Lemma 4) is the uniform probability distribution. Thus = argmax a2A p (a) = A. Therefore,

V (A) = 1 | | X a2 p(a) = 1 |A| X a2A p(a) = 1 |A| X a2A 1 = 1 |A| Hence H 1 (A) = log ⇣ |A| ⌘ .

A posteriori belief-vulnerability

The belief-vulnerability of A given the evidence O is the expected probability of guessing A in one try given the evidence. Given evidence O = o, the adversary will choose a value having the maximal conditional probability according to her belief, that is a value a 0 2 o , where o = argmax a2A p (a | o). But unlike the a priori belief-vulnerability, here the evidence O could contradict the attacker prebelief. For example assume that the adversary initially believes that the high input value is a 2 , that is p (a 2 ) = 1 then she observes the output o 1 of PROG C5 of which we only give the channel matrix Table 3. The evidence o 1 contradict her prebelief since only a 0 or a 3 could produce o 1 . Hence her prebelief becomes vacuous and cannot be used as an a priori probability to update her belief. To avoid such completely wrong belief, we take the point of view that the adversary initial beliefs satisfy an admissibility restriction (see e.g. [START_REF] Clarkson | Quantifying information flow with beliefs[END_REF][START_REF] Cover | Elements of Information Theory[END_REF]).

In particular, we consider an admissibility restriction we deem ✏-admissible beliefs 5 , where a belief never di↵ers by more that a factor of ✏ from a uniform distribution, that is, p (a)

✏ |A| for all a in A. Note that the evidence o and the adversary prebelief could still be highly conflicting but never fully contradicting each other. Indeed, consider again the program PROG C5 above. If we assume that the adversary prebelief is such that p (a 0 ) = 0.90 and p (a 3 ) = 0.01 then her belief highly supports a 0 . Now observing o 1 would conflict with this belief as the evidence o 1 alone highly supports a 3 rather than a 0 : a 0 would more likely have produced o 0 . In this section, we shall assume that the adversary updates her belief using the Bayes' rule. Thus, the a posteriori belief is

p (a | o) = p(o | a)p (a) p (o) = p(o | a)p (a) P a 0 2A p(o | a 0 )p (a 0 )
which is well defined thanks to the admissibility requirement. Appendix Appendix B introduces an advanced technique that takes into account the level of conflict to estimate the admissibility factor of an arbitrary belief given the evidence (i.e. the observables) induced by the channel. The vulnerability of A given o is then the real probability that the adversary's choice (viz. a value a 0 2 o = argmax a2A p (a | o) is the correct one, that is the objective conditional probability p(a 0 | o). Again, as there might be many values of A with the maximal conditional probability, the attacker will pick uniformly at random one element in o . Hence we have the following definition.

Definition 5. The belief-vulnerability of A given O is defined as

V (A | O) = X o2O p(o)V (A | o), where V (A | o) = 1 | 0 | X a2 o p(a | o).
Next, we show how to compute

V (A | O) from the channel matrix p(o | a)
and the actual a priori probability p(a).

V (A | O) = X o2O p(o)V (A | o) = X o2O p(o) ⇣ 1 | o | X a2 o p(a | o) ⌘ = X o2O 1 | o | X a2 o p(a | o)p(o).
By Bayes theorem, we have

V (A | O) = P o2O 1 | o| P a2 o p(o | a)p

(a)

. Therefore, the a posteriori belief-vulnerability can be easily computed as follows.

Proposition 5. Let o = argmax a2A p (a | o) then V (A | O) = X o2O 1 | o | X a2 o p(o | a)p(a).
We then define the remaining uncertainty as the belief min-entropy of A | O. Definition 6. Let A be a high level input of a channel and O its low output. The remaining threat to A after observing O, denoted H 1 (A | O), is defined as

H 1 (A | O) = log ⇣ 1 V (A | O) ⌘ .
Example 4. Again suppose that A is uniformly distributed over {0, 1, 2, 3} and the adversary's initial belief is about the parity of A. Table 4 summarizes the remaining uncertainty about A after observing O, the output of the program PROG C5 (see Table 3). Here, the actual a priori distributions are p 1 and p 2 as defined in Example 3. The prebeliefs p 0 1 and p 0 2 are slight modifications of p 1 and p 2 of Example 3 to cope with the admissibility requirement. For instance, consider the 0.04-admissible belief p 0 1 . Then the adversary's a posteriori belief is as follows:

p 0 1 (a | o) a 0 a
Hence, o 0 = {a 0 }, o 1 = {a 3 } and o 2 = {a 2 }. Therefore, V (A | O) = X o2O 1 | o | X a2 o p(o | a)p(a) = X j2{0,1,2} 1 | o j | X a2 o j p(o j | a)p(a) = p(o 0 | a 0 )p(a 0 ) + p(o 1 | a 3 )p(a 3 ) + p(o 2 | a 2 )p(a 2 ) = 0.99 ⇥ p(a 0 ) + 1 ⇥ p(a 3 ) + 0.99 ⇥ p(a 2 ) = 0.99 ⇥ ⇣ p(a 0 ) + p(a 2 ) ⌘ + p(a 3 ).
In other words, if the actual a priori distribution does not support a 1 highly then program PROG C5 will leave A highly vulnerable. This is the case for both p 1 and p 2 even though p 2 is highly conflicting with p 0 1 . The reason is that the a posteriori belief p 0 1 (a | o) never supports a 1 . So putting almost all the mass on a 1 will always fool the attacker. Similarly, for p 0 2 , we obtain

V (A | O) = p(a 1 ) + 0.99 ⇥ p(a 2 ) + p(a 3
). In order to minimize the a posteriori belief-vulnerability of A, the actual a priori distribution p must put almost all the mass on a 0 . Again, this is not the case for both p 1 and p 2 which explains why V (A | O) is always greater that 1 2 . Now we establish both lower and upper bounds for the remaining uncertainty in the presence of beliefs. We start with the lower bound and show that, as in the case of the initial uncertainty, it is obtained with a full knowledge of the actual a priori distribution (viz., a true and justifiable belief).

Theorem 3. H 1 (A | O)  H 1 (A | O). Proof. Let o = argmax a2A p (a | o). V (A | O) = X o2O p(o)V (A | o) = X o2O p(o) ⇣ 1 | o | X a2 o p(a | o) ⌘  X o2O p(o) ⇣ 1 | o | X a2 o max a 0 2A p(a 0 | o) ⌘ (since o ✓ A)  X o2O p(o) ⇣ 1 | o | X a2 o V (A | o) ⌘  X o2O p(o) ⇣ | o | | o | V (A | o) ⌘  V (A | O).
Hence,

H 1 (A | O)  H 1 (A | O).
Again, the lower bound is reached if and only if all the adversary's possible choices have the actual maximal a posteriori probability.

Proposition 6. H 1 (A | O) = H 1 (A | O) i↵ 8o 2 O, o ✓ argmax a2A p(a | o).
Proof. The proof in the right direction is similar to the proof of Theorem 3 where the inequality is replaced by the equality since o ✓ argmax a2A p(a | o). To see why the opposite holds, it is su cient observe that when there exists an element of o that has not the maximal a posteriori probability then

V (A | o)  V (A | o).
Hence the uncertainty is greater than the lower-bound.

In particular when the initial belief coincides with the actual a priori distribution then the belief-vulnerability remaining uncertainty reduces to the vulnerability remaining uncertainty.

Corollary 2. If p(a) = p (a) for all a in A, then H 1 (A | O) = H 1 (A | O).
Now, onto the upper-bound. Theorem 4. Let A be a high input of a channel and O its low output. Then

H 1 (A | O)  log ⇣ 1 ⇣ ⌘ , where ⇣ = min o2O 1 | o | X a2 o p(a | o) .
Note that ⇣ in the above theorem is strictly greater than zero since we consider admissible beliefs for some positive ✏. Hence the upper bound is well defined. yet, ⇣ could be very small, meaning that the presence of belief could add a huge amount of uncertainty and hence reduce a lot the vulnerability of A.

Proof. Let o = argmax a2A p (a | o). V (A | O) = X o2O p(o)V (A | o) = X o2O p(o) ⇣ 1 | o | X a2 o p(a | o) ⌘ X o2O p(o) min o2O ⇣ 1 | o | X a2 o p(a | o) ⌘ X o2O p(o)⇣ = ⇣. Hence, H 1 (A | O)  log ⇣ 1 ⇣ ⌘ .

Belief-leakage

As usual, we define the information leakage of a channel as the reduction of uncertainty. Definition 7. Let A be a high input of a channel C and O its low output. Given p, the actual prior distribution of A and p the belief of the adversary about A, the information leakage of C is 2 and4 we obtain the information leakage of the program PROG C5 as in Table 5.

IL (p, C : p ) = H 1 (A) H 1 (A | O). (p 1 , p 0 1 ) (p 1 , p 0 2 ) (p 2 , p 0 1 ) (p 2 , p 0 2 ) IL (C5) 1 5.65 4.72 1.05
We remark that when the initial belief and the actual a priori distribution are not highly conflicting (viz. (p 1 , p 0 1 ) and (p 2 , p 0 2 )) the leakage is about 1 bit of information. Moreover, the leakage is almost equal to the actual leakage of the program. However, even though the leakage is high (more than 4 bits of information), when they are highly conflicting, the actual leakage cannot exceed two bits of information. Hence much of the leakage is due to the correction of the misinformation induced by the wrong belief.

We note that while the remaining uncertainty H 1 (A | O) is a good characterization of the vulnerability of A after observing O, the information leakage alone, as usual, does not tell us much about the security of A. Moreover it might correct a lot the misinformation induced by a wrong belief about A. It is therefore important to characterize the the amount of uncertainty induced by a wrong belief.

Accuracy

From Theorems 1 and 3 we learned that wrong beliefs increase uncertainty. We introduce here a metric for the accuracy of a belief which quantifies the amount of uncertainty induced by the belief inaccuracy. Intuitively, the more the belief is inaccurate, the more the adversary's uncertainty should increase. We therefore quantify the inaccuracy of a belief by the divergence between the vulnerability induced by the belief and the actual vulnerability. Similarly we define the posterior inaccuracy as the divergence between the corresponding posterior vulnerabilities. Definition 9. The posterior inaccuracy of p w.r.t.

p is D (p k p : C) = log ⇣ V (A | O) V (A | O) ⌘ .
Again, it is always positive or null (cf. Theorem 3) and accounts for the amount of increase in the remaining uncertainty due to the inaccuracy of p .

Lemma 2. D (p k p : C) 0 Proposition 8. H 1 (A | O) = H 1 (A | O) + D (p k p : C)

Leakage

In the previous section we have seen that a wrong belief increases the prior and the posterior min-entropy by the terms D (p k p ) and D (p k p : C), respectively. Note that D (p k p ) and D (p k p : C) can be arbitrary high. But: how do belief leakage and min-entropy leakage compare? We would expect the min-entropy leakage never to exceed the belief leakage, since the channel may correct the initial wrong belief and hence leaks more information. Actually this is not always the case. Indeed, as shown by our analysis of program PROG C2 (see Example 1) in Section 6, the belief leakage can be less, equal or greater than the min-entropy leakage. The reason is that the channel is not always reducing the inaccuracy of the belief. In fact a channel may increase the adversary's confidence over some hypotheses which are actually very misleading. Thus the change in inaccuracy can be positive, null or even negative.

From Propositions 7 and 8 we have that a wrong belief increases (resp. Interestingly, as in the case of the min-entropy leakage and the g-leakage, the belief leakage is also null when the low output and the high input are independent.

Theorem 5 (Zero-leakage). H

1 (A) H 1 (A | O) = 0 if A and O are inde- pendent.
Proof. Assume that A and O are independent. Then from Equation 9we have that for all observable o, the posterior belief p (a | o) is equal to the prior belief p (a). Hence, o = for all observable o. In other words, the observables do not a↵ect the adversary's choice. Therefore,

V (A | O) = X o2O p(o)V (A | o) = X o2O p(o) ⇣ 1 | o | X a2 o p(a | o) ⌘ = X o2O p(o) ⇣ 1 | | X a2 p(a | o) ⌘ ( Independence of A and O) = X o2O p(o) ⇣ 1 | | X a2 p(a) ⌘ = X o2O p(o)V (A) = V (A). Hence H 1 (A | O) = H 1 (A).
Finally, we may wonder whether the belief leakage of a channel C can ever be negative, as C may increase the inaccuracy of a belief. However, as in the case of the min-entropy leakage and the g-leakage [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF], the belief leakage is always positive or null as it is defined in terms of expectation.

Theorem 6. H 1 (A) H 1 (A | O) 0.

On the Applicability of the Belief-vulnerability Approach

The previous section establishes our definitions in terms of their theoretical properties. Now we show the utility of our approach by applying it to various threat scenarios and comparing the results to the previous approaches. This is done through an extensive analysis of the deterministic program PROG C1 and the probabilistic program PROG C2 of Example 1. In order to simplify the reading, we reproduce them here.

PROG C2: BEGIN R 'sampled from {0, 2} with p(0) = and p(2) = 1 '; If A = R Then O := A Else O := 1 END PROG C1: BEGIN O := b log(A + 2) c END
Each of these programs is analysed under the following hypothesis.

• The actual prior distribution of the high input A is such that

p(a 0 ) = p(a 2 ) = ! 2(1 + !)
and p(a

1 ) = p(a 3 ) = 1 2(1 + !) ,
for some 0 < !  1.

• The adversary believes that A is most likely an even number, that is she assumes the following 1 2 -admissible belief:

p (a 0 ) = p (a 2 ) = 3 8 and p (a 1 ) = p (a 3 ) = 1 8 .
Thus = {a 0 , a 2 } and hence the probability that a guess of the attacker is correct is reduced by the factor ! compared to someone who knows the actual distribution.

We denote by IU x the initial uncertainty computed using the approach x 2 {s, 1, } where s, 1 and denote the Shannon entropy, Rényi minentropy and belief-based approaches respectively. Ditto for RU x and IL x . We start with PROG C1.

Analysis of PROG C1

Shannon entropy leakage. For the prior entropy we have:

IU s = H(A) = X a2A p(a) log p(a) = ⇣ ! 2(1 + !) log ! 2(1 + !) + 1 2(1 + !) log 1 2(1 + !) + ! 2(1 + !) log ! 2(1 + !) + 1 2(1 + !) log 1 2(1 + !) ⌘ = ⇣ ! 1 + ! log ! 2(1 + !) + 1 1 + ! log 1 2(1 + !) ⌘ = 1 + log(1 + !) ! 1 + ! log !.
For the posterior entropy, we have p(o

0 ) = p(o 1 ) = 1 2 since we have p(o) = P a2A p(o | a)p(a). The conditional probabilities p(a | o) = p(o | a)p (a) p(o)
are given in Table 6. Thus,

RU s = H(A | O) = X o2O p(o) X a2A p(a | o) log p(a | o) = h 1 2 ⇣ ! 1 + ! log ! 1 + ! + 1 1 + ! log 1 1 + ! ⌘ + 1 2 ⇣ ! 1 + ! log ! 1 + ! + 1 1 + ! log 1 1 + ! ⌘i = ⇣ ! 1 + ! log ! 1 + ! + 1 1 + ! log 1 1 + ! ⌘ = log(1 + !) ! 1 + ! log !.
Hence the leakage is IL s = IU s RU s = 1. It is illustrated in Figure 1.

Min-entropy leakage. For the prior min-entropy, we have

IU 1 = H 1 (A) = log V (A) = log(max a2A p(a)) = log 1 2(1 + !) = 1 + log(1 + !).
Similarly, for the posterior min-entropy, we have

RU 1 = H 1 (A | O) = log V (A | O) = log ⇣ X o2O p(o) max a2A p(a | o) ⌘ = log( 1 2 • 1 1 + ! + 1 2 • 1 1 + ! ) = log(1 + !). p(o | a) 0 0 0 1 a 0 1 0 a 1 1 0 a 2 0 1 a 3 0 1 p(a | o) a 0 a 1 a 2 a 3 o 0 ! 1+! 1 1+! 0 0 o 1 0 0 ! 1+! 1 1+! p (a | o) a 0 a 1 a 2 a 3 o 0 3 4 1 4 0 0 o 1 0 0 3 4 1 4 x IU x RU x IL x (C1) s 1 + log(! + 1) ! !+1 log ! log(! + 1) ! !+1 log ! 1 1 1 + log(! + 1) log(! + 1) 1 1 + log(! + 1) log ! log(! + 1) log ! 1
Table 6: Matrices of conditional probabilities and the leakages of PROG C1

Again, the leakage is 1 since

IL 1 = IU 1 RU 1 = 1. It is illustrated in Figure 1.
Belief leakage. Since the adversary initially believes that A is most likely even, then = {a 0 , a 2 }. Hence the belief vulnerability of A is

V (A) = 1 X a2 p(a) = 1 2 X a2{a 0 ,a 2 } p(a)) = ! 2(1 + !)
.

Thus IU = H 1 (A) = log V (A) = 1 + log(1 + !) log(!).
For the posterior belief vulnerability, from Bayes' rule, we obtain the adversary's updated belief p (a | o) as in Table 6, whence we obtain the following sets of adversary's possible choices o 0 = {a 0 } and o 1 = {a 2 }. Therefore,

V (A | O) = X o2O 1 | o | X a2 o p(o | a)p(a) = X j2{0,1} 1 | o j | X a2 o j p(o j | a)p(a) = p(o 0 | a 0 )p(a 0 ) + p(o 1 | a 2 )p(a 2 ) = ! 1 + ! . Hence RU = H 1 (A | O) = log V (A | O) = log(1 + !) log(!)
, which results in a leakage of 1 again. Thus, the fact that the adversary initially believes that A is even does not a↵ect the quantity of information leaked by PROG C1. However, the real question is not how much information is leaked by this program, but what the remaining uncertainty represents in terms of security threat to the high input. Even though the adversary's belief does not a↵ect the quantity of the information leakage, it dramatically a↵ects both the initial and remaining uncertainty. Indeed, as illustrated by Figure 3, both IU and RU tend toward infinity as ! tends toward zero. On the other hand, IU and RU tend toward two and one, respectively, as ! tends toward one. In other words inaccurate beliefs strengthen the security of the program (by confusing the adversary). Thus, a deliberate leakage of a wrong side information biased toward the less likely parity of the high input is a good strategy to strengthen the security of this program.

Analysis of PROG C2

We continue our analysis with the probabilistic program PROG C2. The initial uncertainty remains the same as in the analysis of the program PROG C1. Following the same approach as for PROG C1, we obtain the matrices of conditional probabilities and the leakages for PROG C2 shown in Table 7.

Proposition 10 (Shannon entropy leakage of PROG C2).

IL s (C1) = 1 + log(! + 1) ! 2(! + 1) log ! ! + 2 2(! + 1) log(! + 2) + ! 2(! + 1) ⇣ log + (1 ) log(1 ) ⌘ . p(o | a) 0 0 0 1 0 2 a 0 1 0 a 1 1 0 0 a 2 0 1 a 3 1 0 0 p(a | o) a 0 a 1 a 2 a 3 o 0 (1 )! 2+! 1 2+! ! 2+! 1 2+! o 1 1 0 0 0 o 2 0 0 1 0 p (a | o) a 0 a 1 a 2 a 3 o 0 3 5
(1 ) 1) log( 1)

1 5 3 5 1 5 o 1 1 0 0 0 o 2 0 0 1 0 x RUx ILx(C2) s !+2 2(!+1) log(! + 2) ! 2(!+1) ⇣ log ! + log + (
⌘ see Propostion 10 1 1 log(! + 1) 1 + log(! + 1) log ! log(1 + max( , 1
)) log(1 + max( , 1 ))

Table 7: Matrices of conditional probabilities and the leakages of PROG C2

The information flow ascribed by the Shannon entropy is illustrated in Figures 4 and5, those of the belief-based approach in Figures 6 and7. We note that the randomisation parameter of PROG C2 has no e↵ect on the minentropy leakage. This is due to the fact that this metric focuses on the single probability that poses the greatest risk; the actual posterior probabilities of a 1 and a 3 , the possible choices of the adversary, do not depend on . On the other hand, the accuracy factor ! of the adversary's prior belief has no e↵ect on the belief leakage. This is due to the fact that she always chooses the even number a 0 or a 2 towards which is biased independently of !. Since a 0 and a 2 play symmetric roles with respect to , any gain in uncertainty due to the value towards which is biased is o↵set by the loss due to the other value.

Finally, comparing the min-entropy leakage and the belief leakage of PROG C2 (see Figure 8), we can assert that belief leakage is higher than min-entropy leakage except for highly accurate beliefs. In fact, we have the following result relating min-entropy and belief leakages depending on the randomisation parameter and !, the accuracy factor of the adversary's prior belief.

Proposition 11. The belief leakage of PROG C2 is higher than its minentropy leakage if and only if the randomisation parameter and !, the accuracy factor of the adversary's prior belief, satisfy the following relation:

!  max( , 1 ). 6.3. Belief accuracy vs adversary's confidence Our analysis so far confirmed that inaccurate beliefs tend to confuse the adversary by reducing the probability that she correctly guesses the hidden or protected data. However, it might be the case that the interaction with the security mechanism (wrongly) increased the adversary's confidence about the value of the hidden or protected data, that is, she wrongly believes that she has learned some useful information. Hence, she may end up being highly confident about her (wrong) result and may take action that results in serious harm to an innocent victim or to the whole society.

For instance, assume that A is the set of hidden identities of the users of the security system. Consider a 'dictator' adversary who takes action against a user a only when she believes that a is more likely to be the culprit (i.e. more likely to be the hidden input) than to not be the culprit. In other words, she only takes action against a when p (a) > 1 2 a priori or p (a | o) > 1 2 a posteriori for a given observable o. Now let us see how our simple programs C1 and C2 perform against such adversary. First, we note that, a priori, there is no victim since the adversary's prior belief p does not assign a mass strictly higher than one-half to any value of A. However, after observing the outcome of C1 (see Table 6) we have that p (a

0 | o 0 ) = p (a 2 | o 1 ) = 3 4
. Therefore, the adversary will take action against a 0 (resp. a 2 ) when she observes o 0 (resp. o 1 ) even though a 0 (resp. a 2 ) is highly unlikely to be the input when !, the accuracy factor of the adversary's prior belief, is very small. Let P rob[Vic : p , p, C] (resp. P rob[Inn : p , p, C]) denote the probability that the adversary takes action against a user (resp. an innocent user) after observing the outcome of the channel C when her prior belief is p and the actual prior probability is p. Let p and p be as in the previous section. Then the followings hold.

p , p, C] = X o2O X a2A p(o) ⇥ P rob[p (a | o) > 1 2 ].
Similarly, the probability of having an innocent victim can be expressed as the sum of the probability of having a victim a for each observable o weighted by the actual probability P a 0 6 =a p(a 0 | o) that somebody else could have been the actual input. Thus

P rob[Vic : p , p, C] = X o2O X a2A p(o) ⇥ P rob[p (a | o) > 1 2 ] ⇣ X a 0 6 =a p(a 0 | o) ⌘ .
Since p(o) = P a2A p(o | a)p(a), the proposition follows from Table 6 and Table 7.

The results above show that in terms of protecting everybody (i.e. not having victims), C1 ensures zero level of protection, since whatever the outcome of the program is the adversary will become confident enough about her guess to take action. Ditto for C2 when the randomization factor is highly biased towards one value of A. However, when is not highly biased, then C2 becomes extremely good, since the most likely outcome o 0 does not increase the adversary's confidence enough to trigger an action, specially when !, the accuracy factor of her prior belief, is very small. Hence in terms of protecting everybody against such 'dictator' adversary, C2 performs better than C1 when is not highly biased. But they are equally bad when is highly biased.

In terms of protecting only the innocent victims, C2 is perfect when is not highly biased, since in this case the adversary will never take action against an innocent victim. However when is highly biased, C2 becomes slightly worse that C1. The reason is that in this case even when the input is an even number there is a small probability that the adversary's guess is wrong for C2 when she observes o 0 . This is never the case for C1. The elementary examples in this paper illustrate the applicability of our metric to various threat scenarios. In particular, they show that confidence, i.e., the entropy of the adversary's belief, and accuracy are two orthogonal dimensions of security. We need to consider both of them in order to be able to model a wide range of threat scenarios. Typically, the adversary makes her decision according to her confidence in her beliefs, i.e., based on the uncertainty metric. On the other hand, the consequence of her decision, viz., the gain, usually depends on the accuracy metric. The 'dictator' example illustrates the limit case where the gain is independent of the accuracy (as the dictator always wins). It also shows the importance of the reliability of side information.

Related work

We have already mentioned in Sections 1 and 3 much of the related work. In this section we only discuss the work that is closely related to our framework and that was not already reported there.

As far as we know, [START_REF] Clarkson | Belief in information flow[END_REF][START_REF] Clarkson | Quantifying information flow with beliefs[END_REF] have been the first papers to address the adversary's beliefs in quantifying information flow. This line of work, which inspired our formulation of the belief-vulnerability, is based on the Kullback-Leibler distance, a concept related to Shannon entropy which in general, as already mentioned in Section 3, fails to characterize many realistic attacks scenarios. Belief semantics has been explored also in the context of other security properties in [START_REF] Hirsch | Belief semantics of authorization logic[END_REF][START_REF] Clarkson | Quantification of integrity[END_REF]. In a recent paper [START_REF] Hussein | A precise information flow measure from imprecise probabilities[END_REF], Hussein proposed a generalization of the Bayesian-based framework of [START_REF] Clarkson | Quantifying information flow with beliefs[END_REF] based on Dempster-Shafer theory. The accuracy is expressed in terms of the generalized Jensen-Shannon divergence [START_REF] Klir | Uncertainty and Information: Foundations of Generalized Information Theory[END_REF] between the belief and the actual value of the high input. Our metric is, on the contrary, based on the min-entropy leakage, where a leakage of k-bits means that on average the channel increases the vulnerability of the secret to being guessed correctly in one single try by the factor 2 k . Moreover, as shown by recent work [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF], quantitative information flow metrics based on the min-entropy model can be extended by so-called gain functions to account for a wider range of operational attack scenarios. While the framework in [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF] is closely related to ours, as they both generalize the quantitative information flow model based on Rényi min-entropy, their objectives are orthogonal. Belief functions model the adversary's (potentially incorrect) side information; gain-functions model the operational threat scenarios, such as the adversary's benefit from guessing a value 'close' to the actual value of the secret, guessing a property of the secret, or guessing its value within some number of tries.

A related line of research has explored methods of statistical inference, in particular those from the hypothesis testing framework. The idea is that the adversary's best guess is that the true input is the one which has the maximum conditional probability (MAP rule) and that, therefore, the a posteriori vulnerability of the system is the complement of the Bayes Risk, which is the average probability of making the wrong guess when using the MAP rule [START_REF] Chatzikokolakis | On the bayes risk in information-hiding protocols[END_REF]. This is always at least as high as the a priori vulnerability, which is the probability of making the right guess just based on the knowledge of the input distribution. It turns out that Smith's notion of leakage actually corresponds to the ratio between the a posteriori and the a priori vulnerabilities [START_REF] Smith | On the foundations of quantitative information flow[END_REF][START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF].

Concerning the computation of the channel matrix and of the leakage for probabilistic systems, one of the first works to attack the problem was [START_REF] Andrés | Computing the amount of leakage in information-hiding systems[END_REF], in which the authors proposed various model-checking techniques. One of these is able to generate counterexamples, namely points in the execution where the channel exhibits an excessive amount of leakage. This method is therefore also useful to fix unsound protocols. A subsequent paper [START_REF] Chadha | Computing information flow using symbolic model-checking[END_REF] focussed more on the e ciency and proposed the use of binary decision diagrams and symbolic model checking. For systems that are too large to apply model-checking, approximate techniques based on statistics have been proposed [START_REF] Chatzikokolakis | Statistical measurement of information leakage[END_REF].

Conclusion and future work

This paper presents a new approach to quantitative information flow that incorporates the attacker's beliefs in the model on Rényi min entropy. We investigate the impact of such adversary's inaccurate, misleading or outdated side information on the security of the secret information. Our analysis reveals that inaccurate side information tends to confuse the adversary by decreasing the probability of a correct guess. However, due to the inaccuracy of her side information, the interaction with the security mechanism may (wrongly) strengthen the adversary's confidence about her choice. While the attacker might not actually discover the true value of the secret, the fact that she wrongly believes to actually know it constitutes a security threat, since it can adversely influence how she views or interacts with the victim. We have shown the strength of our definitions both in terms of their theoretical properties and of their utility by applying them to various threat scenarios. As already stated in [START_REF] Clarkson | Belief in information flow[END_REF][START_REF] Clarkson | Quantifying information flow with beliefs[END_REF], our results confirm, in particular, that the confidence of the attacker and the accuracy of her belief are two orthogonal dimensions of the security. Depending on the threat operational scenario, both could be equally important or one more relevant than the other. We observe that our approach can also be seen as moving away from the often criticised yet standard assumption in information flow that the adversary knows the true distribution of secrets. More realistically, here the focus is on the attacker's assumptions about such distributions (their a priori beliefs), and the consequences of making them.

As future work, we shall extend our model to consider a wide range of operational threat scenarios especially in the presence of wrong beliefs. To achieve this goal, we plan to build upon our belief framework and the gainfunctions framework [START_REF] Alvim | Measuring information leakage using generalized gain functions[END_REF]. Secondly, we shall devise methods and techniques of collecting and aggregating the adversary's side information from di↵erent and potentially conflicting sources such as social networks, online forums and blogs, etc. We believe that the body of concepts and results related to the notion of belief combination will provide natural and solid tools for this goal. Finally, we also plan to implement our framework in a tool to assess the e↵ectiveness of current security/privacy mechanisms in a realworld context and under various attack scenarios. Doing so, will help us to have a clear view of the real impact of side information collected from social networks, online forums, blogs and other forms of online communication and information sharing. It will also help us to accurately estimate the reliability of each of these sources, as well as providing guidelines and some mechanism design principles for privacy-preserving and security mechanisms.

[1] D. Chaum, The dining cryptographers problem: Unconditional sender and recipient untraceability, Journal of Cryptology 1 (1988) 65-75.

[2] M. K. Reiter, A. D. Rubin, Crowds: anonymity for Web transactions, ACM Transactions on Information and System Security 1 (1) (1998) 66-92.

The mass m(⇥) expresses our confidence or belief that the actual state of the world belongs to the subset ⇥. It represents only the proportion of all relevant and available evidence supporting ⇥ and makes no additional claims about any subset of ⇥. Note that the condition m(;) = 0 specifies the closedworld assumption, that is, the exhaustiveness of the hypotheses in the frame of discernment.

The focal elements of a bba m are the subsets ⇥ of X such that m(⇥) > 0. The set of the focal elements constitutes the core of the bba. A categorical belief is a bba m focusing on a single element, that is, there exists a subset ⇥ such that m(⇥) = 1. A categorical belief focusing on the entire world X is called a vacuous belief and expresses a total ignorance about the actual state of the world. A bba focusing on singletons of X is a Bayesian belief. Finally, the set {(⇥, m(⇥) | ⇥ 2 2 X and m(⇥) > 0} of focal elements together with their mass is called a body of evidence (BOE). By abuse of language we shall identify a BOE by its corresponding bba. We also write m(x) for m({x}).

Since our attacker may have collected her side information from many (potentially conflicting) sources, she needs to find a way of combining the different BOEs provided by her sources. Moreover, since some of these sources might be unreliable, she also needs a sound technique to discount beliefs from unreliable sources. Finally, since our adversary is a decision maker as she needs to make one single guess based on her belief, see needs a way of deriving a subjective probability distribution from her belief mass function. The following sections present such techniques.

Definition 8 .D

 8 The belief divergence of p and p (aka the inaccuracy of p w.r.t. p) is D (p k p ) = log ⇣ (p k p ) is always positive or null and accounts for the amount of increase in initial uncertainty due to the inaccuracy of p . Lemma 1. D (p k p ) 0 Proof. Follows directly from Theorem 1. Proposition 7. H 1 (A) = H 1 (A) + D (p k p ) Proof. Follows directly from their respective definitions (4 and 8).

  decreases) the leakage by a term D (p k p : C) = D (p k p ) D (p k p : C) equal to the decrease (resp. increase) in inaccuracy. Hence, the belief leakage IL (p, C : p ) is related to the min-leakage IL 1 (p, C) as follows. Proposition 9. IL (p, C : p ) = IL 1 (p, C) + D (p k p : C)

Figure 1 :

 1 Figure 1: Shannon leakage of C1 Figure 2: Min-leakage of C1 Figure 3: Belief leakage of C1

Figure 4 :Figure 5 :Figure 6 :Figure 7 :

 4567 Figure 4: RU s of PROG C2

Figure 8 :

 8 Figure 8: Belief leakage vs min-entropy leakage (PROG C2)

Table 2 :

 2 Initial uncertainty in presence of belief

		49			0.01			0.02	0.47
	H 1 (A)	1.03			6.64			5.64	1.09
		p ⇢1 p	1	p	2	p	1	p	2
		a 0	0.49 0.03 0.5 0
		a 1	0.01 0.47 0 0.95
		a 2	0.49 0.01 0.5 0
		a 3	0.01 0.49 0 0.05

Table 3 :

 3 Channel matrix of PROG C5

Table 4 :

 4 Remaining uncertainty of program PROG C5

				1	a 2	a 3
	o	0	0.9702 0.02 0.0098	0
	o	1	0.3289 0	0	0.6711
	o	2	0	0	1	0

Table 5 :

 5 Information leakage of program PROG C5 Example 5. Let's consider again the parameters in Example 4. Since p 0

	1

  The probability of having a victim can be expressed as the sum of the probability P rob[p (a | o) > 1 2 ] that user a is a victim given the observable o weighted by the actual probability p(o) of the observable. Hence P rob[Vic :

	as follows.
	P rob[Vic : p , p, C1] = 1
	P rob[Inn : p , p, C1] = P rob[Vic : p , p, C2] = P rob[Inn : p , p, C2] =	1 1 + ! ⇢ ! 2(1+!) 1 ( 0 2+!⇥min( ,1 ) if 1 6   5 6 otherwise if 1 6   5 6
		otherwise
		2(1+!)
	Proof.
	Proposition 12. Programs C1 and C2 perform against a dictator adversary

See §Appendix A for the rationale for representing the adversary's belief by a subjective probability distribution.

We call it belief min-entropy since when the belief coincides with the actual a priori distribution, then the belief min-entropy reduces to min-entropy.

Also considered in[START_REF] Clarkson | Belief in information flow[END_REF].

When for instance the evaluator of source of a bba need to be rated himself.

See[START_REF] Jousselme | Distances in evidence theory: Comprehensive survey and generalizations[END_REF] for more detail on distances between beliefs.

Appendix A. Some notions of the Dempster-Shafer Theory

In this paper, we have considered the case where the adversary is combining information from an external ( and potentially unreliable) source and the observables of the program/protocol in order to increase her chance of breaking the system. Many fusion theories such as possibility theory [START_REF] Dubois | Possibility theory, probability theory and multiplevalued logics: A clarification[END_REF],

probability theory [START_REF] Cover | Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)[END_REF], and Dempster-Shafer theory [START_REF] Dempster | A generalization of bayesian inference[END_REF][START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] have been proposed for the combination of information from di↵erent sources. Both possibility and probability theories can model imprecise and uncertain data at the same time. But the Dempster-Shafer theory is more adapted because it generalizes the others and, in particular, it has higher ability to combine information from (partially or totally) disagreeing sources.

Appendix A.1. Belief functions

Let X be a frame of discernment, that is, a finite set of exhaustive and mutually exclusive hypotheses 6 .

Definition 10 (Basic belief assignment (bba)). A basic belief assignment (aka belief mass function) is a mapping m : 2 X ! [0, 1] that satisfies:

(1) : m(;) = 0;

(2) : P ⇥✓X m(⇥) = 1. 6 Non-exhaustive and infinite frames of discernment are not considered.

Appendix A.2. Combination of information

Given two bodies of evidence m 1 and m 2 , the more classical way of combining them is Dempster's rule of combination (DRC) defined as

otherwise.

(A.1) DRC is not the only rule to combine two bbas. Indeed, there is a 'jungle' of combination rules developed in the literature essentially to answer the following Zadeh's [START_REF] Zadeh | Book review: A mathematical theory of evidence[END_REF] famous counterexample. Consider X = {x 0 , x 1 , x 2 } and two expert opinions given by m 1 (x 0 ) = 0.9, m 1 (x 2 ) = 0.1, and m 2 (x 1 ) = 0.9, m 2 (x 2 ) = 0.1. The DRC gives m 1 m 2 (x 2 ) = 1. Hence, since the two experts are highly conflicting in the hypothesis they strongly support, the alternative x 2 , hardly supported by each of them, turn out to be fully supported after the combination.

Several alternatives solutions have been proposed that all reject the m 1 m 2 (x 2 ) = 1 solution (e.g [START_REF] Yager | On the dempster-shafer framework and new combination rules[END_REF][START_REF] Smets | The transferable belief model[END_REF][START_REF] Dubois | Representation and combination of uncertainty with belief functions and possibility measures[END_REF]). None has reached a universal acceptance and interestingly DRC remains the most widely accepted and used in many application. The main concern with all these rules is that they are all based on the assumption that the sources of information are fully reliable. A strong assumption hardly supported for real life applications. Indeed, in intelligence gathering as well as in many real world information fusion systems, one must rate separately the quality (reliability, trustworthiness) of both the source and the content of the report. If the source is judged unreliable then the contain must by discarded. Therefore, one must first determine the reliability of the sources of the bbas before combining them.

Appendix A.3. Belief reliability

If one assumes that the source of his belief is fully reliable then he must accept it as it is. On the contrary, if the source is unreliable, then the belief must be discarded. An intermediate case is where we accept that the source might be more or less unreliable. Thus, we are building a bba m ⇢ over the space R = {r, nr} representing our beliefs about the fact that the source of our bba m is reliable (r) or not reliable (nr). Let ↵ = m ⇢ (r) be our belief about the fact that the source is reliable. If ↵ = 1 then we would accept m. If ↵ = 0 then we would discard m and our belief would become vacuous. More generally, said ↵ is the confidence level on the reliability of the source of the bba m about ⇥, the application of the General Bayesian Theorem [START_REF] Smets | Belief functions: The disjunctive rule of combination and the generalized bayesian theorem[END_REF] produces our discounted [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] belief about ⇥,

Every mass in m is shrunk by a factor ↵ and the mass lost is transferred to the universe (i.e. the frame of discernment). The factor ↵ is called the coe cient of the reliability and = 1 ↵ is the discount rate.

It is easy to see that discounting a discounted bba 7 is equivalent to discounting the bba by the product of the coe cients of the reliability.

Appendix A.4. Pignistic transformation

The mass m(⇥) expresses our confidence that the actual state of the world belongs to the subset ⇥ and makes no additional claims about any subset of ⇥. However, it is usually necessary to use the beliefs to make a decision, like the single-try attack scenario considered in this paper. In this case, a rational decision-maker should approximate the bba by a subjective probability measure, known as pignistic probability measure, based on the underlying frame of discernment. Many pignistic transformations (aka pignistic probabilizations) have been proposed (e.g [START_REF] Dezert | A new probabilistic transformation of belief mass assignment[END_REF]). Here, we only consider the well-known and widely used transformation defined as [START_REF] Smets | Decision making in the tbm: the necessity of the pignistic transformation[END_REF]

where |⇥| is the cardinality of the set ⇥.

The next lemma shows that the transformation of a categorical belief redistributes uniformly the mass of its unique focal element ⇥ to the singletons of ⇥. In particular, when m is vacuous, its transformation is the uniform probability distribution over the frame of discernment X . The transformation of a Bayesian belief m is equal to m. Finally, the discounted mass of a belief is uniformly redistributed to the singletons of the frame after the transformation.

Lemma 4.

1. If m is categorical focusing on ⇥, then

In summary, the adversary constructs her belief as follow: she collects information from di↵erent sources represented by the BOEs, she discounts each BOE according to the reliability of its source, she combines the discounted BOEs using the Dempster's rule of combination, then she finally derives the subjective probability distribution thanks to the pignistic transformation above. This subjective probability distribution models the adversary's belief in our framework.

Appendix B. Reliability and discounting

In Section 4.2, our belief updating based on the Bayes' rule requires the admissibility restriction. We introduce here a new approach which allow us to estimate the admissibility factor ✏ of an arbitrary belief given the channel matrix. More precisely, given an arbitrary belief p , we will compute its reliability factor ↵ w.r.t. the evidence induced by the channel (viz its observables). The discounted belief p ↵ is ✏-admissible, with ✏ = (1 ↵). Indeed the following holds.

Proposition 13. Let p be an arbitrary belief and ↵ be the reliability factor of its source. Then the discounted belief p ↵ is (1 ↵)-admissible.

Proof. From Lemma 4 we have p

Appendix B.1. Belief reliability

Estimating the reliability of beliefs from di↵erent sources of evidence is a challenging and very popular topic of research. Indeed, the Theory of Evidence (viz Theory of Belief) is becoming increasingly popular and widely used for decision making [START_REF] Ja↵ray | Application of linear utility theory to belief functions[END_REF][START_REF] Murphy | Combining belief functions when evidence conflicts[END_REF] in information fusion. Moreover, in many real applications, not all the sources of evidence might have the same reliability and there is no prior knowledge about it. Recently, many discounting frameworks (e.g. [START_REF] Florea | Robust combination rules for evidence theory[END_REF][START_REF] Liu | Combination of sources of evidence with di↵erent discounting factors based on a new dissimilarity measure[END_REF]), mainly based on two di↵erent approaches, have been proposed to enhance the trustworthiness of information from unreliable sources of evidence. On the one hand, there are methods that propose distance metrics 8 to capture the level (viz the quantity) of the dissimilarity between di↵erent opinions, but cannot show whether or not they conflict in the hypothesis they strongly support. On the other hand, most of the metrics proposed in the literature measure the conflict between beliefs. These metrics capture well the quality of the dissimilarity of opinions, that is, whether or not they distribute most of their support to compatible (viz same) elements. Having noticed that both approaches fail to give satisfactory results in general and that each of them capture only one of two complementary aspects of the dissimilarity, [START_REF] Liu | Combination of sources of evidence with di↵erent discounting factors based on a new dissimilarity measure[END_REF] propose to combine both approaches.

The distance and conflict metrics of [START_REF] Liu | Combination of sources of evidence with di↵erent discounting factors based on a new dissimilarity measure[END_REF] translate in our setting as

Conf(p, q) = ⇢ 0 i fa r g m a x a2A p(a) \ argmax a2A q(a) 6 = ; p(a 0 )q(a 0 0 ) otherwise, where a 0 2 argmax a2A p(a) and a 0 0 2 argmax a2A q(a). An immediate consequence is that the distance between two beliefs is null if and only if the two opinions fully agree, i.e. they produces the same belief. Conversely, the distance is maximum if they fully contradict each other. Lemma 5. Dist(p, q) = 0 i↵ 8a 2 A, p(a) = q(a). Lemma 6. Dist(p, q) = 1 i↵ 8a 2 A, p(a) 6 = 0 ) q(a) = 0.

Similarly, the conflict is maximum if and only if they fully support two distinct elements. Lemma 7. Conf(p, q) = 1 i↵ 9a 0 , a 0 0 2 A s.t. p(a 0 ) = q(a 0 0 ) = 1 and a 0 6 = a 0 0 . The disagreement between two beliefs is an indicator of the unreliability of at least one of them. If they totally disagree then at least one of them is unreliable, while if they totally agree then both are equi-reliable. In this framework we adopt the following dissimilarity metric as an estimation of the relative disagreement between two beliefs.

. Discount rate

In order to determine the coe cient of the reliability of the belief, we first need to determine the belief induced by an evidence o. For example, considering the channel PROG C5 (see Table 3), when the adversary sees o 2 then the belief mass m o 2 induced by her observation is

But if she observes o

1 then she knows that the high input is either a 0 or a 3 but has no clear reason to prefer one over the other, even though o 1 is unlikely when the high input is a 0 . In fact, if the actual a priori distribution of A is such that p(a 3 ) = 0.01, then when we observe o 1 , the unlikely has happened either at the random generation of A or in the channel output. Therefore the only reasonable belief mass induced by o 1 is

The dissimilarity metric defined in Equation B.1 allows us to estimate the relative disagreement between two beliefs. However in an uncertain environment where the reliability of the sources of both beliefs is unknown, we have no clear way to tell which of them is more reliable as the dissimilarity only measures their relative disagreement. Fortunately, in this paper, the belief p o induced by a channel output is fully reliable. Hence the dissimilarity between p o and p is a good indicator of the unreliability of the prebelief p .

Proof. We start with Equivalence (1).

For Equivalence (2):

We finally define the discount rate of a belief w.r.t. a channel as the expectation of the discount rates induced by its observables. Note that our approach of deriving p o as the pignistic probabilization of the categorical belief mass m o is equivalent to Bayesian update of a vacuous belief (i.e. in the absence of any information) when observing o. Therefore, we take the expectation under the uniform distribution p u (a) over A. Hence, the discount rate of a belief p w.r. Next we show that a belief cannot be fully discounted since it cannot totally conflict with all the observables. Theorem 7. 0  < 1.

Proof. We start with the proof of 0  . Hence p would be a contradictory belief, which is not possible under our closed-world assumption.

From the first point of Lemma 8, from Theorem 7 and Proposition 13, we know that the discounted belief p

(1 ) (a) is never in full contradiction with the evidence o. We therefore define the posteriori belief as the Bayesian update of the discounted belief, i.e.