Zakaria Gheid
email: zgheid@esi.dz

Yacine Challal
email: ychallal@esi.dz

An Efficient and Privacy-preserving Similarity Evaluation For Big Data Analytics

Keywords: big data, data analytics, cosine similarity, privacy

Big data systems are gathering more and more information in order to discover new values through data analytics and depth insights. However, mining sensitive personal information breaches privacy and degrades services' reputation. Accordingly, many research works have been proposed to address the privacy issues of data analytics, but almost seem to be not suitable in big data context either in data types they support or in computation time efficiency. In this paper we propose a novel privacy-preserving cosine similarity computation protocol that will support both binary and numerical data types within an efficient computation time, and we prove its adequacy for big data high volume, high variety and high velocity.

I. INTRODUCTION

Advances in sensing and storing technologies along with the expansion of the number of connected objects have led to capture and store a huge amount of data. This data explosion phenomenon was called big data by Cox et al. [START_REF] Cox | Applicationcontrolled demand paging for out-of-core visualization[END_REF] and has since been largely shared between academia, industry and the media. According to a Gartner Group report, a Big data involves data sets that are big in size with a high variety of data types and a high velocity of streaming in and out [START_REF] Laney | Meta group 3d data management: controlling data volume, velocity and variety[END_REF]. This widely quoted definition was followed by developing more scalable tools and technologies, such as Google Map Reduce [START_REF] Dean | Mapreduce: simplified data processing on large clusters[END_REF] and Apache Hadoop [START_REF]The apache hadoop project[END_REF], in order to better deal with these new data dimensions. Furthermore, data analysts are struggling upstream to extract patterns and knowledge from datasets combined as never before. Businesses that seek new paradigms, governments that would like enhance their authorities, security agencies and research communities are still rummaging through big data silos to satiate their desires. For example, eBay.com had implemented a 40PB Hadoop cluster to improve its recommendation system. Facebook and Twiter are handling billions of queries which are stored for being analysed with data mining techniques [START_REF] Prajapati | Big data analytics with R and Hadoop[END_REF]. Another anecdotal example consists of Barack Obama's 2012 winning re-election campaign, in which, big data analytics were used to discover political interest of the voters, thus address them more accurately [START_REF] Kreiss | Taking our country back: The crafting of networked politics from Howard Dean to Barack Obama[END_REF]. However, when individual records involve sensitive information, the application of some data mining techniques such as similarity measurement raises confidentiality issues and breaches privacy policies of services and institutions. For instance, when a hospital receives a new patient, requesting for similar Electronic Medical Record (EMR) [START_REF] Ilie | Paper versus electronic: Challenges associated with physicians -usage of electronic medical records[END_REF] to other collaborator hospitals may breach the patient privacy. Concerning the biometric identity, disclosing a passenger biometric template to be compared with a template list of suspect persons is a privacy breach for innocent passengers. With regard to document similarity, a paper reviewer who searches for similar paper submited to other journals in order to check for plagiarisme shouldn't disclose papers still in submission, otherwise, the journal privacy policy is broken. Moreover, when a service provider is comparing a user sessions to enhance recommandation, mining the sessions in a clear way breaches the user privacy and demean the service reputation.

In this paper we tackle the issue of privacy in big data analytics. In particular, we focus on the cosine similarity metric as a similarity-based method, and we will show that big data requires efficient similarity computation to scale to large amounts of data. Therefore, protecting privacy should not induce high computation overhead. Then we propose a novel cosine similarity calculation method for which we will demonstrate privacy preservation and efficiency.

We organize our paper as follows: Section II presents a background on cosine similarity computation and its involved privacy issue. In Section III we expose recent research works having targeted the privacy concern of scalar product and we show briefly their inadequacy for big data analytics. Then, we introduce a novel efficient and privacy preserving cosine similarity protocol in section IV, and we detail its implementation within two different contexts. Section V shows some real world application scenarios of our protocol, and the last two sections are dedicated to prove the privacy preservation of our protocol as well as its efficiency. We conclude by summarizing the contribution of this paper and its suitability for big data analytics.

II. BACKGROUND AND PROBLEM STATEMENT

Cosine similarity is a statistical metric used for measuring similarities between vectors of numerical attributes. It consists of calculating the cosine (cos) of the angle (θ) between two vectors of attributes. cos(θ) belongs to [-1,1] and the more it is closer to 1, the more vectors are similar, and vice-versa. Let a = (a 1 , ..., a n ) and b = (b 1 , ..., b n ) be 2 vectors in R n vector space and θ the angle between them. Cosine similarity between a and b is measured by

cos(θ) = ( a • b) a b (1)
where ( a • b) is the dot product obtained as follows Nevertheless, computing the dot product i.e. n i=1 (a i ×b i ) needs to disclose attributes of one individual to the other. Moreover, in big data era, almost relevant analytics raise from sharing datasets between several parties or from outsourcing them to expert analytics service providers. However, when attributes include sensitive information, disclosing them to other parties threats clients confidentiality and breaches privacy policies. The issue is then how to compute the similarity of two individuals without revealing their attributes values. Thereafter, we note a cosine similarity computation system by χ 1 = {S, D}, where S includes stations involved in the compuation and D is the set of required data.

( a • b) = n i=1 (a i × b i ) (2

A. Big data analytics requirements

In addition to privacy need, big data analytics require some constraints due to its main characteristics which are illustred in Figure 2.

1) Volume requirement: big data is a great amount of datasets. Therefore, this high volume drives us to compute similarity for many times. Thus, using a method which performs a privacy-preserving similarity computations without inducing a high computation cost is a keystone requirement.

2) Variety requirement: big data silos involve a high variety of data types, both structural and non-structural datasets, including textual, numerical and binary attributes. So, we have to address all this variety in similarity computations.

3) Velocity requirement: big data are subjected to a high velocity stream of input and output queries which requires in some contexts real time interactions. Thus, introducing privacy preserving mechanisms should not induce unaffordable computation overhead. III. RELATED WORKS Computing the scalar product in a privacy way has attracted many contributions from the research community. Jaideep Vaidya and Chris Clifton [START_REF] Vaidya | Privacy preserving association rule mining in vertically partitioned data[END_REF] have addressed the problem of association rule mining in vertically partitioned data. In order to identify valid association rules from different transactions distributed over sources, sites need to collaborate provided that they shouldn't disclose their individual transaction data. Thus, authors proposed a privacy preserving scalar product protocol wich was based on algebraic operations in order to scale well to data mining problem. Nonetheless, B. Goethals et al. [START_REF] Goethals | On private scalar product computation for privacy-preserving data mining[END_REF] have identified some attacks against this protocol proving that one of the two parties running the protocol [START_REF] Vaidya | Privacy preserving association rule mining in vertically partitioned data[END_REF] can disclose the private input of the other party with probability near to 1. Authors highlighted the privcy risk with {0,1} values and affirmed that remedies proposed by [START_REF] Vaidya | Privacy preserving association rule mining in vertically partitioned data[END_REF] have no security proof. In contrast, B. Goethals et al. proposed another secure protocol based on Homomorphic encryption [START_REF] Goethals | On private scalar product computation for privacy-preserving data mining[END_REF]. Nevertheless, Homomorphic encryption induces a high computation overhead according to [START_REF] Lu | Toward efficient and privacy-preserving computing in big data era[END_REF], thus it is inadequate for big data analytics. Wenliang Du and Mikhail J.Atallah [START_REF] Du | Privacy-preserving cooperative statistical analysis[END_REF] introduced a privacy-preserving statistical analysis protocol for cooperative environments. In addition to use Homomorphic encryption operations that raises inefficiency, this protocol is unsecure and can be subjected to privacy breaches when it comes to binary data as proved by [START_REF] Goethals | On private scalar product computation for privacy-preserving data mining[END_REF]. Work proposed by Wei Jiang et al. [START_REF] Jiang | Similar document detection with limited information disclosure[END_REF], later extended by Mummoorthy Murugesan et al. [START_REF] Murugesan | Efficient privacy-preserving similar document detection[END_REF], has introduced two cosine similarity based-methods for similar document detection. The first method used the matrixbased protocol proposed in [START_REF] Vaidya | Privacy preserving association rule mining in vertically partitioned data[END_REF] which presents privacy risk as aforementioned. The second method has used a Homomorphic encryption-based protocol. Methods introduced by Hiroaki Kikuchi et al. [START_REF] Kikuchi | Privacy-preserving similarity evaluation and application to remote biometrics authentication[END_REF] have been proposed for secure remote biometrics authentication. Authors have evaluated similarity using the cosine correlation and the Euclidean distance by implementing two Homomorphic encryption-based protocols. I. Leontiadis et al. [START_REF] Leontiadis | Privacy preserving similarity detection for data analysis[END_REF] have proposed a mechanism for privacy preserving clustering using the cosine similarity metric. The idea of solution consists of applying a rotation in a two dimensional space to generate sub-vectors from the original data vectors. Sub-vectors are then randomly scaled and subjected to cosine computation. Even this technique is efficient, it relies on the average between sub-vectors similarities which is different from direct cosine computation. Dexin Yang et al. [START_REF] Yang | Secure cosine similarity computation with malicious adversaries[END_REF] have proposed an ElGamel encryption-based protocol for secure cosine similarity computation which resists to malicious adversaries attacks. Authors have proved that their protocol can target integer attributes unlike proposed schemes which consider, only, similarity of binary data. More recently, R. LU et al. [START_REF] Lu | Toward efficient and privacy-preserving computing in big data era[END_REF] have proposed a privacy preserving cosine similarity protocol for big data analytics. Their solution was based on algebraic operations in order to be more efficient in big data contexts. Nevertheless, this protocol presents a serious privcy risk when it comes to binary data. Indeed, we suppose that Sa and Sb are two stations having respectively a = (a 1 , ..., a n ) and b = (b 1 , ..., b n ) as individuals. The protocol assumes that Sb sends to Sa a parameter B = (

n i=1 b 2 i ).
So, when it comes to binary attributes:

