Paul Lajoie-Mazenc

Emmanuelle Anceaume
email: emmanuelle.anceaume@irisa.fr

Gilles Guette

Thomas Sirvent
email: thomas.sirvent@m4x.org

Valérie Viet

Triem Tong

Efficient Distributed Privacy-Preserving Reputation Mechanism Handling Non-Monotonic Ratings

Keywords: Reputation Mechanisms, Security, Privacy, Distributed Systems

come

I. INTRODUCTION

Reputation mechanisms have come out as an effective tool to encourage trust and cooperation in electronic environments, e.g. e-commerce applications or web-based communities. A reputation mechanism enables users to rate services or people based on their experience [START_REF] Hamilton | Report on trust and reputation models[END_REF]. These ratings or feedback are aggregated to derive reputation scores. Scores are publicly available, which allows any user to evaluate the trustworthiness of target entities (the ratees). Thus, reputation mechanisms identify capable entities and discourage others from behaving incorrectly [START_REF] Dellarocas | Immunizing online reputation reporting systems against unfair ratings and discriminatory behavior[END_REF]. Some reputation mechanisms require a central authority to correctly process ratings and compute reputation scores, while others rely on distributed components. The former design introduces a single point of vulnerability, allowing a single entity to fully control all reputation scores. As will be shown in the following, our reputation mechanism meets security and trust exigences through distributed computations.

While aggregating ratings is necessary to derive reputation scores, identifiers and ratings are personal data, whose collect and use may fall under legislation [START_REF]European Parliament and Council of the European Union. Directive 95/46/EC[END_REF]. 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 | Signatures of reputation[END_REF], the non-disclosure of individual feedback [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], [START_REF] Pavlov | Supporting privacy in decentralized additive reputation systems[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] Androulaki | Reputation systems for anonymous networks[END_REF], [START_REF] Bethencourt | Signatures of reputation[END_REF].

Regrettably, the search for privacy has led to restrictions in the computation of the reputation score: clients cannot issue negative ratings anymore [START_REF] Androulaki | Reputation systems for anonymous networks[END_REF], [START_REF] Bethencourt | Signatures of reputation[END_REF]. This restriction comes from the management of ratings. In existing privacy-preserving mechanisms, the ratees have the opportunity to skip some of the received ratings to increase their privacy. This is not conceivable in a non-monotonic reputation mechanism: ratees could skip negative ratings to increase their reputation scores. This is a problem because a ratee that received a thousand positive ratings and no negative ratings is indistinguishable from a ratee that received a thousand positive ratings and a thousand negative ratings. This clearly does not encourage ratees to behave correctly. 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]. Negative ratings are thus essential to reputation mechanisms. 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 | Signatures of reputation[END_REF].

The design of privacy-preserving non-monotonic reputation mechanisms is highly desirable in many applications, where both quality of service and privacy are very important. This is particularly true in all audit processes, and web-based community applications. As an example, let us focus on an application concerning all of us, the scientific peer review process.

This process is at the core of many scientific committees, including those of conferences, journals, and grant applications. Its goal is to assess the quality of research through experts, the peer reviewers, that evaluate manuscripts and proposals based on their scientific quality, significance, and originality. Peer reviewing is an activity that requires to spend considerable effort and time for doing legitimate, rigorous and ethical reviews. Reviewers are chosen by committee members among all their colleagues and peers. In order to remove any bias, several reviewers are assigned to each manuscript, and the reviews are double-blind. The increasing number of solicitations makes the reviewing task even more challenging and, by force of circumstances, may lower the quality of reviews.

Imagine now a privacy-preserving reputation mechanism whose goal would be to assess reviews according to their helpfulness and fairness. Authors would anonymously rate each received review according to both criteria. Journal editors or committee chairs would collect these ratings to update the reputation score of the concerned reviewers. Those reputations would be maintained in a very large shared anonymous repository organized according to the thematic of the anonymized reviewers. Editors and chairs would then have the opportunity to choose anonymous reviewers from this repository according to their reputation to build their reviewing committee. The rationale of such a repository is three-fold. Authors would have an incentive to honestly and carefully rate each received review as their goal would be to contribute to the creation of a pool of helpful and fair reviewers. Committee chairs would take advantage of using such a repository as they could decrease the load imposed to each selected reviewer by soliciting a very large number of them. Consequently, each reviewer could devote more time to their few reviews, and would thus provide highly helpful reviews, increasing accordingly the quality of published articles or granted applications. Finally, it would be at reviewers' advantage to provide helpful reviews to have a high reputation, which would be a unanimous acknowledgment of their expertise. As a consequence, such an anonymous repository would increase the quality of accepted manuscripts and proposals in a fully privacy-preserving way.

In the remaining of the paper, we present the design and evaluation of a non-monotonic distributed reputation mechanism preserving the privacy of both parties. After having presented the state of art in Section II, we motivate and present the properties that should be met by a reputation mechanism to be secure, to respect the privacy of all its parties, and to handle non-monotonic ratings in Section III. Section IV then provides a description of the main principles of our approach to build such a mechanism. As detailed in Section V, it relies on two distinct distributed third-parties and cryptographic tools. The orchestration of these tools is presented in Section VI. We finally show in Section VII that this unprecedented mechanism is computationally efficient, and thus implementable in largescale applications. Section VIII concludes.

