Sébastien Canard

Georg Fuchsbauer

Aline Gouget

Fabien Laguillaumie

Plaintext-Checkable Encryption

Keywords: Deterministic/probabilistic encryption, unlinkability, group signature with VLR and backward unlinkability

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The problem of searching on data that is encrypted has been studied intensively and in many different scenarios. For instance, the problem of delegation of keyword search on private databases to a data storage provider concerns users who upload their data to a provider they do not fully trust. When the user wants to delegate keyword search on his own encrypted data to the provider, he usually has to transmit a corresponding message-dependent trapdoor (or encrypted keyword) which enables the provider to perform the search. When the databases are public, the user wishes to delegate the search on public data to a cloud data storage provider without revealing the plaintext content of the search. Another setting is the delegation of search to an email gateway [START_REF] Boneh | Public key encryption with keyword search[END_REF], where data collected by the mail server is from third parties (contrary to the private-key setting as above) and the database is not public.

Most of the constructions proposed in the literature are based either on symmetric-key cryptography to encrypt the plaintext message or keyword, or on searchable encryption without the ability to decrypt the message as done in [START_REF] Ostrovsky | Skeith III. Private searching on streaming data[END_REF]. The security of the search process in the state of the art of publickey encryption constructions has always been studied assuming that the search process uses a secret trapdoor and not a plaintext message. In this work we focus on this latter case, which is naturally related to public-key cryptography. This case can in practice be very useful when the database contains relations between different words (a name and a status for example) and it is these relations that have to be kept secret rather than the words themselves. Thus, when searching e.g. the number of persons having the status "important illness", the keyword "important illness" is not secret and can be directly used to perform the search. Many functionalities extending the basic setting of public-key encryption have been considered, in particular related to data search. For example, decryptable searchable encryption [START_REF] Fuhr | Decryptable searchable encryption[END_REF] allows someone having a trapdoor corresponding to a message, to test whether a given ciphertext encrypts this message. Another example is encryption with equality test, proposed in [START_REF] Yang | Probabilistic public key encryption with equality test[END_REF]. Using the equality test, one can check whether two ciphertexts encrypt the same plaintext.

In this paper we propose and study a new cryptographic primitive we call plaintext-checkable encryption (PCE). A plaintext-checkable encryption scheme is a probabilistic public-key encryption scheme with the additional functionality that anyone can test whether a ciphertext c is the encryption of a given plaintext message m under a public encryption key pk. Despite this functionality, we demand that the ciphertext leak as little information as possible about the plaintext. Of course, a PCE scheme cannot achieve the standard notion of indistinguishability under chosen-plaintext attack, as an adversary choosing two messages and receiving the encryption of one of them can simply test which message was encrypted. The same holds when the encryption algorithm is deterministic: an adversary can just re-encrypt candidate messages and thus break classical indistinguishability.

As was done in the case of deterministic encryption [START_REF] Bellare | Deterministic and efficiently searchable encryption[END_REF], we assume that the plaintexts are drawn from a space of large min-entropy; indistinguishability means thus the impossibility of distinguishing ciphertexts of messages drawn from different high min-entropy spaces. We show however that we can achieve a strictly stronger security notion than indistinguishability for deterministic encryption [START_REF] Bellare | Deterministic and efficiently searchable encryption[END_REF][START_REF] Bellare | Deterministic encryption: Definitional equivalences and constructions without random oracles[END_REF]: an adversary is not able to distinguish two encryptions of the same message from encryptions of different messages. This notion cannot be achieved by deterministic encryption, since there is only one possible ciphertext per message, and encryption with equality check cannot achieve it either. We say that an encryption scheme satisfies unlinkability if no polynomial-time adversary can win the following game: a challenger draws two messages from a high min-entropy space of the adversary's choice and gives the adversary either encryptions of the two messages or two encryptions of one message, and the adversary has to decide which is the case. We relate this notion to the different types of indistinguishability, showing e.g. that it is strictly stronger than the indistinguishability notion for deterministic encryption, and we argue that our notion is sufficient for our applications. We provide efficient generic constructions of PCE schemes satisfying unlinkability based either on probabilistic or deterministic encryption with a security proof in the random-oracle model (ROM). 1We also build a practical construction based on ElGamal encryption, secure in the standard model.

Apart from its immediate applications to searching on encrypted data, PCE lends itself naturally to improve the efficiency of group signatures with verifierlocal revocation (VLR). Group signatures allow members of a group to sign on behalf of the group without revealing their individual identity. Group signatures with VLR were introduced by Boneh and Shacham [START_REF] Boneh | Group signatures with verifier-local revocation[END_REF] and allow efficient revocation of group members, which is a key issue in practical applications. In VLR group signatures the revocation messages only have to be sent to signature verifiers, as opposed to both signers and verifiers in previous schemes. We note that unlinkability of ciphertexts is precisely the property required by the encryptions contained in group signatures [START_REF] Boneh | Short group signatures[END_REF][START_REF] Camenisch | Group signatures: Better efficiency and new theoretical aspects[END_REF]. We show that PCE can be used to encrypt a user-specific revocation token, like a certificate, which will be part of a group signature. A group member can then be revoked by publishing the token, as every verifier can apply the plaintext check to the encrypted token in order to determine whether it corresponds to a revoked user. Since tokens will be drawn from a high min-entropy space, two group signatures containing the same token are unlinkable by the security of the PCE. Our VLR group signature scheme achieves backward unlinkability and is proven secure in the standard model.

The paper is organized as follows. In Sect. 2 we formally define plaintextcheckable encryption and we give security definitions and compare them to existing security notions for public-key encryption. In Sect. 3 we provide generic constructions of PCE in the random-oracle model based on either deterministic or probabilistic encryption, while Sect. 4 gives the description of our practical construction in the standard model. We finally show in Sect. 5 how PCE can be used to design very practical group signatures with VLR. Due to space limitations, proofs are omitted but are available in the full version.

Plaintext-Checkable Encryption

We define here the notion of plaintext-checkable encryption and its security.

Definition of Plaintext-Checkable Encryption

Let k ∈ N be a security parameter. A plaintext-checkable encryption scheme (PCE for short) is composed of the following algorithms (of which the first 3 constitute a public-key encryption scheme).

-KeyGen is a probabilistic algorithm which takes as input 1 k and outputs a key pair (pk, sk) of public and secret key, respectively.

-Encrypt is a probabilistic algorithm which takes as inputs 1 k , a public key pk and a plaintext m ∈ {0, 1} * and outputs a ciphertext c. -Decrypt is a deterministic algorithm which takes as inputs 1 k , a ciphertext c and a secret key sk and outputs either a plaintext m or ⊥. -PCheck is a deterministic algorithm which takes as inputs 1 k , a ciphertext c, a public key pk and a putative message m. It outputs 1 if c is an encryption of m, and 0 otherwise.

These algorithms must verify the following properties of correctness.

Correctness of decryption: ∀k ∈ N and m ∈ {0, 1} * , Pr (pk, sk)

$ ← -KeyGen(1 k ), c $ ← -Encrypt(1 k , pk, m) : Decrypt(1 k , sk, c) = m = 1.
Correctness of plaintext check (perfect consistency): ∀k ∈ N and m ∈ {0, 1} * , Pr (pk, sk)

$ ← -KeyGen(1 k ), c $ ← -Encrypt(1 k , pk, m) : PCheck(1 k , c, pk, m) = 1 = 1.
The property of perfect consistency is implied by the correctness of decryption and the two following properties, which guarantee that PCheck behaves as expected. The following two notions state that if a ciphertext decrypts to a plaintext then PCheck matches them (completeness) and if PCheck matches a ciphertext to a plaintext then the former encrypts the latter (soundness).

Checking completeness: no adversary is able to output a ciphertext c which decrypts to a message that is refused by PCheck on input c. Formally, for every k ∈ N and every probabilistic polynomial-time (p.p.t.) algorithm A that, on inputs 1 k and a public key pk, outputs a ciphertext c, the following probability should be negligible:

Pr (pk, sk) $ ← -KeyGen(1 k ), c $ ← -A(1 k , pk), m $ ← -Decrypt(1 k , c, sk) : PCheck(1 k , pk, c, m) = 0 .
Checking soundness: this property states that no adversary should be able to produce a plaintext and ciphertext such that the decryption and the check procedures do not agree on the plaintext related to c. More formally, for every k ∈ N and every p.p.t. algorithm A that, on inputs 1 k and a public key pk, outputs a ciphertext c and a plaintext m, the following probability should be negligible:

Pr (pk, sk) $ ← -KeyGen(1 k ), (c, m) $ ← -A(1 k , pk), m $ ← -Decrypt(1 k , c, sk) : m = m ∧ PCheck(1 k , pk, c, m) = 1 .

A Taxonomy of Indistinguishability

The classical property of indistinguishability (for public-key encryption schemes) cannot be achieved by a PCE due to the ability to check the plaintext messages

Exp ind-cpa Π,A (k) b $ ← -{0, 1} (pk, sk) ← G(1 k ) (m0, m1, st) ← A f (1 k , pk) c ← E(1 k , pk, m b ) b ← Ag(1 k , c, st) Return (b = b) Exp unlink Π,A (k) b $ ← -{0, 1} (pk, sk) ← G(1 k ) m0 ← A f (1 k , pk) m1 ← A f (1 k , pk) c0 ← E(1 k , pk, m b ) c1 ← E(1 k , pk, m1) b ← Ag(1 k , pk, c0, c1) Return (b = b) Exp ind-det Π,A (k) b $ ← -{0, 1} m ← A f (1 k , b) (pk, sk) ← G(1 k ) c ← E(1 k , pk, m) b ← Ag(1 k , pk, c) Return (b = b)
Fig. 1. Security experiments for indistinguishability of Π (see below). We discuss in this section the properties of indistinguishability for encryption schemes.

In the following, we denote by Π = (G, E, D) a secure encryption scheme. Depending on the context, Π can be either probabilistic (denoted Π p ) or deterministic (denoted Π d ). We first remark that a PCE can also be represented as an encryption scheme (G, E, D) = (KeyGen, Encrypt, Decrypt), in the notation from Sect. 2.1.

An adversary A is defined by a pair of algorithms denoted by A = (A f , A g ), representing the find and guess stage of the experiment, respectively. The adversary A is said to be polynomial if each constituent algorithm has a running time polynomial in its input length. It is assumed that A f and A g share neither coins nor state. We study three security experiments for the indistinguishability properties of an encryption scheme Π; the three security experiments, denoted by Exp ind-cpa Π,A (k), Exp unlink Π,A (k) and Exp ind-det Π,A (k), are described in Fig. 1. We first define two classes of adversaries.

Definition 1 (High min-entropy). An adversary

A = (A f , A g ) is legitimate if there exists a function (•) s.t. for all c and all m ∈ [A f (1 k , c)] we have |m| = (k) (
where c can be a bit, as for ind-det adversaries, or a public key, as for ind-cpa and unlink adversaries).

Moreover, we say that an adversary

A = (A f , A g ) has min-entropy µ if ∀k ∈ N ∀c ∀m : Pr m ← A f (1 k , b) : m = m ≤ 2 -µ(k) .
A is said to have high min-entropy if it has min-entropy µ with µ(k) ∈ ω(log k).

The first experiment Exp ind-cpa

Π,A (k) represents the standard indistinguishability property for probabilistic encryption schemes.

Definition 2 (IND-CPA). Let k ∈ N, let Π = (G, E, D) be an encryption scheme, let Exp ind-cpa Π,A
be as defined in Fig. 1

and denote Adv