b 2 i = bi ⇒ B = ( n i=1 b i ).
Therefore Sa can know the number of (b i = 0), and the number of (b i = 1) which is a privacy breach according to Definition 4 presented in section VI-A. Authors have argued that they add the values (a n + 1 = a n + 2 = b n + 1 = b n + 2 = 0) to ensure the existence of at least two random numbers in the information sent by Sb to Sa which involves bi attributes so that Sa can't guess b. Though, in the case of binary vectors and when all (b i = 0), Sb will send (B = n) which discloses b despite the presence of random numbers in the information sent to Sa. This protocol presents a privacy risk for binary contexts, thus it is not suitable for all big data types.

To summarize, existing solutions can be classified into two categories: a) approaches [START_REF] Goethals | On private scalar product computation for privacy-preserving data mining[END_REF][START_REF] Du | Privacy-preserving cooperative statistical analysis[END_REF][START_REF] Jiang | Similar document detection with limited information disclosure[END_REF][START_REF] Murugesan | Efficient privacy-preserving similar document detection[END_REF][START_REF] Kikuchi | Privacy-preserving similarity evaluation and application to remote biometrics authentication[END_REF][START_REF] Yang | Secure cosine similarity computation with malicious adversaries[END_REF] that include encryption-based methods, such as Homomorphic encryption. In spite of enforcing the privacy, encryption decreases the service efficiency, it involves time expensive operations which is not suitable for the high velocity of big data. b) The second approach [START_REF] Vaidya | Privacy preserving association rule mining in vertically partitioned data[END_REF][START_REF] Lu | Toward efficient and privacy-preserving computing in big data era[END_REF][START_REF] Jiang | Similar document detection with limited information disclosure[END_REF][START_REF] Murugesan | Efficient privacy-preserving similar document detection[END_REF][START_REF] Leontiadis | Privacy preserving similarity detection for data analysis[END_REF] comprises algebraicbased methods that apply some arithmetic and/or geometric transformations. Despite the low computation cost, almost all those protocols protect privacy in some contexts but not in others, such as binary data. This is not tolerable in the case of big data known for its high variety of data types.

In this paper, we will propose a new protocol for computing the dot product in order to better address cosine similarity as a privacy preserving and efficient building block for big data analytics.

IV. Π-CSP: PRIVACY-PRESERVING AND EFFICIENT COSINE SIMILARITY PROTOCOLS

A. Overview of our solution

Our concern will focus upon computing cos( a, b) in a privacy way, where a and b are two individuals, which means computing ( a × b) after a normalization process (see section II.A for normalization detail). While taking into consideration the three big data main characteristics (Volume, Velocity and Variety), our solution consists of obfuscating individuals through adding a noise and performing some arithmetic operations allowing coine similarity calculation. We adopt an arithmetic-based method to be more efficient in addressing big data high velocity. As regards to big data high volume, it implies a high individual size (a great number of attributes) and a high number of individuals. In order to cope with the high size of individuals our solution uses an attribute-independent noise contrary to existing similar approaches [START_REF] Vaidya | Privacy preserving association rule mining in vertically partitioned data[END_REF][START_REF] Leontiadis | Privacy preserving similarity detection for data analysis[END_REF] that generate a scalar noise for each individual attribute. With respect to the high number of individuals, we assess similarities of the maximum available set of individuals in the minimum communication steps. By dealing with normalized individuals we are addressing big data high variety, i.e. we ensure computing similarities of binary individuals without communicating a or b which breach their privacy (see section III), thus we are preserving the privacy of both binary and integer individuals. Let Sa and Sb be two stations having respectivly A (a row matrix) and B (a column matrix) set of individuals. To ensure privacy, our solution allow calculating the product (A × B) without revealing the individuals themselves. Indeed, our method obfuscates A in a matrix product (M × A) (where M can be considered as a random noise) and sends the result (M A) to Sb. Sb performs (M A × B) and sends the result matrix (M AB) to Sa which performs (M -1 × M AB) to get the matrix(AB) that contains in each element AB[i, j]: cos( a i , b j ) . We set some conditions on the dimension of each matrix (M , A and B) in a way that prevents mutual disclosure risks, thus to preserve privacy.

In what follows, we will present details of our solution as well as a three-party variant protocol which is useful in some application scenarios.

B. Π-CSP implementation

In order to comply with different application scenarios, we will propose two protocols. The first is a two-party computation protocol used for a privacy shared cosine similarity computation between two stations. The second protocol takes into consideration analytic service providers, thus, it performs privacy computation between three parties. Let us consider Sa and Sb two stations having respectively a i = (a 1 , ..., a n ) and b i = (b 1 , ..., b n ) individuals. We consider χ 1 = {(Sa, Sb), (M, A, B)} a cosine similarity computation system, where A (resp. B) is a row (resp. column) matrix containing a i (resp. b i ) individuals and M is an invertible random noise matrix. We define Π, a private and efficient cosine similarity protocol, as follows When analytics are performed through an analytic service provider: P , we can define Π over an augmented cosine similarity computation system: χ 2 = {(Sa, Sb, P ), (M, A, B)} in the same way and we detail its implementation over χ 2 in Protocol 2.

Π : [k × k] × [k × n] × [n × p] → [k × p] (M, A, B) → Π(M, A, B) = AB Where: (k, n, p) ∈ N * × N * × N * such as: {1 < k < n, 1 ≤ m ≤ k, 1 < p < k}. The implementation of Π over χ 1 is detailed in Protocol 1.

V. EXAMPLES OF REAL-WORLD APPLICATION SCENARIOS

A. Health-care application

To illustrate the application of our protocol in a real-world medical case, we'll introduce this scenario: The clinician-staff of the hospital H 1 receives new patients. After analysis they make some hypothesis about what the patients could have. To check their hypothesis, the clinicians request for local similar cases. Because the result was not relevant enough, they extend their search query for extern cases. The request is handled by a central computation service which multi-cast it for collaborative hospitals. We suppose that the hospital H 1 , the central computation service and a collaborative hospital H 2 correspond respectively to Sb, P and Sa. By applying our three-party Π-CSP, similarities are computed in a privacy way and communicated efficiently to the clinicians. We suppose that an EMR (Electronic Medical Record) has this structure: EMR (High temperature, headache, cough, chest pain, tinnitus, stomach pain). Let P 1 and P 2 be the patients received by H 1 . H 2 's relevant cases are C 1 , C 2 and C 3 which have respectively: hypertension, influenza and stomach problem. We set Parameters: n = 6, k = 2. Computation details are presented in TableI.

Results have revealed a similar case with a similarity score= 1 between patients P1(1,1,0,0,1,0) and C1(1,1,0,0,1,0), in addition to a relevant one with a similarity score= 0.85 between patients P2(1,0,1,1,0,0) and C2(1,1,1,1,0,0).

B. Recommendation system application

Assume that an online provider of a service S wants to improve his quality of service by setting up a recommendation system. For this, he decides to mine his users' sessions in order to categorize them according to some predefined profile and wants to guarantying their privacy. We suppose that the service includes 7 links: L 1 ,..., L 7 and 3 profiles: P 1 , P 3 and P 3 . The service provider will mine the click stream of a user during his last two sessions: S 1 and S 2 to match him with the most suitable profile. Let the service provider and the user be Sa and Sb respectively. Table2 bellow presents the click stream under each link. After applying our two-party Π-CSP in the same way detailed above we obtain results shown in TableII.

Table II. Results show that the most suitable profile for this user is P 1 with asimilarity score= 0.87 for session 1 and 0.74 for session 2. This method can also improve the clustering of the recommendation system by discovering new profiles in the case of divergent similarities.

RECOMANDATION SYSTEM L1 L2 L3 L4 L5 L6 L7 P1 1 1 1 1 1 1 1 P2 2 2 0 6 6 0 0 P3 0 0 3 4 5 0 0 S1 0 2 3 6 1 0 7 S2 4 0 2 3 5 3 3 M [3 × 3] M -1 [3 × 3] 1

VI. PRIVACY PROOF

A. security model

In this section we introduce communication and security models that will be used later to proof the privacy preservation property of our proposal.

Definition 1 (Multi-Party Computation MPC):

In an MPC model, a given set of participants want to compute the value of a public function relying on the join of their private data. Let P 1 , ..., P n be the participants and v 1 , ..., v n their private data respectively. The application of a public function f at the point (v 1 , ..., v n ) i.e. f (v 1 , ..., v n ) is an MPC [START_REF] Lindell | Secure multiparty computation for privacy-preserving data mining[END_REF].

Definition 2 (Semi-honest model):

In a semi honest model all participants to the execution of a communication protocol are supposed following the protocol with the exception that they save their intermediate results [START_REF] Lindell | Secure multiparty computation for privacy-preserving data mining[END_REF].

Definition 3 (Malicious model): In a malicious model there are no suppositions on the behaviour of participants to the execution of a communication protocol. There are three common situations which are: a) participant who stops the protocol untimely , b) participant who substitutes their input and c) participant who refuses to participate [START_REF] Lindell | Secure multiparty computation for privacy-preserving data mining[END_REF].

Definition 4 (Privacy preservation): An MPC protocol is privacy-preserving if no participant can learn about his/her collaborators's private data more than he/she can learn from the description of the public function and the result of its application, depending on the considered security model (semihonest, malicious).

B. System of equations: prerequisites

Definition 5 (System of equations): A system of equations is a collection of equations involving the same set of variables. We set (k 1 , k 2 ) ∈ N * ×N * . Let Γ be a system of (k 1 ) equations including (k 2 ) variables, then we note Γ as: Γ(k 1 , k 2 ).

Lemma 1: the matrix product between M [k×k] and A[k× n] is a system of (k×n) equations that involve [(k×k)+(k×n)] variables according to definition 5. i.e.