II. 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 using Distributed Hash Tables to collect ratings or manage reputation scores [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], [START_REF] Kamvar | The EigenTrust algorithm for reputation management in P2P networks[END_REF]. Jøsang et al. propose a broad survey of reputation mechanisms and reputation score functions [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 are data that can be considered personal. Specifically, as pointed out by Mahler and Olsen [START_REF] Mahler | Reputation systems and data protection law[END_REF], the European Directive 95/46/EC on data protection states that "the data [must not] be excessive in relation to the purposes for which they are processed" [START_REF]European Parliament and Council of the European Union. Directive 95/46/EC[END_REF]. A priori, the identity of users have no relation to their behavior. Thus, identities have no added utility for reputation mechanisms and are not necessary. 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, pseudonymity, and identity management[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 kanonymity of service providers. However, this mechanism does not preserve the privacy of clients. Androulaki et al. [START_REF] Androulaki | Reputation systems for anonymous networks[END_REF] propose a centralized reputation mechanism guaranteeing both the anonymity and 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 ballotstuffing 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. Hence, a provider with thousands of positive ratings from a single client is indistinguishable from a provider with positive ratings from thousands of different users, which is problematic.

Whitby et al. [START_REF] Whitby | Filtering out unfair ratings in bayesian reputation systems[END_REF] propose a technique mitigating ballotstuffing attacks, however, such a technique requires the ability to link the ratings concerning the same provider. Bethencourt et al. [START_REF] Bethencourt | Signatures of reputation[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 (client and service provider), while preserving their privacy. However, their reputation mechanism requires high computational power, bandwidth and storage capacity. For instance, when proving their reputation score, providers must send about 500 kB per received rating, which is from a practical point of view unbearable. Furthermore, clients cannot issue negative ratings.

We are not aware of any reputation mechanism preserving the privacy of its users and allowing clients to issue negative ratings. So far, achieving both at the same time has been recognized as a complex challenge. This is the objective of this paper.

III. MODEL AND PROPERTIES

A. Terminology

In the following, we differentiate transactions from interactions. More precisely, a transaction corresponds to the exchange of a service between a client and a service provider. An interaction corresponds to the whole protocol followed by the client and the provider, during which the clients gets 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 reviews, web-based community applications, or the purchase and delivery of physical goods.

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, this is not the case of satisfied clients. 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 when 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. Finally, a report or a reputation score is valid if an honest user accepts it. A more rigorous definition is given in Section VI.

B. Model of the System

We consider an open system populated by a large number of users, who can be malicious. 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 assume that users communicate over an anonymous communication network, e.g. Tor [START_REF] Dingledine | Tor: The secondgeneration onion router[END_REF], to prevent the tracking of their IP addresses.

C. Properties of Reputation Mechanisms

Our reputation mechanism aims at offering three main guarantees to users. First and foremost, the privacy of users must be preserved. Second, the issuing of reports must take place without any problems. Finally, every data needed for the computation of reputation scores must be available and unfalsifiable. Note that we only give intuitive views of the properties; we defer their formal statements and their proofs in Appendix B.

Privacy properties are detailed by Property 1 and 2. Property 1 stipulates that clients do not know the service providers they interacted with when they rate them. Property 2 claims that any two clients have to remain indistinguishable. Properties 3 and 4 are related to the undeniability of reports. These properties expect that providers obtain proofs of transaction, and that clients are able to issue ratings. Property 5 tackles with the unforgeability of reports. Finally, Properties 6 and 7 respectively stipulate that computation of the reputation scores cannot be biased by ballot-stuffing attacks, and that reputation scores are unforgeable.

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 service provider conducts a transaction with an honest client, this client is anonymous among all honest clients. Furthermore, the interactions of honest clients with different service providers are unlinkable.

Property 3: Undeniability of ratings. At the end of a transaction between a client and a service 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 service 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 service provider cannot forge a valid reputation score different from the one computed from all her reports.

IV. PRINCIPLES OF THE SOLUTION

A. Distributed Trusted Third-Parties

We explained in Section I that 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 others.

Moreover, to ensure the undeniability of ratings (Property 3), 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 to ensure the undeniability of proof of transactions (Property 4).

To solve this issue, 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. We thus suggest distinct authorities, for efficiency reasons. 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.

B. Sketch of the Protocol

The ultimate goal of our solution is to provide clients with an access to a shared repository, in which a list of services are recorded together with the reputation scores of the anonymous providers that supply those services. Clients can select services based on the displayed reputation score, which automatically sends an anonymous invitation to the associated providers. The service provider replies by sending her pseudonym, and proofs that both the pseudonym and the displayed reputation are valid. Since providers and clients must not reveal any personal information, they both use zero-knowledge proofs of knowledge [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] to prove the validity of their pseudonyms. Note that both clients and providers compute their own pseudonyms, which they are free to renew at each interaction. Providers and clients also need to sign their messages to guarantee their integrity, without revealing their identity. They thus use anonymous proxy signatures [START_REF] Abe | Structure-preserving signatures and commitments to group elements[END_REF]. Meanwhile, they agree on the set of share carriers they will rely on.

The next step of the protocol guarantees the undeniability of ratings and proofs of transaction. As aforementioned, a provider uses verifiable secret sharing to split her identifier among all share carriers. Thanks to the zero-knowledge proof system, the provider is also able to prove that the secret was correctly shared. Similarly, the client uses verifiable secret sharing and zero-knowledge proofs of knowledge to guarantee that the provider will obtain a proof of transaction. Once this step is over, both parties engage in their transaction.

At the end of the transaction, both parties issue their report through an interactive process. As will be detailed in the following, a report contains the rating of the client as well as the identifier of the provider. Note that the presence of the provider identifier does not violate Property 1 since the rating of the client is signed before the service provider reveals her identifier. If the client does not want to rate the service, then the provider obtains a proof of transaction from the share carriers. On the other hand, if the provider does not want to help in the construction of the report, then the client signs the rating and obtains the identifier of the provider from the share carriers.

Periodically, the accredited signers gather all the issued reports, and verify them. They then update and sign the reputation scores of all service providers. Thanks to these signatures, service providers will be able to prove their updated reputation score during their subsequent interactions. More details are given in Sections V and VI.

V. BUILDING BLOCKS This section describes the tools used during interactions to guarantee both privacy and security of the users.

A. Building Trust

1) Share Carriers: As previously explained, at the beginning of the interaction, both the client and the provider randomly choose sufficiently many users to constitute the share carriers. Specifically, both parties independently draw their own nonces, i.e. random numbers, and combine them to deterministically select the share carriers. The independent choice of the nonces guarantees that neither the client nor the service provider are able to choose the share carriers by themselves. Let seed be the combination of the drawn nonces, {0, 1, . . . , N -1} be the set of potential share carriers (i.e. the set of service providers), and n SC be the number of share carriers to be selected. The function ChooseSC(seed, N ) returns a set of n SC share carriers randomly chosen in the system. We have

ChooseSC(seed, N ) = H(01 seed i) × N 2 h , i ∈ {0, . . . , n ′ -1} ,
where H is a hash function, e.g. SHA-256 [START_REF]Secure hash standard[END_REF], with h-bits output and n ′ is chosen so that the resulting set contains n SC different share carriers. The idea behind this function is to divide the set {0, 1, . . . , 2 h -1} into N intervals of similar sizes, and to compute a sequence of pseudo-random elements in {0, 1, . . . , 2 h -1} from the seed. Each element points out an interval, and the first n SC different intervals corresponding to the first elements in the sequence are selected. We obtain the n SC corresponding share carriers. Appendix A discusses the number of share carriers that must be chosen to prevent collusions.

2) Accredited Signers: Accredited signers are users chosen in the system. There are no restrictive requisites for the selection of these users within the system, but choosing them among reasonably available users will have less impact on the latency of the reputation score updates. For instance, the central authority C (see Section III-B) can be in charge of choosing the accredited signers. These accredited signers obtain from C a delegation for the verification of reports, and the signature of reputation scores. In the following, n AS represents the number of accredited signers. We assume that at least a majority of the accredited signers are honest.

As previously described, the aggregation of the reports and the computation of reputation scores is done off-line, without any direct impact on the interactions. Therefore, the accredited signers do not sign reputation scores after each interaction. Rather, they sign scores at fixed intervals of time, that we call rounds in the following. Both the duration and start time of each round are public parameters. A reasonable trade-off is to sign reports every day. To prove their reputation score, service providers use signatures on the current round from a majority of the accredited signers, i.e. at least t AS = (n AS + 1)/2 signatures.

B. Cryptographic Tools

We now present the cryptographic tools used by our reputation protocol, that is, the invariant to prevent ballot stuffing; the non-interactive zero-knowledge proof system; an anonymous proxy signature scheme that preserves the privacy of users; finally, a verifiable secret sharing scheme that guarantees the undeniability of reports.

1) Setting: The underlying structure for our cryptographic 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 (and resp. G 2 ∈ G 2 ) is a group generator of G 1 (resp. G 2 )
. The security of the presented tools relies on the intractability of the Symmetric eXternal Diffie-Hellman (SXDH) assumption in Λ, and on a specific assumption along the same lines as the Strong Diffie Hellman (SDH) assumption [START_REF] Abe | Structure-preserving signatures and commitments to group elements[END_REF]. In the following, if X is a tuple then X k represents the k-th term of X.