ind-cpa Π,A (k) := 2 • Pr Exp ind-cpa Π,A (k) → true -1.
We say that Π satisfies indistinguishability under a chosen-plaintext attack if for every legitimate p.p.t. adversary A = (A f , A g ), the advantage Adv ind-det Π,A (k) is negligible.

The experiment Exp ind-det Π,A (k) is a simplified definition of the indistinguishability property for deterministic encryption introduced in [START_REF] Bellare | Deterministic encryption: Definitional equivalences and constructions without random oracles[END_REF], which has been shown to be equivalent to the original definition considered in [START_REF] Bellare | Deterministic and efficiently searchable encryption[END_REF]. We simplify the original definition by considering adversaries that produce distributions of messages rather than distributions of message vectors2 . Definition 3 (IND-DET [START_REF] Bellare | Deterministic encryption: Definitional equivalences and constructions without random oracles[END_REF]). Let k ∈ N, let Π = (G, E, D) be an encryption scheme, and let Exp in-det Π,A be as defined in Fig. 1.

Let Adv ind-det Π,A (k) := 2 • Pr Exp ind-det Π,A (k) → true -1. We say Π satisfies ind-det if for every legitimate p.p.t. adversary A = (A f , A g ) with high min-entropy, Adv ind-det Π,A (k) is negligible.
We define the third security experiment as the infeasibility of deciding whether two ciphertexts encrypt the same message. The definition shares with ind-det that the messages have to be chosen from a high min-entropy space: otherwise the notion is not satisfiable by a plaintext-checkable scheme, since the adversary could simply check all messages. As we will show all along this paper, this security definition is achievable by plaintext-checkable schemes and sufficient for our applications.

Definition 4 (UNLINK). Let k ∈ N and Adv unlink Π,A (k) := 2•Pr Exp unlink Π,A (k) → true -1, for an encryption scheme Π = (G, E, D) with Exp unlink
Π,A as defined in Fig. 1. We say Π has unlinkable encryptions (or "satisfies unlink") if for every legitimate p.p.t. adversary A with high min-entropy, Adv unlink Π,A (k) is negligible.

We now give a complete taxonomy of all these security notions and we prove (see the full version) that the unlink notion falls strictly between ind-cpa of probabilistic encryption, and ind-det of deterministic encryption. More precisely, we show the following relation:

IND-CPA UNLINK IND-DET.
This means that every scheme that achieves ind-cpa is unlink and every scheme that achieves unlink is ind-det. On the other hand, there are schemes that are unlink but not ind-cpa, and others satisfying ind-det but not unlink.

It is obvious that a PCE scheme cannot be ind-cpa since the adversary could forward m 0 and m 1 as st from A f to A g , which could then apply PCheck to the challenge c and for example m 0 , and win the experiment with overwhelming probability. As a consequence, the somewhat best we can hope for in the case of PCE is unlinkability. We will thus show that our schemes satisfy this new security notion.

Deterministic encryption schemes [START_REF] Bellare | Deterministic and efficiently searchable encryption[END_REF], though trivially plaintext-checkable, cannot satisfy the property unlink since every two encryptions of a message are equal, which allows a trivial check of plaintext equality. One may attempt to construct plaintext-checkable encryption from an encryption scheme with equality test as described in [START_REF] Yang | Probabilistic public key encryption with equality test[END_REF] by simply encrypting the message and then performing the test of equality. However, this scheme does not satisfy unlink either for obvious reasons. Moreover, as noticed by the authors, their Test function only works properly when the ciphertexts are two real encryptions of messages, as this procedure does not check the validity of the ciphertexts.

It thus remains open to give a construction (practical or generic) with the above features, namely providing a PCheck procedure, while maintaining unlinkability. We give such constructions in the two following sections.

Generic Constructions for PCE in the ROM

We show how to obtain secure PCE schemes using a secure probabilistic or deterministic encryption scheme with security proofs in the random-oracle model.

A PCE based on a Probabilistic Encryption Scheme

In this construction a message m is encrypted by first choosing a random string r and computing a hash value ρ of the message and r. This value ρ is then used as the random coins of the probabilistic encryption algorithm to encrypt m, and r is added to the ciphertext. The algorithm PCheck consists essentially in re-computing ρ and then re-encrypting the message with random coins ρ and comparing it to the candidate ciphertext. Our solution is described in Fig. 2. The triple Π p = (G p , E p , D p ) denotes a probabilistic encryption scheme satisfying indistinguishability under chosen-message attack, and H : {0, 1} * → {0, 1} (k) denotes a hash function modeled as a random oracle. The following theorem states the security of the construction of Fig. 2,i.e. that it satisfies unlinkability. Essentially, the unlinkability of this construction follows from the indistinguishability of the underlying encryption scheme. However, quite some care needs to be taken to ensure that the simulation in the reduction is perfect, as the adversary against unlinkability may make queries to the random oracle that the simulator cannot answer.

Algorithm KeyGen(1 k ) (pk, sk) $ ← -Πp.Gp(1 k ) pk ← pk sk ← sk return (pk, sk) Algorithm Encrypt(1 k , pk, m) pk ← pk r $ ← -{0, 1} (k) ρ ← H(m r) c ← Πp.Ep(1 k , pk, m; ρ) C ← (c, r) return C Algorithm Decrypt(1 k , sk, C) (c, r) ← C sk ← sk m ← Πp.Dp(1 k , sk, c) return m Algorithm PCheck(1 k , pk, C, m) (c, r) ← C pk ← pk ρ ← H(m r) c ← Πp.Ep(1 k , pk, m; ρ) if c = c then return 1 else return 0
Theorem 1. If Π p satisfies ind-cpa then the PCE from Fig. 2 satisfies unlink.

Proof (sketch, see full version for the full proof ). We show that a successful adversary A against unlink of our PCE scheme can be used to construct an adversary B against ind-cpa of Π p . A natural construction of B is the following: B f runs A f twice and outputs the obtained messages m 0 and m 1 . The challenger then gives B g a Π p -encryption c of m b . Now B g must use A g to determine b. Playing the unlinkability game, A g expects two PCE ciphertexts; one of m b and one of m 1 . While the latter can be computed honestly, B g could construct the former as (c, r 0 ), for some random r 0 .

However, this implicitly defines H(m b , r 0 ) to be the randomness B's challenger used in constructing c; B can thus not answer this random-oracle query and the simulation might fail. In a series of lemmas, we show that under ind-cpa of Π p , the probability of A g (who does not know m 0 and m 1 ) querying m 0 or m 1 to H is negligible. We first show that this holds if B's challenger's bit b = 0: Suppose in game unlink when b = 0, A g queries (m 0 r) (for some r) to the random oracle H. Then we construct B that breaks ind-cpa. It uses A f to sample m 0 and m 1 , gets an encryption c of m d from its challenger and then runs A g on (c, r 0 ) (for some random r 0 ) and a PCE encryption of an independent message m . Since A g does not have any information on m 1-d (which was sampled from a high min-entropy space), querying e.g. m 0 must mean d = 0. Thus if A g makes a query to H containing m d , B g outputs d as its guess. Note that the issue of correctly simulating the random oracle does not arise here, as B g aborts as soon as A g makes a critical query. Analogously, we show that when b = 0, the probability that A g queries (m 1 •) is negligible.

It remains to prove that when b = 1 then A g queries (m 1 •) with negligible probability. Again, assuming A g makes such a query, we construct B breaking ind-cpa. As before, B uses A f to sample m 0 and m 1 and receives c. Now B g picks a random bit d and sends A g the following: (c, r 0 ), for some random r 0 and a PCE encryption of m d . If A g queries (m d •) then B g outputs d. (Note that up to this point, the simulation is perfect.) We show that B wins the indistinguishability game. If d equals B 's challenger's bit then A g gets two encryptions of the same message; A is thus playing the unlink game with b = 1, for which we assumed A g queries the encrypted message to H with non-negligible probability, in which case B wins. On the other hand, if d is different from the challenger's bit (in which case B loses) then A gets encryptions of two different messages and it is thus playing unlink with b = 0. For this case however, the previous result for b = 1 asserts that A will not query an encrypted message to the random oracle.

Algorithm KeyGen(1 k ) (pk, sk) $ ← -Π d .G d (1 k ) pk ← pk sk ← sk return (pk, sk) Algorithm Encrypt(1 k , pk, m) pk ← pk r $ ← -{0, 1} (k) ρ ← H1(m r) c1 ← Π d .E d (1 k , pk, ρ) c2 ← m ⊕ H2(ρ) C ← (c1, c2, r) return C Algorithm Decrypt(1 k , sk, C) (c1, c2, r) ← C sk ← sk ρ ← Π d .D d (1 k , sk, c1) m ← c2 ⊕ H2(ρ) if ρ = H1(m||r) then return m Algorithm PCheck(1 k , pk, C, m) (c1, c2, r) ← C pk ← pk ρ ← H1(m r) c ← Π d .E d (1 k , pk, ρ) if c = c1
then return 1 else return 0 Fig. 3. Unlinkable PCE from a deterministic encryption scheme Π d

A PCE based on a Deterministic Encryption Scheme

Let Π d = (G d , E d , D d ) be a secure deterministic encryption scheme, meaning that it satisfies the ind-det property as defined in [START_REF] Bellare | Deterministic encryption: Definitional equivalences and constructions without random oracles[END_REF] and recalled in Sect. 2.2. Let H 1 : {0, 1} * → {0, 1} (k) and H 2 : {0, 1} * → {0, 1} (k) be two hash functions modeled as random oracles.

The idea behind this construction is to encrypt with the deterministic encryption algorithm a hash value ρ of the message m together with a random element r and then to compute a one-time pad of the message and the hash value of ρ. We include r in the ciphertext, so knowing m and r, one can recompute the (deterministic) ciphertext and thus perform the plaintext check.

Our random-oracle based construction is detailed in Fig. 3, and Corollary 1 states its security. As we will see, this theorem is a consequence of Theorem 1.

Corollary 1 (sketch, see full version for the full proof ). The PCE construction given in Fig. 3 is unlinkable under the assumption that Π d is one-way, in the random-oracle model.

Proof (sketch, see full version for the full proof )

. This proof is a direct application of Theorem 1 combined with the result from [START_REF] Bellare | Random oracles are practical: A paradigm for designing efficient protocols[END_REF] which states that the encryption scheme which consists in computing c 1 ← Π d .E(1 k , pk, r) and c 2 ← m ⊕ H 2 (r), where r $ ← -{0, 1} (k) , is ind-cpa if the underlying deterministic encryption scheme Π d is one-way.

Practical Constructions in the Standard Model

A construction of a secure plaintext-checkable encryption can be proved in the standard model using the technique from [START_REF] Bellare | Deterministic encryption: Definitional equivalences and constructions without random oracles[END_REF] for deterministic encryption (see Fig. 3 of [START_REF] Bellare | Deterministic encryption: Definitional equivalences and constructions without random oracles[END_REF]): one replaces the random oracle by a pseudo-random generator [START_REF] Blum | How to generate cryptographically strong sequences of pseudo-random bits[END_REF][START_REF] Andrew | Theory and applications of trapdoor functions (extended abstract)[END_REF][START_REF] Goldreich | A hard-core predicate for all one-way functions[END_REF] based on a family of trapdoor permutations. As for the previous construction, the idea is to use a secure encryption scheme whose randomness is generated using a secure pseudo-random generator with a seed depending on the message and the random value used to check the plaintext. We here give another practical construction based on the ElGamal encryption scheme [START_REF] El | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF], which we will then use for our standard-model VLR group signature scheme given in Sect. 5.

