Mouna Chebbah
email: mouna.chebbah@univ-rennes1.fr

Arnaud Martin
email: arnaud.martin@univ-rennes1.fr

Ben Yaghlane
email: boutheina.yaghlane@ihec.rnu.tn

Combining partially independent belief functions

Keywords: Theory of belief functions, Combination rules, Clustering, Independence, Sources independence, Combination rule choice

Introduction

Uncertainty theories like the theory of probabilities, the theory of fuzzy sets [START_REF] Zadeh | Fuzzy sets[END_REF], the theory of possibilities [START_REF] Dubois | Representation and combination of uncertainty with belief functions and possibility measures[END_REF] and the theory of belief functions [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF][START_REF] Shafer | A mathematical theory of evidence[END_REF] model and manage uncertain data. The theory of belief functions can deal with imprecise and/or uncertain data provided by several belief holders and also combine them.

Combining several evidential information held by distinct belief holders aggregates their points of view by stressing common points. In the theory of belief functions, many combination rules are proposed, some of them like [START_REF] Dubois | Representation and combination of uncertainty with belief functions and possibility measures[END_REF][START_REF] Martin | Toward a combination rule to deal with partial conflict and specificity in belief functions theory[END_REF][START_REF] Murphy | Combining belief functions when evidence conflicts[END_REF][START_REF] Smets | The transferable belief model[END_REF][START_REF] Yager | On the Dempster-Shafer framework and new combination rules[END_REF][START_REF] Lefèvre | How to preserve the conflict as an alarm in the combination of belief functions?[END_REF] are fitted to the aggregation of evidential information provided by cognitively independent sources whereas the cautious, bold [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence[END_REF] and mean combination rules can be applied when sources are cognitively dependent. The choice of combination rules depends on sources independence. Some researches are focused on doxastic independence of variables such as [START_REF] Ben Yaghlane | Belief function independence: I. The marginal case[END_REF][START_REF] Ben Yaghlane | Belief function independence: II. The conditional case[END_REF]; others [START_REF] Shafer | A mathematical theory of evidence[END_REF][START_REF] Smets | Belief functions: The disjunctive rule of combination and the generalized Bayesian theorem[END_REF] tackled cognitive and evidential independence of variables. This paper is focused on measuring the independence of sources and not that of variables. We suggest a statistical approach to estimate the independence of sources on the bases of all evidential information that they provide. The aim of estimating the independence of sources is to guide the choice of the combination rule to be used when combining their evidential information.

We propose also a new combination rule to aggregate evidential information and take into account the independence degree of their sources. The proposed combination rule is weighted with that degree of independence leading to the conjunctive rule [START_REF] Smets | The combination of evidence in the transferable belief model[END_REF] when sources are fully independent and to the cautious rule [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence[END_REF] when they are fully dependent.

In the sequel, we introduce in Section 2 preliminaries of the theory of belief functions. In the Section 3, an evidential clustering algorithm is detailed. This clustering algorithm will be used in the first step of the independence measure process.

Independence measure is then detailed in Section 4. It is estimated in four steps: In the first step the clustering algorithm is applied. Second a mapping between clusters is performed; then independence of clusters and sources are deduced in the last two steps. Independence is learned for only two sources and then generalized for a greater number of sources. A new combination rule is proposed in the Section 5 taking into account the independence degree of sources. The proposed method is tested on random mass functions in Section 6. Finally, conclusions are drawn.

Theory of belief functions

The theory of belief functions was introduced by Dempster [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF] and formalized by Shafer [START_REF] Shafer | A mathematical theory of evidence[END_REF] to model imperfect data. The frame of discernment also called universe of discourse, Ω = {ω 1 , ω 2 , . . . , ω N }, is an exhaustive set of N mutually exclusive hypotheses ω i . The power set 2 Ω is a set of all subsets of Ω; it is made of hypotheses and unions of hypotheses from Ω. The basic belief assignment (BBA) commonly called mass function is a function defined on the power set 2 Ω and spans the interval [0, 1] such that:

∑ A⊆Ω m(A) = 1 (1)
A basic belief mass (BBM) also called mass, m(A), is a degree of faith on the truth of A. The BBM, m(A), is a degree of belief on A which can be committed to its subsets if further information justifies it [START_REF] Smets | The transferable belief model[END_REF].

Subsets A having a strictly positive mass are called focal elements. Union of all focal elements is called core. Shafer [START_REF] Shafer | A mathematical theory of evidence[END_REF] assumed a normality condition such that m( / 0) = 0, thereafter Smets [START_REF] Smets | The combination of evidence in the transferable belief model[END_REF] relaxed this condition in order to tolerate m( / 0) > 0.

The frame of discernment can also be a focal element; its BBM, m(Ω), is interpreted as a degree of ignorance. In the case of total ignorance, m(Ω) = 1.

A simple support function is a mass function with two focal elements including the frame of discernment. A simple support function m is defined as follows:

m(A) =          1 -w i f A = B for some B ⊂ Ω w if A = Ω 0 otherwise (2)
Where A is a focus of that simple support function and w ∈ [0, 1] is its weight. A simple support function is simply noted A w . A nondogmatic mass function can be obtained by the combination of several simple support functions. Therefore, any nondogmatic mass function can be decomposed into several support functions using the canonical decomposition proposed by Smets [START_REF] Smets | The canonical decomposition of a weighted belief[END_REF].

The belief function (bel) is computed from a BBA m. The amount bel(A) is the minimal belief on A justified by available information on B (B ⊆ A):

bel(A) = ∑ B⊆A,B = / 0 m(B) (3)
The plausibility function (pl) is also derived from a BBA m. The amount pl(A)

is the maximal belief on A justified by information on B which are not contradictory with A (A ∩ B = / 0):

pl(A) = ∑ A∩B = / 0 m(B) (4)
Pignistic transformation computes pignistic probabilities from mass functions in the purpose of making a decision. The pignistic probability of a single hypothesis A is given by:

BetP(A) = ∑ B⊆Ω,B = / 0 |B ∩ A| |B| m(B) 1 -m( / 0) . (5)
Decision is made according to the maximum pignistic probability. The single point having the greatest BetP is the most likely hypothesis.

Discounting

Sources of information are not always reliable, they can be unreliable or even a little bit reliable. Taking into account reliability of sources, we adjust their beliefs proportionally to degrees of reliability. Discounting mass functions is a way of taking consideration of sources' reliabilities into their mass functions. If reliability rate α of a source is known or can be quantified; discounting its mass function m is defined as follows:

   m α (A) = α × m(A) , ∀A ⊂ Ω m α (Ω) = 1 -α × (1 -m(Ω)) (6)
This discounting operator can be used not only to take consideration of source's reliability, but also to consider any information which can be integrated into the mass function, (1 -α) is called discounting rate.

Combination rules

In the theory of belief functions, a great number of combination rules are used to summarize a set of mass functions into only one. Let s 1 and s 2 be two distinct and cognitively independent sources providing two different mass functions m 1 and m 2 defined on the same frame of discernment Ω. Combining these mass functions induces a third one m 12 defined on the same frame of discernment Ω.

There is a great number of combination rules [START_REF] Dubois | Representation and combination of uncertainty with belief functions and possibility measures[END_REF][START_REF] Martin | Toward a combination rule to deal with partial conflict and specificity in belief functions theory[END_REF][START_REF] Murphy | Combining belief functions when evidence conflicts[END_REF][START_REF] Smets | The transferable belief model[END_REF][START_REF] Yager | On the Dempster-Shafer framework and new combination rules[END_REF][START_REF] Lefèvre | How to preserve the conflict as an alarm in the combination of belief functions?[END_REF]], but we enumerate in this section only Dempster, conjunctive, disjunctive, Yager, Dubois and Prade, mean, cautious and bold combination rules. The first combination rule was proposed by Dempster in [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF] to combine two distinct mass functions m 1 and m 2 as follows:

m 1⊕2 (A) = (m 1 ⊕ m 2 )(A) =            ∑ B∩C=A m 1 (B) × m 2 (C) 1-∑ B∩C= / 0 m 1 (B) × m 2 (C) ∀A ⊆ Ω, A = / 0 0 i f A = / 0 (7)
The BBM of the empty set is null (m( / 0) = 0). This rule verifies the normality condition and works under a closed world where Ω is exhaustive.

In order to solve the problem highlighted by Zadeh's counter example [START_REF] Zadeh | A mathematical theory of evidence (book review)[END_REF] where Dempster's rule of combination produced unsatisfactory results, many combination rules appeared. Smets [START_REF] Smets | The combination of evidence in the transferable belief model[END_REF] proposed an open world where a positive mass can be allocated to the empty set. Hence the conjunctive rule of combination for two mass functions m 1 and m 2 is defined as follows:

m 1 ∩ 2 (A) = (m 1 ∩ m 2 )(A) = ∑ B∩C=A m 1 (B) × m 2 (C) (8)
Even if Smets [START_REF] Smets | The nature of the unnormalized beliefs encountered in the transferable belief model[END_REF] interpreted the BBM, m 1 ∩ 2 ( / 0), as an amount of conflict between evidences that induced m 1 and m 2 ; that amount is not really a conflict because it includes a certain degree of auto-conflict due to the non-idempotence of the conjunctive combination [START_REF] Martin | Conflict measure for the discounting operation on belief functions[END_REF].

The conjunctive rule is used only when both sources are reliable. Smets [START_REF] Smets | The combination of evidence in the transferable belief model[END_REF] proposed also to use a disjunctive combination when an unknown source is unreliable. The disjunctive rule of combination is defined for two BBAs m 1 and m 2 as follows:

m 1 ∪ 2 (A) = (m 1 ∪ m 2 )(A) = ∑ B∪C=A m 1 (B) × m 2 (C) (9)
Yager in [START_REF] Yager | On the Dempster-Shafer framework and new combination rules[END_REF] interpreted m( / 0) as an amount of ignorance; consequently it is allocated to Ω. Yager's rule of combination is also defined to combine two mass functions m 1 and m 2 as follows:

         m Y (X ) = m 1 ∩ 2 (X ) ∀X ⊂ Ω, X = / 0 m Y (Ω) = m 1 ∩ 2 (Ω) + m 1 ∩ 2 ( / 0) m Y ( / 0) = 0 (10)
Dubois and Prade's solution [START_REF] Dubois | Representation and combination of uncertainty with belief functions and possibility measures[END_REF] was to affect the mass resulting from the combination of conflicting focal elements to the union of these subsets:

     m DP (B) = m 1 ∩ 2 (B) + ∑ A∩X= / 0, A∪X=B m 1 (X )m 2 (A) ∀A ⊆ Ω, A = / 0 m DP ( / 0) = 0 (11)
Conjunctive, disjunctive and Dempster's rules are associative and commutative, but Yager and Dubois and Prade's rules are not associative, even if they are commutative. Unfortunately, all combination rules described above are not idempotent because m ∩ m = m and m ∪ m = m.

Mean combination rule detailed in [START_REF] Murphy | Combining belief functions when evidence conflicts[END_REF], m Mean , of two mass functions m 1 and m 2 is the average of these ones. Therefore, for each focal element A of M mass functions, the combined one is defined as follows:

m Mean (A) = 1 M M ∑ i=1 m i (A) (12)
Besides idempotence, this combination rule verifies normality condition (m( / 0) = 0) if combined mass functions are normalized (∀i ∈ M, m i ( / 0) = 0). We note also that this combination rule is commutative but not associative.

All combination rules described above work under a strong assumption of cognitive independence since they are used to combine mass functions induced by two distinct sources. This strong assumption is always assumed but never verified.

Denoeux [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence[END_REF], proposed a family of conjunctive and disjunctive rules based on triangular norms and conorms. Cautious and bold rules are members of that family and combine mass functions for which independence assumption is not verified.

Cautious combination of two mass functions m 1 and m 2 issued from probably dependent sources is defined as follows:

m 1 ∧ m 2 = ∩ A⊂Ω A w 1 (A)∧w 2 (A) (13)
Where A w 1 (A) and A w 2 (A) are simple support functions focused on A with weights w 1 and w 2 issued from the canonical decomposition [START_REF] Smets | The canonical decomposition of a weighted belief[END_REF] of m 1 and m 2 respectively, note also that ∧ is a min operator of simple support functions weights. The bold and cautious combination rules are commutative, associative and idempotent.

To summarize, the choice of the combination rule is based on the dependence of sources. Combination rules like [START_REF] Dubois | Representation and combination of uncertainty with belief functions and possibility measures[END_REF][START_REF] Martin | Toward a combination rule to deal with partial conflict and specificity in belief functions theory[END_REF][START_REF] Murphy | Combining belief functions when evidence conflicts[END_REF][START_REF] Smets | The transferable belief model[END_REF][START_REF] Yager | On the Dempster-Shafer framework and new combination rules[END_REF] combine mass functions which sources are independent, whereas cautious, bold and mean rules are the most fitted to combine mass functions issued from dependent sources.

In this paper, we propose a method to quantify sources' degrees of independence that may be used in a new mixed combination rule. In fact, we propose a statistical approach to learn sources' degrees of independence from all provided evidential information. Indeed, two sets of evidential information assessed by two different sources are classified into two sets of clusters. Clusters of both sources are matched and the independence of each couple of matched clusters is quantified in order to estimate sources' degrees of independence. Therefore, a clustering technique is used to gather similar objects into the same cluster in order to study the source's overall behavior. Before introducing our learning method, we detail in the next section the evidential clustering algorithm that will be used in the learning of sources' degrees of independence.

Evidential clustering

In this paper, we propose a new clustering technique to classify objects; their attributes values are evidential and classes are unknown. Proposed clustering algorithm uses a distance on belief functions given by Jousselme et al. [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF] such as proposed by Ben Hariz et al. [START_REF] Ben Hariz | Clustering approach using belief function theory[END_REF].

Ben Hariz et al. [START_REF] Ben Hariz | Clustering approach using belief function theory[END_REF] detailed a belief K-modes classifier in which Jousselme distance [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF] is adapted to quantify distances between objects and clusters modes.

These are sets of mass functions; each one is the combination of an attribute's values of all objects classified into that cluster. An object is attributed to the cluster having the minimum distance to its mode.

Temporal complexity of clustering algorithm proposed by Ben Hariz et al. [START_REF] Ben Hariz | Clustering approach using belief function theory[END_REF] is quite high as clusters modes and distances are computed in each iteration. The combination by the mean rule to compute modes values leads to mass functions with a high number of focal elements. Hence, the bigger the cluster is, the least significant is the distance.

We propose a clustering technique to classify objects that attributes values are uncertain. However uncertainty is modeled with the theory of belief functions detailed in Section 2. In the proposed algorithm, we do not use any cluster mode to avoid the growth of focal elements number in clusters modes. Temporal complexity is also significantly reduced because all distances are computed only once.

In this section, K is the number of clusters Cl k (1 ≤ k ≤ K); n is the number of objects to be classified; n k is the number of objects classified into cluster Cl k ;

o i are objects to classify o i : 1 ≤ i ≤ n; c is the number of evidential attributes a j : 1 ≤ j ≤ c which domains are Ω a j and finally m i j is a mass function value of attribute " j" for object "i". Mass functions m i j can be certain, probabilistic, possibilistic, evidential and even missing.

To classify objects o i into K clusters, we use a clustering algorithm with a distance on belief functions given by [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF]. The number of clusters K is assumed to be known. Proposed clustering technique is based on a distance which quantifies how much is far an object o i from a cluster Cl k . This distance is the mean of distances between o i , and all objects o q that are classified into cluster Cl k as follows:

D(o i ,Cl k ) = 1 n k n k ∑ q=1 dist(o i , o q ) (14)
and

dist(o i , o q ) = 1 c c ∑ j=1 d(m i j , m q j ) (15)
with :

d(m i j , m q j ) = 1 2 (m i j -m q j ) t D(m i j -m q j ) (16)
such that :

D(A, B) =    1 if A = B = / 0 |A∩B| |A∪B| ∀A, B ∈ 2 Ω a j ( 17
)
Each object is affected to the most similar cluster in an iterative way till reaching an unchanged cluster partition. It is obvious that clusters number K must be known. Temporal complexity of the proposed algorithm is significantly optimized as pairwise distances are computed once a time from the beginning. We do not use any cluster mode. Consequently, there will be no problem of increasing number of Temporal complexity of the evidential clustering algorithm is optimized and that optimization is especially noticed when the number of mass functions to classify is high and also when the frame of discernment contains many hypotheses. Thanks to the improve of the temporal complexity, this clustering algorithm is used in the following sections.

Learning sources independence degree

In this section we extend paper [START_REF] Chebbah | About sources dependence in the theory of belief functions[END_REF] for many sources, and propose a combination rule emphasizing sources independence degree. In the theory of prob- abilities, two hypotheses X and Y are assumed to be statistically independent if P(X ∩Y ) = P(X ) × P(Y ) or P(X |Y ) = P(X ). In the context of the theory of belief functions, Shafer [START_REF] Shafer | A mathematical theory of evidence[END_REF] defined cognitive and evidential independence. Definition 1. "Two frames of discernment may be called cognitively independent with respect to the evidence if new evidence that bears on only one of them will not change the degree of support for propositions discerned by the other" 1 .

The cognitive independence is a weak independence; two variables are independent with respect to a mass function if new evidence that bears on only one of the two variables does not change propositions discerned by the other one. For two variables X and Y such that Ω X and Ω Y their domains (frames of discernment)

and Ω X × Ω Y the product space of domains Ω X and Ω Y . Variables X and Y are cognitively independent with respect to m Ω X ×Ω Y if:

pl Ω X ×Ω Y (x, y) = pl Ω X ×Ω Y ↓Ω X (x) × pl Ω X ×Ω Y ↓Ω Y (y) (18)
Note that [START_REF] Smets | The transferable belief model[END_REF][START_REF] Smets | Uncertainty Management in Information Systems: From Needs to Solutions[END_REF].

Ω X × Ω Y ↓ Ω X is the marginalization of Ω X × Ω Y in Ω X
Shafer [START_REF] Shafer | A mathematical theory of evidence[END_REF] defined also a strong independence called evidential independence as follows:

Definition 2. "Two frames of discernment are evidentially independent with respect to a support function if that support function could be obtained by combining evidence that bears on only one of them with evidence that bears on only the other".

Two variables are evidentially independent if their joint mass function can be obtained by combining marginal mass functions that bears on each one of them.

Variables X and Y are evidentially independent with respect to m Ω X ×Ω Y if:

   pl Ω X ×Ω Y (x, y) = pl Ω X ×Ω Y ↓Ω X (x) × pl Ω X ×Ω Y ↓Ω Y (y) bel Ω X ×Ω Y (x, y) = bel Ω X ×Ω Y ↓Ω X (x) × bel Ω X ×Ω Y ↓Ω Y (y) (19)
Independence can also be defined in terms of irrelevance.

m Ω X ×Ω Y ↓Ω X [y] (x) ∝ m Ω X ×Ω Y ↓Ω X (x) (20)
Note that proportionality ∝ is replaced by equality when

m Ω X ×Ω Y ↓Ω X [y]
and m Ω X ×Ω Y ↓Ω X are normalized.

Doxastic independence is especially proposed in the theory of belief functions by [START_REF] Ben Yaghlane | Belief function independence: I. The marginal case[END_REF][START_REF] Ben Yaghlane | Belief function independence: II. The conditional case[END_REF] and it is defined as follows:

Definition 3. "Two variables are considered as doxastically independent only when they are irrelevant and this irrelevance is preserved under Dempster's rules of combination".

In other words, two variables X and Y are doxastically independent if they are irrelevant with respect to m ⊕ m 0 when they are irrelevant with respect to m and m 0 .

Indeed, if X and Y are irrelevant according to any mass function m and if they are also irrelevant with respect to another mass function m 0 ; they are assumed to be doxastically independent if they are irrelevant with respect to the orthogonal sum of m and m 0 . Thus, if IR m (X ,Y ), IR m 0 (X ,Y ) and IR m⊕m 0 (X ,Y ) is verified then X and Y are doxastically independent.

This paper is not focused on variables independence [START_REF] Ben Yaghlane | Belief function independence: I. The marginal case[END_REF][START_REF] Ben Yaghlane | Belief function independence: II. The conditional case[END_REF][START_REF] Shafer | A mathematical theory of evidence[END_REF] but on sources independence. Sources independence is computed according to a set of different belief functions provided by each source separately. Sources are dependent when all their beliefs are correlated, there is a link between all mass functions they provide. This problem is not tackled till now, we noticed a lack of references treating this problem. To study sources independence, a great number of mass functions provided by both sources is needed. This set of mass functions must be defined on the same frame of discernment according to the same problems. For example, two distinct doctors provide n diagnoses in the examination of the same n patients. In that case, the frame of discernment contains all diseases and is already the same for both doctors. We define sources independence as follows: In this paper, mass functions provided by two sources are studied in order to reveal any dependence between them. In the following, we define an independence measure I d , (I d (s 1 , s 2 )), as the independence of s 1 on s 2 verifying the following axioms:

1. Non-negativity: The independence of a source s 1 on another source s 2 , I d (s 1 , s 2 )

cannot be negative, it is either positive or null.

2. Normalization: The degree of independence I d is a degree over [0, 1], it is null when the first source is dependent on the second one, equal to 1 when it is completely independent and a degree from [0, 1] otherwise.

3. Non-symmetry: In the case where s 1 is independent on s 2 , s 2 is not necessarily independent on s 1 . Even if s 1 and s 2 are mutually independent, degrees of independence are not necessarily equal.

4. Identity: Any source is completely dependent on itself and I d (s 1 , s 1 ) = 0.

If s 1 and s 2 are independent, there will be no correlation between their mass functions. The main idea of this paper is: First, classify mass functions provided by each source separately. Then, study similarities between cluster partitions to reveal any dependence between sources. By using clustering algorithm, sources overall behavior is studied. The proposed method is in three steps: First, mass functions of each source are classified. Then, similar clusters are matched. Finally, weights of linked clusters and sources independence are quantified.

Clustering

Clustering algorithm detailed in Section 3 is used to classify two sets of n mass functions respectively provided by sources s 1 and s 2 . Clustering algorithm is performed on all mass functions of s 1 independently of the clustering performed on those of s 2 . We remind that all mass functions of both sources are defined on the same frame of discernment and so considered as values of only one attribute when classifying their corresponding objects. For the same example of doctors, patients are objects to classify according to an attribute disease. Values of this attribute are mass functions defined on the frame of discernment enumerating all possible diseases. Distance ( 14) can be simplified as follows because we have only one attribute:

D(o i ,Cl k ) = 1 n k n k ∑ q=1 d(m i , m q ) (21)
In this paper, we fix the number of clusters to the number of hypotheses in the frame of discernment. In a classification point of view, number of hypotheses is the number of possible classes. For example, the frame of discernment of the attribute disease enumerates all possible diseases. Hence, when a doctor examines a patient, he gives a mass function as a classification of the patient in some possible diseases.

Cluster matching

After clustering technique, both mass functions provided by s 1 and s 2 are distributed separately on K clusters. In this section, we try to find a mapping between clusters in order to link those containing the same objects. If clusters are perfectly linked, meaning all objects are classified similarly for both sources, we can conclude that sources are dependent as they are choosing similar focal elements (not contradictory at least) when providing mass functions for same objects. If clusters are weakly linked, sources choose similar focal elements for different objects and so they are independent. Clusters independence degree is proportional to the number of objects similarly classified. More clusters contain the same objects, more they are dependent as they are correlated.

We note Cl

β i k i k j = β i (Cl i k i ,Cl j k j ) = | Cl i k i ∩Cl j k j | | Cl i k i | (22)
with i, j ∈ {1, 2} and i = j. β

. Note that β 1 k 1 k 2 = β 2 k 2 k 1 since the number of objects classified into Cl 1 k 1 and Cl 2 k 2 are different (| Cl 1 k 1 | =| Cl 2 k 2 |
). We remind that β 1 are similarities towards s 1 and β 2 are those towards s 2 . It is obvious that β i (Cl i k i ,Cl j k j ) = 0 when Cl i k i and Cl j k j do not contain any common object; however they are completely different. β i (Cl i k i ,Cl j k j ) = 1 when these clusters are strongly similar so they contain the same objects. A similarity matrix M 1 containing similarities of clusters of s 1 according to those of s 2 (β 1 ), and M 2 the similarity matrix between clusters of s 2 and those of s 1 (β 2 ) are defined as follows:

M 1 =           
β 1 K1 β 1 K2 . . . β 1 KK            and M 2 =           
β 2 K1 β 2 K2 . . . β 2 KK            (23)
We note that M 1 and M 2 are different since

β 1 k 1 k 2 = β 2 k 2 k 1 .
Clusters of s 1 are matched to those of s 2 according to maximum of β 1 such that each cluster Cl 1 k 1 is linked to only one cluster Cl 2 k 2 and each cluster Cl 2 k 2 has only one cluster Cl 1 k 1 linked to it. The idea is to link iteratively clusters having the maximal β 1 in M 1 then elim- inate these clusters and the corresponding line and column from the matrix until having a bijective cluster matching. Algorithm 1 details cluster matching process.

We note that different matchings are obtained for s 1 and s 2 because M 1 and M 2 are different. This algorithm is iterative and the number of iteration is equal to the Algorithm 1 Cluster matching Require: Similarity matrix M .

1: while M is not empty do 2:

Find max(M) and indexes c and l of clusters having this maximal similarity. number of clusters K. Even if this algorithm is quite simple, it provides a matching of clusters in order to compare evidential information provided by both sources.

The assignment algorithm proposed in [START_REF] Munkres | Algorithms for the Assignment and Transportation Problems[END_REF] for square matrices and that for rectangular matrices [START_REF] Bourgeois | An Extension of the Munkers Algorithm for the Assignement Problem to Rectangular Matrices[END_REF] can also be used to minimize the dissimilarity between matched clusters. Other methods for cluster matching [START_REF] Wemmert | A multi-view voting method to combine unsupervised classifications[END_REF] and [START_REF] Ganc ¸arski | Collaborative multi-strategy classification: Application to per-pixel analysis of images[END_REF] can also be used.

Cluster independence

Once cluster matching is obtained, a degree of independence/dependence of matched clusters is quantified in this step. A set of matched clusters is obtained for both sources and a mass function can be used to quantify each couple of clusters independence. Assume that cluster Cl 1 k 1 is matched to Cl 2 k 2 , a mass function m Ω I 2 defined on the frame of discernment Ω I = {Dependent Dep, Independent Ind} describes how much this couple of clusters is independent or dependent as follows:

         m Ω I ,i k i k j (Dep) = α i k i β 1 k i k j m Ω I ,i k i k j (Ind) = α i k i (1 -β 1 k i k j ) m Ω I ,i k i k j (Dep ∪ Ind) = 1 -α i k i ( 24
)
2 We note the frame of discernment in the mass functions to avoid confusion.

A mass function quantifies the degree of independence of each couple of clusters according to each source; m Ω I ,i k i k j is a mass function for the independence of each linked clusters Cl i k i and Cl j k j according to s i with i, j ∈ {1, 2} and i = j. Coefficient α i k i is used to take into account of number of mass functions in each cluster Cl k i of the source i. Reliability factor α i k i is not the reliability any source but it can be seen as the reliability of the clusters independence estimation. Consequently, independence estimation is more reliable when clusters contain enough mass functions.

For example, assume two clusters; one containing only one mass function and the second one containing 100 mass functions. It is obvious that the independence estimation of the second cluster is more precise and significant than the independence estimation of the first one. Reliability factors α i k i are proportional to the number of hypotheses in the frame of discernment | Ω |, and the number of objects classified in Cl i k i as follows:

α i k i = f (| Ω |, | Cl i k i |) (25)
The bigger | Ω | is, the more mass functions are needed to have a reliable cluster independence estimation. For example, if | Ω |= 5 then there are 2 5 possible focal elements, also independence estimation of a cluster containing 20 objects cannot be precise. No existing method to define such function f . Hence, we use simple heuristics as follows:

α i k i = 1 - 1 | Cl i k i | 1 |Ω| (26)
As shown in figure 2

m Ω I ,s i (A) = 1 K K ∑ k i =1 m Ω I ,i k i k j (A) ∀A ⊆ 2 Ω (27)
With k j is the cluster matched to k i according to s i . Two different mass functions m Ω I ,s 1 and m Ω I ,s 2 are obtained for s 1 and s 2 respectively. We note that m Ω I ,s 1 is the combination of K mass functions representing the independence of matched clusters according to s 1 defined using equation [START_REF] Bourgeois | An Extension of the Munkers Algorithm for the Assignement Problem to Rectangular Matrices[END_REF]. Mass functions m Ω I ,s 1 and m Ω I ,s 2 are different since cluster matchings are different which verifies the axiom of non-symmetry.

β 1 k 1 k 2 , β 2 k 2 k 1 ∈ [0, 1]
verify the non-negativity and the normalization axioms. Finally, pignistic probabilities are computed from these mass functions in order to decide about sources independence I d such that:

   I d (s 1 , s 2 ) = BetP(Ind) I d (s 1 , s 2 ) = BetP(Dep) (28) If I d (s 1 , s 2 ) > I d (s 1 , s 2 )
we claim that sources s 1 and s 2 are independent otherwise they are dependent.

General case

The method detailed above estimates the independence of one source on another one. Independence measure is non-symmetric because if a source s 1 is independent on a source s 2 then s 2 is not necessarily independent on s 1 and even if it is the case, degrees of independence are not necessarily the same.

It is wise to choose the minimum independence from I d (s 1 , s 2 ) and I d (s 2 , s 1 ) as the overall independence. Consequently, if at least one of two sources is dependent on the other, then sources are considered dependent. In other words, two sources are independent only if they are mutually independent. Hence, overall independence that is denoted I(s 1 , s 2 ) is given by:

I(s 1 , s 2 ) = min(I d (s 1 , s 2 ), I d (s 2 , s 1 )) (29)
We note that I(s 1 , s 2 ) is non-negative, normalized, symmetric and identical.

We define an independence measure, noted I, generalizing the independence for more than two sources verifying the following axioms:

1. Non-negativity: Many sources independence {s 1 , s 2 , s 3 , . . . , s ns }, noted I d (s 1 , s 2 , . . . , s ns ) cannot be negative, it is either positive or null.

2. Normalization: Sources independence I is a degree in [0, 1]. The minimum 0 is reached when sources are completely dependent and the maximum 1 is reached when they are completely independent.

3. Symmetry: I(s 1 , s 2 , s 3 , . . . , s ns ) is the sources' overall independence and I(s 1 , s 2 , s 3 , . . . , s ns ) = I(s 2 , s 1 , s 3 , . . . , s ns ) = I(s 3 , s 1 , s 2 , . . . , s ns ).

4. Identity: I(s 1 , s 1 , s 1 ) = 0. It is obvious that any source is completely dependent on itself.

Increasing with inclusion:

I(s 1 , s 2 ) ≤ I(s 1 , s 2 , s 3 )
, more there are sources, more they are likely to be independent.

To compute the overall independence of ns sources {s 1 , s 2 , . . . , s ns }, independencies of pairs of sources are computed and the maximum4 independence is the sources overall independence:

I(s 1 , s 2 , . . . , s ns ) = max(I(s i , s j )), ∀i ∈ [1, ns] , j ∈]i, ns] (30)
or equivalently:

I(s 1 , s 2 , . . . , s ns ) = max(min(I d (s i , s j ), I d (s j , s i ))), ∀i, j ∈ [1, ns] i = j (31)
Independence degree of sources is then integrated in the combination step using the following mixed combination rule.

Combination rule

Combination rules using conjunctive and/or disjunctive rules such as [2, 5,

are used when sources are completely independent but cautious and bold rules [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence[END_REF] tolerate redundant information and consequently can be used to combine mass functions which sources are dependent. In the combination step, sources dependence or independence hypothesis is intuitively made without any possibility of check. Sources independence degree is neither 0 nor 1 but a level over [0, 1].

The main question is "which combination rule to use when combining partially independent\dependent mass functions?"

In this paper, we propose a new mixed combination rule using conjunctive and cautious rules detailed in equations ( 8) and ( 13). In the case of totally dependent sources (where independence is 0), the cautious and proposed mixed combination rules are similar; whereas in the case of totally independent sources (independence is 1), the conjunctive and proposed combination rules are similar. In the case of an independence degree in ]0, 1[, combined mass function is the average of conjunctive and cautious combinations weighted by sources' independence degree.

Assume that two sources s 1 and s 2 are independent with a degree γ such that γ = I(s 1 , s 2 ); m 1 and m 2 are mass functions provided by s 1 and s 2 . The proposed mixed combination rule is defined as follows:

m Mixed (A) = γ * m ∩ (A) + (1 -γ) * m ∧ (A), ∀A ⊆ Ω (32)
The degree of independence of a set of sources is given by equation (30), and the mixed combination of a set of mass functions {m 1 , m 2 , . . . , m ns } provided by sources {s 1 , s 2 , . . . , s ns } is also a weighted average such that:

γ = I(s 1 , s 2 , . . . , s ns ) (33)
Properties of the proposed mixed combination rule:

• Commutativity: Conjunctive and cautious rules are commutative. Independence measure is symmetric because sources' degree of independence is the same for a set of sources. Then the proposed rule is commutative.

• Associativity: Conjunctive and cautious rule are associative but the proposed rule is not because independence degree of n sources and n + 1 ones is not necessarily the same.

• Idempotent: Degree of independence of one source to itself is 0, in that case the proposed rule is equivalent to the cautious rule. As the cautious rule is idempotent, it is the case of the proposed mixed rule.

• Neutral element: Mixed combination rule does not have any neutral element.

• Absorbing element: No absorbing element also.

Example. Assume a frame of discernment Ω = {a, b, c} and two sources s 1 and s 2 providing two mass functions m 1 and m 2 . Table 1 illustrates conjunctive and cautious combinations as well as mixed combination in the cases where γ = 0, γ = 0.

Experiments

Because of the lack of real evidential data, we use generated mass functions to test the method detailed above. Moreover, it is difficult to simulate all situations with all possible combinations of focal elements for several degrees of independence between sources. First, we generate two sets of mass functions for two sources s 1 and s 2 ; then we illustrate for three sources.

Generated data depiction

Generating sets of n mass functions for several sources depends on sources independence. We discern cases of independent and dependent sources. In the case of independent sources, masses can be anywhere and focal elements of both sources are chosen independently. Mass functions of s 1 and s 2 are generated following algorithm 2. We note that focal elements, their number and BBMs are chosen randomly according to the universal low. Focal elements BBMs are intervals sizes.

6: end for 7: return n mass functions

Dependent sources

The case of dependent sources is a bit difficult to simulate as several scenarios can occur. In this section, we will try to illustrate the most common situations. Generated mass functions for dependent sources are supposed to be consistent and do not enclose any internal conflict [START_REF] Daniel | Conflicts within and between belief functions[END_REF]. Consistent mass functions contain at least one focal element common to all focal sets. Figure 4

Results of tests

Algorithms detailed in the previous section are used to test some cases of sources' dependence and independence. We note that in extreme cases where mass functions are certain or even when focal elements do not intersect; maximal values of independence are obtained. In the case of perfect dependence; mass functions 6 Conflict within such mass functions is null. Choose randomly a focal set ω i (it can be a single point) from Ω.

3:

Find the set S of all focal sets including ω i .

Independent sources

In this paragraph, mass functions are independent. Focal elements and BBMs are randomly chosen ensuing algorithm 2. For tests, we choose | Ω |= 5 which is considered as medium-sized frame of discernment and n = 100. Table 2 illustrates the mean of 100 tests in the case of independent sources. The mean of 100 tests for two dependent sources yields to a degree of independence γ = 0.68, thus sources are independent. Assume that m 1 and m 2 , given in table Find the set S of all focal sets including d. 2 illustrates the mean of 100 independence degrees of two dependent sources providing each one 100 randomly generated mass functions. These sources are dependent with a degree 1 -γ = 0.66. In table 3, m 1 and m 2 are combined using the mixed rule when γ = 0.34.

To illustrate the case of three dependent sources, three sets of 100 dependent mass Finally, assume that m 1 , m 2 and m 3 of table 6 are three mass functions defined on a frame of discernment Ω = {a, b, c} and provided by three dependent sources.

The mixed combined mass function when their degree of independence is γ = 0.35 is also given in table 6.

Conclusion

In this paper, we proposed a method to learn sources cognitive independence in order to use the appropriate combination rule either when sources are cognitively dependent or independent. Sources are cognitively independent if they are different; not communicating and they have distinct evidential corpora. The proposed statistical approach is based on a clustering algorithm applied to mass functions

  focal elements because attributes values are not combined. Indeed, the evidential clustering algorithm provides a cluster partition that minimizes distances between objects into the same cluster and maximizes the distance between objects classified into different clusters. The main asset of the evidential clustering algorithm according to the belief K-modes proposed by Ben Hariz et al.[START_REF] Ben Hariz | Clustering approach using belief function theory[END_REF] is the optimization of the temporal complexity. In fact, run-time of the evidential clustering algorithm is improved. The optimization of run-time depends on the size of the frame of discernment |Ω a j |, the number of clusters K and number of objects n. For example, figure1shows a big gain in the run-time of evidential clustering according to the belief K-modes when the number of mass functions varies, n ∈ [10, 1000].

  of belief K-modes algorithm Runtime of the evidental clustering algorithm

Figure 1 :

 1 Figure 1: Run-time optimization of the evidential clustering and the belief K-modes [20] according to n ∈ [10, 1000], | Ω a j |= 5 and K = 5

  The knowledge of the value of one variable does not change the belief on the other one. In the theory of belief functions, irrelevance is based on the conditioning. Variables X and Y are irrelevant with respect to m, IR m (X ,Y ) if the marginal mass function on X is obtained by conditioning the joint mass function on values y of Y and marginalizing this conditioned joint mass function on X :

Definition 4 .Definition 5 .

 45 Two sources are cognitively independent if they do not communicate and if their evidential corpora are different. Evidential corpus is the set of all pieces of evidence held by a source.Not only communicating sources are considered dependent but also sources having the same background of knowledge since their beliefs are correlated. The aim of estimating sources independence is either to guide the choice of combination rules when aggregating their beliefs, or to integrate this degree of independence in a new combination rule.

  . . . . . . . . .

  . . . . . . . . .

3 :

 3 Map clusters l and c.

4 :

 4 Delete line l and column c from M.5: end while 6: return Cluster matching.

Figure 2 :

 2 Figure 2: Reliability factors α i k i

3 ,γ

 3 = 0.6 and γ = 1. When γ = 0, mixed and cautious combinations are equivalent; when γ = 1, mixed and conjunctive combinations are equivalent, otherwise it is a weighted average by γ ∈]0, 1[. Finally, to illustrate the proposed mixed combination rule and compare it to other combination rules, three mass functions are generated randomly using algorithm 2. These mass functions are combined with conjunctive, Dempster, Yager, disjunctive, cautious and mean combination rules. They are also combined with the mixed combination rule with different independence levels.

Figure 3

 3 Figure3illustrates distances5 between the mixed combination with several degrees of independence and combined mass functions using conjunctive, Dempster, Yager, disjunctive, cautious and mean combination rules. Distances between mixed combination with several independence degrees; and Yager, disjunctive, mean and Dempster's rules are linear and decreasing proportionally to γ.

a

  ∪ b ∪ c 0.3 0.3 0.1913 0.09 0.1913 0.1609 0.1305 0.09

6. 1 . 1 .

 11 Independent sourcesIn general, to generate mass functions some information are needed: the number of hypotheses in the frame of discernment, | Ω | and the number of mass func-

Figure 3 :

 3 Figure 3: Distances between combined mass functions

Algorithm 2 2 :

 22 Independent mass functions generating Require: |Ω|, n : number of mass functions 1: for i = 1 to n do Choose randomly | F |, the number of focal elements on [1, |2 Ω |].

3 :

 3 Choose randomly | F | focal elements noted F.

4 :

 4 Divvy the interval [0, 1] into |F| continuous sub-intervals.5:

  illustrates a consistent mass function where all focal elements {A, B, C, D} intersect.

Figure 4 :

 4 Figure 4: Consistent belief function

Algorithm 3

 3 Consistent mass functions generating Require: |Ω|, n : number of mass functions 1: for i = 1 to n do 2:

4 :

 4 Choose randomly | F |, the number of focal elements on [1, |S|].

5 : 6 :

 56 Choose randomly | F | focal elements from S noted F. Divvy the interval [0, 1] into |F| continuous sub-intervals.

7 :

 7 BBMs of focal elements are intervals sizes. 8: end for 9: return n consistent mass functions have the same focal elements; however, clusters contain mass functions with consistent focal elements. Clustering is performed according to focal elements and clusters are perfectly linked.

3 :

 3 Choose randomly | F |, the number of focal elements on [1, |S|].

4 :

 4 Choose randomly | F | focal elements from S noted F.

5 : 6 :

 56 Divvy the interval [0, 1] into |F| continuous sub-intervals.Focal elements BBMs are intervals sizes. 7: end for 8: return n consistent mass functions Table 2: Mean of 100 tests on 100 generated mass functions for two sources Dependence type Degree of independence Overall independenceIndependence I d (s 1 , s 2 ) = 0.68, Ī d (s 1 , s 2 ) = 0.32 γ = 0.68 I d (s 2 , s 1 ) = 0.68, Ī d (s 2 , s 1 ) = 0.32Dependence I d (s 1 , s 2 ) = 0.34, Ī d (s 1 , s 2 ) = 0.66 γ = 0.34I d (s 2 , s 1 ) = 0.35, Ī d (s 2 , s 1 ) = 0.656.2.2. Dependent sourcesIn the case of dependent sources, mass functions are generated ensuing algorithms 3 and 4. For tests, we choose | Ω |= 5 and n = 100. We generate 100 mass functions of both s 1 and s 2 for 100 times and then compute the average of I d (s 1 , s 2 ), I d (s 2 , s 1 ) and I(s 1 , s 2 ). Table

  following algorithms 3 and 4 when | Ω |= 5. The mean of 100 degrees of independence are illustrated in table 5.

a

  ∪ b ∪ c 0.28 0.41 0.74 0.15

  1 k 1 where 1 ≤ k 1 ≤ K for clusters of s 1 and Cl 2 k 2 where 1 ≤ k 2 ≤ K for those of s 2 . The similarity between two clusters Cl 1 k 1 and Cl 2 k 2 is the proportion of objects simultaneously classified into Cl 1 k 1 and Cl 2 k 2 :

Table 1 :

 1 Combination of two mass functions

	2 Ω	m 1 m 2 m ∧	m ∩ m Mixed m Mixed	m Mixed	m Mixed

table 4 .

 4 1, are provided by two sources s 1 and s 2 which independence degree is given in table 2. Combination of m 1 and m 2 is given in table 3.To illustrate the case of three independent sources, three sets of 100 independent mass functions are generated following algorithm 2 with | Ω |= 5. The mean of 100 tests are illustrated in Algorithm 4 Dependent mass functions generating Require: |Ω|, n : number of mass functions, d decision of another source 1: for i = 1 to n do

	2:

Table 3 :

 3 Mixed combination of m 1 and m 2

Table 4 :

 4 Mean of 100 tests on 100 generated mass functions for three independent sourcesI d (s 1 , s 2 ) = 0.67, Ī d (s 1 , s 2 ) = 0.33 I(s 1 , s 2 ) = 0.67 I d (s 2 , s 1 ) = 0.67, Ī d (s 2 , s 1 ) = 0.33 s 1 -s 3 I d (s 1 , s 3 ) = 0.68, Ī d (s 1 , s 3 ) = 0.32 I(s 1 , s 3 ) = 0.68 γ = 0.68 I d (s 3 , s 1 ) = 0.68, Ī d (s 3 , s 1 ) = 0.32 s 2 -s 3 I d (s 2 , s 3 ) = 0.68, Ī d (s 2 , s 3 ) = 0.32 I(s 2 , s 3 ) = 0.68 I d (s 3 , s 2 ) = 0.68, Ī d (s 3 , s 2 ) = 0.32provided by several sources. A pair of sources independence is deduced from weights of linked clusters after a matching of their clusters. Independence degree of sources can either guide the choice of the combination rule if it is either 1 or 0;when it is a degree over ]0, 1[, we propose a new combination rule that weights the conjunctive and cautious combinations with sources' independence degree.

	Sources	Degree of independence	Pairwise	Overall
			independence	independence
	s 1 -s 2

Table 5 :

 5 Mean of 100 tests on 100 generated mass functions for three dependent sourcesI d (s 1 , s 2 ) = 0.35, Ī d (s 1 , s 2 ) = 0.65 I(s 1 , s 2 ) = 0.34 I d (s 2 , s 1 ) = 0.34, Ī d (s 2 , s 1 ) = 0.66 s 1 -s 3 I d (s 1 , s 3 ) = 0.32, Ī d (s 1 , s 3 ) = 0.68 I(s 1 , s 3 ) = 0.31 γ = 0.35 I d (s 3 , s 1 ) = 0.31, Ī d (s 3 , s 1 ) = 0.69 s 2 -s 3 I d (s 2 , s 3 ) = 0.36, Ī d (s 2 , s 3 ) = 0.64 I(s 2 , s 3 ) = 0.35 I d (s 3 , s 2 ) = 0.35, Ī d (s 3 , s 2 ) = 0.65

	Sources	Degree of independence	Pairwise	Overall
			independence	independence
	s 1 -s 2

Table 6 :

 6 Mixed combination of m 1 , m 2 and m 3

	2 Ω	m 1	m 2	m 3	m Mixed

[START_REF] Shafer | A mathematical theory of evidence[END_REF], page 149

Big clusters are those containing enough mass functions according to | Ω |.

The maximum is used to insure the property of increasing with inclusion.

Jousselme distance detailed in equation (16).


Paul Lajoie-Mazenc

Emmanuelle Anceaume
email: emmanuelle.anceaume@irisa.fr

Gilles Guette

Thomas Sirvent
email: thomas.sirvent@m4x.org

Valérie Viet

Triem Tong

Privacy-Preserving Reputation Mechanism: A Usable Solution Handling Negative Ratings

Reputation mechanisms allow users to mutually evaluate their trust. This is achieved through the computation of a reputation score summarizing their past behaviors. Depending on these scores, users are free to accept or refuse to interact with each other. When users are virtual, volatile, or distant, an accurate evaluation of reputation scores is complex. Furthermore, users expect reputation mechanisms to preserve the privacy of their interactions and of their feedback. Existing solutions often rely on costly cryptographic tools that may lead to impractical solutions. In this article, we propose a usable privacy preserving reputation mechanism. This mechanism is distributed and handles non-monotonic ratings. Its implementation on cheap single board computers validates its adequacy to large-scale systems.

Introduction

Reputation mechanisms tend to be an effective tool to encourage trust and cooperation in electronic environments [START_REF] Dellarocas | Immunizing online reputation reporting systems against unfair ratings and discriminatory behavior[END_REF]. This is achieved by enabling users to rate services or people, based on their past experience. These ratings or feedback are aggregated to derive publicly available reputation scores. Reputation mechanisms either rely on a central authority or take advantage of the participating users to compute reputation scores. To circumvent the vulnerability of the former approach, both in terms of privacy and fault-tolerance, we present a reputation mechanism that meets security and trust requirements through distributed computations. While aggregating ratings is necessary to derive reputation scores, identifiers and ratings are personal data, whose collection and usage may fall under legislation [2]. Furthermore, as shown by recent works [START_REF] Narayanan | Robust de-anonymization of large sparse datasets[END_REF], solely relying on pseudonyms to interact is not sufficient to guarantee user privacy [START_REF] Steinbrecher | Enhancing multilateral security in and by reputation systems[END_REF]. This has given rise to the proposition of a series of reputation mechanisms which address either the non-exposure of the history of raters [START_REF] Bethencourt | Financial Cryptography and Data Security (FC)[END_REF], the non-disclosure of individual feedback [START_REF] Pavlov | Supporting privacy in decentralized additive reputation systems[END_REF][START_REF] Hasan | Preserving privacy of feedback providers in decentralized reputation systems[END_REF][START_REF] Kerschbaum | A verifiable, centralized, coercion-free reputation system[END_REF], the secrecy of ratings and the k-anonymity of ratees [START_REF] Clauß | k-anonymous reputation[END_REF], or the anonymity and unlinkability of both raters and ratees [START_REF] Bethencourt | Financial Cryptography and Data Security (FC)[END_REF][START_REF] Androulaki | Reputation systems for anonymous networks[END_REF]. Regrettably, the search for privacy has led to algorithmic restrictions, in the sense that handling solely non-negative ratings seems to be the sine qua non condition to preserve user privacy [START_REF] Bethencourt | Financial Cryptography and Data Security (FC)[END_REF][START_REF] Androulaki | Reputation systems for anonymous networks[END_REF]: existing privacy-preserving mechanisms give their users the opportunity to skip some of the received ratings to increase their privacy, which is unfortunately not compatible with negative ratings. Furthermore, Baumeister et al. explain that "bad feedback has stronger effects than good feedback" on our opinions [START_REF] Baumeister | Bad is stronger than good[END_REF]. Thus, it is crucial to allow clients to issue negative ratings.

In the remaining of the article, we present the design and evaluation of a non-monotonic distributed reputation mechanism preserving the privacy of both parties. This work is the continuation of our preliminary work [START_REF] Lajoie-Mazenc | Extending signatures of reputation. In: Privacy and Identity[END_REF]. After having presented the state of the art in Section 2, we present in Section 3 the properties that should be met by a reputation mechanism to be secure, to preserve the privacy of all parties, and to handle non-monotonic ratings. Section 4 provides a description of the main principles of our approach to build such a mechanism, and their orchestration is presented in Section 5. The main contribution of this paper is presented in Section 6. This section shows that this unprecedented mechanism is computationally efficient, and thus implementable in large-scale applications. Finally, Section 7 concludes.

State of the Art

One of the first examples of reputation mechanisms has been set up by eBay. In this mechanism, clients and service providers rate each other after each transaction: ratings are either +1, 0, or -1 according to the (dis)satisfaction of users. The reputation score of a user is simply the sum of the received ratings. Resnick and Zeckhauser have analyzed this mechanism and the effects of reputation on eBay [START_REF] Resnick | Trust among strangers in Internet transactions: Empirical analysis of eBay's reputation system[END_REF], and have highlighted a strong bias toward positive ratings. More elaborated reputations mechanisms have been proposed, such as the Beta Reputation System [START_REF] Jøsang | The beta reputation system[END_REF], methods based on the Dempster-Shafer theory of belief [START_REF] Yu | Distributed reputation management for electronic commerce[END_REF], or based on distributed hash tables [START_REF] Kamvar | The EigenTrust algorithm for reputation management in P2P networks[END_REF][START_REF] Anceaume | Incentive-based robust reputation mechanism for P2P services[END_REF][START_REF] Hasan | A decentralized privacy preserving reputation protocol for the malicious adversarial model[END_REF]. Jøsang et al. propose a broad survey of reputation mechanisms [START_REF] Jøsang | A survey of trust and reputation systems for online service provision[END_REF], while Marti and Garcia-Molina focus on their implementation in P2P systems [START_REF] Marti | Taxonomy of trust: Categorizing P2P reputation systems[END_REF]. Indubitably, the nature of ratings and the computation of reputation scores have been thoroughly researched. In this work, we do not make any assumptions regarding the function that computes reputation scores. Indeed, our solution handles both positive and negative ratings, and may thus use any computation function.

One of the first known reputation mechanism taking the privacy of users into account has been proposed by Pavlov et al. [START_REF] Pavlov | Supporting privacy in decentralized additive reputation systems[END_REF]. Their solution presents a series of distributed algorithms for computing the reputation score of service providers without divulging the ratings issued by clients. Their solution has been improved by Hasan et al. [START_REF] Hasan | Preserving privacy of feedback providers in decentralized reputation systems[END_REF][START_REF] Hasan | A decentralized privacy preserving reputation protocol for the malicious adversarial model[END_REF] for different adversary models, and stronger privacy guarantees. Similarly, Kerschbaum proposes a centralized mechanism computing the reputation scores of service providers without disclosing the individual ratings of the clients [START_REF] Kerschbaum | A verifiable, centralized, coercion-free reputation system[END_REF]. The secrecy of ratings contributes to the privacy of users, but is clearly insufficient: service providers can still discriminate their clients according to their identity or to additional information unrelated to the transaction. As we previously mentioned, identifiers and ratings can be considered personal data. Steinbrecher argues that reputation mechanisms must guarantee both the anonymity of their users, and the unlinkability of their transactions to be fully adopted [START_REF] Steinbrecher | Enhancing multilateral security in and by reputation systems[END_REF]. Both properties have been lately formalized by Pfitzmann and Hansen [START_REF] Pfitzmann | A terminology for talking about privacy by data minimization: Anonymity, unlinkability, undetectability, unobservability[END_REF]. Namely, a user is anonymous if this user is not identifiable within a set of users, called the anonymity set. The transactions of a user are unlinkable if the participants in two different transactions cannot be distinguished. Hence, Clauß et al. [START_REF] Clauß | k-anonymous reputation[END_REF] propose a centralized mechanism guaranteeing both the secrecy of ratings and the k-anonymity of service providers. However, beyond being centralized, this mechanism does not preserve the privacy of clients. Androulaki et al. [START_REF] Androulaki | Reputation systems for anonymous networks[END_REF] also propose a centralized reputation mechanism guaranteeing both the anonymity and the unlinkability of both parties. However, since providers send a request to the central bank for their ratings to be taken into account, only positive ratings are handled. In addition, this mechanism is vulnerable to ballot-stuffing attacks [START_REF] Dellarocas | Immunizing online reputation reporting systems against unfair ratings and discriminatory behavior[END_REF], that is, a single client can issue many ratings on a provider to bias her reputation. Whitby et al. [START_REF] Whitby | Filtering out unfair ratings in bayesian reputation systems[END_REF] propose a technique mitigating ballot-stuffing attacks, however their technique requires the ability to link the ratings concerning the same provider. Bethencourt et al. [START_REF] Bethencourt | Financial Cryptography and Data Security (FC)[END_REF] propose to compute such a link. That is, they propose a mechanism linking all the transactions that have occurred with the same partners, while preserving their privacy. However, beyond handling only positive ratings, their reputation mechanism requires high computational power, bandwidth and storage capacity. For instance, when proving their reputation score, providers must send about 500 KiB per received rating, which is unbearable from a practical point of view.

So far, preserving the privacy of both raters and ratees and handling both positive and negative ratings has been recognized as a complex challenge. Quoting Bethencourt et al., "Most importantly, how can we support non-monotonic reputation systems, which can express and enforce bad reputation as well as good? Answering this question will require innovative definitions as well as cryptographic constructions" [START_REF] Bethencourt | Financial Cryptography and Data Security (FC)[END_REF]. To the best of our knowledge, no distributed reputation mechanism preserves the privacy of its users and allow clients to efficiently issue both positive and negative ratings. This is the objective of this paper.

Model and Properties

Terminology. In the following, we differentiate transactions from interactions. A transaction corresponds to the exchange of a service between a client and a service provider, while an interaction is the whole protocol followed by the client and the provider, during which the clients get the provider's reputation and the client issues a rating on the provider. Note that we make no assumption about the nature of transactions: they can be, for example, web-based community applications or e-commerce ones. Once a transaction is over, the client is expected to issue a rating representative of the provider's behavior during the transaction.

Nevertheless, clients can omit to issue such a rating, deliberately or not. While dissatisfied clients almost always issue a rating, satisfied clients seldom do it. To cope with this asymmetry, we introduce the notion of proofs of transaction: a proof of transaction is a token delivered to providers for transactions during which the client did not issue a rating. Such proofs of transaction allow clients to distinguish between multiple providers that have the same reputation. We denote by report the proof of transaction associated with the client's rating, if any. These reports serve as the basis to compute reputation scores. Finally, we say that a user is honest if this user follows the protocol of the reputation mechanism. Otherwise, this user is malicious.

Model of the System. We consider an open system populated by a large number of users. A proportion of these users can be malicious (more details are given below). Before entering the system, users register to a central authority C, that gives them identifiers and certificates. Once registered, users do not need to interact with C anymore. A user can act as a client, as a service provider, or as both, and obtains credentials for both roles. We also assume that users communicate over an anonymous communication network, e.g. Tor [START_REF] Dingledine | Tor: The second-generation onion router[END_REF].

Properties of our Reputation Mechanism. Our reputation mechanism aims at offering three main guarantees to users. First and foremost, the privacy of users must be preserved. Second, users must always be able to cast their report. Finally, every data needed for the computation of reputation scores must be available and unforgeable. Privacy properties are stated in Properties 1 and 2, while Properties 3 and 4 are related to the undeniability of reports. Both properties expect that providers obtain proofs of transaction, and that clients are always able to cast ratings. Property 5 deals with reports unforgeability. Finally, Properties 6 and 7 respectively stipulate that the computation of the reputation scores cannot be biased by ballot-stuffing attacks, and that reputation scores are unforgeable. Note that since clients do not know the provider they are interacting with, targeted bad-mouthing attacks cannot be launched. Property 1. Privacy of service providers. When a client rates an honest service provider, this service provider is anonymous among all honest service providers with an equivalent reputation.

Property 2. Privacy of clients. When a provider conducts a transaction with an honest client, this client is anonymous among all honest clients. Furthermore, the interactions of honest clients with different providers are unlinkable. Property 3. Undeniability of ratings. At the end of a transaction between a client and a provider, the client can issue a valid rating, which will be taken into account in the reputation score of the provider. Property 4. Undeniability of proofs of transaction. At the end of a transaction between a client and a provider, the provider can obtain a valid proof of transaction.

Property 5. Unforgeability of reports. Let r be a report involving a client and a service provider. If r is valid and either the client or the provider is honest, then r was issued at the end of an interaction between both users. Property 6. Linkability of reports. Two valid reports emitted by the same client on the same service provider are publicly linkable.

Property 7. Unforgeability of reputation scores. A provider cannot forge a valid reputation score different from the one computed from all the reports assigned to this provider.

Building Blocks

Distributed Trusted Third-Parties

As explained in Section 1, service providers must not manage themselves their reputation score to guarantee their reliability. To solve this issue, we propose to construct a distributed trusted authority in charge of updating and certifying reputation scores. We call accredited signers the entities constituting this authority. This first distributed authority has two main features. Firstly, this authority must involve fairly trusted entities or enough entities to guarantee that the malicious behavior of some of them never compromises the computation of reputation scores. Secondly, this authority must ensure that providers remain indistinguishable from each other. Moreover, to ensure the undeniability of ratings, a client must be able to issue his report, even if the service provider does not complete the interaction. However, the precautions taken for that purpose must not imply sending identifying data before the transaction. In the same way, data identifying the client must not be sent before the transaction, even to ensure the undeniability of proof of transactions. To solve all these issues, we propose a distributed trusted authority in charge of guaranteeing that reports can be built. This distributed authority must collect information before the transaction, and potentially help one of the two parties afterwards; it must thus be online. We call share carriers the entities constituting this authority.

Both distributed authorities could be gathered in a single one. The drawback of this approach is that this distributed trusted authority should be simultaneously online, unique, and fairly trusted or reasonably large. The uniqueness and the participation in each interaction would induce an excessive load on each entity of this distributed authority. For efficiency reasons, we thus suggest distinct authorities. Accredited signers are then a unique set of fairly trusted or numerous entities, periodically updating the reputation scores of all providers. On the other hand, share carriers are chosen dynamically during each interaction among all service providers. Accredited signers manage every reputation score, and are thus critical in our mechanism. On the other side, share carriers are responsible for the issuing of a single report. Hence, they do not need to be as trustworthy as the accredited signers.

To deal with the privacy of both clients and providers, share carriers use verifiable secret sharing [START_REF] Feldman | A practical scheme for non-interactive verifiable secret sharing[END_REF]. This basically consists in disseminating shares of a secret to the share carriers, so that they cannot individually recover the secret, but allow the collaborative reconstruction of this secret.

Cryptographic tools

Our mechanism relies on cryptographic tools to guarantee its properties. The underlying structure of those tools is a bilinear group

Λ = (p, G 1 , G 2 , G T , e, G 1 , G 2 ) in which G 1 , G 2 , G T are
three groups of prime order p that we write multiplicatively. The map e :

G 1 × G 2 → G T is non-degenerate and bilinear. G 1 ∈ G 1 (resp. G 2 ∈ G 2 ) is a group generator of G 1 (resp. G 2 ).
First, our mechanism uses SXDH commitments [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF]. To commit to a value in G 1 or G 2 , one needs two random scalars. Then, our mechanism relies on the Non-Interactive Zero-Knowledge (NIZK) proof system proposed by Groth and Sahai [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], which allows users to prove their possession of secrets without revealing the secrets. Instead, the secrets are masked by SXDH commitments. For instance, this proof system allows users to compute Anonymous Proxy Signatures [START_REF] Fuchsbauer | Anonymous proxy signatures[END_REF], i.e. to sign messages without revealing the message, the signature, or their verification key. This requires particular signature schemes, e.g. Structure-Preserving Signatures [START_REF] Abe | Structurepreserving signatures and commitments to group elements[END_REF]. Finally, as previously mentioned, our mechanism relies on verifiable secret sharing. Such a scheme allows a prover to split a secret into n shares, and to reconstruct the secret from t shares (with t n). More specifically, the prover sends a share to n share carriers, and convinces a verifier that the verifier will be able to reconstruct the prover secret. To convince the verifier, the prover uses NIZKs to prove (a) the correctness of the secret, and (b) the consistency of the shares. An optimal choice for t is t = n/3 , which tolerates up to t -1 malicious share carriers. In this case, the verifier accepts the sharing as soon as 2t -1 share carriers have confirmed the reception of their share. The analysis leading to this choice is detailed in the companion paper [START_REF] Lajoie-Mazenc | Efficient distributed privacy-preserving reputation mechanism handling nonmonotonic ratings[END_REF].

As explained in Section 2, reputation mechanisms must defend themselves against ballot-stuffing attacks. Bethencourt et al. [START_REF] Bethencourt | Financial Cryptography and Data Security (FC)[END_REF] propose such a method by computing a value that depends only on the client and the provider, but that does not allow different providers to compare their clients. We propose a similar method, yet simpler, allowing to compute such an invariant. Let Id SP ∈ G 1 (resp. id Cl ∈ Z p ) be the identifier of the provider (resp. client). We then define the invariant as inv = Id SP id Cl . Note that the invariant must not be computed directly: it requires the client to know the provider's identifier, and vice versa. Hence, they jointly compute the invariant in three steps, which require an additional group element Y 1 ∈ G 1 . First, the provider computes a pre-invariant with randomness r ∈ Z

p : pre_inv = (G 1 r , Id SP •Y 1 r ). The client then ran- domly chooses s ∈ Z p to compute a masked invariant: masked_inv = (G 1 s • Y 1 id Cl , pre_inv 1 s • pre_inv 2 id Cl ).
Finally, the provider obtains the invariant from masked_inv: inv = masked_inv 2 • masked_inv 1 -r = (Id SP ) id Cl . Note that the invariant is computed after the transaction, otherwise the provider would know whether she has already interacted with the client or not, which might introduce a bias in the provision of the service.

Throughout the reputation protocol, users need cryptographic keys and identifiers. Specifically, the central authority C uses a structure-preserving signature key pair (vk C , sk C ) to generate certificates on users' credentials. To enter the system, users register to this authority, which may require a computational or monetary cost to mitigate Sybil attacks. Note that this authority is required only for the registration of users, and possibly for the choice of accredited signers.

Clients have a structure-preserving signature key pair, consisting of a verification key vk Cl and a signing key sk Cl . When clients enter the system, they register to the central authority C to get a random identifier id Cl ∈ Z p , and a certificate cert Cl on id Cl and vk Cl . Similarly, service providers have a structurepreserving signature key pair (vk SP , sk SP ), and register to C to obtain a random identifier Id SP ∈ G 1 , and a certificate cert SP on Id SP and vk SP .

Accredited signers have a structure-preserving signature key pair (vk AS , sk AS ) and a certificate cert AS on vk AS . They use these keys to sign the reputation score of service providers at regular intervals, that we call rounds. We denote by σ i the signature of the i-th accredited signer on the reputation score rep SP of the provider, for current round rnd, i.e. a signature on vk SP , H(rep SP , rnd) . In the following, n AS represents the number of accredited signers. We assume that a majority t AS of them are honest.

Share carriers possess two key pairs, namely a classical encryption key pair (ek SC , dk SC ), and a classical signature key pair (sk SC , vk SC ), used to encrypt received messages and sign sent messages. They also have a certificate cert SC on ek SC and vk SC , issued by the central authority C.

Both clients and providers compute by themselves their own pseudonyms. They renew them at each interaction. Pseudonyms nym Cl and nym SP are SXDH commitments to verification keys vk Cl and vk SP . Similarly, both clients and service providers compute commitments C id Cl and C IdSP to their identifiers id Cl and Id SP . Clients compute commitments C cert Cl to their certificate, and NIZK proofs of their validity Π cert Cl . Similarly, service providers compute commitments C certSP and proofs Π cert Cl . Finally, service providers compute a pre-invariant pre_inv from Id SP and a randomly chosen scalar r pre_inv .

Due to space constraints, we defer the cryptographic proofs of the security of our protocol as well as figures detailing this protocol in a companion article [START_REF] Lajoie-Mazenc | Efficient distributed privacy-preserving reputation mechanism handling nonmonotonic ratings[END_REF].

Proof of the Reputation Score

When a client wishes to interact with a service provider, he sends a pseudonym nym Cl and a proof of its validity C id Cl , C cert Cl , and Π cert Cl to the provider. Once the provider has verified this proof, she chooses a nonce s SC and commits to it by computing C SC = H(00 s SC ). 5 Then, the provider sends back her pseudonym, reputation, pre-invariant and respective proofs of validity, and committed nonce. That is, she sends nym SP , C IdSP , C certSP , Π certSP , rep SP , a proof of reputation Π rep , pre_inv, a proof Π pre_inv of its computation while masking Id SP and r pre_inv , and C SC .

If the client is satisfied with the reputation of the provider, and if all the proofs are valid, the client computes the masked invariant masked_inv, chooses a nonce r SC , computes a signature σ Cl on H(C SC , r SC , nym SP ), and sends r SC and σ Cl to the provider. If σ Cl is valid, the provider computes a signature on H(s SC , r SC , nym Cl ), and sends s SC and σ SP to the client. Note that the signatures guarantee that the client agreed to conduct a transaction with provider nym SP , who uses the randomness hidden in C SC , and that the provider agreed to conduct a transaction with client nym Cl , who uses randomness r SC . Once the client and the provider have exchanged their nonces, they choose the share carriers, using (s SC r SC nym Cl nym SP ) as a seed. For that purpose, they iterate a hash function, e.g. SHA-256 [29], to randomly select n SC share carriers among all service providers. In the remainder, this seed serves as an identifier of the transaction, and we note it id trans .

During this step, the client sends one element in Z p , 86 in G 1 , and 74 in G 2 to the provider, while the provider sends 3 element in Z p , (74t AS +92) in G 1 , and (66t AS + 84) in G 2 . Once this step is over, besides being mutually authenticated, the provider has proven her reputation score to the client, each party is able to prove the implication of the other one in the interaction, and they finally have jointly and independently chosen the share carriers.

Sharing Ingredients of the Report

The client and the service provider now rely on the verifiable secret sharing scheme to guarantee the undeniability properties. The service provider shares her identifier Id SP , that is, she chooses a polynomial Q of degree t SC -1, with coefficients Id SP , A 1 , . . . , A tSC-1 , where the A j are randomly chosen in G 1 . The shares are the i, Q i = Q(i) for 1 i n SC . To prove the sharing, the provider computes commitments C Aj to the A j , and NIZK proofs Π Qi that share Q i was generated from Id SP and from the A j for 1 i n SC , while masking Id SP and the A j . Note that nym SP , C IdSP , C certSP and Π certSP have already proven the correctness of the secret, that is Id SP . Finally, the provider sends the (C Aj ) to the client, and encrypts and sends id trans , (i, Q i ), C IdSP , (C Aj ) 1 j<tSC , and Π Qi to the i-th share-carrier. If the received proof is valid, the share carriers send a confirmation to the client, that is id trans , i, C IdSP , and (C Aj ), together with a signature. If these commitments are the same as the one received from the provider, the client accepts this confirmation: all the shares were generated from the same polynomial, which evaluates to the correct secret, Id SP , in 0. Since the validity of the shares guarantees the undeniability properties, the client accepts the sharing once he has received 2t SC -1 valid shares. This requires for the provider to send (2t SC -2) elements in G 1 to the client, and 4 in Z p , (2t SC + 3) in G 1 , and 4 in G 2 to each share carrier. Each share carrier sends 2 elements in Z p and 2t SC in G 1 to the provider.

In the meantime, the client shares his secret, that is the masked invariant masked_inv. Since masked_inv consists of two elements, he must double the sharing. That is, the client chooses two polynomial R 1 , R 2 of degree t SC -1 with coefficients masked_inv k , B 1,k , . . . , B tSC-1,k for k ∈ {1, 2}, and the shares are i, R i = R 1 (i), R 2 (i) for 1 i n SC . To prove the sharing, the client computes commitments C masked_inv and C B j,k to masked_inv and to the B j,k , and NIZK proofs Π Ri that R i was generated from masked_inv and from the B j for 1 i n SC , while masking masked_inv and the B j . To prove the correctness of the secret, the client also computes a proof Π C masked_inv guaranteeing the computation of masked_inv, while masking masked_inv, id Cl , and the randomness used. Thus, the client sends C masked_inv , (C B j,k ), and Π C masked_inv to the provider, and encrypts and sends id trans , (i, R i ), C masked_inv , (C B j,k ), and Π Ri to the i-th share carrier. As previously, the i-th share carrier sends a confirmation consisting of id trans , i, C masked_inv , (C B j,k ), and a signature to the provider if the share is valid. The provider accepts such a confirmation if the commitments are identical to the ones she received, and accepts the sharing as soon as she has received 2t SC -1 valid confirmations. Thus, the client sends one element in Z p , (4t SC + 14) in G 1 and 16 in G 2 to the provider, and 2 in Z p , (4t SC + 6) in G 1 and 8 in G 2 to each share carrier. Each share carrier sends 2 elements in Z p and 4t SC in G 1 to the provider. Once this step is over, the client is ensured that he will be able to obtain Id SP to issue the report. Similarly, the provider is guaranteed that she will be able to obtain a proof of transaction through the computation of masked_inv.Therefore, both parties can conduct their transaction.

Construction of the Reports

Once the transaction is over, the client can issue a rating and the provider can obtain a proof of transaction. Scenario A describes their interactions.

Scenario A -Nominal case. The client chooses a rating ρ and computes a signature σ ρ,Cl on H(id trans , ρ) to prevent any modification on ρ, and a proof Π masked_inv of the computation of masked_inv, while masking id Cl and the randomness used. It is very important to note that the identity of the provider is preserved until the client issues and signs his rating, which fully preserves the objectivity of the rating. Once this is achieved, the provider can reveal her identity to the share carriers and even to the client. This allows the rating to be affected to the identity of the provider without allowing bad-mouthing attacks. Note also that by doing so, reputation scores reflect all the provider's interactions, not those conducted under a specific pseudonym. Since masked_inv no longer needs to be hidden, Π masked_inv is a simpler proof than Π C masked_inv . The client sends message m 1 to the provider, with m 1 = (id trans , ρ, masked_inv, Π masked_inv , σ ρ,Cl ). If both the proof and signature are valid, the provider computes the invariant inv from masked_inv and r pre_inv , and a signature σ ρ,SP on H(id trans , σ ρ,Cl ). Note that since the provider reveals her identity, this signature is a structure-preserving signature, not an anonymous proxy signature. The provider then reveals her identifier, opens commitments nym SP and C IdSP , and reveals r pre_inv . These proofs, denoted by Π SP , guarantee both the computation of pre_inv and that this provider is the one hidden behind nym SP . The provider The client verifies Π SP and signature σ ρ,SP . Finally, both the client and the provider are able to issue the report by sending the elements given in the first column of Table 1 to the share carriers (where the first four lines represent the proof of transaction and the last one the rating together with the signatures of both parties). If all the signatures and proofs are valid, the report itself is considered valid by the share carriers. This scenario completes successfully if both parties are honest. If the client does not send message m 1 (resp. the provider does not send message m 2 ) then scenario B (resp. scenario C) is run. Finally, if neither the client nor the provider issue the report, then the transaction is not taken into account in the reputation score of the service provider. If this step proceeds correctly, the client sends 2 elements in Z p , 14 in G 1 , and 14 in G 2 to the provider. Similarly, the provider sends 7 elements in Z p , 19 in G 1 , and 12 in G 2 . The report is composed of 11 elements in Z p , 143 in G 1 , and 116 in G 2 .

Scenario B -Dishonest client. If the provider does not receive message m 1 from the client, she queries the share carriers for their share by sending them id trans . On their turn, they query the client to get his rating and, in absence of his answer, send their shares (i, R i ) and associated proofs Π Ri to the provider. The provider is then able to reconstruct the masked invariant masked_inv from t SC valid received shares. From that point, the provider can compute inv from masked_inv and r pre_inv and issue the report, which only contains the proof of transaction (i.e., the elements in the second column of Table 1). During this step, the provider sends one element in Z p to each share carrier, while each of them sends back to her one element in Z p , 6 in G 1 , and 8 in G 2 . The report is made of (t SC + 10) elements in Z p , (10t SC + 132) in G 1 , and

(8t SC + 108) in G 2 .
Scenario C -Dishonest provider. If the client does not receive message m 2 from the provider, he sends the masked invariant and his rating together with their associated proofs and signatures to the share carriers. That is, the client

sends id trans , nym Cl , C id Cl , C cert Cl , Π cert Cl , nym SP , C idSP , C certSP , Π certSP , pre_inv, Π pre_inv , masked_inv, Π masked_inv , ρ, σ ρ,Cl
. If all the proofs and signatures are valid, the share carriers forward them to the provider to give her the opportunity to reveal Id SP and the invariant. In absence of any response, the share carriers send their share (i, Q i ) and associated proof Π Qi to the client. Note that they also compute a signature σ ρ,SCj on H(id trans , σ ρ,Cl ) to validate the fact that the client has chosen his rating before knowing the provider's identity. Once the client has received t SC valid shares, he reconstructs Id SP , computes inv from Id SP and id Cl , and computes a proof Π inv of the computation of inv while masking id Cl . Finally, the client issues the report by sending the elements presented on the third column of Table 1 to the share carriers. In this step, the client sends 4 elements in Z p , 202 in G 1 , and 178 in G 2 to each share carrier. Each share carrier sends back one element in Z p , 3 in G 1 , and 4 in G 2 . Finally, the report is made of (t SC + 4) elements in Z p , (5t SC + 192) in G 1 , and (4t SC + 164) in G 2 .

Computation of the Reputation Scores

At the end of round rnd, each share carrier gathers all the reports received since round rnd -1, and sends them to the accredited signers. This allows the accredited signers to update the reputation scores of all the service providers concerned by valid reports. Once accredited signers have checked the validity of a report, they only keep the identifier of the provider, the identifier of the transaction, the invariant inv, and the rating of the client, if any, and sign them. Note that if two (or more) reports have the same identifier of transaction and invariant, they keep a single one to avoid duplicates. Beyond handling negative ratings, the accredited signers know the rounds during which reports have been cast. Thus, as described in Section 2, any reputation score function can be used, e.g. to lower the influence of old ratings [START_REF] Jøsang | The beta reputation system[END_REF] or to limit the impact of ballot-stuffing attacks [START_REF] Whitby | Filtering out unfair ratings in bayesian reputation systems[END_REF]. In addition, the accredited signers approximate the reputation score of providers to extend their anonymity set. Once the accredited signers have computed the reputation score of a provider, they compute a signature σ i on vk SP , H(rep SP , rnd) and send it to the provider. Service providers can use these signatures to prove their reputation to their clients during round rnd +1.

Performance Evaluation

We now evaluate our privacy-preserving reputation mechanism both in theoretical and practical ways. The former evaluation is achieved through an analysis of the performance of each building block, while the latter relies on its implementation on a platform made of heterogeneous computing nodes. The number of share carriers n SC and the number of accredited signers n AS are respectively equal to n SC = 28 and n AS = 1. This setting is sufficient to prevent the collusions of n SC /3 -1 = 9 share carriers with probability 2 -20 in a system comprising 10 8 service providers, including 5 × 10 6 malicious ones. This analysis, based on the hypergeometric distribution, appears in a companion paper [START_REF] Lajoie-Mazenc | Efficient distributed privacy-preserving reputation mechanism handling nonmonotonic ratings[END_REF].

Theoretical Study

The correctness of our mechanism relies on the verification of NIZK proofs, which requires the computation of many pairings. To decrease the number of these operations, we adopt the technique proposed by Blazy et al. [START_REF] Blazy | Batch groth-sahai[END_REF] which consists in verifying NIZKs by batches. We also ensure efficient pairing computations by relying on prime-order elliptic curves [START_REF] Aranha | Faster explicit formulas for computing pairings over ordinary curves[END_REF]. We consider elliptic curves in a subclass of the Barreto-Naehrig family. Thus, elements of Z p and G 1 (resp. G 2 ) can be represented by 32 B (resp. 64 B). We use the computation costs given by Aranha et al. [START_REF] Aranha | Faster explicit formulas for computing pairings over ordinary curves[END_REF]. Namely, the four cores of a 3.0 GHz AMD Phenom II X4 940 processor -a top-level processor of 2010 -can compute 8 pairings in a millisecond, 16 exponentiations in G 2 , or 48 in G 1 . In the following, we study two metrics, namely (a) the size of messages exchanged between each entity, and (b) the time necessary for each entity to perform his computation. We now present and comment the main results obtained with these settings. Table 2 gives the size of messages (in KiB) exchanged between the different parties involved in the reputation mechanism, namely, between the client and the provider, the client and one share carrier, and the provider and one share carrier before the transaction takes place. Finally, it gives the size of the report sent to the accredited signer once the transaction is over. These results are both satisfactory and reassuring. The largest messages correspond to the proof of reputation, which comprises the mutual authentication of the service provider and the client, and the proof by the provider of his reputation score. Nevertheless, this exchange requires only around 20 KiB. This is impressive compared to the mechanism proposed by Bethencourt et al. [START_REF] Bethencourt | Financial Cryptography and Data Security (FC)[END_REF], where the proof of reputation requires 500 KiB per received rating. Table 2 also shows that share carriers only need 3 KiB when a transaction goes well, and less than 10 KiB in the worst case situation. This clearly shows that the design of a distributed trusted third party requires very little resources. The same comment applies for the accredited signers. The size of the report, that comprises all the proofs, requires no more than 20 KiB in the worst case. It is important to note that the only message that scales (linearly) as a function of the number of the accredited signers is the proof of reputation. Thus, even for larger sets of accredited signers, which typically do not grow to more than 20 entities, the communication cost remains acceptable. These results are very reassuring because they show that, from a theoretical point of view, privacy-preserving reputation mechanisms are entirely viable. The next section will show that this holds in practice! Figure 1 details the computation cost (in ms) of each phase of the reputation mechanism for each of the involved entities. Several remarks are in order. The main one is that computation times are very low. Indeed, each user needs no more than 200 ms for all their computations. In particular, each share carrier needs no more than 6 ms when both the client and the provider are honest. Even in the worst case, they need only 75 ms to perform their computations. Finally, the verification of a report requires between 45 ms and 90 ms. This clearly shows that participating to one of the two distributed trusted third parties computing entities costs little. Actually, the largest costs are due to scenarii B or C. We can minimize those costs by penalizing malicious users, e.g. by preventing them from interacting for a given period of time.

Implementing the Reputation Mechanism

We have implemented our reputation mechanism in Python 2.7 with the Charm framework [START_REF] Akinyele | Charm: a framework for rapidly prototyping cryptosystems[END_REF]. This framework facilitates the implementation of complex cryptographic primitives, such as Groth-Sahai's NIZK proof system [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], and the combination of multiple primitives, e.g., to build anonymous proxy signatures [START_REF] Fuchsbauer | Anonymous proxy signatures[END_REF]. Furthermore, Charm provides the means to benchmark applications, both by giving their running time and by counting each elementary cryptographic operation. We also use Twisted, an event-driven networking engine, to handle communications between the different parties. Experiments have been conducted on heterogeneous entities, namely, a virtual machine running on a Dell Latitude E6430 laptop with a 2.60 GHz Core i7-3720 QM processor, and cheap Raspberry Pi model B machines with the Raspbian operating system.

Figure 2 presents the results of the conducted experiments. It shows the mean and standard deviation of the computation times of each user for every step of the interaction, namely, the proof of reputation, the sharing, and the issuing of the report in every scenario. Note that the "SC" columns correspond to the computation times of one share carrier running on the virtual machine, and that the "AS" columns relate to the verification of one report by an accredited signer.

Clearly, the computation times are higher than the one obtained in theory, which can easily be explained. First, Aranha et al. carefully select a Barreto-Naehrig curve, and optimize the computation of pairings using Assembly and C code on this specific curve [START_REF] Aranha | Faster explicit formulas for computing pairings over ordinary curves[END_REF]. In our case, we rely on the MNT-159 curve proposed by Charm, which is a Python framework wrapping around Lynn's pbc library. 6 Furthermore, the theoretical number of operations per second assumes that they are all ran in parallel, which is not the case in our experiments. Finally, all the users except one share carrier were run on a single virtual machine. This does not slow down the phases where users run computations sequentially, e.g. the proof of reputation or the construction of the report in Scenario A, but it does slow down the concurrent ones, e.g. the sharing of the secrets.

Even with those limitations, we observe that our mechanism allows clients to interact with providers, and to run all the preparation in no more than 5 s. Issuing the report may take longer, but the most important point is that clients can rapidly verify the reputation of a provider and get involved in the transaction. Similarly, the pre-transaction and the post-transaction phases respectively require no more than 5 s and 1 s which clearly allows the provider to interact with many clients simultaneously. Note that share carriers can even be run on cheap Raspberry Pi machines. In that case, sharing the secrets requires no more than 4.7 s, while issuing the rating in presence of malicious clients needs no more than 59 s. Such cheap machines increase the waiting time of both clients and providers, but this delay remains acceptable (less than 15 s), compared for example to the time required to buy items on any e-commerce web sites. Finally, running clients on Raspberry Pi requires about 75 s for conducting the reputation proof and 115 s for the sharing. That is, clients need about 3 min before being able to conduct a transaction, which is clearly reasonable to engage in (possibly) financial transactions.

Conclusion

In this article, we have presented a privacy-preserving distributed reputation mechanism. Beyond being non-monotonic, this mechanism reveals to be fully usable even with cheap on-board computers. This is a very encouraging result as it shows that privacy does not impede utility and accuracy. This has been achieved by combining distributed algorithms and cryptographic schemes. Our mechanism is independent of the reputation model, that is, our system can integrate any reputation model [START_REF] Jøsang | The beta reputation system[END_REF], preferably one using both positive and negative ratings.

As future works, we plan to study more deeply an off-line version of the secret sharing, which requires the share carriers only in Scenarii B and C, and to improve the report verification when the service provider does not want to collaborate.

Fig. 1 .

 1 Fig. 1. Theoretical computation times (ms)

Table 1 .

 1 Components of the report in the three scenarii Id SP , nym SP , PCertSP, IdSP, (CA j )j, {ij, Qi j , ΠQ i j }j Client C id Cl , nym Cl , PCert Cl C id Cl , nym Cl , PCert Cl C id Cl , nym Cl , PCert Cl Trans. id. idtrans, σSP, σ Cl idtrans, σSP, σ Cl idtrans, σSP, σ Cl Invariant pre_inv, masked_inv, inv, r pre_inv , Π masked_inv pre_inv, masked_inv, inv, r pre_inv , (CB j,k ), {ij, Ri j , ΠR i j }j, C masked_inv , ΠC masked_inv inv, Π inv Rating ρ, σ ρ,Cl , σρ,SP ρ, {σρ,SC i j }j sends message m 2 to the client, with m 2 = (Id SP , vk SP , cert SP , inv, Π SP , σ ρ,SP ).

	Scenario A	Scenario B	Scenario C
	Provider IdSP, vkSP, certSP, nym SP ,	IdSP, vkSP, certSP, nym SP ,	C
	C Id SP , ΠSP	C Id SP , ΠSP

Table 2 .

 2 Size of exchanged messages for nSC = 28 and nAS = 1, in kibibytes

	Phase	Cl ↔ SP Cl ↔ SCi SP ↔ SCi report
	Proof of Reputation	22	0	0	-
	Sharing	3.28	2.69	2.34	-
	Scenario A	2.94	0	0	12.06
	Scenario B	0	0	0.75	19.63
	Scenario C	0	17.94	0	20.75

This concatenation guarantees that sSC and rSC are chosen independently.

http://crypto.stanford.edu/pbc/

This work was partially supported by the ANR French project AMORES (grant #ANR-11-INSE-010).