2) Invariant: As detailed in Section II, reputation mechanisms are potential targets of ballot-stuffing attacks, in which a single client rates a service provider multiple times, in order to heavily bias the reputation of the provider. We protect our system against such attacks by strongly linking each interaction through an invariant jointly computed by both interacting parties. Note that Bethencourt et al. proposed a similar approach, though more complex [START_REF] Bethencourt | Signatures of reputation[END_REF]. We build the invariant as follows. It is derived from the identifiers of both parties, namely Id SP ∈ G 1 for the service provider, and id Cl ∈ Z p for the client. We define the invariant as

Inv(Id SP , id Cl ) = (Id SP ) id Cl .
To preserve the privacy of both interacting parties, the invariant cannot be directly computed before the transaction. Indeed, in order to compute it directly, a user must know the identifiers of both the provider and the client. Thus, we propose to compute the invariant in three steps, which require a fixed group element Y 1 ∈ G 1 randomly generated. First, the service provider computes a pre-invariant by masking her identifier Id SP with randomness r ∈ Z p (G 1 and Y 1 are public elements). We have

pre_inv = Pre_inv(Id SP , r) = (G 1 r , Id SP •Y 1 r ).
Then, the client injects his identifier id Cl ∈ Z p and randomness s ∈ Z p in the previous result to compute a masked invariant defined as

masked_inv = Mask(pre_inv, id Cl , s) = (G 1 s • Y 1 id Cl , pre_inv 1 s • pre_inv 2 id Cl ) = G 1 s • Y 1 id Cl , Id SP id Cl • (G 1 s • Y 1 id Cl ) r .
Finally, the provider obtains the invariant from masked_inv by computing

Unmask(masked_inv, r) = masked_inv 2 • masked_inv 1 -r = (Id SP ) id Cl = Inv(Id SP , id Cl ).
3) SXDH Commitments: SXDH commitments [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] in a multiplicative group G 1 (resp. G 2 ) generated by G 1 (resp. G 2 ) permit to commit to values X in this group without revealing them. Note that it is also possible to commit to scalars m ∈ Z p , by taking X = G 1 m . Committing to X ∈ G 1 requires a commitment key (a tuple of group elements), and two random elements r, r ′ ∈ Z p . The commitment is denoted by C X = Com X, (r, r ′ ) . Opening a commitment C requires an opening key, that is a scalar α associated to the commitment key. The opening is denoted by X = Open(C X , α).

In the remainder of the paper, whenever we write that x is the value committed in C x , we mean that C x is a commitment to x. For simplicity reasons, we use Com to denote the commitment to an element which may be in G 1 , G 2 or Z p . Furthermore, when randomnesses used in a commitment are not essential, we simply write Com(X, _).

4) Non-Interactive Zero-Knowledge Proofs:

To prove their possession of secret values satisfying given statements without revealing them, both clients and service providers use the proof system proposed by Groth and Sahai [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF]. This system allows users to compute Non-Interactive Zero-Knowledge proofs of knowledge (NIZK) on four kinds of statements, including pairing product equations

n i=1 e(A i , Y i )   m j=1 e(X j , B j )     n i=1 m j=1 e(X j , Y i ) γij   = R T , and multi-scalar multiplication equations in G 1 n i=1 A i yi   m j=1 X j bj     n i=1 m j=1 X j γij yi   = R 1 ,
where capital letters denote group elements and lower-case letters denote scalars, i.e. elements of Z p . In these equations, A i , B j , b j , γ ij , R T , and R 1 are public elements, while X j , Y i , and y i are secret values.

The proofs are based on SXDH commitments to the secret values. From the randomnesses used in the commitments, a prover computes specific group elements (the proof). The verifier can check the validity of the equation using the proof and the committed secrets, without any access to the secrets. A prover can moreover combine multiple statements to prove that secret values simultaneously satisfy different equations. According to the notations introduced by Camenish et al. [START_REF] Camenisch | Efficient group signature schemes for large groups (extended abstract)[END_REF], we denote a proof of knowledge of secret values (x 1 , . . . , x k ) following equations (E 1 , . . . , E ℓ ) by NIZK{x 1 , . . . , x k :

E 1 ∧ • • • ∧ E ℓ }.
5) Anonymous Proxy Signatures: Throughout their interaction, both parties must sign messages. However, verifying a signature requires to have access to the verification key of the signer, which is incompatible with the privacy properties since verification keys identify signers. An anonymous proxy signature scheme [START_REF] Fuchsbauer | Anonymous proxy signatures[END_REF] allows receivers to check the validity of signed messages without having access to the identity of the signer. The only obtained information is that the signer received a delegation from an identified authority. To achieve such a property, a signer uses NIZKs to hide all elements related to their identity in the signature. An efficient anonymous proxy signature scheme can be obtained by combining the structure-preserving signature scheme proposed by Abe et al. [START_REF] Abe | Structure-preserving signatures and commitments to group elements[END_REF] and the proof system proposed by Groth and Sahai [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF].

Let (vk U , sk U ) be the verification and signing key of user U . Then, the signature of message m is σ = Sign(m, sk U ). The verification consists in the computation of Verify(σ, m, vk U ): the result is True iff signature σ is valid for the pair (m, vk U ). We now consider a signing key sk C and the corresponding verification key vk C of a certification authority C. A certificate for user

U is cert U = Sign(vk U , sk C ). Such a certificate is valid if and only if Verify(cert U , vk U , vk C ) = True.
Using the structure-preserving property of the signature scheme, an anonymous proxy signature of message m, from an anonymous signer U certified by the authority C, contains the SXDH commitments to cert U , vk U and σ, and a Groth-Sahai proof,

NIZK cert U , vk U , σ : Verify(cert U , vk U , vk C ) = True ∧ Verify(σ, m, vk U ) = True .
In our context, both clients and service providers compute anonymous proxy signatures to authenticate messages without disclosing their identity. More precisely, they first send commitments to their public key vk U and their certificate cert U together with the proof of registration Π cert U given by

Π cert U = NIZK cert U , vk U : Verify(cert U , vk U , vk C ) = True .
For each message m to be signed, both clients and providers compute a signature σ, and send a commitment to this signature, and a proof of validity Π σ , that is