An ElGamal-Based Construction

Our construction lies in an asymmetric bilinear group (p, G 1 , G 2 , G T , e, g, h) where p is a large prime, G 1 , G 2 and G T are cyclic groups of order p and e : G 1 × G 2 → G T is a non-degenerate bilinear map. The elements g and h denote generators of G 1 and G 2 , respectively. In our scheme, the idea is to encrypt a message m under a public key y using randomness r as c 1 = my r , c 2 = g r . If we gave c 3 = h r as well, then using the pairing we can perform plaintext checks since e(c 1 m -1 , g) = e(y, c 3 ). However, this construction does not achieve unlinkability, since we can check whether 2 ciphertexts encrypt the same message by checking whether their quotient encrypts 1. To avoid this, instead of using h as a base for the check element c 3 , we use a random base h a . Since this base is different for every ciphertext, no two ciphertexts can be combined. Our construction is described in Fig. 4 and allows to encrypt messages m ∈ G 1 .

Algorithm KeyGen(1 k ) x $ ← -Z * p y ← g x (pk, sk) ← (y, x) return (pk, sk) Algorithm Encrypt(1 k , pk, m) y ← pk r, a $ ← -Z * p C ← (my r , g r , h a , h ar ) return C Algorithm Decrypt(1 k , sk, C) x ← sk (c1, c2, c3, c4) ← C if e(g, c4) = e(c2, c3) then return ⊥ m ← c1/c x 2 return m Algorithm PCheck(1 k , pk, C, m) y ← pk (c1, c2, c3, c4) ← C if e(g, c4) = e(c2,

Security Arguments

To prove unlinkability of the construction in Fig. 4, we introduce a new assumption (whose security in the generic-group model is proved in the full version), which combines features of the Decision Linear Assumption (DLIN) and the assumption that DDH holds in both base groups of an asymmetric bilinear group (known as "SXDH").

Assumption 1 Given an asymmetric bilinear group (p, G 1 , G 2 , G T , e) with generators g ∈ G 1 and h ∈ G 2 , and the tuple (g x , g rx , g sx , h a , h ar , h b , h br , V ) for random x, r, s, a, b ∈ Z p , it is hard to decide if V = g r+s or V is random in G 1 .

Let us first analyze the G 1 part of our assumption: (g x , g rx , g sx ) and g r+s . DLIN states that given (g x , g y , g rx , g sy ) it is hard to distinguish g r+s from random. The G 1 components of our assumption can thus be seen as a DLIN instance with y = x (note that whereas DLIN also holds in symmetric groups, this is not the case when y = x). It is also immediate that this "partial" assumption is a DDH instance where s = 0, and thus implied by DDH. However, since-as opposed to DDH-we have two random combined exponents r and s for the challenge, this allows us to add values depending on them in G 2 , which cannot be used to verify the structure of g r+s , since the bases h a and h b for r and s are different.

The following theorem holds against adversaries A = (A f , A g ) where A f outputs the uniform distribution. This restriction is similar to the results by Bellare et al. [START_REF] Bellare | Deterministic and efficiently searchable encryption[END_REF] for their practical construction of a deterministic encryption scheme. In fact, in real life applications, the uniform distribution is most of time enough and easily obtained. In particular, this notion also suffices when applying the scheme to VLR group signatures.

Theorem 2. Under Assumption 1, the construction from Fig. 4 is a PCE scheme which is unlink against adversaries outputting the uniform distribution.

Application to VLR Group Signature

In this section we use our new primitive as a building block for group signatures with verifier-local revocation (VLR) [START_REF] Boneh | Group signatures with verifier-local revocation[END_REF]. This is a group signature scheme [START_REF] Ateniese | A practical and provably secure coalition-resistant group signature scheme[END_REF][START_REF] Boneh | Short group signatures[END_REF] which allows an efficient revocation of group members.

Our aim in this section is twofold. First, we present plaintext-checkable encryption as a new building block for group signatures with VLR; thus any improvement to PCE is likely to lead to more efficient group signatures with VLR. Second, we design in the following, to the best of our knowledge, the most efficient group signature scheme with VLR and backward unlinkability in the standard model. We first recall the concept of group signatures with VLR, and eventually describe our new construction.

Definitions for Group Signatures with VLR

Let k, n and T be integers. A group signature scheme with VLR (VLR-GS for short) is composed of the following algorithms (following [START_REF] Libert | Group signatures with verifier-local revocation and backward unlinkability in the standard model[END_REF]).

-KeyGen takes as input a security parameter 1 k , the number n of group members and the number T of time periods. It produces the group public key gpk, an n-element vector of user keys sk = (sk 1 , . . . , sk n ) and an (n × T )-element vector of user revocation tokens grt = (grt [START_REF] Abe | Structure-preserving signatures and commitments to group elements[END_REF][1], . . .

, grt[n][T ]).

Appeared in Orr Dunkelman (Ed.): CT-RSA 2012, volume 7178 of LNCS, pp. 332-348, 2012. c Springer-Verlag Berlin Heidelberg 2012

-Sign takes as input the group public key gpk, the current time interval j, a secret key sk i for i ∈ [ [1, n]] of a group member and a message m ∈ {0, 1} * , and outputs a signature σ. -Verify takes as input the group public key gpk, the current time period j, the public key of the revocation authority rpk, a set of revocation tokens RL j , and a purported signature σ on a message m. It returns either valid if the signature σ is valid or invalid if σ is not a valid signature or if the user who generated it has been revoked.

The security requirements are traceability and backward unlinkability (BU) anonymity. The corresponding formal definitions can be found in [START_REF] Libert | Group signatures with verifier-local revocation and backward unlinkability in the standard model[END_REF]. We only recall the BU-anonymity since adding the VLR functionality to a group signature scheme only concerns this security notion, whereas traceability is inherited from the original scheme. A VLR-GS with backward unlinkability is BU-anonymous if no p.p.t. adversary A has non-negligible advantage in the following game.

1. The challenger C executes (gpk, sk, grt) $ ← -KeyGen(1 k , n, T ) and the adversary is given gpk. 2. For each period, C increments the counter j and during this period, A can access the Sign(•, •) oracle, which gives a group signature on a message m by a user i during time period j, the Corrupt(•) oracle, which permits to corrupt the user i and the Revoke(•) oracle, which revokes the member i. 3. At some period j * ∈ [1, T ], A outputs (m * , i 0 , i 1 ) such that i 0 and i 1 are not corrupted and have not been revoked during or before the time period j * . The challenger C flips a coin b and generates σ * $ ← -Sign(gpk, j * , sk i b , m * ), which is sent to A. 4. A can again access the above oracles. A is not allowed to corrupt i 0 nor i 1 but it may revoke them after time period j * . 5. Eventually, A outputs a bit b * and wins if b = b * . The advantage of A in breaking this anonymity is defined as Adv bu-a VLR-GS,A (k

) := | Pr[b = b * ] -1 2 |.

Using PCE for Group Signatures with VLR

Starting with a group signature scheme. For concreteness, we base our instantiation on the group signature scheme by Fuchsbauer and Abe et al. in [START_REF] Fuchsbauer | Automorphic signatures in bilinear groups and an application to round-optimal blind signatures[END_REF][START_REF] Abe | Structure-preserving signatures and commitments to group elements[END_REF], which is itself based on Groth's scheme [START_REF] Groth | Fully anonymous group signatures without random oracles[END_REF], which makes use of the noninteractive zero-knowledge (NIZK) proofs from Groth and Sahai [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF].

In a nutshell, each user creates a key pair for an automorphic signature scheme3 [START_REF] Fuchsbauer | Automorphic signatures in bilinear groups and an application to round-optimal blind signatures[END_REF][START_REF] Abe | Structure-preserving signatures and commitments to group elements[END_REF]. The group public key is a signature verification key, whose corresponding signing key is used by the group manager to sign a user's verification key when he joins the group. To make a group signature, the user first signs the message using his personal signing key; the group signature is then a Groth-Sahai proof of knowledge of the following: the user's verification key, a valid certificate on it by the group manager, and a signature on the message that is valid under his verification key. Since the registration protocol consists of only one round, the scheme is concurrently secure. Moreover, since the group members create their own signing keys, the scheme achieves non-frameability [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF].

Adding the VLR property. When adding verifier-local revocability, to achieve backward unlinkability, we use the system due to Nakanishi and Funabiki [START_REF] Nakanishi | Verifier-local revocation group signature schemes with backward unlinkability from bilinear maps[END_REF]. This consists in defining time periods and constructing one key (called the revocation token) per group member and time period. This token is to be used by the group member when making a group signature. When a member is revoked, all the revocation tokens related to the revoked group member and future time periods are published. These public revocation tokens are then used by the verifier to check whether the received group signature has been produced with a published value, and thus by a revoked group member.

Making use of a PCE. The group signature cannot contain the revocation token in the clear, as this would compromise the member's anonymity. Our approach is to include in the group signature a plaintext-checkable encryption of the revocation token, together with a proof of well-formedness. When a revoked group member's token gets published, the verifier can use PCheck of the PCE scheme to check whether the group signature comes from a revoked member or not. For our concrete scheme, we use the standard-model PCE scheme from Sect. 4.1, since it complies with the Groth-Sahai methodology.

Our Concrete Instantiation

We will use the group signature scheme on which we base our construction as a black box and simply add one PCE encryption and a proof of consistency to make it a VLR scheme. We require that the group signature is a Groth-Sahai proof of knowledge in an asymmetric bilinear group (p, G 1 , G 2 , G T , e, g, h) and that the user verification key contains a component h vi , where v i is the i-th user's signing key. (This is the case e.g. in the construction from [START_REF] Fuchsbauer | Automorphic signatures in bilinear groups and an application to round-optimal blind signatures[END_REF][START_REF] Abe | Structure-preserving signatures and commitments to group elements[END_REF]).

In the setup phase of scheme (when the common reference string for Groth-Sahai proofs is created), we now also create a key pair (y = g x , x) ∈ G 1 × Z p for our PCE scheme from Sect. 4.1 and add y to the public parameters. As in [START_REF] Nakanishi | Verifier-local revocation group signature schemes with backward unlinkability from bilinear maps[END_REF][START_REF] Libert | Group signatures with verifier-local revocation and backward unlinkability in the standard model[END_REF], we introduce a vector (P 1 , . . . , P T ) of G 1 elements, where T is the maximum number of time periods. The revocation token for user i (holding secret key v i ) for time interval j is defined as P vi j . When creating a group signature, the user must additionally encrypt his token for the current time interval and prove that it is well-formed. The token is of the form P v , so we need to prove that v is the same as in the user verification key element w := h v (of which the group signature will prove knowledge). The PCE encryption of the token is C = (C 1 , C 2 , C 3 , C 4 ) = (P v y r , g r , h a , h ar ). To prove well-formedness, we introduce an auxiliary variable z := h r , of which we also prove knowledge in the group signature. Groth-Sahai proofs allow us to prove knowledge of group elements that satisfy pairing-product equations (PPE). Let v be such that P v is the plaintext of C. Then the following PPEs assert that w = h v (the group elements of which we prove knowledge are underlined): e(C 1 , h) = e(P, w) e(y, z) and e(C 2 , h) = e(g, z).

In addition to C, we include in the group signature a Groth-Sahai NIZK proof that the above equations are satisfied. Our new verification procedure now additionally checks this new proof component, and runs PCheck on C and the elements of the revocation list to check if the user has been revoked.

We note that our techniques also work if the verification key contains g v rather than h v : we can introduce a second encrypted auxiliary variable z := h v and add a proof of e(g v , h) = e(g, z ). We have thus shown that adding to a Groth-Sahai based group signature scheme (with user verification keys containing a generator to the power of the signing key) a plaintext-checkable encryption of a token, gives a group signature scheme with VLR and backward unlinkability.

Backward-Unlinkable Anonymity

We outline the proof that our scheme satisfies backward-unlinkable anonymity. The proof proceeds by a series of games. The first game is the experiment defined in Sect. 5.1. In the second game, instead of running KeyGen, we compute the common reference string for Groth-Sahai proofs in a way that will lead to perfectly hiding proofs of knowledge, which can be simulated. By the zero-knowledge property of Groth-Sahai proofs, the first two games are indistinguishable. In Game 3, the challenger picks 2 random users, hoping they will be the challenge users i 0 and i 1 output by the adversary in Step 3 of the game. If the challenger did not guess these users correctly, it aborts the game. This introduces a polynomial loss in the security reduction.

In Game 4 the challenger simulates the NIZK proofs in the following signatures it gives to the adversary: all signatures in signing queries for users i 0 and i 1 queried up to the challenge time period j * ; and the challenge signature σ * . It follows from the zero-knowledge property of Groth-Sahai proofs that Game 4 is indistinguishable from Game 3.

We can now play with the plaintext-checkable encryptions C of tokens which are given to the adversary as part of the simulated group signature (either in a signing query for users i 0 and i 1 in time j < j * or the challenge signature). Since the proof of consistency of these C's is simulated, we can change the actual values, which we will do in the following. Next, when computing the values P j during setup, the challenger sets them as P j := g dj and stores d j . We now define a series of games, in which, one by one, we replace tokens P vi 0 1 , . . . , P vi 0 j * and tokens P vi 1 1 , . . . , P vi 1 j * by random values. This is reduced to the DDH assumption, which implies that given values g d and g v , we can replace g dv by a random value. Note that given a DDH challenge, the challenger can use the logarithms d j to compute the values P vi j it is not changing in that step. After this series of games, the only dependency of the challenge signature on the bit b occurs when the adversary asks for a signature of user i b in time interval j * . Since the tokens are chosen uniformly at random, we can replace the encryption of the token in the challenge signature by a random value. This is implied by unlinkability of our PCE scheme (which states that two encryptions of the same value are indistinguishable from two encryptions of two different (random) values). After this final step the challenge signature is independent of b and the adversary's winning probability is thus exactly 1 2 .

Comparison with Related Work

Regarding related work on group signature schemes with VLR, there are typically 3 criteria to compare such schemes: random-oracle or standard model, anonymity revocation or not and backward unlinkability or not. Table 1 compares all existing solutions, to the best of our knowledge. Achieving CCA security. An additional property not considered in the above table is CCA-anonymity, meaning the scheme remains anonymous even if the adversary has an oracle to open signatures of its choice, as considered e.g. in the model by Bellare et al. [6]. This notion is achieved by variants of the group signature schemes on which we base our VLR scheme, using one-time signatures and a weakly CCA tag-based encryption scheme, as proposed by Groth in [START_REF] Groth | Fully anonymous group signatures without random oracles[END_REF].

The tag-based encryption scheme used is Kiltz's construction [START_REF] Kiltz | Chosen-ciphertext security from tag-based encryption[END_REF] is secure under the DLIN assumption [START_REF] Boneh | Short group signatures[END_REF] and is defined over symmetric bilinear groups. As DDH is easy in such groups, our PCE scheme would not be secure and can thus not be added to these schemes. We believe however that starting from linear encryption [START_REF] Boneh | Short group signatures[END_REF] rather than ElGamal, and adding elements enabling plaintext checkability, one could define a PCE scheme over symmetric bilinear groups.

Efficiency considerations. We can now compare the efficiency of standard model group signatures with VLR and backward unlinkability, which amounts to comparing us with the scheme by Libert and Vergnaud [START_REF] Libert | Group signatures with verifier-local revocation and backward unlinkability in the standard model[END_REF]. On one hand, regarding [START_REF] Libert | Group signatures with verifier-local revocation and backward unlinkability in the standard model[END_REF], a group signature is composed of 46 elements in G and 1 element in G T . The time complexity of a group-signature creation necessitates 2 modular exponentiations in G, 6 commitment generations, 2 quadratic GS proofs and 4 linear GS proofs. The revocation checking requires the computation of one pairing per element in RL j . On the other hand, our signatures are composed of 12 elements in G 1 , 18 elements in G 2 and no element in G T . The signer must perform 6 modular exponentiations, 1 quadratic GS proofs and 5 linear GS proofs. The revocation checking requires the computation of 2 pairings per element in RL j . Considering moreover that in asymmetric groups, representations of group elements are shorter and computation of pairings are much more efficient, our scheme is more efficient in terms of signature computation and size but necessitates slightly more work during the revocation check.

Conclusion

We proposed a new promising public-key encryption scheme with a special feature: this primitive allows anyone to verify whether a given ciphertext (together with the public key used to encrypt) actually encrypts any potential message. However, if the messages come from a space with enough entropy, one cannot decide whether two ciphertexts encrypt the same message. Plaintext-checkable encryption with unlinkable ciphertexts is perfectly adapted to design group signatures with verifier-local revocation and backward unlinkability. The efficiency of the constructions also enables its use in a context of cloud storage services.

Fig. 2 .

 2 Fig. 2. Unlinkable PCE from an ind-cpa encryption scheme Πp

0 Fig. 4 .

 04 Fig. 4. Unlinkable PCE in the standard model

Table 1 .

 1 Related work on group signatures with VLR

	Papers	Standard	Anonymity	Backward
		model	revocation	unlinkability
	[10]	No	No	No
	[20, 21, 25]	No	Yes	Yes
	[19]	Yes	(Yes)	Yes
	Ours	Yes	(Yes) 4	Yes

Appeared in Orr Dunkelman (Ed.): CT-RSA 2012, volume 7178 of LNCS, pp. 332-348, 2012. c Springer-Verlag Berlin Heidelberg 2012

It may be possible to design PCE schemes from any decryptable searchable encryption scheme by simply publishing trapdoors (one trapdoor per message or, in some cases, the master trapdoor). However, our constructions are more efficient.Appeared in Orr Dunkelman (Ed.): CT-

RSA 2012, volume 7178 of LNCS, pp. 332-348, 2012. c Springer-Verlag Berlin Heidelberg 2012

The original definition considers vectors of messages since (unlike for ind-cpa-secure encryption) there is no reduction to the single-message case by a hybrid argument for deterministic encryption.Appeared in Orr Dunkelman (Ed.): CT-RSA 2012, volume 7178 of LNCS, pp.

[332][333][334][335][336][337][338][339][340][341][342][343][344][345][346][347][348] 2012. c Springer-Verlag Berlin Heidelberg 2012

A signature scheme defined over a bilinear group is automorphic if the verification keys lie in the message space, and if the messages and the signatures consist of group elements. The first property enables certification of keys, whereas the second makes it possible to give efficient NIZK proofs of knowledge of valid signatures and messages using Groth-Sahai proofs. Appeared in Orr Dunkelman (Ed.): CT-RSA 2012, volume 7178 of LNCS, pp. 332-348, 2012. c Springer-Verlag Berlin Heidelberg 2012

Not explicitly detailed but can be easily added by giving the trapdoor for the CRS of Groth-Sahai proofs to the opener. Appeared in Orr Dunkelman (Ed.): CT-RSA 2012, volume 7178 of LNCS, pp. 332-348, 2012. c Springer-Verlag Berlin Heidelberg 2012

Acknowledgements: This work has been supported by the French Agence Nationale de la Recherche under the PACE 07 TCOM Project, the European Commission under Contract ICT-2007-216676 ECRYPT II and EPSRC Grant EP/H043454/1. We are grateful to Jacques Traoré for his suggestions of improvement, and to the anonymous referees for their valuable comments.


J Doncel

U Ayesta

O Brun

B J Prabhu

On the Efficiency of Non-Cooperative Load Balancing

Price of Anarchy is an oft-used worst-case measure of the inefficiency of non-cooperative decentralized architectures. In practice, though, the worst-case scenario may occur rarely, if at all. For non-cooperative decentralized load-balancing in server farms, we show that the Price of Anarchy is an overly pessimistic measure that does not reflect the performance obtained in most instances of the problem. In the case of two classes of servers, we show that non-cooperative load-balancing provides a closeto-optimal solution in most cases, and that the worst-case performance given by the Price of Anarchy occurs only in a very specific setting, namely, when the slower servers are infinitely more numerous and infinitely slower than the faster ones. We explicitly characterize the worst-case traffic conditions for the efficiency of non-cooperative loadbalancing schemes, and show that, contrary to a common belief, the worst inefficiency is in general not achieved in heavy-traffic or close to saturation conditions.

I. INTRODUCTION

Server farms are commonly used in a variety of applications, including cluster computing, web hosting, scientific simulation or even the rendering of 3D computer generated imagery. A central problem arising in the management of the distributed computing resources of a data center is that of balancing the load over the servers so that the overall performance is optimized. In a centralized architecture, a single dispatcher, or a routing agent, routes incoming jobs to a set of servers so as to optimize a certain performance objective, such as the mean processing time of jobs for instance. However, modern data centers commonly have thousands of processors and up, and it becomes difficult or even impossible to centrally implement a globally optimal load-balancing solution. For instance, Akamai Technologies revealed, in march 2012, that it operates 105,000 servers [START_REF] Miller | Who has the most web servers?[END_REF]. Similarly, it is estimated that Google has more than 900,000 servers, and the company recently revealed that container data center holds more than 45,000 servers in a single facility built in 2005 [2]. The ever growing size and complexity of modern server farms thus calls for decentralized control schemes.

In a decentralized routing architecture, several dispatchers are used with each one routing a certain portion of the traffic. There are several possible approaches for the implementation of decentralized routing mechanisms. Approaches based on distributed optimization techniques [START_REF] Bertsekas | Parallel and Distributed Computation: Numerical Methods[END_REF], [START_REF] Mosk-Aoyama | Fully distributed algorithms for convex optimization problems[END_REF], can be cumbersome to implement and can have significant synchronisation and communication overheads, thus reducing the scalability of the decentralized routing scheme.

An alternative approach is based on autonomous, selfinterested agents [START_REF] Roughgarden | Selfish Routing and the Price of Anarchy[END_REF]. Such routing schemes are also known as "selfish routing" since each dispatcher independently seeks to optimize the performance perceived by the jobs it routes. This setting can be analysed within the framework of a non-cooperative routing game. The strategy that rational agents will choose under these circumstances is called a Nash Equilibrium and it is such that a unilateral deviation will not help any routing agent in improving the performance perceived by the traffic it routes.

Apart from the obvious gain in scalability with respect to a centralized setting, there are wide-ranging advantages to non-cooperative routing schemes: ease of deployment, no need for coordination between the routing agents that just react to the observed performances of the servers, and robustness to failures and environmental disturbances. However, it is well-known that noncooperative routing mechanisms are potentially inefficient. Indeed, in general, the Nash equilibrium resulting from the interactions of many self-interested routing agents with conflicting objectives does not correspond to an optimal routing solution; hence, the lack of regulation carries the cost of decreased overall performance.

A standard measure of the inefficiency of selfish routing is the Price of Anarchy (PoA) which was introduced by Koutsoupias and Papadimitriou [START_REF] Koutsoupias | Worst-case equilibria[END_REF]. It is defined as the ratio between the performance obtained by the worst Nash equilibrium and the global optimal solution. Thus the PoA measures the cost of having no central authority, irrespective of a specific data center architecture. A value of the PoA close to 1 indicates that, in the worst case, the gap between a Nash Equilibrium and the optimal routing solution is not significant, and thus that good performances can be achieved even without a centralized control. On the contrary, a high PoA value indicates that, under certain circumstances, the selfish behaviour of the dispatchers leads to a significant performance degradation.

Several recent works have shown that non-cooperative load-balancing1 can be very inefficient in the presence of non-linear delay functions, see, for example, [START_REF] Haviv | The price of anarchy in an exponential multi-server[END_REF], [START_REF] Bell | Individual versus social optimization in the allocation of customers to alternative servers[END_REF], [START_REF] Ayesta | Price of anarchy in noncooperative load-balancing games[END_REF], and [START_REF] Chen | The effect of local scheduling in load balancing designs[END_REF]. We just mention two of them here. First, Haviv and Roughgarden have considered in [START_REF] Haviv | The price of anarchy in an exponential multi-server[END_REF] the socalled non-atomic scenario where every arriving job can select the server in which it will be served. They have shown that in this scenario the PoA corresponds to the number of servers, implying that, in a server farm with S servers, the mean response time of jobs can be as high as S times the optimal one! Another important result on the PoA was proved by Ayesta et al. in [START_REF] Ayesta | Price of anarchy in noncooperative load-balancing games[END_REF]. They investigate the price of anarchy of a load balancing game with a finite number, say K, of dispatchers, and with a price per unit time to be paid for processing a job, which depends on the server. They prove that for a system with two or more servers, the price of anarchy is of the order of √ K, independently of the number of servers, implying that when the number of dispatchers grows large, the PoA grows unboundedly. The fact that the Nash equilibrium can be very inefficient has paved the way to a lot of research on mechanism design that aims at coming up with Nash equilibria that are efficient with respect to the centralized setting [START_REF] Korilis | Achieving network optima using stackelberg routing strategies[END_REF], [START_REF] Korilis | Architecting noncooperative networks[END_REF], [START_REF] Roughgarden | Selfish Routing and the Price of Anarchy[END_REF].

In this paper, we adopt the view that the worstcase analysis (PoA) of the inefficiency of selfish routing is overly pessimistic and that high PoAs are obtained in pathological instances that hardly occur in practice. For example, in [START_REF] Haviv | The price of anarchy in an exponential multi-server[END_REF], the worst-case architecture has one server whose capacity is much larger (tending to infinity) compared to that of the other servers. It is doubtful that such asymmetries will occur in data-centers where processors are more than likely to have similar characteristics.

While the architecture of a data-center is more or less fixed, the incoming traffic volume can vary as a function of time. Thus, for applications such as data-centers, it seems more appropriate to compare the performance of selfish routing and the centralized setting for different traffic profiles and a fixed data-center architecture (number of servers and their capacities). For this reason, we define the inefficiency as the performance ratio between the worst-case Nash equilibrium and the global optimal. The worst-case case is taken over all possible traffic profiles that the routing agents can be asked to route. As is true of the PoA, inefficiency can take values between 1 and ∞. A higher value of inefficiency indicates a worse performance of selfish routing compared to centralized routing. As opposed to the PoA, the inefficiency depends on the parameters (the server speeds and the number of servers in our case) of the architecture. By calculating the worst possible inefficiency, one retrieves the PoA.

The main contributions in this work are the following:

• For an arbitrary architecture in the system, we characterize the traffic conditions (or load) associated with the inefficiency. Contrary to classical queueing theory, we show that the inefficiency is in general not achieved in heavy-traffic or close to saturation conditions. In fact, we show that the inefficiency is close to 1 in heavy-traffic. We also provide examples for which the inefficiency is obtained for fairly low values of the utilization rate. • In the case of two server classes, we show that the inefficiency is obtained when selfish routing uses only one class of servers and is marginally using the second class of servers. This scenario was used in [START_REF] Haviv | The price of anarchy in an exponential multi-server[END_REF], [START_REF] Ayesta | Price of anarchy in noncooperative load-balancing games[END_REF] to obtain a lower bound on the PoA for their models. We give a formal proof on why this is indeed the worst-case scenario for selfish routing. Further, we obtain a closed-form formula for the inefficiency which in particular depends only on the ratio of the number of servers in each class and on the ratio of the capacities of each class (but not on the total nor on their capacities). When the number of servers is large, we also show that the PoA is equal to

K 2 √ K-1
, where K is the number of dispatchers.

• We then show that the inefficiency is very close to 1 in most cases, and that it approaches the known upper bound (given by the PoA) only in a very specific setting, namely, when the slower servers are infinitely more numerous and infinitely slower than the faster ones.

The rest of the paper is organized as follows. In section II we describe the model. In section III we show that the inefficiency of selfish routing does not occur in heavytraffic. In section IV, we give more precise results for server farms with two classes of servers. We give the expression for the load which leads to inefficiency, and the corresponding value of the inefficiency. Finally, the main conclusions of this work are presented in section V.

II. PROBLEM FORMULATION

We consider a non-cooperative routing game with K dispatchers and S Processor-Sharing servers. Denote C = {1, . . . , K} to be the set of dispatchers and S = {1, . . . , S} to be the set of servers. Jobs received by dispatcher i are said to be jobs of stream i.

Server j ∈ S has capacity r j . It is assumed that servers are numbered in the order of decreasing capacity, i.e., if m ≤ n, then r m ≥ r n . Let r = (r j ) j∈S denote the vector of server capacities and let r = n∈S r n denote the total capacity of the system. Jobs of stream i ∈ C arrive to the system according to a Poisson process and have generally distributed service-times. We do not specify the arrival rate and the characteristics of the service-time distribution due to the fact that in an M/G/1 -P S queue the mean number of jobs depends on the arrival process and service-time distribution only through the traffic intensity, i.e., the product of the arrival rate and the mean service-time. Let λ i be the traffic intensity of stream i. It is assumed that λ i ≤ λ j for i ≤ j. Moreover, it will also be assumed that the vector λ of traffic intensities belongs to the following set: Λ( λ) = λ ∈ IR K : i∈C λ i = λ , where λ denotes the total incoming traffic intensity. It will be assumed throughout the paper that λ < r, which is the necessary and sufficient condition to guarantee the stability of the system. Let x i = (x i,j ) j∈S denote the routing strategy of dispatcher i, with x i,j being the amount of traffic it sends towards server j. Dispatcher i seeks to find a routing strategy that minimizes the mean sojourn times of its jobs, which, by Little's law, is equivalent to minimizing the mean number of jobs in the system as seen by this stream. This optimization problem can be formulated as follows:

minimize T i (x) = j∈S x i,j r j -y j (ROUTE-i) subject to j∈S x i,j = λ i , i = 1, . . . , K, (1)
0 ≤ x i,j ≤ r j , ∀j ∈ S, (2)
where y j = k∈C x k,j is the traffic offered to server j. Note that the optimization problem solved by dispatcher i depends on the routing decisions of the other dispatchers since y j = x i,j + k =i x k,j . We let X i denote the set of feasible routing strategies for dispatcher i, i.e., the set of routing strategies satisfying constraints (1)-(2). A vector x = (x i ) i∈C belonging to the product strategy space X = i∈C X i is called a strategy profile.

A Nash equilibrium of the routing game is a strategy profile from which no dispatcher finds it beneficial to deviate unilaterally. Hence, x ∈ X is a Nash Equilibrium Point (NEP) if x i is an optimal solution of problem (ROUTE-i) for all dispatcher i ∈ C.

Let x be a NEP for the system with K dispatchers. The global performance of the system can be assessed using the global cost

D K (λ, r) = i∈C T i (x) = j∈S y j r j -y j , (3)
where the offered traffic y j are those at the NEP. The above cost represents the mean number of jobs in the system. Note that when there is a single dispatcher, we have a single dispatcher with λ 1 = λ. The global cost can therefore be written as D 1 ( λ, r) in this case.

We shall use the ratio between the performance obtained by the Nash equilibrium and the global optimal solution as a metric in order to assess the inefficiency of a decentralized scheme with K dispatchers and S servers. We define the inefficiency as the performance ratio under the worst possible traffic conditions, namely:

inefficiency I S K (r) = sup λ∈Λ( λ), λ<r D K (λ, r) D 1 ( λ, r) . (4)
The rationale for this definition is that in practice the system administrator controls neither the total incoming traffic nor how it is split between the dispatchers, whereas the number of servers and their capacities are fixed. Therefore it makes sense to consider the worst traffic conditions for the inefficiency of selfish routing, provided the system is stable.

The PoA for this system as defined in [START_REF] Ayesta | Price of anarchy in noncooperative load-balancing games[END_REF] can be retrieved by looking at the worst inefficiency, i.e., P oA(K, S) = sup r I S K (r).

(5)

III. INEFFICIENCY IS NOT IN HEAVY-TRAFFIC

The main difficulty in determining the behaviour of the inefficiency stems from the fact that for most cases there are no easy-to-compute explicit expressions for the NEP. A first simplification results from the following theorem which was proved in one of our previous works [START_REF] Ayesta | Price of anarchy in noncooperative load-balancing games[END_REF]. It states that, among all traffic vectors with total traffic intensity λ, the global cost D K (λ, r) achieves its maximum when all dispatchers control the same fraction of the total traffic. Formally, Theorem 1 ( [START_REF] Ayesta | Price of anarchy in noncooperative load-balancing games[END_REF]):

D K (λ, r) ≤ D K ( λ K e, r). ∀λ ∈ Λ( λ),
where e is the all-ones vector.

Thus, we have identified the traffic vector in the set Λ( λ) which has the worst-ratio of global cost at the NEP to the global optimal cost. It follows from the above result that Corollary 1:

I S K (r) = sup λ<r D K ( λ K e, r) D 1 ( λ, r) . (6)
Routing games in which players have exactly the same strategy set are known are symmetric games. These games belong to the class of potential games [START_REF] Monderer | Potential games[END_REF], that is, they have the property that there exists a function, called the potential such that the NEP can be obtained as the solution of an optimization problem with the potential as the objective. This property considerably simplifies the computation of the NEP. Another important consequence of the above results is that the inefficiency depends only the total traffic intensity and not on individual traffic flows to each of the dispatcher. Another consequence of theorem 1 is that the inefficiency of decentralized routing increases with the number of dispatchers, that is, Lemma 1:

I S K (r) ≤ I S K+1 (r), ∀K ≥ 1. (7)
Proof: We have for all λ < r, D K ( λ K e, r) = D K+1 ( λ K e, 0 , r) ≤ D K+1 ( λ K+1 e, r), where the last inequality follows from theorem 1. It yields

sup λ<r D K ( λ K e, r) D 1 ( λ, r) ≤ sup λ<r D K+1 ( λ K+1 e, r) D 1 ( λ, r) , i.e., I K (r) ≤ I K+1 (r).
Before going further, let us take a look at the ratio

DK ( λ K e,r)
D1( λ,r) as a function of the load ρ = λ/r, as is shown in figure 1 for two and five dispatchers. The data-center characteristics are the following: 200 servers of speed 6, 100 servers of speed 3, 300 servers of speed 2, and 200 servers of speed 1.

It can be observed that as the load increases the ratio goes through peaks and valleys, and finally it moves towards 1 as the load moves towards saturation. In the numerical experiments, we noted that the peaks corresponded to the total traffic intensity when selfish routing started to use one more server. Moreover, just after these peaks the number of servers used by selfish routing and the centralized one was the same. A similar behaviour was observed on different sets of experiments.

In general, it is not easy to make formal the above observation, that is to say, there are no simple expressions for the value of loads which corresponds to the peaks and the valleys. However, in heavy-traffic, it helps to observe that both selfish and centralized routing will be using the same number of servers. Then, in order to show that heavy-traffic conditions are not inefficient, it is sufficient to show that the ratio decreases with load when both the setting use the same number of servers.

Proposition 1: If the total traffic intensity λ is such that centralized and the decentralized settings use the same number of servers (more than one), then the ratio of social costs D K ( λ K e)/D 1 ( λ, r) is decreasing with λ.

Proof: See appendix B-A.

In the above result we exclude the case of one server so as to obtain a stronger result. If both the settings use just one server, then the ratio remains 1, which is nonincreasing.

For a sufficiently high load all the servers will be used by both settings in order to guarantee the stability of the system. It then follows that in a server farm with an arbitrary number of servers and with arbitrary server capacities, heavy-traffic regime is not inefficient.

In fact, we can prove a stronger result which states that the inefficiency of the heavy-traffic regime is close to 1, that is, in heavy-traffic both the settings have similar performance. Formally,

Theorem 2: For a fixed K < ∞, lim λ→r D K ( λ K e) D 1 ( λ, r) = 1. Proof: See appendix B-B.
It is important that the number of dispatcher be finite for the above result to hold. If the number of dispatchers is infinite, as in the case of non-atomic games, the above limit may be a value larger than 1.

This result is important because it is widely believed that the maximum inefficiency of the decentralized routing scheme is obtained in heavy-traffic regime. Theorem 2 shows that this belief is false. As can be observed in figure 1, the worst case traffic conditions can occur at low or moderate utilization rates (in fact, the worst total traffic intensity can be arbitrary close to 0 if the server capacities are sufficiently close from each other). In heavy-traffic, even though the cost in both the settings will grow, the rate of growth is the same which results in a ratio close to 1. This result is in sheer contrast with classical queueing theory as well. For example, in a M/M/1 queue the mean sojourn time is characterized by a factor (1 -ρ) -1 , thus, as the load approaches one the mean sojourn time explodes.

The characterization of the exact traffic vector which results in I S K proves to be a difficult task. As a first attempt, in the following section we restrict ourselves to two server classes, which turns out to be more tractable than more number of classes.

IV. INEFFICIENCY FOR TWO-SERVER CLASSES

Consider the case of two classes of servers: there are S 1 "fast" servers of capacity r 1 , and S 2 = S -S 1 "slow" servers, each one of capacity r 2 < r 12 . The behaviour of the ratio of social costs is illustrated in figure 2 in the case of a server farm with S 1 = 100 fast servers of capacity r 1 = 100, and S 2 = 300 slow servers of capacity r 2 = 10. We plot the evolution of the ratio D K /D 1 as the load on the system ranges from 0% to 100% for K = 2, K = 5. It was observed that for low loads both the settings used the fast servers. The ratio in this regime was 1. After a certain point, the centralized setting started to use the slow servers as well, and the ratio increased with the load until the point when the decentralized setting also started to use the slow servers. From this point on, the ratio decreased with increase in load.

We shall now characterize the point where the ratio starts to increase and where the peak occurs. Define

λOP T = S 1 √ r 1 ( √ r 1 - √ r 2 ), (8)
and

λNE = S 1 r 1   1- 2 (K -1) 2 + 4K r1 r2 -(K -1)   . (9)
The following lemma gives the conditions on λ under which the centralized setting and the decentralized one use only the fast class of servers, or both classes.

Lemma 2: λOP T < λNE , and 1) if λ ≤ λOP T , both settings use only the "fast" servers, 2) if λOP T ≤ λ ≤ λNE , the decentralized setting uses only the "fast" servers, while the centralized one uses all servers, 3) if λ > λNE , both settings use all servers.