(M × A) = Γ(k × n, ((k × k) + (k × n))) (3)
Proposition 1: we set (k 1 , k 2 ) ∈ N * × N * , if k 1 < k 2 then Γ(k 1 , k 2 ) has infinitely-many solutions. Proposition 2: we set (k 1 , k 2 , k 3 , k 4 ) ∈ N * × N * × N * × N * , if Γ(k 1 , k 2 ) and Γ(k 3 , k 4 ) are two different systems of equations, then we have Γ(k 1 , k 2 ) ∪ Γ(k 3 , k 4 ) = Γ((k 1 + k 3 ), (k 2 + k 4 )) (4)
C. Privacy proof of our solution Theorem 1: Let us consider χ= {(Sa, Sb), (M, A, B)} a cosine similarity computation system and Π our two-party Π-CSP presented in Section IV-B. Π(M, A, B) is a privacypreserving MPC protocol under the malicious model.

Proof: In the construction of the Π-CSP presented in section IV-B we have assumed that:

1 < k < n 1 < p < k
where n, k and p are respectively: the number of individual attributes, the number of Sa's individuals and the number of Sb's individuals. We will prove that through these conditions we are preserving the privacy with no additional assumptions on Sa and Sb behaviours while verifying the privacy under the malicious model. Details of privacy proof throughout Π-CSP communication steps are presented below:

Step1: Sb receives M A[k × n] where M (resp. A) is a [k × k] (resp. [k × n]) matrix. According to Lemma 1: M A = Γ(k × n, ((k × k) + (k × n))) (5)
Because we have set k > 1, then (k×k

) > 1 ⇒ [(k×k)+(k× n)] > [(k × n) + 1] > (k × n).
Therefore, (5) has infinitelymany solutions according to Proposition 1. Thus, Sa's privacy is preserved.

Step2: Sa receives M AB[k × p] where B is a [n × p] matrix. We set: X[k × n] = M A[k × n] (6)
(6) ⇒ XB[k × p] = M AB[k × p] (7)
So, according to Lemma 1

XB = Γ(k × p, ((k × n) + (n × p))) (8)
But as X is well-known by Sa, its [k × n] variables could be substituted by their values, in this case [START_REF] Programering | mahout similarity algorithm[END_REF] becomes

XB = Γ((k × p), (n × p)) (9)
Then, given ( 7) and ( 9) we get

M AB = Γ((k × p), (n × p)) (10)
Since we have k < n then (k × p) < (n × p) and according to Proposition 1, M AB will have infinitely-many solutions. Therefore Sb's privacy is preserved.

Step3: AB[k × p] will be shared to Sb. Because A is a [k × n] matrix and B is a [k × p] matrix, we have according to Lemma 1

AB = Γ(k × p, ((k × n) + (k × p))) (11)
But as B is well-known by Sb, its [k × p] variables could be substituted by their values, thus [START_REF] Goethals | On private scalar product computation for privacy-preserving data mining[END_REF] becomes

AB = Γ((k × p), (k × n)) (12)
Since we have p < n then (k × p) < (n × p). So, according to Proposition 1, AB will have infinitely-many solutions. Therefore Sa's privacy is preserved.

Step1 with Step3: Sb will possess (5) from step1 and (11) from step3. Then, according to Proposition 2 M A∪AB = Γ(((k×n)+(k×p)), ((k×k)+(k×n)+(k×n))) [START_REF] Du | Privacy-preserving cooperative statistical analysis[END_REF] Because variables of A[k × n] are the same in M A and AB, then the number of variable in (13) will be reduced by [k × n] variables. Thus, [START_REF] Du | Privacy-preserving cooperative statistical analysis[END_REF] becomes

M A ∪ AB = Γ(((k × n) + (k × p)), ((k × k) + (k × n))) (14) Because we have set p < k and (k > 1 ⇒ k > 0), then we have (k × p) < (k × k) ⇒ ((k × n) + (k × p)) < ((k × k) + (k × n))
which means according to Proposition 1 that M A∪AB will have infinitely-many solutions. So, Sa's privacy is preserved. In the cases when noise vectors are added in the matrix A, their product with B will be considred as additional informations derived by Sa about Sb which may breach the Definition 4. Nonetheless, with the conditions that we have set on n, p and k, disclosing B as we have prooved is impossible, therefore additional derived information are not helpful.

Under a malicious model we distinguish three possible station behaviours according to Definition 3. if a station stops running the protocol untimely, no privacy risk may occur because the privacy of both stations is well preserved during the three Π-CSP steps as we have proved above. When it comes to injecting fake input by a station, The Π-CSP result will not provide more information about individuals of the other participant station than the cosine similarity result which respects well the Definition 4. Furthermore, if a station refuses to participate to the two-party Π-CSP, then no communication steps will take place.

With the privacy preservation proof throughout the different two-party Π-CSP steps and with no additional assumption on the stations' behaviours, in addition to considering some common malicious behaviours, we have proved the privacy preservation of the two-party Π-CSP under the malicious models according to (Definition 4, Definition 3).

Theorem 2: Let us consider χ= {(Sa, Sb, P ), (M, A, B)} a cosine similarity computation system and Π our three-party Π-CSP presented in Section IV-B. Π(M, A, B) is a privacypreserving MPC protocol under the semi-honest model.

Proof: We can prove Theorem 2 in the same way we have proved Theorem 1, provided that P follows the protocol and thus it does not disclose M to Sb. By adding this assumption on the behaviour of the service provider P , our three-party Π-CSP is a privacy-preserving MPC protocol under the semihonest model according to (Definition 4, Definition 2).

VII. PERFORMANCE EVALUATION

A. Simulation model and scenarios

In order to prove the efficiency of our Π-CSP we will evaluate the impact of Big data high volume and high velocity on Π-CSP running time and we compare it to the recent privacy-preserving cosine similarity PCSC protocol proposed in [START_REF] Lu | Toward efficient and privacy-preserving computing in big data era[END_REF]. We have avoided to test encryption-based privacy preserving protocols because of their inadequacy for big data analytics as was reported in [START_REF] Lu | Toward efficient and privacy-preserving computing in big data era[END_REF]. We make the experiments on the same set of attributes through a Python script in an Intel i5-2557M CPU running at 1.70GHz and having a 4 GB of RAM. We note that communication costs are not considred.

1) Volume impact: Big data high volume implies a high individual size and a high number of individuals. To target these characteristics, we make an evaluation test across three experiments: E 1 , E 2 and E 3 . We plot the running time of the direct cosine similarity computation DCC as a reference experiment in order to make comparison tests more significant. In E 1 we compute the similarity of a set up to 10000 individuals having each one a size of 100 attributes. In E 2 we evaluate the impact of individual size by expanding it to 1000 attributes and computing the similarity of the same set.

Finally, we perform E 3 by re-expanding the size of individuals to 10000 attribues, in order to check the precedent results.

2) Velocity impact: In this evaluation we will model the Π-CSP and PCSC protocol using the queuing theory. we consider an analytics service provider that receives on the average λ requests for individual similarity evaluation, every minute, according to a Poisson process. we assume that the request processing times are exponentially distributed with rate µ requests per minute and the service provider is operating all day long. We distinguish two different queuing system models whether their capacity is infinite or finite. Using Kendall notation [START_REF] Gelenbe | Introduction to queueing networks[END_REF] these models are denoted by M/M/1 and M/M/1/k and having both an infinite request sources and a FIFO service discipline. To determine λ and µ parameters, we explore the results of volume evaluation described above and we consider that one request corresponds to two individuals in addition to considering one minute as the time unit. Details are shown in TableIII.

B. Results and discussion

In what follows we present the different evaluation results and derive conclusions.

1) Volume evaluation results:

In E 1 we tested the impact of the number of individuals on the similarity compuation time. Results presented in Figure 3a show the efficiency of our Π-CSP compared to PCSC. By performing E 2 we have obtained results illustrated in Figure 3b which reveal the efficiency of Π-CSP with a low distance increase ( 0.0007s measured with a set of 10000 individuals) from DCSC running time. However, expanding the size of individuals has expanded significantly the distance between PCSC and DCSC running time with a rate of ( 348s measured with a set of 10000 individuals). The final experiment E 3 illustrated in Figure 3c is confirming the precedent results, Π-CSP running time remains stable as it was in E 2 in the neiberhood of exp(-5)s (with a set of 10000 individuals) and keeps a slow increasing distance rate from DCSC running time, while PCSC running time has augmented significantly with a rate of ( 7955s measured with a set of 10000 individuals) which increases consequently the distance from DCSC running time to ( 8103s). Volume evaluation tests have confirmed the efficiency of our Π-CSP compared to the recent PCSC protocol, it does not provoke an overhead in 2) Velocity evaluation results: Performance of the queueing systems running Π-CSP and PCSC are measured across the server utilization rate U , the mean queue length Q and the mean response time of the system R in function of the traffic intensity factor ρ. Performance results are described according to each model.

The M/M/1 model corresponds to a service provider who has an unlimited access. Performance measures of this model are calculated by the following equations

ρ = λ µ (15)
U = ρ (16)
Q = N -ρ (17)
R = N λ ( 18
)
Where N is the average number of requests in the system obtained as

N = ρ 1 -ρ (19)
Results of TableIV illustrated in Figure 4 show that the server running Π-CSP is undergoing a low intensity traffic ρ that raises in a low probability of server overload. This result is confirmed by looking the low server utilization rate U and the very low response time R even for a high request rate. The zero queue length result whatever the traffic intensity is also confirming the efficiency of the server running Π-CSP. However, running PCSC have resulted in a non linear increased intensity of the request traffic ρ that finished by a rate ρ = 1.24 > 1 which prevents the system reach the steady state and overload the server with an utilization rate U = 124%, this unreal rate reveal the need to add more PCSC server.

Results of Table V illustrated in Figure 4 are obtained by increasing the size of individuals to 1000 attributes, they reveal the efficiency of Π-CSP server which provides a high speed service by looking the low response time R and the zero queue length Q. However, PCSC server was subjected to an earlier overload reaching a utilization rate U = 1250% which requires adding more and more server.

  ) and a (resp. b ) is the Euclidean norm obtained by n i=1 a 2 i (resp. n i=1 b 2 i ). If vectors are normalized, i.e. a = (a 1 / a , ..., a n / a ) and b = (b 1 / b , ..., b n / b ), then the cosine similarity will be shortened to the dot product, i.e. cos(θ) = ( a • b).