Π σ = NIZK vk U , σ : Verify(σ, m, vk U ) = True .
The use of the same commitment to vk U is of primary interest here, as the verifier has to check only one proof of registration. Moreover, this commitment establishes a link between the anonymous proxy signatures sent during an interaction: the signer is the same. For convenience reasons, we denote by APSign(m, sk U ) the proof Π σ with the commitment to the signature of m.

6) Verifiable Secret Sharing: Verifiable secret sharing [START_REF] Feldman | A practical scheme for non-interactive verifiable secret sharing[END_REF] is a threshold cryptographic scheme allowing to split a secret into n different shares. As in a secret sharing scheme, the secret can be recomputed from a predefined number t of shares (with t n), while giving no information to whoever knows strictly less than t shares. The extra-property consists in the proven consistency of distributed shares: the prover guarantees that the expected secret was shared, and that any set of t shares allows the computation of this unique secret. We now present a verifiable secret sharing scheme for group elements, using both SXDH commitments and NIZKs.

Let X ∈ G 1 be the secret of the prover, on which this prover has certificate cert X such that Verify(cert X , X, vk C ) = True.

To share X, the prover chooses a t -1 degree polynomial

Q : z ∈ Z p → (X • t-1 j=1 (A j ) z j ) ∈ G 1 , in which the (A j ) are randomly chosen in G 1 . The shares are (i, Q i = Q(i)) 1 i n . Lagrange interpolation with t distinct shares (i 1 , Q i1 ), . . . , (i t , Q it ) allows the reconstruction of secret X = Q(0), as follows X = Interp (i j , Q ij ) 1 j t = t j=1 Q ij k =j (i k /(i k -ij )) .
To prove the consistency of the shares, the prover shows that the same polynomial Q is used for the computation of all shares. Thus, the prover commits to the secret X and to the coefficients (A j ), that is, C X = Com(X, _) and C Aj = Com(A j , _) for 1 j < t. The prover then computes NIZKs assessing both the consistency of the shares, i.e. a proof Π Qi that Q i = Q(i), and the correctness of the secret, using a proof of correctness Π X including a commitment to the certificate (see details in Section VI). Afterwards, the prover sends i, Q i , C X , (C Aj ), and Π Qi to each share carrier, and C X , (C Aj ), C cert X and Π X to the verifier. Each share carrier verifies Π Qi and sends a confirmation to the verifier, that is i, C X , and (C Aj ). If the commitments received from the share carriers and from the prover are the same, then the consistency of the shares is proven. In the meantime, the verifier checks the validity of Π X .

The verifiable secret sharing is useful iff (i) the verifier will eventually receive enough valid signatures, (ii) the malicious share carriers cannot recover the secret, and (iii) the honest share carriers can recover the secret. By noting b the number of malicious share carriers and ℓ the number of responses that the verifier is waiting for, these conditions translate to b < t, ℓ n -b, and t ℓ -b. An optimal choice for t is t = ⌈n/3⌉ and ℓ = 2t -1, which tolerates up to b = t -1 malicious share carriers.

Remark 1: Such a sharing can be made offline, that is without any interaction with the share carriers before the reconstruction of the secret. In this case, the prover encrypts the shares with the keys of the share carriers to prevent the verifier from reconstructing the secret. To guarantee the correctness of the shares, the prover computes NIZK proofs of their encryption and of their reconstruction. To prevent the verifier from asking the decryption of arbitrary encrypted shares, the prover also signs each share, and computes a NIZK proving the validity of each signature, while masking the share, the signature, and the verification key.

VI. REPUTATION PROTOCOL

A. System Setup

Throughout the reputation protocol, users need the cryptographic keys and identifiers presented in Table I. 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 [START_REF] Borisov | Computational puzzles as sybil defenses[END_REF] to mitigate Sybil attacks. Note that the central authority is required only for the registration of users, and possibly for the choice of accredited signers (see Section V-A2).

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 classical certificate cert AS on vk AS . They use these keys to sign the reputation score of service providers. 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 (see Section V-A):

σ i = Sign vk SP , rep SP , rnd , sk ASi .
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 ), each of them used to protect their communications (encryption of received messages, and signature of 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 are SXDH commitments to their verification keys. Similarly, both clients and service providers compute commitments C id Cl and C IdSP to their identifiers id Cl and Id SP , leading to

nym Cl = Com(vk Cl , _) C id Cl = Com(id Cl , _), nym SP = Com vk SP , (r SP , r ′ SP ) C IdSP = Com(Id SP , (r IdSP , r ′ IdSP )
). Clients compute commitments C cert Cl to their certificate, and NIZK proofs of their validity Π cert Cl (see Section V-B5). Similarly, service providers compute commitments C certSP and proofs Π cert Cl . Finally, service providers compute a preinvariant pre_inv from Id SP and a randomly chosen scalar r pre_inv : pre_inv = Pre_inv(Id SP , r pre_inv ) (see Section V-B2).

B. 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 (see Figure 1). Once the provider has verified this proof, she sends back her pseudonym, reputation, pre-invariant and respective proofs of validity. That is, she sends nym SP , C IdSP , C certSP , Π certSP , rep SP , a proof of reputation Π rep , pre_inv, and a proof Π pre_inv of its computation. These proofs are defined by In the meantime, the provider chooses a nonce s SC and commits to it by sending C SC = H(00 s SC ). 1 If the reputation of the provider suits the client, and if all the proofs are valid, the client computes the masked invariant masked_inv = Mask(pre_inv, id Cl , r masked_inv ), chooses a nonce r SC , signs a hash of (C SC , r SC , nym SP ), and sends r SC and the signature σ Cl to the provider with

Π rep = NIZK vk SP , σ i1 , . . . ,
σ Cl = APSign H(C SC , r SC , nym SP ), sk Cl .
If σ Cl is valid, the provider signs a hash of (s SC , r SC , nym Cl ), and sends s SC and the signature σ SP to the client with σ SP = APSign H(s SC , r SC , nym Cl ), sk SP .

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 as described in Section V-A1, using (s SC r SC nym Cl nym SP ) as a seed. In the remainder, this element serves as an identifier of the transaction, and we note it id trans .

C. Sharing Ingredients of the Report

Once both the client and the service provider have agreed to engage in the transaction, they rely on the verifiable secret sharing scheme described in Section V-B6 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 defined by

Π Qi = NIZK Id SP , (A j ) j : Q i = Id SP tSC-1 j=1 A j (i j ) ,
for 1 ≤ i ≤ n SC . Note that nym SP , C IdSP , C certSP and Π certSP have already proven the correctness of the secret. 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. Once the client has received ℓ = 2⌈n SC /3⌉ -1 valid shares, he accepts the sharing (as the validity of the shares guarantees the undeniability properties). Figure 2 describes this exchange. 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 defined by

SP SC i Client id trans , (i, Q i ), C IdSP , (C Aj ) j , Π Qi id trans , i, C IdSP , (C Aj ) j (C Aj ) j
Π Ri = NIZK masked_inv, (B j,k ) : R i,k = masked_inv k • tSC-1 j=1 B j,k (i j ) , k ∈ {1, 2} , for 1 ≤ i ≤ n SC .
To prove the correctness of the secret, the client also computes a proof Π C masked_inv defined by Π C masked_inv = NIZK id Cl , masked_inv, r masked_inv : masked_inv = Mask(pre_inv, id Cl , r masked_inv ) .

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 ℓ valid confirmations. Figure 3 describes this exchange. Once both sharings have been accepted, both parties can conduct their transaction.

Client SC i SP id trans , (i, R i ), C masked_inv , (C Bj,k ) j,k , Π Ri id trans , i, C masked_inv k , (C Bj,k ) j,k C masked_inv , (C Bj,k ) j,k , Π Cmasked_inv

D. Issuing 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. a) Scenario A -Standard case.: The client chooses a rating ρ and computes both a signature σ ρ,Cl to prevent any modification on ρ, and a proof Π masked_inv of masked_inv computation. We have σ ρ,Cl = APSign id trans , ρ , sk Cl , Π masked_inv = NIZK r masked_inv , id Cl : masked_inv = Mask(pre_inv, id Cl , r masked_inv ) .