Proof: See appendix C-A.

Since λOP T < λNE , a consequence of lemma 2 is that the decentralized setting always uses a subset of the servers used by the centralized one. We immediately obtain expressions of the social cost in the centralized and decentralized settings, as given in corollary 2.

Corollary 2: For the centralized setting, if λ ≤ λOP T D 1 ( λ, r) = λ/(r 1 - λ S 1 ), otherwise D 1 ( λ, r) = λ r 1 r 2 + S 1 y 1 1 - r 1 r 2 1 r 1 -y 1 , (10)
where

y 1 = √ r 1 λ-S2 √ r2( √ r2- √ r1) S1 √ r1+S2 √ r2
, and y 2 = ( λ -S 1 y 1 )/S 2 are the loads on each fast server and on each slow server in the case λ ≥ λOP T , respectively. Similarly, if λ ≤ λNE

D K ( λ, r) = λ/(r 1 - λ S 1 ),
and

D K ( λK , r) = 1 2 2 j=1 S j (K -1) 2 +4Kr j γ(K) -(K + 1)
otherwise.

Proof: See appendix C-B.

In lemma 2, we identified three intervals, namely, [0, λOP T ), [ λOP T , λNE ), [ λNE , r), each one corresponding to a different set of servers used by the two settings. In proposition 2, we describe how the ratio of the social costs evolves in each of these three intervals.