Figure 1

 1 illustrates the relatonship between cos(θ) and the similarity of ( a, b).

Figure 1 .

 1 Figure 1. Cosine similarity[START_REF] Programering | mahout similarity algorithm[END_REF]

Figure 2 .

 2 Figure2. Big data characteristics[START_REF]Quora. what is big data and hadoop[END_REF]

Protocol 1 :

 1 Two party Π-CSP Step1: Sa 1: Generates a random invertible matrix M [k × k] 2: Creates A[k × n] from m normalized vectors Ai (as rows) 3: Adds (k -m) noise rows to A 4: Performs (M × A) and sends the result (M A) to Sb Step2: Sb 5: Creates B[n × p] from p normalized vectors Bi (as columns) 6: Performs (M A × B) and sends the result (M AB) to Sa Step3: Sa 7: Performs (M -1 × M AB) = AB[k × p] = Π(M, A, B) 8: Shares AB with Sb

Protocol 2 :

 2 Three party Π-CSP Step1: P 1: Generates a random invertible matrix M [k × k] 2: Sends M to Sa Step2: Sa 3: Creates A[k × n] from m normalized vectors Ai (as rows) 4: Adds (k -m) noise rows to A 5: Performs (M × A) and sends the result (M A) to Sb Step3: Sb 6: Creates B[n × p] from p normalized vectors Bi (as columns) 7: Performs (M A × B) and sends the result (M AB) to P Step4: P 8: Performs (M -1 × M AB) = AB[k × p] = Π(M, A, B) 8: Shares AB with Sa and Sb

Figure 3 .

 3 Figure 3. Volume evaluation

Table I .

 I

			HEALTH CARE
		High	Headache	Cough	Chest pain	Tinnitus	Stomach
		Temperature					pain
	P1	1	1	0	0	1	0
	P2	1	0	1	1	0	0
	C1	1	1	0	0	1	0
	C2	1	1	1	1	0	0
	C3	1	1	0	0	0	1
				Normalization
	P1	0.57	0.57	0	0	0.57	0
	P2	0.57	0	0.57	0.57	0	0
	C1	0.57	0.57	0	0	0.57	0
	C2	0.5	0.5	0.5	0.5	0	0
	C3	0.57	0.57	0	0	0	0.57
		M[3×3]		M -1 [3×3]
		2	3	4	2	-0.5	-1
		0	2	4	-3	0	2
		3	5	6	1.5	0.25	-1
				MA[3×6]
		4.92	4.92	1.5	1.5	1.14	2.28
		3.28	3.28	1	1	0	2.28
		7.63	7.63	2.5	2.5	1.71	3.42
		MAB[3×2]		AB[3×2]
		6.26	4.51		1	0.32
		3.74	3.01		0.57	0.85
		9.67	7.2		0.64	0.32

Table III .

 III QUEUEING MODEL

	Requests / min		100	500	1000	5000
	number of individuals	200	1000	2000	10000
	λ		100	200	500	10000
		Π-CSP Rtime (s)	0.00020	0.00048	0.00062	0.00260
	Size=100	PCSC Rtime (s) µ -Π-CSP (×10 7 )	1.52 3	7.31 6.25	14.88 9.67	74.44 11.53
		µ -PCSC	3947	4103	4032	4030
		Π-CSP Rtime (s)	0.00051	0.00144	0.00230	0.00975
	Size=1000	PCSC Rtime (s) µ -Π-CSP (×10 7 )	14.88 1.18	73.70 2.32	148.41 2.6	749.94 3.08
		µ -PCSC	403	407	404	400
		Π-CSP Rtime (s)	0.00451	0.01343	0.02497	0.07886
	Size=10000	PCSC Rtime (s) µ -Π-CSP (×10 6 )	148.41 1.33	749.94 2.23	1480.30 2.4	7480.09 3.8
		µ -PCSC	40	40	40	40

After increasing the size of individuals to 10000 attributes, results shown in Table VI and illustrated in Figure 4 show that Π-CSP server is still providing an efficient service, while PCSC server becomes totally overloaded, thus it can not even handle a low traffic rate ρ = 100 requests/minute.

.00 0.00 0.00 0.00

Because unlimited request access has produced an overload in the server running PCSP, we have used M/M/1/k system to model less efficient servers who have an access limited to k requests at one time. We have fixed the system capacity k to 300 requests involving individuals of 1000 attributes, and we measured its performance. Also, we introduce the request reject rate λ r in order to evaluate the quality of service. Results

are obtained as follows

Where λ e , P 0 and P k are respectively the effective arrival rate, the probabilty that system is full and the probability that system is empty. they are obtained as follows

Results of M/M/1/k model evaluation presented in TableVII and illustrated in Figure 5 show an efficiency in the server running Π-CSP with the same performance as it was in the unlimited acces model (with an individual size=1000 attributes). Nevertheless, limiting request access to 300/minute in order to avoid the overload of PCSC server did not improve its performance which is revealed by a high response time R and a maximum utilization rate U = 99.99% for a high intensity traffic. Running the PCSC system with a full request queue Q = 299 has led to a high request reject rate λ r = 4600 requests from 5000, which decreases consequently the quality of service.

VIII. CONCLUSION

In this paper we have proposed a novel efficient and privacy-preserving protocol for cosine similarity computation that we have called Π-CSP. Our protocol ensures data privacy in different scenarios through a matrix product. By a privacy proof throughout Π-CSP steps we are protecting the privacy of both numerical and binary attributes in order to target big data high variety. Across different performance evaluation tests, Π-CSP running time remains efficient either for a high data volume or a high velocity stream. When comparing these results to existing constructions, our protocol is the most suitable for big data analytics.


Guillaume Ansanay-Alex
email: guillaume.ansanay@cstb.fr

Yassine Abdelouadoud
email: yassine.abdelouadoud@cstb.fr

Pascal Schetelat
email: pascal.schetelat@cstb.fr

Statistical and Stochastic Modelling of French Households and Their Energy Consuming Activities

Keywords: energy performance gap, occupant behavior, prediction, building design

There often is a significant difference between predicted energy performance of buildings and measured energy performance once buildings are operational. Actual occupant behavior is often different from the assumptions made in the design stage, and this is regarded as one of the main reasons for the performance gap. The diversity in occupants' sociological and behavioral characteristics must then be taken into account when predictions are undertaken, in order to determine confidence intervals of the expectable performances. Software tools must then be made available to design firms, letting them generate statistically representative sets of occupants and plausible activity and appliance use scenarios. Here we introduce two tools developed at CSTB, named Qiriel and Croniq, focused respectively on statistical generation or inference of dwellings, appliances and households, and on stochastic simulation of occupants' activities and the implied appliances activation and power consumption. They are built upon French national databases on households and time use surveys. These tools enable their users to generate in a short amount of time hundreds of occupancy, activity and power consumption profiles for specific sociological profiles or for representative sets of households. The obtained sets of series can then be used to determine median and extreme configurations of building usage, and the implied range of building performances. Such tools can also be useful at the building design stage, in order to evaluate how robust a building, its HVAC systems and their regulation can be when confronted to a large variety of usage patterns.

Introduction

Several causes can affect the energy consumption of a building: its physical properties, HVAC equipments, weather and also user behavior. The environmental context engages the industry in developing efficient building components, faster and faster. This need, associated with the need of guaranteed energy consumptions, has made inevitable the use of energy simulation programs, from building design to building operation.

Even if many developments have been pursued to ensure more detailed and faster building energy simulations taking into account the building envelope, HVAC systems and weather conditions, most simulations still rely on static, constant, a priori determined occupancy profiles for modeling occupancy and its impacts on building energy performance. As a result, in more and more energy-efficient building where specific energy consumptions weigh more and more, the random aspect of user behavior can play a great part in the gap between predicted and actual performances.

The question that we can formulate is then: are we able to compute, not a single deterministic prediction of building energy consumption using many assumptions, but a range of probable building energy consumption values taking into account the uncertainties linked to building construction defaults or user behavior? Answering to the last part of this question leads us to observe, describe and model occupants and the diversity of their activities.

The modeling paradigm which suits this need of reproducing transient phenomena with switches between different states correlated to many possible variables, particularly with the time of the day and the day of the week, is stochastic modeling. In this class, inhomogeneous Markov chains are well suited for modeling time series of the presence and activity of occupants in a building.

Following early publications focused on the correct evaluation of the benefits of managing lights, first references of stochastic models appear concerning office presence modeling [START_REF] Wang | Modeling occupancy in single person offices[END_REF], then first approaches [START_REF] Herkel | A preliminary model of user behaviour regarding the manual control of windows in office buildings[END_REF] and their consolidation [START_REF] Herkel | Towards a model of user behaviour regarding the manual control of windows in office buildings[END_REF] for modeling window opening behaviors.

Stochastic modeling of the presence and activity of occupants is then further studied in papers and PhDs under the supervision of Darren Robinson. Based on stochastic presence models ( [START_REF] Page | Simulating occupant presence and behaviour in buildings[END_REF], [START_REF] Page | A generalised stochastic model for the simulation of occupant presence[END_REF]), Robinson then focuses on thermal comfort adaptation behaviors [START_REF] Haldi | On the unification of thermal perception and adaptive actions[END_REF], and details this approach further in window opening models [START_REF] Haldi | Interactions with window openings by office occupants[END_REF] and interaction with blinds. Haldi's PhD thesis gathers these results on thermal comfort adaptation behavior in [START_REF] Haldi | Towards a Unified Model of Occupants' Behaviour and Comfort for Building Energy Simulation[END_REF].

Simultaneously, stochastic models of the activity of occupants in dwellings are developed by Richardson [9] in order to estimate the instantaneous power loads of specific appliances.