Since masked_inv no longer needs to be hidden, this proof is simpler than Π C masked_inv . As described in Figure 4, 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 = Unmask(masked_inv, r pre_inv ), and a signature σ ρ,SP with σ ρ,SP = Sign id trans , σ ρ,Cl , sk SP .

Note that σ ρ,SP guarantees that the client chose his rating before knowing the identifier of the provider, which guarantees his objectivity. The provider then reveals her identifier and the randomnesses used in nym SP , C IdSP , and pre_inv, that is Π SP = (r SP , r ′ SP , r IdSP , r ′ IdSP , r pre_inv ). The provider sends message m 2 to the client, with m 2 = (Id SP , vk SP , cert SP , inv, Π SP , σ ρ,SP ). The client verifies that

       nym SP = Com vk SP , (r SP , r ′ SP ) C IdSP = Com(Id SP , (r IdSP , r ′ IdSP )) pre_inv = Pre_inv(Id SP , r pre_inv inv = Unmask(masked_inv, r pre_inv ).
Finally, both the client and the provider are able to issue the report by sending the elements given in the first column of Table II 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.

Client SP

m 1 = (id trans , ρ, masked_inv, Π masked_inv , σ ρ,Cl ) m 2 = (Id SP , vk SP , cert SP , inv, Π SP , σ ρ,SP )
Broadcast of the report b) Scenario B -Dishonest client/honest provider: If the provider does not receive message m 1 from the client, she queries the share carriers for their share. On their turn, they query the client to get his rating and, in absence of his answer, send their shares and associated proofs to the provider. The provider is able to reconstruct the masked invariant as masked_inv = Interp (i j , R ij ) 1 j tSC from t valid received shares. From that point, the service provider computes inv = Unmask(masked_inv, r pre_inv ), and issues the report, which only contains the proof of transaction (i.e., the elements in the second column of Table II). Figure 5

(C B j,k ), {i j , R i j , Π R i j } j , C masked_inv , Π C masked_inv inv, Π inv Rating ρ, σ ρ,Cl , σ ρ,SP ρ, {σ ρ,SC i j } j
c) Scenario C -Dishonest provider/honest client: If the client does not receive message m 2 from the provider, he informs the share carriers by sending them the masked invariant and his rating together with the associated proofs and signatures as shown in Figure 6. If 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 shares to the client. Note that they also sign the rating of the client to validate the fact that the client has chosen his rating before knowing the provider's identity. We have

σ ρ,SCi = Sign id trans , σ ρ,Cl , sk SCi .
Once the client has received t valid shares, he computes Id SP = Interp (i j , Q ij ) 1 j tSC , inv = Inv(Id SP , id Cl ), and a proof Π inv of its computation, with

Π inv = NIZK id Cl : inv = Id SP id Cl .
Finally, the client issues the report by sending the elements presented on the third column of Note that if neither the client nor the service provider issue the report, then the transaction is not taken into account in the reputation score of the service provider.

Remark 2: One may argue that both parties can collude by jointly issuing reports as soon as the preparation is over, that is, without having actually conducted a transaction. Similarly, clients may choose arbitrary ratings regardless of the behavior of providers. The only way to prevent such behaviors would be to have an omniscient and trusted third party capable of telling whether the transaction really occurred, or whether the effort exerted by the provider during her transaction was bad or good enough to deserve such a rating, which is clearly impossible.

E. 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, 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. Beyond handling negative ratings, the accredited signers know the rounds during which reports have been cast. Thus, as motivated in Section II, 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 ballotstuffing attacks [START_REF] Whitby | Filtering out unfair ratings in bayesian reputation systems[END_REF]. In addition, the accredited signers approximate the reputation score of service providers to extend their anonymity set. Once the accredited signers have computed the reputation score of a provider, they sign it along with the round, rnd, and send it to the service provider:

σ i = Sign vk SP , rep SP , rnd , sk ASi .
Service providers can then use these signatures to prove their reputation to their clients during round rnd +1.

VII. 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, as explained in Appendix A.

A. 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 III 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 | Signatures of reputation[END_REF], where the proof of reputation requires 500 KiB per received rating. Table III 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 7 details the computation cost (in ms) of each phase of the reputation mechanism at 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.

B. 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 8 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 be easily explained. First, Aranha et al. carefully select a Barreto-Naehrig curve, and optimize the computation of pairings using Assembly and C code [START_REF] Aranha | Faster explicit formulas for computing pairings over ordinary curves[END_REF] on this specific curve. In our case, we rely on the MNT-159 curve proposed by Charm, which is a Python framework wrapping around Lynn's pbc library. 2 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 posttransaction 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. In this article, we have presented a practical distributed reputation mechanism addressing two main issues of reputation mechanisms: preserving all users' privacy and computing reputation scores based on both positive and negative ratings. This has been achieved by combining distributed algorithms with cryptographic schemes. Furthermore, our proposition 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 the offline version of the secret sharing, in particular to improve the report verification when the service provider does not want to collaborate. We also plan to study whether the presence of a unique trusted entity is a necessary condition to handle both non monotonic reputation scores and the permanent anonymity of providers.

APPENDIX

A. Number of Share Carriers

The share carriers are users that guarantee the undeniability of reports. They are jointly chosen by clients and service providers for a single interaction. As explained in Section V-A1, they are randomly chosen among all service providers. Hence, the choice of the share carriers is equivalent to a draw without replacement, which can be modeled by the hypergeometric distribution. Let N be the number of potential share carriers and m the number of malicious users. Then, the probability of having chosen less than a third of malicious share carriers corresponds to 1 -cdf N,m,nSC (t SC -1), where cdf N,m,nSC is the cumulative distribution function of the hypergeometric distribution with parameters (N, m, n SC ). 3 Therefore, if we wish to achieve a given maximal probability of collusion p max , we must choose As we can see, the number of required share carriers does not grow after the number of users has reached 1,000,000. This means that whatever the size of the system, the number of required share carriers does not grow and our mechanism scales. Figure 10 represents n SC for p max varying between 2 -10 and 2 -70 , and N = 10 8 . As we can see, the number of required share carriers is logarithmic in the maximal probability of collusion targeted. For instance, with n SC = 100, we can either either prevent collusions representing 15% of total users from obtaining a third of malicious share carriers with probability 2 -20 , or prevent collusions representing 10% of total users with probability 2 -35 . Since the share carriers are renewed for each transaction, it is acceptable that a report in a million is either falsified or denied. We can thus take p max = 2 -20 .