Proposition 2: The ratio D K ( λ, r)/D 1 ( λ, r) is (a) equal to 1 for 0 ≤ λ ≤ λOP T , (b) strictly increasing over the interval λOP T , λNE , (c) and strictly decreasing over the interval λNE , r .

Proof: See appendix C-C.
Moreover, the ratio of social costs has the following property.

Lemma 3:

The ratio D K ( λ, r)/D 1 ( λ, r) is a continuous function of λ over the interval [0, r).

Proof: See appendix C-D.

We can now state the main result of this section.

Theorem 3: The inefficiency is worst when the total arriving traffic intensity equals λNE , namely,

I S K (r) = D K ( λNE , r) D 1 ( λNE , r) , (11)
Proof: It was shown in lemma 3 that D K ( λ, r)/D 1 ( λ, r) is a continuous function of λ over the interval [0, r). Proposition 2.(a) states that the ratio is minimum for 0 ≤ λ ≤ λOP T . For λ in λOP T , λNE , we know from proposition 2.(b) that this ratio is strictly increasing, which implies that I S K (r) ≥ D K ( λNE , r)/D 1 ( λNE , r) by continuity. Since, according to proposition 2.(c), the ratio is decreasing over the interval ( λNE , r), we can conclude that its maximum value is obtained for λ = λNE .