Following these works, review papers were issued in 2012 about window opening behavior [START_REF] Fabi | Occupants' window opening behaviour: A literature review of factors influencing occupant behaviour and models[END_REF] and interactions with blinds [START_REF] Van Den | Patterns of occupant interaction with window blinds: A literature review[END_REF].

Lastly, two recent PhD works have summed up many previous references on occupancy modeling: Wilke's PhD thesis [START_REF] Wilke | Probabilistic Bottom-up Modelling of Occupancy and Activities to Predict Electricity Demand in Residential Buildings[END_REF] is focused on the simulation of specific energy consumption, and Vorger's [START_REF] Vorger | Étude de l'influence du comportement des occupants sur la performance énergétique des bâtiments[END_REF] implements a set of models from the literature along with new models.

Statistical Generation of Dwellings and Households : QIRIEL

QIRIEL is a Python module for sampling populations of occupants, dwellings and household appliances, the characteristics of which are based on national studies, or for inferring missing characteristics.

Fig. 1 shows, on an example of a sample of 1000 dwellings, a subset of the dwelling characteristics that can be generated: number of occupants, socio-economic classification of each occupant, age and marital status of the dwelling's reference occupant, dwelling area and number of rooms, dwelling type and occupation status, construction year, heating type and fuel, and the mutual information between these dwelling sociotechnical characteristics. Sample generation in QIRIEL is based on a Bayesian network modeling the joint distribution of variables in the national census [START_REF] Insee | Recensement de la population[END_REF] and studies [START_REF] Insee | Enquête Logement[END_REF] on housing. Samples can be generated representing the population of the whole country, or smaller territories of France, even on a scale smaller than the city scale.

A Bayesian network is a way of describing a multivariate probability distribution taking into account the statistical dependences between variables, via a directed acyclic graph. Said differently, a probabilistic graph describes a joint probability using a set of conditional probabilities. Taking as an example random variables , and , we can draw: Fig. 2: Example discrete Bayesian network Fig. 2 illustrates that depends on and depends on and . In this case, we can factorize the expression of the joint probability :

| |
where | is the probability of x given y. If these variables are discrete, the Bayesian network is also called discrete. For more details on Bayesian networks, the reader should turn to [START_REF] Koller | Probabilistic Graphical Models: Principles and Techniques[END_REF].

In QIRIEL, a Bayesian network has been built using data from the French national studies. The structure of this network is illustrated by Fig. 3.

The generation step (network sampling) is based on successive random selection of variables from the network conditionally to their parent(s) in the network. It is implemented through a Markov Chain Monte-Carlo method called Gibbs sampling. Once draws have been made, we get a sample of dwellings described by discrete variables. Continuous variables are generated from discrete ones using uniform draws in each discretization interval. Geographical Area (Region, Department, City) Fig. 3: Bayesian network for Qiriel

Stochastic Simulation of Occupants' Activities : CRONIQ

CRONIQ is a Python module for the stochastic modeling of occupant presence and activity, and for the simulation of specific electricity power load of home appliances. It is based on the results of the French national Time Use Survey [START_REF] Insee | Enquête Emploi du temps[END_REF] and measurement campaigns conducted by Enertech [START_REF]Enertech[END_REF].

The Time Use Survey concerned 12000 French households over one year, using in particular daily notebooks where surveyed individuals must write, every 10 minutes, what their activities are, possible activities being categorized.

In its current version, CRONIQ implements a kernel of activity modeling on which is built a set of appliance activation models. Once an appliance is activated, a power consumption model is called. CRONIQ's kernel of activity modeling is composed of a set of transition matrices corresponding to inhomogeneous Markov chains.

A discrete time Markov process is a sequence of random variables with values in state space .

is the state of the process at time . When is finite or countable, the process is called a Markov chain or discrete state space Markov chain.

For CRONIQ, is the set of possible activities:

{ }

The main property of a Markov chain is that all the information needed for the prediction of a future state is contained in the present state:

| | |

Probability

| is called transition probability from state i to state j. Denoting this transition probability as , we call ( ) the transition matrix of the Markov chain at time .

Activity modeling in CRONIQ is based on such transition matrices: by applying Hierarchical Ascendant Classification and self-organizing maps algorithms on the whole set of daily activities from the TUS, we determined a set of typical days, and the corresponding transition matrices for each time of day. These transition matrices are used successively, with probabilities of being used depending on occupants' sociological characteristics.

Each of these typical days is composed of activities which can be linked to presence, internal gains and the activation of home appliances, the power consumption of which is then simulated.

Application Results

In order to demonstrate the possibilities of QIRIEL and CRONIQ, in this section we show example results of running these tools for the sampling of dwellings and households in two French cities: Paris and Brioude, a little city located in the department of Haute-Loire.

Statistical Generation of Dwellings and Households

Using QIRIEL, we can generate 500 dwellings in each city, and illustrate the sociotechnical differences between households in these two cities, as they are described by INSEE studies. Figs. 4 to 7 illustrate some dwelling or household characteristics that can be computed.

Stochastic Simulation of Activities

Using CRONIQ and the sets of dwellings and households generated by QIRIEL, we can simulate the activity and specific energy consumption in all dwellings. Figs. 8 and9 illustrate the activity profiles and implied energy consumptions that can be computed.

Conclusion and Perspectives

Using QIRIEL and CRONIQ enables the generation of varied profiles of presence, activity, internal gains and specific electricity consumption for population samples with statistically representative socio-technical characteristics.

The mathematical framework behind QIRIEL and CRONIQ has nothing specific to the residential sector, or to the French territory: perspectives then include the extension of these tools to other sectors, provided sufficiently representative datasets are available, or the application of the statistical and stochastic methods to other countries where census data and Time Use Surveys are available.

Fig. 1 :

 1 Fig. 1: Dwellings and households sociotechnical characteristics generated by QIRIEL

Fig. 4 :Fig. 5 :Fig. 6 :Fig. 7 :

 4567 Fig. 4: Areas of generated dwellings

Fig. 8 :Fig. 9 :Fig. 10 :

 8910 Fig. 8: Activity profiles of all occupants in generated dwellings over one week, in Paris

Acknowledgment

The authors acknowledge the support of the French Agence Nationale de la Recherche (ANR) under reference ANR-13-VBDU-0006 (OMEGA project).


Mourad Benmalek
email: mbenmalek@esi.dz

Yacine Challal
email: ychallal@esi.dz

eSKAMI: Efficient and Scalable multi-group Key management for Advanced Metering Infrastructure in Smart Grid

Keywords: Advanced Metering Infrastructure (AMI), Smart Grid (SG), Security, Key Management Scheme (KMS)

Advanced Metering Infrastructure (AMI) is composed of systems and networks for measuring, collecting, storing, analyzing, and exploiting energy usage related data. AMI is an enabling technology for Smart Grid (SG) and hence represents a privileged target for security attacks with potentially great damage against infrastructures and privacy. For this reason, security has been identified as one of the most challenging topics in AMI development, and designing an efficient Key Management Scheme (KMS) is one of first important steps. In this paper, we propose a new scalable and efficient key management scheme that we call Efficient and Scalable multi-group Key Management for AMI (eSKAMI) to secure data communications in an Advanced Metering Infrastructure. It is a key management scheme that can support unicast, multicast and broadcast communications based on an efficient Multi-group Key graph technique. An analysis of security and performance, and a comparision of our scheme with recently proposed schemes show that our KMS induces low storage overhead compared to existing solutions (reduction reaches 83%) without increasing the communication overhead.

I. INTRODUCTION

A SMART GRID (SG) is an electrical grid that is enhanced with communications and networking, computing, and signal processing technologies [START_REF] Fang | Smart Grid -The New and Improved Power Grid: A Survey[END_REF]. Two-way flows of electricity and real-time energy related information (production, transport, distribution and consumption) issued by smart devices and smart meters, brings new perspectives to energy management and optimization in the SG. A practical example of the benefits of introducing the smart grid includes the greater availability of electricity to homes at a lower cost, and the integration of distributed and renewable power generation such as local solar and wind generators [START_REF] Fadlullah | Toward Intelligent Machine-to-Machine Communications in Smart Grid[END_REF]. To achieve an intelligent grid, a succession of sub-systems should be realized [START_REF] Mohassel | A survey on Advanced Metering Infrastructure[END_REF] : Advanced Metering Infrustructure (AMI), Advanced Distrubtion Operations (ADO), Advanced Transmission Operations (ATO) and Advanced Assent Management (AAM).

Advanced Metering Infrastructure (AMI) is a key element in the smart grid. It is responsible for collecting all the data and information from loads and consumers. AMI is also responsible for implementing control signals and commands to perform necessary control actions [START_REF] Mohassel | A survey on Advanced Metering Infrastructure[END_REF]. A typical AMI involves Smart Meters (SMs), Home Area Networks (HANs), wide area communications infrastructure, and Meter Data Management Systems (MDMS). The critical role of AMI in the smart grid has made this system a privileged target of cyber attacks. Consequently, AMI security is of very high importance for the security of the smart grid.

In general, the fundamental security requirements of AMI are: confidentiality, integrity, and availability [START_REF] Cleveland | Cyber Security Issues for Advanced Metering Infrasttructure (AMI)[END_REF]. Privacy of the customers sensitive data like metering and energy consumption is the most important issue of confidentiality in AMI, Customers do not want unauthorized people or marketing firms to know how much energy they are using, what their pattern of energy usage is, or other energy-related information. Integrity in AMI is very important for both meter reading stored in smart meters or transmitted over the communication channels and control commands such as Demand Response (DR) mechanisms that enable customers to cut down energy usage at peak times for example. Unlike traditionnal systems, availability of information and control commands generated and managed by AMI is compulsory for the operation of the whole smart grid. which contains much more meter readings being exchanged between smart meters and utility system.

To meet these security requirements, cryptographic countermeasures must be deployed to protect data integrity and confidentiality for AMI. However, cryptographic mechanisms for AMI require also an efficient key management. Inadequate key management can result in possible key disclosure to attackers, and even jeopardizing the entire goal of secure communications in AMI. Therefore, key management is a critical process to ensure the secure operation of AMI.