n SC = min n 1 -cdf N,m,n n 3 -1 < p max .

-

B. Cryptographic Proofs

In this appendix, we present proofs that our reputation mechanism guarantees the properties presented in Section III. Note that these proofs are not the most formal. In particular, we do not present the setups of the underlying schemes. To prevent interferences, each cryptographic tool should be setup independently. Furthermore, each cryptographic tool should have different setups for each role. That is, there be one setup for NIZKs constructed by clients and another one for those constructed by providers, and similarly for every cryptographic tool.

Before presenting the formal definitions and proofs of our properties, we must discuss the model of the adversary, that we call A. First, we consider A to be probabilistic polynomialtime Turing machine. We want the adversary to be able to: (i) make two users interact; (ii) corrupt users, since the adversary might be a collusion of users; and (iii) know which client was involved in a transaction. Hence, we consider three oracles that A might query during the games:

(i) O inter that, given a client and a provider, makes them interact; (ii) O corr that, given a user, returns all this user's credentials; (iii) O inv that, given an invariant, returns the client involved. Note that the winning conditions of each game will depend on the oracles queried by the adversary. For instance, the adversary must not corrupt a user to compromise this user's privacy.

C. Privacy of Service Providers

Privacy of service providers -Property 1 -is guaranteed if the following experiment returns 1 with probability 1 2 +neg(λ), where neg is a negligible function:

1 A can also corrupt any users, but strictly less than a majority of n AS accredited signers. Service providers SP 0 and SP 1 are service providers of equivalent reputation that were not corrupted by A. In Step 4, A cannot corrupt SP 0 , SP 1 , SP b , SPb or more than t SC share carriers involved in one of SP b 's or SPb's interactions. A also cannot make SP b or SPb interact with a client and go beyond the report; thus, there is no invariant computed by SP b or SPb, and SP b and SPb have not revealed their identity to any client.

) (state) ← Setup(1 λ ) 2) (state, SP 0 , SP 1 ) ← A O inter (•),Ocorr(•),O inv (•) (state) 3) b ← {0, 1} 4
Proof: The only way for A to obtain information regarding b is to have clients interact with SP b . However, A does not see neither the invariant nor the identity of SP b . Furthermore, making SP b interact simultaneously with many different clients does not give more information to A than just one interaction: all the elements shown by SP b are randomized. Therefore, we consider a single interaction between SP b and a client chosen by A, and we assume that the last phase of the transaction has not started yet.

During this interaction, A sees nym

SP b , C IdSP b , rep SP b , pre_inv b , {vk ASi k } 1 k tAS , C certSP b , Π certSP b , Π rep b , Π pre_inv,b , s SC,b , σ SP,b , {C A j,b } 1 j tSC-1 , {Q i,b , Π c,i,b } i∈I ,
where I is a set of cardinal lower than t SC . Since A has corrupted less than t SC share carriers, the Q i,b give no information about Id SP b and can be considered as random elements.

Among those elements, s SC,b and the Q i,b are random elements, hence they give no information about the service provider. Using the hiding property of commitments and NIZKs, new games can be defined, in which all commitments and NIZKs -hence anonymous proxy signatures -are replaced by random elements. The indistinguishability of these games with the original ones is related to the security assumption of the commitment and NIZK schemes. The only element that might leak information is pre_inv b , that is

(G 1 r , Id SP b Y 1 r ), where r is randomly chosen by SP b . From the DDH assumption in G 1 on the tuple (G 1 , G 1 r , Y 1 = G 1 α1 ), it follows that Y 1 r is indistinguishable from a random element R ∈ G 1 . By taking R ′ = Id SP1 -1 • Id SP0 •R, we have Id SP0 •R = Id SP1 •R ′ , where R ′ is also indistinguishable from Y r 2 . Thus, Id SP0 •Y 1 r is indistinguishable from Id SP1 •Y 1 r
, and the advantage of the adversary in this game is lower than two times the DDH advantage.

The same reasoning can be applied to SPb.

D. Privacy of Clients

Privacy of clients (Property 2) relies on two parts. First, during a transaction, the provider does not know whom they are interacting with. Secondly, the transactions between a client and different service providers are unlinkable. The following two experiments capture these notions. This property is guaranteed if both return 1 with probability 1 2 + neg(λ).

1) (state) ← Setup(1 λ ) 2) (state, Cl 0 , Cl 1 , {SP i } 1 i n ) ← A O inter (•),Ocorr(•),O inv (•) (state) 3) b ← {0, 1} 4) b ′ ← A O inter (•),Ocorr(•),O inv (•) (state, Cl b , Clb, {SP i } 1 i n ) 5) Return 1 if b ′ = b; 0 otherwise.
In Step 2 of this experiment, Cl 0 and Cl 1 are clients who have not been corrupted by A. In Step 4, A cannot corrupt Cl 0 , Cl 1 , Cl b , or Clb. Furthermore, the set of service providers having interacted (and gone beyond the transaction) with Cl 0 or Cl 1 is disjoint from the set of providers having interacted (and gone beyond the transaction) with Cl b or Clb. That is, no service provider has interacted with (Cl 0 or Cl 1 ) and (Cl b or Clb).

Proof: The proof of this property contains two parts. Firstly, can the adversary obtain any information about b without having the clients go beyond the transaction? Secondly, can the adversary link the clients of different providers?

Similarly to the previous proof, if the clients do not go beyond the transaction, A sees only commitments, NIZK proofs, anonymous proxy signatures, and randomnesses. As explained previously, these elements give no information about b or b.

After the transaction, the only different elements are the masked invariants, and the invariants:

masked_inv = (G 1 s Y 1 id Cl , Id SP id Cl G 1 rs Y 1 r id Cl ) inv 0 = Id SP id Cl
Note that since the provider proves the computation of pre_inv, an honest client will not compute anything more than this masked invariant. Furthermore, we remark that the masked invariant is based on the invariant, and G 1 s Y 1 id Cl . Since s is chosen randomly by the client, this last element is indistinguishable from a random element, and only the final invariant is useful to A. Now, the adversary A only has access to the invariants involving Cl 0 , Cl 1 , Cl b , or Clb with the SP i , with the restriction that a given service provider cannot produce an invariant with (Cl 0 or Cl 1 ) and (Cl b or Clb). Thus, we consider a hybrid sequence composed of k service providers involved only with Cl 0 and Cl 1 , and n -k other providers involved only with Cl b and Clb:

Game G 0 : Inv(SP i , Cl b ), Inv(SP i , Clb) , 1 i n Game G 1 : Inv(SP i , Cl 0 ), Inv(SP i , Cl 1 ) , 1 i n Game G 1 k Inv(SP i , Cl 0 ), Inv(SP i , Cl 1 ) 1 i k Inv(SP i , Cl b ), Inv(SP i , Clb) k < i n, Game G 2 k      Inv(SP i , Cl 0 ), Inv(SP i , Cl 1 ) 1 i < k R ← G 1 , Inv(SP i , Clb) i = k Inv(SP i , Cl b ), Inv(SP i , Clb) k < i n, Game G 3 k      Inv(SP i , Cl 0 ), Inv(SP i , Cl 1 ) 1 i < k R ← G 1 , R ′ ← G 1 i = k Inv(SP i , Cl b ), Inv(SP i , Clb) k < i n, Game G 4 k      Inv(SP i , Cl 0 ), Inv(SP i , Cl 1 ) 1 i < k Inv(SP i , Cl 0 ), R ′ ← G 1 i = k Inv(SP i , Cl b ), Inv(SP i , Clb)
k < i n, for 1 k n, where R and R ′ are taken uniformly at random. Note that G 0 and G 1 0 are the same, as well as G 1 and G Let us consider a DDH tuple (A = G a , B = G b , Z). We fix Id SP k = B and id Cl0 = a. If the adversary A is able to distinguish these two games, A is also able to distinguish G ab from a random element R. That is, the adversary can tell whether Z is G ab or a random element, knowing only G, G a , and G b .

Hence, G 1 k and G 2 k are indistinguishable for A. With the same reasoning, we can show that all the successive games are indistinguishable for A. Therefore, the advantage of the adversary in this hybrid sequence is lower than 4n times the DDH advantage, and games G 0 and G 1 are indistinguishable.

E. Undeniability of Reports

The undeniability of ratings (see Property 3), captures the notion that a service provider cannot prevent a client from rating her, and that the client's rating will be taken into account in the provider reputation score. Property 3 is guaranteed if the following game returns 1 with probability neg(λ):

1) (state) ← Setup(1 λ ) 2) (Cl 0 ) ← A O inter (•),Ocorr(•),O inv (•) (state)

3) A makes Cl 0 interact with SP 0 , and Cl 0 issues a report rpt 0 4) Return 1 if Cl 0 has not been corrupted by A, and either rpt 0 is not valid or rpt 0 was not issued on SP 0 Proof: A game-based approach can formally prove the undeniability of reports, however we only give hints for such a proof. First, we consider the elements received by the client before the transaction. Under the robustness of the signature scheme, and the binding property of the commitment scheme and NIZK proof system, the adversary is not able to impersonate an uncorrupted service provider. Thus, the adversary necessarily uses the credentials of one of the corrupted providers, and must share this provider's identity with the share carriers. After the transaction, when the adversary completes the protocol, the binding property once more guarantees that the revealed identity is the one used before the transaction, which correspond to one of the corrupted service providers. In the other case, the adversary cannot prevent the client from obtaining the share carriers' shares, and then reconstructing the secret. In both cases, the client can construct a valid report. Similar experiment and reasoning can be used to prove Property 4.

F. Unforgeability of Reports

An adversary has two options to forge a report. First, by forging signatures from a majority of the accredited signers. By assumption, less than nAS 2 accredited signers are malicious, thus such a case is not possible. Secondly, the adversary may forge a valid report. The unforgeability of reports -Property 5 -is guaranteed if the following experiment returns 1 with probability neg(λ):

1) (state) ← Setup(1 λ ) 2) rpt 0 ← A O inter (•),Ocorr(•),O inv (•) (state) 3) Return 1 if a) rpt 0 is valid b) vk Cl0 = Open(nym Cl,0 ) c) either Cl 0 or SP 0 has not been corrupted by A d) rpt 0 is different from any other report between Cl 0 and SP 0 where rpt 0 is a report issued by nym Cl,0 on provider SP 0 .

Proof: The report rpt 0 consists of the following four elements:

• the identity of the service provider, represented by Id SP0 and vk SP0 , and their pseudonym for the transaction, that is C IdSP 0 and nym SP0 ; • the pseudonym of the client, nym Cl0 and C id Cl 0 ;

• the identifier of the transaction, id trans,0 ;

• the invariant, inv 0 And, if the client is correct, the report also comprises their rating ρ 0 . Each of these elements is either signed by both the client and the provider -like id trans0 -or proven thanks to proofs that may be non-interactive and zero-knowledge, or not -like inv 0 . We show that to change any of these elements, A must break one of the underlying primitives.

a) Changing the identity of the service provider: Suppose that A has modified Id SP , vk SP and cert SP . Thus, either A has forged Π SP , or modified nym SP0 and C IdSP 0 , and computed a correct proof Π SP . The security of NIZKs prevents A from doing the former. Furthermore, σ SP and σ Cl are two signatures from both the provider and the client on id trans0 = s SC r SC nym Cl nym SP . The security of the anonymous proxy signatures hence prevents A from forging such signatures. If the service provider did not participate in the report emission, the client proves the reconstruction of Id SP0 thanks to the shares of the share carriers. Each of these shares is signed by the service provider, which prevents A from forging them. Therefore, A cannot modify the provider's identity. The same reasoning shows that A cannot modify the identity of the client or the identifier of the transaction either.

b) Changing the invariant: If the service provider did not participate in the report emission, changing the invariant comes down to modifying Id SP0 or id Cl0 -which is hard, as shown previously -or forging Π inv0 , which is hard as well. If the service provider did participate, inv 0 depends directly from masked_inv 0 . Modifying inv 0 thus means modifying masked_inv 0 . masked_inv 0 is computed from pre_inv 0 , which depends directly on Id SP0 . As shown previously, Id SP0 cannot be modified. Thus, to modify masked_inv 0 , A must forge Π masked_inv 0 , which is hard. Therefore, A cannot modify the invariant.

c) Changing the rating: To modify the rating, A must either forge signatures σ d,Cl0 and σ d,SP0 if both the client and the provider are correct, or forge t signatures from the share carriers. Since A cannot corrupt both Cl 0 and SP 0 , the security of the anonymous proxy signature scheme prevents them to do so.

Since the adversary must break the NIZK proofs or the anonymous proxy signatures to win this game, their advantage is negligible and the unforgeability of reports is guaranteed.

G. Linkability of Reports

The linkability of reports (Property 6) is guaranteed if the following experiment returns 1 with probability neg(λ):

1) (state) ← Setup(1 λ ) 2) (rpt 0 , rpt 1 ) ← A O inter (•),Ocorr(•),O inv (•) (state)