Theorem 3 fully characterizes the worst case traffic conditions for a server farm with two classes of servers. It states that the worst inefficiency of the decentralized setting is achieved when (a) each dispatcher controls the same amount of traffic and (b) the total traffic intensity is such that the decentralized setting only starts using the slow servers.

The behaviour described by proposition 2 can easily be observed in figure 2.

For more than two classes of servers, we were unfortunately not able to prove the above results concerning the worst traffic conditions. Nevertheless, we conjecture that a similar behaviour happens also in this case. As another illustration of this behaviour, in figure 3 we plot the ratio of social costs as a function of the load on the system, for a server farm with 3 server classes (and for K = 2, K = 5) with S 1 = 100 fast servers of capacity r 1 = 30, S 2 = 200 intermediate servers of capacity r 2 = 20 and S 3 = 100 slow servers of capacity r 3 = 10.

A. Inefficiency for a given architecture

We now give the expression for the inefficiency of selfish routing for data-centers with two classes of servers. Using theorem 3 we assume the worst traffic conditions for the inefficiency of selfish routing, i.e., the symmetric game obtained for λ = λNE . Proposition 3:

I S K (r) = 1 2 (K -1) 2 + 4Kβ -(K + 1) ( 1 α + √ β) 2 1 α + 2β √ (K-1) 2 +4Kβ-(K-1) -( 1 α + 1) (12)
where β = r1 r2 ≥ 1 and α = S1 S2 > 0. Proof: According to theorem 3, we have I S K (r) = D K ( λNE , r)/D 1 ( λNE , r). The proof is then obtained after some algebra by using the expressions for D K ( λNE , r) and D 1 ( λNE , r) given in corollary 2, and with the expression for λNE given in lemma 2.

The inefficiency I S K (r) does not depend on the total number of servers S, but only on the ratio of server capacities and on the ratio of the numbers of servers of each type. In figure 4, we plot the inefficiency I K (r) of the non-cooperative routing scheme with K = 5 dispatchers as the parameters α and β change. It can be observed that even for unbalanced scenarios (α small and β large), the inefficiency is always fairly close to 1, indicating that, even in the worst case traffic conditions, the gap between the NEP and the optimal routing solution is not significant.

With slight abuse of notation, let us denote the RHS of ( 12) by I K (α, β).

Lemma 4:

The function I K (α, β) is decreasing with α.

Proof: See appendix C-E.

A consequence of the above result is that given the ratio of server speeds in a data-center, the inefficiency is largest when there is one fast server and all the other servers are slow. Selfish routing has the tendency to use the fast servers more than the slow ones. When there is just one fast server, its performance tends to be the worst as compared to that of the centralized routing which reduces its cost by sending traffic to the slower ones as well. Thus, in decentralized routing architectures, it is best to avoid server configurations with this particular kind of asymmetry.

B. Price of Anarchy

The PoA is defined as the worst possible inefficiency when the server capacities are varied. Then, from (4), (5) and proposition 3,

P oA(K, S) = sup α,β I K (α, β).
From lemma 4 and the fact that, for a fixed S, α can take values in { 1 S-1 , 2 S-2 , . . . , S -1}, we can deduce that P oA(K, S) = sup

β I K 1 S -1 , β . ( 13
)
While there is no simple expression for the P oA in terms of K and S, we can nonetheless derive a certain number of properties from the preceding set of results.

Proposition 4:

The Price of Anarchy has the following properties. 1) For fixed K, P oA(K, S) is increasing in S; and 2) for a fixed S, P oA(K, S) is increasing in K.

Proof: For fixed K and for every β, from lemma 4 and (13),

I K 1 S -1 , β ≤ I K 1 S , β ≤ sup β I K 1 S , β = P oA(K, S + 1),
where the last equality follows from [START_REF] Monderer | Potential games[END_REF]. Taking the supremum over β in the above inequality, we obtain, for a fixed K, P oA(K, S) ≤ P oA(K, S + 1), which proves the first property.

For a fixed S and β, from lemma 1,

I K 1 S -1 , β ≤ I K+1 1 S -1 , β ≤ sup β I K+1 1 S -1 , β = P oA(K + 1, S),
Again, taking the supremum over β in the above inequality, we obtain, for a fixed S, P oA(K, S) ≤ P oA(K + 1, S), In figure 5, the PoA is plotted as a function of S for different values of K. It is observed that this value remains modest even when the number of servers is 10, 000.

We now give an upper bound the PoA. For this, we first need the following result.

Lemma 5: For a server farm with two server classes and K dispatchers,

lim S→∞ P oA(K, S) = K 2 √ K -1 . ( 14
)
Proof: See appendix C-F.

Proposition 5: For a server farm with two server classes and K dispatchers, and for all K and S,

P oA(K, S) ≤ min K 2 √ K -1 , S . (15)
Proof: From proposition 4, P oA(K, S) is increasing with S. Combining this fact with lemma 5, we can conclude that

P oA(K, S) ≤ K 2 √ K -1 .
Moreover, it was shown in [START_REF] Haviv | The price of anarchy in an exponential multi-server[END_REF] that, for the Wardrop case which is the limit of K → ∞, P oA(∞, S) ≤ S. Thus, P oA(K, S) ≤ S.