Several key management schemes have been proposed [START_REF] Kamto | Light-weight key distribution and management for Advanced Metering Infrastructure[END_REF][START_REF] Yan | A secure and reliable in-network collaborative communication scheme for advanced metering infrastructure in smart grid[END_REF][START_REF] Li | Multicast authentication in the smart grid with one time signature[END_REF][8][START_REF] Wu | Fault-tolerant and scalable key management for smart grid[END_REF][START_REF] Xia | Secure Key Distribution for the Smart Grid[END_REF][START_REF] Liu | A Key Management Scheme for Secure Communications of Advanced Metering Infrastructure in Smart Grid[END_REF][START_REF] Wan | SKM: Scalable Key Management for Advanced Metering Infrastructure in Smart Grids[END_REF], but none of them can completely satisfy the security requirements mentioned previously. Hence, we propose a new key management scheme for AMI based on an efficient and scalable multi-group key graph technique to secure unicast, multicast, and broadcast communications in a smart grid network while meeting the security requirements of AMI.

The remainder of this paper is organized as follows. We discuss related work in Section II. In Section III we study the architecture of an AMI and the key management function requirements. In Section IV we present our KMS which is an efficient key management scheme that can support unicast, multicast and broadcast communications. We give a security and performance analysis of our KMS in Section VI. Finally, we draw our conclusions and future works in Section VII.

II. RELATED WORKS

In recent years, several schemes have been proposed to secure communications for AMI in smart grid.

According to [START_REF] Shein | Security Measures for Advanced Metering Infrastructure Components[END_REF], key management has been identified as a fundamental security challenge in an AMI. Kamto et al. [START_REF] Kamto | Light-weight key distribution and management for Advanced Metering Infrastructure[END_REF] proposed a key distribution and management scheme for large customer networks to achieve authentication, privacy and data confidentiality in AMI. The proposed scheme is computationally expensive because of relying on Diffie-Hellman (DH) [START_REF] Diffie | New directions in cryptography[END_REF] key exchange and a group ID-based mechanism [START_REF] Shamir | Identity-based cryptosystems and signature schemes[END_REF]. Furthermore, this scheme only secures communications between HAN (Home Area Network) devices and the gateway.

AMI devices authentication, and confidentiality for user privacy and user behavior is an issue that still lacks a complete solution. Yan et al. [START_REF] Yan | A secure and reliable in-network collaborative communication scheme for advanced metering infrastructure in smart grid[END_REF] proposed an integrated approach in which trust services, integrity and data privacy could be provided by mutual authentications. In [START_REF] Li | Multicast authentication in the smart grid with one time signature[END_REF], Li and Cao proposed a one-time signature scheme to address the problem of preventing message forgery attacks in multicast communications. The proposed scheme presents a significant reduction in the storage and communication overhead, but only focuses on communication integrity and do not address confidentiality.

Nicanfar et al. [8] developed a key management protocol for data communication between the utility server and customers smart meters based on the concept of ID-Based public/private key pair model [START_REF] Shamir | Identity-based cryptosystems and signature schemes[END_REF]. Although the proposed key management prsotocol aims to reduce the computation overheads, the synchronization process still demands considerable computation efforts. Wu and Zhou [START_REF] Wu | Fault-tolerant and scalable key management for smart grid[END_REF] combines symmetric key technique based on the Needham-Schroeder authentication protocol [START_REF] Needham | Using encryption for authentication in large networks of computers[END_REF] and elliptic curve public key technique [START_REF] Miller | Use of Elliptic Curves in Cryptography[END_REF] to provide a novel key management scheme for smart srid assuring strong security, fault-tolerance, efficiency and scalability. In the work of Xia and Wang [START_REF] Liu | A Key Management Scheme for Secure Communications of Advanced Metering Infrastructure in Smart Grid[END_REF], the authors showed that Wu and Zhous scheme is vulnerable to the man-in-the-middle attack and proposed an improvement for this scheme based on a trusted third party. However, these two schemes do not support secure multicast communications that play an important role and have wide applications in the SG.

Recently, a key management scheme is proposed by Liu et al. [START_REF] Liu | A Key Management Scheme for Secure Communications of Advanced Metering Infrastructure in Smart Grid[END_REF] to secure unicast, multicast, and broadcast communications in AMI. This scheme based on the key graph management approach [START_REF] Wong | Secure group communication using key graphs[END_REF] suffers from a lack of scalability due to inefficient key management that results in nonnegligible communication overhead for such a large-scale system. Moreover, we found that Liu et al.'s scheme is not tolerant to packet loss. Wan et al. [START_REF] Wan | SKM: Scalable Key Management for Advanced Metering Infrastructure in Smart Grids[END_REF] proposed an improvement for Liu et al.'s scheme that combines an adapted identitybased cryptosystem [START_REF] Chen | Identity based authenticated key agreement protocols from pairings[END_REF] and one-way function tree (OFT) approach [START_REF] Mcgrew | Key establishment in large dynamic groups: Using one-way function trees[END_REF] for multicast key management. The use of an OFT for each DR project (DR projects are programs designed to decrease electricity consumption or shift it from on-peak to off-peak periods depending on consumers preferences) results in non-negligible overhead for key storage.

III. AMI SYSTEM STRUCTURE AND KMS SECURITY REQUIREMENTS

In this section we analyze AMI system structure to identify the basic requirements that are relevant to key management.

A. AMI System Structure

An AMI is composed of (Fig. 1): 1) Smart Meters (SMs): Which are electrical meters providing two-way communications, automated meter data collection and outage management. They also allow dynamic pricing, and joining/leaving Demand Response pricing projects for load control. 3) Gateways (GWs): Implement protocol conversion and communications between two heterogeneous networks, like the in-home network and wide area network.

4) Wide Area Communication Infrastructure: It supports bidirectional communication between costumers domain and the utility system. Different architectures and medias can be used like power line communication system, cellular networks, or IP-based networks [START_REF] Sauter | End-to-End Communication Architecture for Smart Grids[END_REF].

5) Meter Data Management Systems (MDMS): Acts as a database system for storing, managing, and further analyzing metering data in order to propose dynamic pricing, better customer service, DR and energy consumption management purposes.

B. KMS Function Requirements

As KMS is a critical subsystem of the whole AMI security architecture, and given the above characteristics of AMI interactive messages, we summarize in what follows the basic requirements for an effective KMS of AMI:

1) Hybride Transmission Modes: The key management framework should support the three tansmission modes in AMI: unicast, multicast and broadcast. For each mode, methods of key generating, refreshing, and distribution policies must be designed clearly.

2) Scalability: It represents a major issue for such a largescale system consisting of millions of SMs.

3) Efficiency: We consider three aspects: computation, storage, and communication because of their impact on the overal system performance. The KMS processes should be computationally efficient as well as memory-usage efficient meeting the scarcity of computation and storage capacities in SMs. The processes of key generation, distribution, usage, and refreshment should also induce low communication overhead, which is important to time-critical scenarios in AMI.

4) Backward and forward secrecy: Users participating in DR projects are not fixed. Any user can join or leave any DR project at any time. For this reason, it is obvious that the forward and the backward sercery [START_REF] Wong | Secure group communication using key graphs[END_REF] should be guaranteed. The forward sercery implies that previously used secret keys and messages must be inaccessible by the new users who participate in a DR project, and the backward secrecy means that the future secret keys and messages must be inaccessible by users who leave a DR project.

5) Collusion freedom: Any set of users that unsubscribe a DR project should not be able to deduce the current used group key.

IV. PROPOSED SOLUTION

We introduce a new scalable and efficient key management scheme that we call Efficient and Scalable multi-group Key management for secure data communications in an Advanced Metering Infrastructure (eSKAMI). It is based on a Multigroup Key graph structure that supports the management of multiple Demand Response projects simultaneously for each customer. We will demonstrate later that this new structure scales to large smart grids with dynamic Demand Response projects membership while meeting Smart Meters constraints in terms of memory and bandwidth capacities.

A. Assumptions

1) The Advanced Metering Infrastructure complies with the architecture illustrated in Fig. 1. The MDMS denotes the management side and it is responsible for key generation and rekeying, and it is well protected from attacks.

2) A specific default DR project is mandatory for all users of the SG, i.e. all users are subscribed to this default DR project. This default DR project will be used by MDMS to broadcast control messages or information to all customers of the SG.

3) Except the mandatory DR project, any user can join or leave any DR project at any time.

B. Initialization of the KMS

Let us consider a set of n smart meters. Initially, a specific method of securely exchanging cryptographic keys over a public channel is used to establish individual keys between the MDMS and smart meters (For example, we can use the Elliptic Curve Diffie-Hellman ECDH key agreement [22] that is known to induce less overhead compared to many exiting end-to-end key establishement using standard Diffie-Hellman protocol). Theses individual keys {k 1 , ..., k n } will be refreshed periodically and will be used in two ways. The first one is to secure unicast communications between MDMS and the SMs, and in the other one they are used for generating the multigroup key graph for secure multicast communications.

Moreover, The MDMS must generate a group key GK 0 (refreshed periodically) for the default DR project. This key will be generated and transmitted through secure channels for each SM, and will be used to secure messages transmitted in broadcast mode. In Table I, we summarize the terminology that we will use throughout the remaining of this paper.

C. Group Key Management

In our solution, we propose a secure, efficient and scalable management of group keys in the AMI system. To address the scalability issue, LKH (Logical Key Hierarchy) [START_REF] Wong | Secure group communication using key graphs[END_REF] is mostly used in the literature. However, as the users can subscribe to multiple DR projects at the same time, an intuitive solution is to use a key tree for each DR project as shown in Fig. 2. In LKH, each member holds a copy of its leaf secret key and all the keys corresponding to the nodes in the path from its leaf to the root. Hence, if a user u i subscribes to two or more DR projects simultaneously (e.g. DR j and DR k ), she/he needs to manage two sets of keys. As a result, directly applying LKH may be costly and has a non-negligible overhead for key storage. The idea of our new key graph technique is to allow multiple DR projects to share a new set of keys. For instance (as illustrated in Fig. 2), a user u 1 in DR 1 ∩ DR 2 ∩ DR 3 does not need to manage three set of keys to handle the three DR projects. Indeed, in our solution u 1 will hold only keys on its path to group key corresponding to her/his last subscription. Moreover, when a user joins or leaves a DR project, the communication cost for rekeying operations will not increase significantly compared to the cost induced by using separate LKH tree inside each DR project.