3) Return 1 if: a) rpt 0 , rpt 1 are valid, and b) rpt 0 and rpt 1 concern the same provider, and c) Open(nym Cl,0 ) = Open(nym Cl,1 ) and inv 0 = inv 1 , or d) Open(nym Cl,0 ) = Open(nym Cl,1 ) and inv 0 = inv 1 Proof: We previously proved that reports are unforgeable. Thus, if rpt 0 (resp. rpt 1 ) is valid, rpt 0 contains inv 0 = Id SP0 id Cl 0 (resp. inv 1 = Id SP0 id Cl 1 ), where Cl 0 = Open(nym Cl,0 ) (resp. Cl 1 = Open(nym Cl,1 )). Therefore, inv 0 = inv 1 if and only if Cl 0 = Cl 1 , and reports are linkable.

H. Representativeness of Reputation Scores

The representativeness of reputation scores (Property 7), captures the notion that an adversary cannot prove another reputation than their own one. This property is guaranteed if the following game returns 1 with probability neg(λ):

1) (state) ← Setup(1 λ ) 2) (nym SP,0 , C IdSP,0 , rep SP,0 , C certSP,0 , Π certSP,0 , Π rep,0 ) ← A O inter (•),Ocorr(•),O inv (•) (state)

3) Return 1 if: a) Π certSP,0 and Π rep,0 are valid for nym SP,0 , C IdSP,0 , C certSP,0 and rep SP,0 , and b) SP ′ 0 = Open(nym SP,0 ) and rep SP ′ 0 = rep SP,0 Proof: As proven previously, reports cannot be forged, and thus the reports signed by the accredited signers are legitimate reports. Hence, honest accredited signers compute and sign a representative reputation score. Since we made the assumption that less than n AS /2 accredited signers are malicious, a service provider cannot receive enough signatures from accredited signers to prove a different reputation score. Furthermore, the security of NIZKs and anonymous proxy signatures prevent A from forging valid proofs of reputation. Therefore, the representativeness of reputation scores holds.

Figure 1 .

 1 Figure 1. Proof of the reputation score

Figure 2 .

 2 Figure 2. Secretly Sharing the Provider's Identifier

Figure 3 .

 3 Figure 3. Secretly Sharing the Masked Invariant

Figure 4 .

 4 Figure 4. Interactions between the client and the provider to jointly issue their report

Figure 6 .

 6 Figure 6. Interactions between the client and the share carriers to issue the report

Figure 7 .

 7 Figure 7. Theoretical computation times (ms)

  2 http://crypto.stanford.edu/pbc/ VIII. CONCLUSION

Figure 9

 9 Figure 9 represents n SC for N varying between 100 and 10 15 , for fixed percentages m of malicious users, and for p max = 2 -20 .

Figure 9 .

 9 Figure 9. Dependance of n SC in N and m (pmax = 2 -20 )

Figure 10 .

 10 Figure 10. Dependance of n SC in pmax and m (N = 10 8 )Finally, Figure11presents the number of required share carriers for N = 10 8 and p max = 2 -20 , for varying m. As we can see, to keep a reasonable number of share carriers, our mechanism can tolerate up to 5% colluding users, which requires 28 share carriers. That is, the probability that enough share carriers are chosen among the 10 7 colluding ones is lower than 2 -20 .

Figure 11 .

 11 Figure 11. Dependance of n SC in m (pmax = 2 -20 and N = 10 8 )

  ) b ′ ← A O inter (•),Ocorr(•),O inv (•) (state, SP b , SPb) 5) Return 1 if b ′ = b; 0 otherwise.In Step 2 of this game, A can make any two users interact.

  σ it AS :

	∧ tAS j=1 Verify(σ

ij , vk SP , rep SP , rnd , vk ASi j ) , Π pre_inv = NIZK Id SP , r pre_inv : pre_inv = Pre_inv(Id SP , r pre_inv ) .

  (vk Cl , id Cl ) (Πcert Cl , nym Cl , C id Cl ) (vk SP , Id SP ) (Πcert SP , nym SP , C Id SP ) (vk SP , rep SP ) (nym SP , rep SP ) Cl , C idCl , C certCl , Π certCl nym SP , C IdSP , C certSP , Π certSP , rep SP , Π rep , pre_inv, Π pre_inv , C SC r SC , σ Cl s SC , σ SP

				Table I
			USERS' CREDENTIALS (BOLD KEYS ARE SECRET)
			Client		Provider	SC	AS
		Element	Commitment	Element	Commitment
	Signature key	sk Cl		sk SP		sk SC	sk AS
	Verification key	vk Cl	nym Cl	vk SP	nym SP	vk SC	vk AS
	Decryption key					dk SC
	Encryption key					ek SC
	Invariant	id Cl	C id Cl	Id SP	C Id SP
	Certificate	cert Cl	Ccert Cl	cert SP	Ccert SP	cert SC	cert AS
	(verified with) Reputation			rep SP
	Cert. of reputation			{σ 1 , . . . , σt AS }	Πrep SP
	(verified with)
	Client		SP
	nym

  describes this interaction. Id SP , vk SP , cert SP , nym SP , C Id SP , Π SP Id SP , vk SP , cert SP , nym SP , C Id SP , Π SP C Id SP , nym SP , PCert SP , Id SP , (C A j ) j , {i j , Q i 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 Transaction identifier idtrans, σ SP , σ Cl idtrans, σ SP , σ Cl idtrans, σ SP , σ Cl

			Table II
		COMPONENTS OF THE REPORT IN THE THREE SCENARII
		Scenario A (honest users)	Scenario B (dishonest client)	Scenario C (dishonest provider)
	Service provider
	Invariant	pre_inv, masked_inv, inv, r pre_inv ,	pre_inv, masked_inv, inv, r pre_inv ,
		Π masked_inv
			Client	SC i	SP
				"Nothing received for id trans "
			"What is your rating
			about id trans ?"
			timeout
				i, R i , Π Ri
				Broadcast of the report
			Figure 5. Interactions between the provider and the share carriers to issue
			the report

  Table II to the share carriers. Cl , Cid Cl , Ccert Cl , Πcert Cl , nym SP , CId SP , Ccert SP , Πcert SP , pre_inv, Πpre_inv, masked_inv, Πmasked_inv, ρ, σρ,Cl idtrans, ρ, masked_inv, Πmasked_inv, σρ,Cl (i, Qi), ΠQ i , σρ,SC i

	Client	SCi	SP
	m1
	idtrans, nym Broadcast of the report	timeout

Table III SIZE

 III OF EXCHANGED MESSAGES FOR n SC = 28 AND n AS = 1, IN KIBIBYTES Phase Cl ↔ SP Cl ↔ SC i SP ↔ SC i 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

  The only difference between those two two games concerns SP k : the adversary has access to either inv(SP k , Cl 0 ) or to a random element R.

	1 n . We k and G i+1 prove that for k ∈ {0, . . . , n}, for i ∈ {1, 2, 3}, G i k are indistinguishable, as well as G 4 k and G 1 k+1 . Hence, games G 0 and G 1 are indistinguishable.
	First, let us prove that games G 1 k and G 2 k are indistin-
	guishable.

This concatenation guarantees that s SC and r SC are chosen independently.

We showed in Section V-B6 that t SC = ⌈n SC /3⌉.