We can deduce the desired result from the above two inequalities.

In server farms with large number of servers, it follows from lemma 5 that the PoA will be K 2 √ K-1 . In [START_REF] Ayesta | Price of anarchy in noncooperative load-balancing games[END_REF], it was shown that this value was a lower bound on the PoA. The model in that paper had server dependent holding cost per unit time. The lower bound was obtained in an extreme case with negligible (tending to 0) holding cost on the fast servers and the decentralized setting marginally using the slow servers. Our present results show that the lower bound is indeed tight. Moreover, even in a less asymmetrical setting of equal holding costs per unit time, one can construct examples in which the PoA is attained.

The PoA obtained in the non-atomic case in [START_REF] Haviv | The price of anarchy in an exponential multi-server[END_REF] comes into play when there are few servers and a relatively large number of dispatcher. However, for data-centers the configuration is reversed : there are a few dispatchers and a large number of servers. In this case it is more appropriate to use the upper bound given in (15).

V. CONCLUSIONS

Price of Anarchy is an oft-used worst-case measure of the inefficiency of non-cooperative decentralized architectures. In spite of its popularity, we have shown that the Price of Anarchy is an overly pessimistic measure that does not reflect the performance obtained in most instances of the problem. For an arbitrary architecture in the system, we have seen that, contrary to a common belief, the inefficiency is in general not achieved in heavy-traffic or close to saturation conditions. Surprisingly, we have shown that inefficiency might be achieved at arbitrarily low load. In the case of two classes of servers, we have explicitly characterized the traffic conditions (or load) associated with the inefficiency. This has allowed us to obtain a refined upper bound on the Price of Anarchy and to show that non-cooperative loadbalancing has close-to-optimal performances in most cases. The worst-case performances given by the Price of Anarchy occur only in a very specific setting, namely, when the slower servers are infinitely more numerous and infinitely slower than the faster ones. In future research we plan to generalize some of the results to an arbitrary number of classes of servers. It will also be worthwhile to investigate what happens when the number of dispatches grows to infinity, that is, when the equilibrium traffic pattern is characterized by the socalled Wardrop equilibrium.

APPENDIX A SOME KNOWN RESULTS

The results in this section are taken from [START_REF] Ayesta | Price of anarchy in noncooperative load-balancing games[END_REF]. Since they are cited several times in the present work, we choose to present them here for its easy perusal. Define the function

W j (K, z) = 1 {z∈[ 1 r j , 1 r j+1 )} • j s=1 2r s (K -1) 2 +4Kr s z-(K -1) - j s=1 r s + λ , and let W (K, z) = j∈S W j (K, z).
The following proposition gives the solution of the symmetric game.

Proposition 6: The subset of servers that are used at the NEP is S * (K) = {1, 2, . . . , j * (K)}, where j * (K) is the greatest value of j such that W (K, 1/r j+1 ) ≤ 0 < W (K, 1/r j ). The equilibrium flows are x i,j (K) = y j (K)/K, i ∈ C, j ∈ S * (K), where the offered traffic of server j is given by

y j (K) = r j (K -1) 2 + 4Kγ(K)r j -(K + 1) (K -1) 2 + 4Kγ(K)r j -(K -1) , (16) with γ(K) the unique root of W (K, z) = 0 in [ 1 r1 , ∞).

APPENDIX B PROOFS OF THE RESULTS IN SECTION III

A. Proof of proposition 1

Before proving proposition 1, we first establish closedform expressions for the value of the social costs in the centralized and decentralised settings. Recall that we assume a server farm with S servers with decreasing values of the capacities, i.e, r i ≤ r j , if i > j. The result is stated in the following lemma.

Lemma 6: Let n be the number of servers that the centralized setting uses, for n = 1 . . . , S, then

D 1 ( λ, r) = n j=1 √ r j 2 n j=1 r j - λ -n. (17)
Similarly, if the decentralized setting uses n servers, we have

D K ( λ, r) = 1 2 n j=1 (K -1) 2 +4Kr j γ(K) -(K + 1) . (18)
Proof: We first prove the results for the centralized setting. When the centralized setting uses n servers proposition 6 states that in this case, we have

y j (1) = r j 1 - 1 γ(1) √ r j , j = 1, . . . , n, (19)
and it yields

y j (1) r j -y j (1) = γ(1) √ r j -1, j = 1, . . . , n. (20)
We thus obtain

D 1 ( λ, r) = n j=1 y j (1) r j -y j (1) = γ(1) n j=1 √ r j -n. (21)
According to proposition 6, γ(1) is the solution of

1 √ γ (1) n j=1
√ r j = n j=1 r j -λ and we thus obtain γ(1) = n j=1 √ r j /( n j=1 r j -λ). It yields

D 1 ( λ, r) = ( n j=1 √ r j ) 2 n j=1 r j - λ -n, (22) as claimed.
Let us now consider the decentralized setting. If the number of servers used is n, then (16) gives that

1 - y j (K) r j = 2 (K -1) 2 + 4Kγ(K)r j -(K -1) , (23)
for j = 1, . . . , n.

With ( 16) and ( 23), we obtain

DK ( λ, r) = n j=1 yj(K) rj 1 - yj(K) rj -1 = 1 2 n j=1 (K -1) 2 + 4Kγ(K)rj -(K + 1) ,
which yields the desired result.

We show in the following lemma an important property to prove proposition 1.

Lemma 7: Let a k = (K -1) 2 + 4Kγ(K)r k + (K -1)
, then for all i > j, aj ai is increasing. with λ, where

Proof:

First, we define b j = (K -1) 2 + 4Kγ(K)r j and we see that bj bi is increasing if (K-1) 2 +4Kγ(K)rj (K-1) 2 +4Kγ(K)ri is increasing because bj bi is positive.

(K -1) 2 + 4Kγ(K)r j (K -1) 2 + 4Kγ(K)r i ′ = 4Kγ(K) ′ (K-1) 2 (r j -r i ) ≥ 0 due to r j ≥ r i if i ≥ j.
We have proved that (K-1) 2 +4Kγ(K)rj (K-1) 2 +4Kγ(K)ri is increasing and that implies that bj bi is increasing.

We also observe that b

′ j ≥ b ′ i , if i > j: b ′ j ≥ b ′ i ⇐⇒ 2Kγ(K)r j b j ≥ 2Kγ(K)r i b i ⇐⇒ 1 (K-1) 2 r 2 j + 4Kγ(K) rj ≥ 1 (K-1) 2 r 2 i + 4Kγ(K)
ri and this inequality holds since r j ≥ r i when i > j.

As b ′ j = a ′ j and a j = b j + (K -1), for all the values of j, we are able to state that if bj bi is increasing, then aj ai is increasing.

a j a i ′ > 0 ⇐⇒ b ′ j a i -b ′ i a j a 2 i > 0 ⇐⇒ b ′ j b i -b ′ i b j + (K -1)(b ′ j -b ′ i ) > 0 and we know the inequality is satisfied because bj bi ′ > 0 and b ′ j > b ′ i .
We can now prove proposition 1.

Proof of proposition 1:

We show that when both settings use n servers (n = 1, . . . , S), then the ratio DK D1 is decreasing with λ.

First, we modify this fraction with the values of D K and D 1 described for the case of arbitrary number of servers in lemma 6.

DK D1 = 1 2 n j=1 (K -1) 2 +4Krjγ(K) -(K + 1) -n + γ(1) n j=1 √ rj = -n + 1 2 n j=1 (K -1) 2 +4Krjγ(K) -(K -1) -n + γ(1) n j=1 √ rj = f1 + f2 f1 + g2
where we define

f 1 = -n √ γ (1)
,

g 2 = n j=1 √ r j and f 2 = 1 2 √ γ(1) n j=1 (K -1) 2 +4Kr j γ(K) -(K -1) . D K D 1 ′ < 0 ⇐⇒ f ′ 1 (g 2 -f 2 ) + f ′ 2 D K γ(1) < 0
We observe that f 1 is increasing with λ, due to being γ(1) increasing with λ, and D 1 ≤ D K implies that g 2 ≤ f 2 . Therefore, we show that f 2 is decreasing and we conclude that DK D1 is decreasing.

According to what has been shown in lemma 6 and using the definition of γ of proposition 6, we have the following equality when both settings use n servers:

1 γ(1) = n j=1 r j -λ n j=1 √ r j = 1 n j=1 √ r j n s=1 2r s a s
where a s = (K -1) 2 + 4Kγ(K)r s -(K -1).

Taking into account this expression we rewrite f 2 as follows:

f 2 = 1 n j=1 √ r j n j=1 a j n s=1 r s a s = 1 n j=1 √ r j   n j=1 r j + n j=1 i>j r j a i a j + r i a j a i  
We define a s = (K -1) 2 + 4Kγ(K)r s + (K -1) and we notice that if we multiply and divide a s by a s it yields

a s = 4Kγ(K)r s a s
So f 2 gets modified as follows with this property:

f 2 = 1 2 j=1 √ r j   n j=1 r j + n j=1 i>j r j a i a j + r i a j a i  
Now, we show that r j /a 2 j > r i /a 2 i for all i > j because rk a 2 k is decreasing with k since we can write it in the following way

r k a 2 k =     (K -1) 2 r k + 4Kγ(K) + K -1 √ r k   -1   2
and r k decreases with k.

To finish, we see that f 2 is decreasing with λ.

f ′ 2 = 1 2 j=1 √ r j n j=1 i>j (a ′ j a i -a ′ i a j ) r i a 2 i - r j a 2 j < 0
and we conclude that this is true because lemma 7 states that aj ai is increasing with λ if i > j (so that a ′ j a i -a ′ i a j > 0) and we have just observed that r j /a 2 j > r i /a 2 i when i > j.

B. Proof of theorem 2

Proof: First, we know that in heavy-traffic all the servers are used, so we consider that S servers are used in both settings. Now, we observe that in heavy-traffic γ(K), as defined in proposition 6, tends to ∞, and thus the following approximation is satisfied for any value of K and r j :

(K -1) 2 + 4Kγ(K)r j -(K -1) ≈ 2 Kγ(K)r j (24)
From ( 24) and from the definition of γ(K), we obtain

Kγ(K) = S j=1 √ r j S j=1 r j - λ (25)
Now, using (25) and (24), we show that D K = D 1 in heavy-traffic:

D K = 1 2 S j=1 (K -1) 2 + 4Kγ(K)r j -(K + 1) = -S + 1 2 S j=1 (K -1) 2 + 4Kγ(K)r j -(K -1) = -S + Kγ(K) S j=1 √ r j = -S + ( S j=1 √ r j ) 2 S j=1 r j - λ = D 1 ,
according to lemma 6.

APPENDIX C PROOFS OF THE RESULTS IN SECTION IV

A. Proof of lemma 2

Proof: Let us first prove that λOP T < λNE . We have,

λOP T < λNE ⇐⇒ √ r 1 r 2 > 2r 1 (K -1) 2 + 4Kr 1 /r 2 -(K -1) ⇐⇒ (K -1) 2 + 4Kr 1 /r 2 > √ r 1 [2 √ r 1 + (K -1) √ r 2 ] ⇐⇒ 4Kr 1 > 4r 1 + 4(K -1) √ r 1 r 2 ⇐⇒ r 1 > r 2 ,
and we thus conclude that λOP T < λNE .

We now turn to the second part of the proof. According to proposition 6, the centralized setting uses only the fast servers (S 1 servers of capacity r 1 ) for all values of