1) Multi-group Key Graph Structure: Our multi-group key graph structure can be modeled as shown in Fig. 2: in the lower level, each LKH tree represents a set of users with the same first DR project subscription, the leaf node of the tree is a user's individual key and tree's root is the DR project's group key. The graph in the upper level represents combinaisons of root keys for users subscribing to multiple DR projects at the same time. Our multi-group key graph has the following proprieties: (a) a user only belongs to one LKH tree in the multi-group key graph corresponding to her/his Home DR (first DR project subscription). She/He holds a copy of its leaf secret key and all keys corresponding to the nodes in the path from its leaf to the root in this tree; (b) a user has all group keys of the other DR projects to which she/he is subscribed; (c) if a user leaves her/his first DR project and remains subscribed to one or more DR projects, she/he will shift to a new LKH tree (this LKH tree will be the tree corresponding to her/his new Home DR). These features ensure that a user will not subscribe and pay for the same DR project multiple times.

An example of the key graph is given according to Fig. 2., the MDMS provides 4 DR projects. Some users subscribe to only one of DR projects (e.g. u 2 subscribes only to DR 1 ), while other users may subscribe to multiple DR projects simultaneously (e.g. u 1 subscribes to DR 1 , DR 2 , and DR 3 ). In this figure, no user subscribes to both DR 2 and DR 3 at the same time. We next illustrate both member join and leave procedures executed by the MDMS when receiving a member join or leave request.

2) Rekeying operations: In our solution, when a user subscribes or leaves a DR project, rekeying consists of 3 operations: joining/leaving an LKH tree, shifting among LKH trees, and receiving new keys for new subscriptions. Table II. lists the rekey operations and their corresponding user events.

a) Leave procedure: The leave procedure deals with the case when a user unsubscribes from a DR project (u i leaves DR j ). Let φ j = {u l /u l subscribed to DR j }, Let X jk = {u l /u l ∈ φ j and Home DR (u l ) = DR k }, Let ω 1k = {u l /u l ∈ χ jk and DR k ∈ set(u i )}, Let ω 2k = {u l /u l / ∈ χ jk and DR k ∈ set(u i )}.

• Case 1: We consider a user who subscribed to one or multiple DR projects and leaves her/his Home DR project:

The MDMS updates and renew keys according to Algorithm 1.

Algorithm 1 : Update keys when user leaves Home DR Function leaveHomeDR (ui, DRj) ; 1 Update GKj (GK j is the new group key); 2 Apply standard LKH approach in DRj tree; 3 If N sub(ui) = 1 : 4 MDMS → X jk :

Enc(Enc(GK j , GK k ), GKj) 5 Else : 6 MDMS → ω 1k : 1≤h≤d Enc(Enc(GK j , Child h (GK k )), GKj) 7 MDMS → ω 2k : Enc(Enc(GK j , GK k ), GKj) 8
Shift user ui to LKH tree corresponding to his/her second subscription DRx using standard LKH apporach (without updating key GKx that ui already has)

Example 1: When u 2 (user who subscribed only to DR 1 ) leaves DR 1 : (a) standard LKH approach is used to replace keys in the key tree corresponding to DR 1 :

MDMS → {u 1 } : Enc(GK 1 , k 1 ) (1) Enc(GK 1-4 , k 1 ) (2)
MDMS → {u 3 , u 4 } : Enc(GK 1 , k 3-4 ) (3) Enc(k 1-4 , k 3-4 ) (4)
MDMS → {u 5 , u 6 , u 7 , u 8 } : Enc(GK 1 , k 5-8 ) (5) (b) update GK 1 for users in X 1k : first, we encrypt the new key GK 1 with keys GK k to ensure that only users belonging to DR k tree can obtain the relevant key, and the second encryption with GK 1 to ensure that only users subscribing to DR1 can obtain the key.

MDMS → X 12 : Enc(Enc(GK 1 , GK 2 )), GK 1 ) (6)
MDMS → X 14 : Enc(Enc(GK 1 , GK 4 )), GK 1 )

Example 2: When u 1 (user who subscribed to DR 1 , DR 2 and DR 3 ) leaves DR 1 : (a) standard LKH approach is used to replace keys in the key tree corresponding to DR 1 :

MDMS → {u 2 } : Enc(GK 1 , k 2 ) (8) Enc(GK 1-4 , k 2 ) (9) MDMS → {u 3 , u 4 } : Enc(GK 1 , k 3-4 ) (10) Enc(k 1-4 , k 3-4 ) (11)
MDMS → {u 5 , u 6 , u 7 , u 8 } :

Enc(GK 1 , k 5-8 ) (12)
(b) update GK 1 for users in ω 1k :

MDMS → ω 12 : Enc(Enc(GK 1 , k 9-12 ), GK 2 ) (13) Enc(Enc(GK 1 , k 13-14 ), GK 2 ) (14) MDMS → ω 13 : Enc(Enc(GK 1 , k 15-16 ), GK 3 ) (15) Enc(Enc(GK 1 , k 17-18 ), GK 3 ) (16) (c) update GK 1 for users in ω 2k : MDMS → ω 24 : Enc(Enc(GK 1 , GK 4 ), GK 1 ) (17)
(d) shift u 1 the LKH tree corresponding to DR 2 which becomes her/his new home DR project using standard LKH approach (without updating GK 2 that u 1 already has).

• Case 2: We consider a user who is subscribed to multiple DR projects and leaves one DR project which is not her/his Home DR project: The MDMS updates and renews keys according to Algorithm 2.

Let DR x = Home DR(u i ), Let ω 3k = {u l /u l ∈ ω 1k and DR k = DR x }.

Algorithm 2: Update keys when user leaves DR project Function leaveDR (ui, DRj) ; 1 Update GKj (GK j is the new group key); 2 MDMS → φj : 1≤h≤d Enc(GK j , Child h (GK j ))

3 MDMS → Xjx : kαxshared keys in DR k tree
Enc(Enc(GK j , kαx), GKj)

4 MDMS → ω 3k : 1≤h≤d Enc(Enc(GK j , Child h (GK k )), GKj) 5 MDMS → ω 2k : Enc(Enc(GK j , GK k ), GKj)
Example 3: When u 1 (user who subscribed to DR 1 , DR Leave an LKH tree A user has subscribed to only one DR project. Then, he leaves this DR project.

Shift among LKH trees

A user has subscribed to multiple DR projects. Then, she/he leaves her/his Home DR project.

b) Join procedure: The join procedure deals with the case that a user subscribes to a new DR project (u i joins DR j ).

• Case 1: We consider a user who joins her/his first DR project: The MDMS apply the join rekeyin Algorithm 3.

Algorithm 3 : Update keys when user joins Home DR Function joinHomeDR (ui, DRj) ; 1 GK j = H(GKj); 2 Send a notification to all users in X jk about the application of the one-way function; 3 Apply standard LKH approach in DRj tree.

• Case 2: We consider a user who joins one DR project which is not her/his Home DR project: The MDMS updates and renews keys according to Algorithm 4.

Algorithm 4: Update keys when user joins DR project Function joinHomeDR (ui, DRj) ; 1 GK j = H(GKj); 2 Send the new group key GK j to ui ; 3 Send a notification to all users in φj about the application of the one-way function.

D. Secure Unicast, Multicast, and Broadcast Communications

In the unicast, multicast, and broadcast communication process, the confidentiality and integrity of the messages should be provided. For this purpose, individual keys {k 1 , ..., k n }, broadcast key {GK 0 }, and group keys {GK 1 , ..., GK m } are used to secure interactive messages in AMI exchanged between the MDMS and SMs. Our scheme adopts the following message transmission methods:

1) Secure Unicast Communications: Suppose the individual key k i is established between the MDMS and a smart meter SM i . When the MDMS (resp. SM i ) wants to send a message M to SM i (resp. MDMS), the MDMS (resp. SM i ): (a) generates a session key sk i from individual user key k i ; (b) encrypts, authenticates, and sends the following message:

MDMS → SM i : (Enc(M, sk i ) HM AC ski (M )) (24)
On receiving the message, SM i (resp. MDMS) generates the session key sk i and then verifies and decrypts the message M .

2) Secure Multicast, and Broadcast Communications: The same transmission method used to secure unicast communications is adopted to send a secure message M from MDMS to all users or subscribed users to a specific DR project. The MDMS: (a) generates a session key sgk j (resp. sgk 0 ) from j t h DR project group key GK j (resp. broadcasts key GK 0 ) (b) encrypts, authenticates, and sends the following message: MDMS → {SM i } :

(Enc(M, sgk j ) HM AC skgj (M )) (25)
MDMS → {SM i , ..., SM n } :

(Enc(M, sgk 0 ) HM AC skg0 (M )) (26)
V. PERFORMANCE EVALUATION

In this section we present a security and performance analysis of our solution and prove its safety and efficiency. In Table III we compare our scheme with two recently proposed schemes in [START_REF] Liu | A Key Management Scheme for Secure Communications of Advanced Metering Infrastructure in Smart Grid[END_REF] and [START_REF] Wan | SKM: Scalable Key Management for Advanced Metering Infrastructure in Smart Grids[END_REF]. A. Security Analysis 1) Confidentiality and Integrity: As mentioned above, the session keys used to ensure the communciations are generated before every session. These session keys are held only by the two communication ends which garantees message confidentiality. Moreover, receiver verifies the MAC code of encrypted message using these session keys to ensure message integrity.

2) Forward and Backward Sercery: The proposed key management scheme supports both backward secrecy and forward secrecy. Aftze a new node joins a DR project, all users applies a one-way hash function to the affected keys. That ensures that none of the old key can be recovered by the new coming user which garantees backward secrecy. When a user leaves a DR project, all affected keys (those known be the departing user in both lower and upper level) will be changed and redistributed securely which prevents the departing customer from having acces to the new keys and hence forward secrecy is preserved.

3) Collusion freedom: Any set of users unsubscribe a set of DR projects can not be able to deduce the current used DR projects keys, because all affected keys when any user leaves a DR project will be update and new keys are independents.

B. Performance Analysis 1) Storage Cost: On the aspect of the storage cost, we mainly focus on the number of symmetric keys stored in the MDMS/SMs, and used for unicast, broadcast and multicast transmissions (individual keys, group keys and broadcast key). We compare our scheme with these proposed in [START_REF] Liu | A Key Management Scheme for Secure Communications of Advanced Metering Infrastructure in Smart Grid[END_REF] and [START_REF] Wan | SKM: Scalable Key Management for Advanced Metering Infrastructure in Smart Grids[END_REF] as shown in Table IV (we use balanced binary LKH trees).

m i -Npr + 1 N sub(u i ) i=1 (log 2 m i +1)+1 eSKAMI 2 Npr i=1 (m i -1) + 1 log 2 (|Home DR(u i )|)+ N sub(u i ) + 1
2) Communication Cost: The solution we proposed uses an efficient multi-group key graph structure. Rekey operations (join, leave, and shift) introduce extra rekey cost. In the joining/leaving scenario, even though the number of group members and subscribed DR projects are the same, the number of keys to be updated varies according to the positions of the joining/leaving member in the multi-group key graph.

a) Leave procedure: According to Algorithm 1 and Algorithm 2, the communication cost in the worse cases will be as follows:

• Case 1: When u i leaves her/his Home DR project DR j (user subscribed only to one DR project) :

comCost = (2h j + N pr -1)|K| (27)
|K| : the size of the key in bit.

• Case 2: When u i leaves her/his Home DR project DR j (user subscribed to multiple DR projects at the same time):

comCost = (2h j + d.A + B + 2h k )|K| + c (28)
h k : the hight of the new Home DR project.

A = N sub(u i ) B = N pr -N sub(u i )
The " + c" term is to specify on which group key we must apply the one-way function c = log 2 N pr .

• Case 3: When u i leaves one DR project DR j which is not her/his Home DR project DR l :

comCost = (d + 2h l + d.A + B)|K| (29)
b) Join procedure: According to Algorithm 3 and Algorithm 4, the communication cost will be as follows:

• Case 1: When u i joins her/his Home DR project DR j :

comCost = 2h j |K| + c (30)
• Case 2: When u i joins a new DR project DR j which is not her/his Home DR project DR l :

comCost = |K| + c (31)
3) Simulation:

• Simulation Model: We consider a smart grid with 1 million users. The utility provides 15 DR projects to users (for example, Real Time Pricing program, Time Of Use Pricing program, Critical Pick Pricing program, ... etc). We assume that users arrivals are modeled as a Poisson process with parameter λ (users/months), and given that there are no statistical studies of DR projects membership behavior for the moment, we assume that membership duration in each DR projects follows an law with parameter µ. Our assumption stays very close to reality.

A typical user session starts by a join event, which can be followed by one or more join/leave to/from other DR projects events. At the end of a membership in a DR project, a user leaves this DR project.

We will consider a session of 24 months. Interarrival average λ is of 1000 users/month, and average membership duration µ is 4 months. We will use a 128b long symmetric keys, and balanced binary LKH trees (d = 2). Storage and Communication costs of Lius et al. and SKM+ KMS are readily obtained from [START_REF] Liu | A Key Management Scheme for Secure Communications of Advanced Metering Infrastructure in Smart Grid[END_REF] and [START_REF] Wan | SKM: Scalable Key Management for Advanced Metering Infrastructure in Smart Grids[END_REF].

• Simulation Results :

Storage Cost: For MDMS, the storage cost is not a problem, we can use special key servers as storage. In constract, the storage ability of SMs is limited to 4-12 KB [START_REF] Wang | Cyber security in the Smart Grid: Survey and challenges[END_REF]. Fig. 3 shows a comparison of average storage cost in SMs between the three schemes according to the number of subscribed DR projects at the same time and fixing the members of DR projects members to around 100000. We can see that in our scheme, a SM stores much fewer keys than that in [START_REF] Wan | SKM: Scalable Key Management for Advanced Metering Infrastructure in Smart Grids[END_REF] (reduction reaches 83% while a user can subscribe to 15 DR projects at the same time) and little more keys than that in [START_REF] Liu | A Key Management Scheme for Secure Communications of Advanced Metering Infrastructure in Smart Grid[END_REF]. This can be explained as follows: the scheme proposed by liu et al. do not adopt a key graph technique, a SM stores one key for each subscribed DR project which represents an inefficient key management that results in non-negligible communication overhead. In SKM+, authors used a One-way Function Tree OFT for each DR project, the number of keys stored will increase significantly when a user subscribes to new DR projects. Whereas, in eSKAMI we see that the number of subscribed DR project do not affect significantly the storage cost. Communication Cost: Fig. 5 (a) and (b) shows a comparison of average communication cost par event (join/leave) according to the number of subscribed DR projects at the same time. We assume that there are 100000 users (on average) subscribing to each DR project. The bandwith overhead of a join is the same as a leave for the scheme of Liu et al. and it is a lot more than that of SKM+ and eSKAMI because of the inefficient multicast key management. Note that although SKM+ has less communication overhead than eSKAMI for join/leave event, the difference is not significant and it is too little to be seen in the Fig. 5 (a). In this paper, we proposed a new key management scheme for AMI in smart grid. It is an efficient and scalable key management scheme, capable of supporting unicast, broadcast, as well as broadcast communications. The proposed scheme use a novel multi-group key graph technique that supports the management of multiple Demand Response projects simultaneously for each customer and induces low storage overhead compared to existing solutions whithout increasing the communiction overhead. In addition, the proposed KMS can achieve both forward and backward secrecy. An automatic verification of security with an automated validation tool like AVISPA is also in our perspectives.

Fig. 1 :

 1 Fig. 1: System structure of AMI

Fig. 2 :

 2 Fig. 2: Example of our multi-group key graph structure

Fig. 3 :

 3 Fig. 3: Average storage cost in SMs according to number of subscribed DR projects

15 Fig. 4 :

 154 Fig. 4: Average storage cost according to DR projects members

Fig. 6 (

 6 Fig.5(a) and (b) shows a comparison of average communication cost par event (join/leave) according to the number of subscribed DR projects at the same time. We assume that there are 100000 users (on average) subscribing to each DR project. The bandwith overhead of a join is the same as a leave for the scheme of Liu et al. and it is a lot more than that of SKM+ and eSKAMI because of the inefficient multicast key management. Note that although SKM+ has less communication overhead than eSKAMI for join/leave event, the difference is not significant and it is too little to be seen in the Fig.5 (a).Fig.6(a) and (b) shows a comparison of average communication cost par event for the three schemes according to the number of subscribes in DR projects and fixing the number of

Fig. 5 :

 5 Fig. 5: Average communication cost by event according to number of DR projects

Fig. 6 :

 6 Fig. 6: Average communication cost by event according to DR projects members

TABLE I :

 I Notation Table Height of i th LKH tree h i = log d (m i ) Child i (GK j )The i th child of (GK j ) in LKH tree

	Notation	Description
	H(.)	A One-way hash functions
	n	Number of SMs
	m i	Number of the i th DR project members
	d	LKH trees degree
	h i
	Npr	Number of DR projects
	N sub(u i )	Number of DR projects to which subscribes user u i
	Home DR(u i ) First DR project to which subscribes user u i
	set(u i )	Set of DR projects to which subscribes user u i
	DR i	The ith DR project
	GK i	Group key of DR i
	a b	A concatenation between a and b
	Enc(M, k)	Message M encrypted with key k
	HM AC k (c)	Keyed-hash using k as the key

⊕

Mixing function such as bitwise exclusive-or (XOR)

A → B : M A sends a message M to B

  GK 2 for users in φ 1 using a double encryption to ensure that only users susbscribing to DR 2 can obtain the new key (suppose u 5 and u 7 subscribed to DR 2 ) :MDMS → {u 5 , u 7 } : Enc(Enc(GK 2 , k 5.8 ), GK 2 ) (20) (c)update GK 2 for users in ω 3k : MDMS → ω 33 : Enc(Enc(GK 2 , k 15-16 ), GK 2 ) (21) MDMS → ω 33 : Enc(Enc(GK 2 , k 17-18 ), GK 2 ) (22) (d) update GK 2 for users in ω 2k : MDMS → ω 24 : Enc(Enc(GK 2 , GK 4 ), GK 2 )

		(23)
	TABLE II: Rekey Operations and User Events
	Operations	User events
	Join an LKH tree	A user has subscribed to only default DR project. Then, he subscribes to a new DR project.

2 and DR 3 ) leaves DR 2 : (a) update GK 2 for users in φ 2 : MDMS → {u 9 , u 10 , u 11 , u 12 } : Enc(GK 2 , k 9-12 ) (18) MDMS → {u 13 , u 14 } : Enc(GK 2 , k 13-14 ) (19) (b) update

TABLE III :

 III Comparison of Key Management Schemes

			Liu's et al., 2013 [11]	SKM+, 2014 [12]	eSKAMI
	Key graph techniques	No	Yes	Yes
	Hybride Transmission	Yes	Yes	Yes
	Backward and forward secrecy	Yes	Yes	Yes
	Collusion freedom	Yes	Yes	Yes
	Overhead	Commun. storage	High Low	Very Low High	Low Low

TABLE IV :

 IV Storage Cost

	Scheme		MDMS	Storage Overhead	SM i
	Liu's et al., 2013 [11]		n + Npr + 1	N sub(u i ) + 2
	SKM+, 2014 [12]	2	Npr i=1