λ such that W 2 (1, 1 r2 ) ≤ 0. It yields λ ≤ (S 1 r 1 + S 2 r 2 ) - √ r 2 (S 1 √ r 1 -S 2 √ r 2 )
which is equivalent to λ ≤ λOP T . Similarly, we know from proposition 6, that the decentralized setting starts using the second group of servers if and only if

λ ≥ S 1 r 1 + S 2 r 2 - S1+S2 s=1 2r s (K -1) 2 +4Kr s /r 2 -(K -1) ≥ S 1 r 1 + S 2 r 2 - 2 s=1 S s 2r s (K -1) 2 +4Kr s /r 2 -(K -1) = S 1 r 1 -S 1 2r 1 (K -1) 2 +4Kr 1 /r 2 -(K -1) ,
which is equivalent to λ ≥ λNE , as claimed.

B. Proof of corollary 2

Proof: We first prove the results for the centralized setting. For λ < λOP T , we know from lemma 2 that the centralized setting uses only the first group of servers, and we thus have

D 1 ( λ, r) = S1 j=1 λ S1 r 1 -λ S1 = λ r 1 -λ S1
For λ ≥ λOP T , we know from lemma 2 that the centralized setting uses the second group of servers.

According to the KKT conditions,

r 1 (r 1 -y 1 ) 2 = r 2 (r 2 -y 2 ) 2 (26)
where λ = S 1 y 1 + S 2 y 2 . After some algebra, it yields

y 1 = √ r 1 λ -S 2 √ r 2 ( √ r 2 - √ r 1 ) S 1 √ r 1 + S 2 √ r 2 (27)
With the constraint of S 1 y 1 + S 2 y 2 = λ and (26) we obtain

D 1 = S 1 y 1 r 1 -y 1 + S 2 y 2 r 2 -y 2 = S 1 y 1 r 1 -y 1 + ( λ -S 1 y 1 ) 1 r 2 -y 2 = S 1 y 1 r 1 -y 1 + ( λ -S 1 y 1 ) r 1 r 2 1 r 1 -y 1 = λ r 1 r 2 + S 1 y 1 1 - r 1 r 2 1 r 1 -y 1
where y 1 is given in (27).

Let us now consider the decentralized setting. For λ < λNE , we know from lemma 2 that the decentralized setting uses only the servers of the first class, and we thus have

D K ( λ, r) = λ r 1 -λ S1 .
For λ ≥ λNE , all the servers are used and (16) gives that for all the servers of each class

1 - y j (K) r j = 2 (K -1) 2 + 4Kγ(K)r j -(K -1) . (28)
With ( 16) and (28), we obtain

D K ( λ, r) = S 1 +S 2 j=1 y j (K) r j 1 - y j (K) r j -1 = 1 2 S 1 +S 2 j=1 (K -1) 2 + 4Kγ(K)r j -(K + 1) = 1 2 2 j=1 S j (K -1) 2 + 4Kγ(K)r j -(K + 1) ,
which yields the desired result.

C. Proof of proposition 2

We shall break-down the proof of the proposition in three parts according to the three intervals which define the behaviour of the ratio of the social costs. In the following two lemmata, we show that the ratio is increasing in one of the intervals and decreasing in the other.

Lemma 8:

The ratio DK ( λ,r) D1( λ,r) is strictly increasing over the interval λOP T , λNE .

Proof: In order to prove that DK ( λ,r) D1( λ,r) is an increasing function of λ for λ ∈ ( λOP T , λNE ) we shall prove the following equivalent statement.

D ′ K ( λ, r) D K ( λ, r) > D ′ 1 ( λ, r) D 1 ( λ, r) . Since λ < λNE , we have D K ( λ, r) = λ r1-λ S 1
and

D ′ K ( λ, r) = r 1 (r 1 -λ) 2 = r 1 λ(r 1 -λ S1 ) D K ( λ, r)
from which we deduce that

D ′ K ( λ, r) D K ( λ, r) = r 1 λ(r 1 -λ) = r 1 λ2 D K ( λ, r). (29)
For the centralized setting, λ ≥ λOP T means that

D 1 ( λ, r) = S 1 y 1 r 1 -y 1 + S 2 y 2 r 2 -y 2
According to (26), the derivative of D 1 gets modified as follows:

D ′ 1 ( λ, r) = S 1 r 1 y ′ 1 (r 1 -y 1 ) 2 + S 2 r 2 y ′ 2 (r 2 -y 2 ) 2 (30) = (S 1 y ′ 1 + S 2 y ′ 2 ) r 1 (r 1 -y 1 ) 2 (31)
The constraint S 1 y 1 + S 2 y 2 = λ implies that S 1 y ′ 1 + S 2 y ′ 2 = 1 and hence

D ′ 1 ( λ, r) = r 1 (r 1 -y 1 ) 2 It yields D ′ 1 ( λ, r) D 1 ( λ, r) = r 1 (r 1 -y 1 ) 2 1 D 1 ( λ, r) 2 D 1 ( λ, r) = r 1 λ r1 r2 + S 1 y 1 1 -r1 r2 2 D 1 ( λ, r)
As a result, for λ ∈ ( λOP T , λNE ), D ′ K ( λ,r)

DK ( λ,r) > D ′ 1 ( λ,r) D1( λ,r) is equivalent to r 1 λ2 D K ( λ, r) > r 1 λ r1 r2 + S 1 y 1 1 -r1 r2 2 D 1 ( λ, r) and D K ( λ, r) D 1 ( λ, r) > λ2 λ r1 r2 + S 1 y 1 1 -r1 r2 2
Now, we assume that there exist λ ∈ ( λOP T , λNE ) such that DK ( λ,r) D1( λ,r) is not increasing with λ.

Since DK ( λ,r) D1( λ,r) ≥ 1, it results

1 ≤ D K ( λ, r) D 1 ( λ, r) ≤ λ2 λ r1 r2 + S 1 y 1 1 -r1 r2 2 With (27), it yields 1 ≤ λ λ r1 r2 + S 1 √ r 1 λ-S2 √ r2( √ r2- √ r1) S1 √ r1+S2 √ r2 1 -r1 r2 ≤ λ(S 1 √ r 1 + S 2 √ r 2 ) λ√ r 1 (S 1 + S 2 ) -S 1 S 2 √ r 1 ( √ r 2 - √ r 1 ) 2
This is equivalent to

λ√ r1(S1 + S2) -S1S2 √ r1( √ r2 - √ r1) 2 ≤ λ(S1 √ r1 + S2 √ r2)
and after rearranging both sides of the expression, we arrive at the following condition λ ≤ S 1 √ r 1 ( √ r 1 -√ r 2 ) = λOP T that it is a contradiction since λ ∈ ( λOP T , λNEP ).

Lemma 9:

The ratio DK ( λ,r) D1( λ,r) is strictly decreasing over the interval λNE , r .

Proof: In the interval λNE , r we know that all servers are used. Thus, according to proposition 1, the ratio DK ( λ,r) D1( λ,r) is decreasing as a function of λ.

We can now prove proposition 2.

Proof of proposition 2:

The proof directly results from corollary 2, and lemmata 8 and 9.

D. Proof of lemma 3

Proof: First, we state that this function is continuous in [0, λOP T ), ( λOP T , λNE ) and ( λNE , r) which follows from the definitions of D K and D 1 in corollary 2. Now, we show that DK D1 is continuous in λOP T and λNE because where

y N E 1 = √ r 1 λNE -S2 √ r2( √ r2- √ r1) S1 √ r1+S2 √ r2

E. Proof of lemma 4

Proof: First, we modify I K (α, β) of the definition of inefficiency as follows:

I K (α, β) = 1 2 (x -2)( 1 α + 2β x ) 1 α (2 √ β -1 -2β x ) + β(1 - 2
x ) where x = (K -1) 2 + 4Kβ -(K + 1).

We now show that the derivative of I K (α, β) with respect to α is always negative.

∂I K (α, β) ∂α = 1 2 1 α ′ β(1 -2 x ) -2β x (2 √ β -1 -2β x ) 1 α (2 √ β -1 -2β x ) + β(1 -2 x ) 2 = 1 2 1 α ′ 1 -2β x 2 1 α (2 √ β -1 -2β x ) + β(1 -2 x )
2 < 0 because the derivative of 1 α is negative.

F. Proof of lemma 5

Proof: From (13), In order to compute the limit of the P oA, we shall first compute the limit of I K and then we shall compute the supremum. Let x = (K -1) 2 + 4Kβ-(K -1). We can rewrite [START_REF] Korilis | Architecting noncooperative networks[END_REF] as

I K 1 S -1 , β = 1 2 x -2 (S-1+ √ β) 2 S-1+ 2β x -S
In order to evaluate the limit of the I K , it is sufficient to compute the limit of the denominator of the above expression. For large S, x .

Now that we have computed the limit of I K as S → ∞, we shall compute the supremum with respect to β. In order to do this, we shall show that the limit computed previously is an increasing function of β.

Denote F K (β) = lim S→∞ I K (1/(S -1), β). We shall show that it is an increasing function of β.

We first write F K (β) as follows:

F K (β) = 1 2 y -(K + 1) 2 √ β -1 -y+K-1

2K

where y = (K -1) 2 + 4Kβ.

We now show that the derivative of F K (β) with respect to β is positive. > 0 ⇐⇒ (β -1)(K + 1) 2 -4K(β -1) > 0 ⇐⇒ (K -1) 2 (β -1) > 0 due to being β > 1 (if β = 1, then r 1 = r 2 and then they belong to the same class).

∂FK (β) ∂β > 0 ⇐⇒ y ′ 2 √ β -1 -y+K-1 2K -(y -(K + 1)) 1 √ β -1 2K y ′ > 0 ⇐⇒ 2y ′ ( √ β -

Fig. 1 .

 1 Fig.1. Evolution of the ratio of social costs for K = 2 and K = 5 as the utilization rate ranges from 0% to 100%.

Fig. 2 .

 2 Fig.2. Evolution of the ratio of social costs for K = 2 and K = 5 as the utilization rate ranges from 0% to 100%.

Fig. 3 .

 3 Fig. 3. The evolution of the ratio of social costs for K = 2 and K = 5 with respect to ρ in a server farm with 3 server classes.

Fig. 4 .

 4 Fig. 4. Evolution of the inefficiency as a function of α and β for K = 5 dispatchers.

Fig. 5 .

 5 Fig. 5. The Price of Anarchy as a function of the number of servers for different values of the number of dispatcher

•

  lim λ→ λOP T -DK D1 ( λ) = lim λ→ λOP T + DK D1 ( λ) = DK D1 ( λOP T ) = 1 • lim λ→ λNE -DK D1 ( λ) = lim λ→ λNE + DK D1 (

-

  S ≈ 2 β -1 -2β

- 1 )

 1 -(K -1) 2 + 4Kβ -(K + 1)y > 0 ⇐⇒ 4Kβ -4K √ β -(K + 1) 2 + 4K(β -1) -(K + 1)y > 0 ⇐⇒ -4K( √ β -1) + (K + 1)(y -(K + 1)) > 0 ⇐⇒ -4K( √ β -1) + (K + 1) 4K(β-1) y+K+1 > 0 ⇐⇒ -1 + (K + 1) ( √ β+1) y+K+1 > 0 ⇐⇒ √ β(K + 1) -y > 0 ⇐⇒ β(K+1) 2 -[(K+1) 2 +4K(β-1)] √ β(K+1)+y

We shall use the terms load-balancing and routing interchangeably.

In the case r2 = r1, it is easy to see that the NEP is always an optimal routing solution, whatever the total traffic intensity.