Romain Millot

Philippe Négrel

Water Rock Interaction [WRI 14]

Keywords: weathering, granite, Pb isotopes, Li isotopes

In order to characterize water/rock interactions of granite, we performed laboratory experiments and Pb-Li isotopes tracing. The aim of the present work is to better constrain the processes of water/rock interactions both in terms of source and extent of weathering, by measuring major and trace elements as well as Pb and Li isotope signatures.

Introduction and objective of the study

Weathering reactions, e.g. breakdown and alteration of rocks and minerals at the Earth's surface, supply solutes to both surface and ground waters. In a recent study [1] focusing on the lead geochemistry and Pb-isotope ratios of groundwaters along a small (53 km [START_REF] Millot | Accurate and high precision measurement of lithium isotopes in two reference materials by MC-ICP-MS Geostandards and[END_REF] ) endoreic granitic catchment in India (Masheshwaram, Andhra Pradesh), we have shown that most of the lead in the groundwaters is of geogenic origin. Combining a weathering model and field observations, we were able to define a two steps weathering process that includes a control on the Pb-isotope ratios by accessory phases and by the main minerals from the granite in a second step of weathering. In order to go further and to better characterize water/rock interactions, we performed laboratory experiments with granite rock samples from this field site.

The aim of the present work is to better constrain the processes of water/rock interactions both in terms of (i) source (dissolution of different primary minerals and (ii) extent of weathering (precipitation of secondary minerals), by measuring Pb and Li isotope signatures. This is because lithium is a fluid-mobile element and, due to the large relative mass difference between its two stable isotopes, it is subject to significant low temperature mass fractionation which provides key information on the nature and extent of weathering processes.

Experimental setup and analytical methods

Laboratory experiments consisted in measuring the evolution through time of major and trace elements, as well as Pb and Li isotopic compositions of a rainwater solution in equilibrium with a granite powder. Experiments were carried out at 25°C with a solution/powder mass ratio of 10. 15 mL of reference solution TMRAIN-95 and 1.5 g of powdered granite were placed in screw-top Teflon® PFA beakers. The beakers were kept in a temperature-controlled oven, which temperature was maintained within 5% of target temperature over the total duration of the experiments. Aliquots of the solution (after filtration at 0.20 µm) in contact with the granite powder were periodically sampled (from weeks up to more than one year) and analyzed for lead and lithium isotopic compositions.

Lithium isotopic compositions were measured using a Neptune Multi-Collector ICP-MS at BRGM's Isotopic Geochemistry Laboratory. 7 Li/ 6 Li ratios were normalized to the L-SVEC standard solution (NIST SRM 8545) following the standard-sample bracketing method (see the method reported by [2]).

Lead isotopic compositions in waters were also measured using with the Neptune Multi-Collector ICP-MS in operation at the BRGM. According to the recent protocol developed by our group [3], the key parameter for the analysis of water by the mean of the MC-ICP-MS is the lead concentration and the cations matrix of the water sample. The high sensitivity of the Multi-Collector ICP-MS allows direct measurements at Pb concentration levels as low as 10 ng/mL and there is no effect of the matrix if the ion charge is lower than 400 mg/L [3]. With this method using multi-collection on Faraday cups, the Tl correction technique is used for mass discrimination calculation. In such conditions, 2σ standard errors of 0.10% and 0.01% are achieved for 206

Results and comments

Major and trace elements

During the experiments, the evolution through time of the major and trace elements concentrations shows that major cations (Na, K, Mg and Ca) are released into solution during water/rock interaction, then these concentrations seem to reach stable values (Figure 1a). By contrast, anions concentrations are low in solution, with the exception of F (Figure 1b). Li and Pb are also released into solution during water/rock interaction, like Sr and U (Figure 1c). In addition, SiO 2 , Al and Fe concentrations display evolution through time suggesting that in the first stage of water/rock interaction, these elements are released into solution, then due to secondary mineral formation incorporating these elements, the concentrations decrease.

Pb-Li isotopes tracing

Lead isotope tracing of these water/rock interactions shows that starting from the Pb isotope composition of the rain water solution (TMRAIN-95) having low 206 Pb/ 204 Pb, 207 Pb/ 204 Pb and 208 Pb/ 204 Pb ratios, the solution having interacted with the powdered granite shows a rapid increase of all isotope ratios through time (Figure 2a,b,c). After several weeks, the Pb isotopes ratios are very constant and do not vary through time radiogenic values are obtained for both 206 Pb/ 204 Pb and 208 Pb/ 204 Pb ratios.

The evolution of Li and its isotopes ( 7 Li) in solution (Figure 2d, e) as a function of time during water/rock interaction shows that Li concentration increases whereas Li isotopic signal decrease down to reach a constant value around ~+2‰. This evolution suggests that first, dissolution processes are predominant and release Li into solution (consequently  7 Li sharply decreases, whereas Li concentrations increase). This step is rather short. Then, during the second step, a steady state is reached between dissolution of granite, on the one hand, and precipitation of alteration minerals, on the other hand.

Fig. 2. Graphs showing the evolution over time of lead isotopes (a, b and c), lithium isotopes (d) and lithium concentrations (e).

Concluding remarks

Our data show that a radiogenic contribution of lead is observed during the experiments, in agreement with the field observations, and that the light lithium isotope ( 6 Li) is preferentially retained during uptake of Li into secondary minerals during weathering. If we compare the values obtained during our experiments with granite rock samples from the field site in India, the different minerals and the weathering model data [1]: we can observe that our experiments are in agreement with a major contribution of K-feldspar and plagioclase dissolution and to a lesser extent by biotite and apatite contribution. Further characterization of the secondary mineral phases after experiments is now needed in order to better constrain the minerals that can control Pb and Li isotopes during these experiments. The competition between dissolution and precipitation processes is likely to be the key factor controlling Pb and Li and their isotopes in these experiments.

Fig. 1 .

 1 Fig. 1. Graphs showing the evolution over time of (a) cations concentrations (Na, K, Mg and Ca in mg/L); (b) anions concentrations (Cl, SO4, HCO3 and F in mg/L); (c) trace elements concentrations (Li, Pb, Sr and U in µg/L); (d) SiO2, Al and Fe concentrations in mg/L.

  Pb/ 204 Pb, 207 Pb/ 204 Pb, 208 Pb/ 204 Pb ratios and 207 Pb/ 206 Pb and 208 Pb/ 206 Pb ratios respectively.


Martin R Albrecht

Carlos Cid
email: carlos.cid@rhul.ac.uk

Jean-Charles Faugère
email: jean-charles.faugere@inria.fr

Robert Fitzpatrick
email: robert.fitzpatrick.2010@live.rhul.ac.uk

Ludovic Perret
email: ludovic.perret@lip6.fr

J.-C Faugère

On the complexity of the Arora-Ge Algorithm against LWE

 recently showed that solving LWE can be reduced to solve a high-degree non-linear system of equations. They used a linearization to solve the systems. We investigate here the possibility of using Gröbner bases to improve Arora & Ge approach.

Introduction

The Learning With Errors (LWE) Problem was introduced by Regev in [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF][START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. It is a generalisation for large primes of the well-known LPN (Learning Parity with Noise) problem. Since its introduction, LWE has become a source of many innovative cryptosystems, such as the oblivious transfer protocol by Peikert et al. [START_REF] Peikert | A framework for efficient and composable oblivious transfer[END_REF], a cryptosystem by Akavia et al. [START_REF] Akavia | Simultaneous hardcore bits and cryptography against memory attacks[END_REF] that is secure even if almost the entire secret key is leaked, homomorphic encryption [START_REF] Gentry | A fully homomorphic encryption scheme[END_REF][START_REF] Brakerski | Efficient fully homomorphic encryption from (standard) LWE[END_REF][START_REF] Albrecht | Polly Cracker, revisited[END_REF], etc. . . Reasons of LWE's success in cryptography include its simplicity as well as convincing theoretical arguments regarding its hardness, i.e. a reduction from (worst-case) assumed hard lattice problems to (average-case) LWE.

The purpose of this paper is to investigate whether algebraic techniques (e.g. [START_REF] Faugère | Algebraic cryptanalysis of hidden field equation (hfe) cryptosystems using gröbner bases[END_REF][START_REF] Faugère | Polynomial equivalence problems: Algorithmic and theoretical aspects[END_REF][START_REF] Faugère | Cryptanalysis of minrank[END_REF][START_REF] Faugère | Advances in Cryptology -EURO-CRYPT 2010[END_REF][START_REF] Albrecht | Breaking an identity-based encryption scheme based on dhies[END_REF][START_REF] Albrecht | Cold boot key recovery by solving polynomial systems with noise[END_REF][START_REF] Faugère | Improving the complexity of index calculus algorithms in elliptic curves over binary fields[END_REF]) can be used in the context of LWE. This is motivated by a recent result Arora & Ge [START_REF] Arora | New algorithms for learning in presence of errors[END_REF] who showed that solving LWE can be reduced to solve a high-degree non-linear system of equations.

Learning With Errors

We reproduce below the definition of the LWE problem from [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF][START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF].

Definition 1 (LWE).

Let n ≥ 1 be the number of variables, q be an odd prime integer, χ be a probability distribution on Z q and s be a secret vector in Z n q . We denote by L (n) s,χ the probability distribution on Z n q × Z q obtained by choosing a ∈ Z n q at random, choosing e ∈ Z q according to χ, and returning (a, c) = (a, a, s + e) ∈ Z n q × Z q . LWE is the problem of finding s ∈ Z n q given pairs Z n q × Z q sampled according to L

(n) s,χ .
The modulus q is typically taken to be polynomial in n, and χ is the discrete Gaussian distribution on Z q with mean 0 and standard deviation σ = α • q, for some α. To discretize the Gaussian distribution N0, σ 2 modulo q, we sample according to N0, σ 2 and round to the nearest integer mod q. In what follows, χ α,q will then denote this discretized distribution.

A typical setting for the standard deviation (std) is σ = n ε , with ε, 0 ≤ ε ≤ 1. For example, [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] suggests q ≈ n 2 and α = 1/( √ n•log 2 n). Indeed, as soon as ε ≥ 1/2 (worst-case) GAPSVP-Õ (n/α) reduces to (average-case) LWE1 . Thus, any algorithm solving LWE (when ε ≥ 1/2) can be used for GAPSVP -Õ (n/α). We emphasize that it is widely believed that only exponential algorithm exists for solving GAPSVP -Õ (n/α).

Recently, Arora & Ge [START_REF] Arora | New algorithms for learning in presence of errors[END_REF] introduced a variant of LWE with structured errors. In this setting, you have given an oracle such that given LWE samples returns polynomials which vanish on the errors.

WMC & SCC 2012

They showed that the (discretized) Gaussian intrinsically induced a structure on the errors. This feature can be used to reduce LWE to the problem of solving a non-linear system of multivariate of equations.

The total complexity (time and space) of their approach is 2 Õ (n 2ε ) . It is then subexponential when ε < 1/2, but remains exponential when ε ≥ 1/2. It is interesting that Arora&Ge reach with a completely different approach the ε = 1/2 hardness limit advised by Regev [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF][START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF].

Note that an improvement on Arora&Ge could allow to challenge the 'subexponetiality' of GAPSVP -Õ (n/α). Remark that [START_REF] Arora | New algorithms for learning in presence of errors[END_REF] uses linearization to solve the non-linear system. It is then natural to investigate whether more advanced tools, such as Gröbner bases [START_REF] Buchberger | Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal[END_REF][START_REF] Buchberger | Computer algebra symbolic and algebraic computation[END_REF][START_REF] Cox | Ideals, Varieties and Algorithms[END_REF], could improve the algorithm of Arora&Ge.

In this note, we will show that Gröbner bases can bring a practical improvement on the complexity of [START_REF] Arora | New algorithms for learning in presence of errors[END_REF]. We also briefly discuss whether Gröbner bases can (or can not) allow to change the complexity class of Arora&Ge. Before that, we need to recall some basic complexity results about Gröbner bases.

Gröbner bases -Complexity Results

Gröbner basis is probably the main tool allowing to solve non-linear system of finite fields. From an algorithmic point of view, Lazard [START_REF] Lazard | Gröbner-bases, Gaussian elimination and resolution of systems of algebraic equations[END_REF] showed that computing the Gröbner basis for a system of polynomials is equivalent to perform a Gaussian elimination on the Macaulay matrices [START_REF] Macaulay | On some formula in elimination[END_REF] M acaulay d,m for d, 1 ≤ d ≤ D for some integer D. Moreover, the most efficient known algorithms such as F 5 [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF] reduce Gröbner basis computations to a series of Gaussian eliminations on matrices of increasing sizes.

Definition 2 (Macaulay Matrix

[23]). Let f 1 , . . . , f m ∈ Z q [x 1 , . . . , x n ]. The Macaulay matrix M acaulay d,m ( f 1 , . . . , f m )
of degree d is defined as follows: list "horizontally" all the degree d monomials from smallest to largest sorted by some fixed admissible monomial ordering. The smallest monomial comes last. Multiply each f i by all monomials t i, j of degree dd i where d i = deg( f i ). Finally, construct the coefficient matrix for the resulting system:

M acaulay d,m ( f 1 , . . . , f m ) := monomials of degree ≤ d sorted for < (t 1,1 , f 1 ) (t 1,2 , f 1 )
. . . Consequently, the complexity of computing a Gröbner basis is bounded by the complexity of performing Gaussian elimination on the Macaulay matrix in some degree D. Roughly, the complexity of computing a Gröbner basis with an algorithm based on the degree of regularity (such as -but not limited too -Buchberger's algorithm, F 4 , F 5 [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF][START_REF] Buchberger | Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal[END_REF][START_REF] Buchberger | Computer algebra symbolic and algebraic computation[END_REF][START_REF] Faugère | A new efficient algorithm for computing Gröbner bases (F4)[END_REF]) is:

(t m,1 , f m ) (t m,2 , f m ) . . .                     Theorem 3 ([22]). Let f = ( f 1 , . . . , f m ) ∈ (Z q [x 1 , . . . , x n ]) m
O n + D D ω , (1)
where 2 ≤ ω < 3 is the linear algebra constant, and D is the degree of semi-regularity of the system. In general, computing the degree of regularity of a system is a difficult problem. However, it is known for a specific family of polynomial systems [START_REF] Bardet | Étude des systèmes algébriques surdéterminés[END_REF][START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF][START_REF] Bardet | Complexity study of Gröbner basis computation[END_REF][START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF]. Definition 4 (Semi-regular Sequence [START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF]). Let m > n, and f 1 , . . . , f m ∈ Z q [x 1 , . . . , x n ] be homogeneous polynomials of degrees d 1 , . . . , d m respectively and I the ideal generated by these polynomials. The system is said to be a semi-regular sequence if the Hilbert series [START_REF] Cox | Ideals, Varieties and Algorithms[END_REF] of I w.r.t. the grevlex order is:

H I (z) = ∏ m i=1 (1 -z d i ) (1 -z) n + , (2)
where [S] + denotes the series obtained by truncating S before the index of its first non-positive coefficient. Thus, the degree of regularity D involved in Theorem 3 for a semi-regular sequence is:

1 + deg(H I ).

Improving Arora-Ge Approach

We briefly detail below the linearization approach of Arora-Ge. We then discuss whether Gröbner bases can be used in this context.

Basic Arora-Ge Algorithm -A Linerization Approach

The idea of [START_REF] Arora | New algorithms for learning in presence of errors[END_REF] is to generate a non-linear noise-free system of equations from LWE samples. This is due to the following well-known feature of a Gaussian noise:

Lemma 5. Let C > 0 be a constant. It holds that:

Pr[e $ ← χ α,q : |e| > C • σ] ≤ e O (-C 2 ) .
As a consequence, elements sampled from a Gaussian distribution only takes values on a (small) subset [-C • σ, . . . ,C • σ] of Z q with high probability. From now on, we set t = C • σ. We can reinterpret Lemma 5 algebraically by considering the polynomial:

P(X) = X t ∏ i=1 (X + i)(X -i).
Clearly P is of degree 2t + 1 ∈ O (σ). Thus, if e $ ← χ α,q , then P(e) = 0 with probability at least

1 -e O (-C 2 ) . For i ≥ 1, let (a i , a i , s + e i ) = (a i , b i ) ∈ Z n q × Z q . If e i $ ← χ α,q , then P a i , a i , s -b i = 0, (3)
with probability at least 1e O (-C 2 ) . As a consequence, each sample (a i , a i , s + e i ) = (a i , b i ) ∈ Z n q × Z q allows to generate a non-linear equation of degree 2t + 1 in the n components of the secret s.

The idea of Arora & Ge is then to generate sufficiently many equations as in (3) to perform a linearization. However, one has to choose the constant -denoted by C AG -occurring in Lemma 5 sufficiently big so that all errors generated lies with high probability in [-C AG • σ, . . . ,C AG • σ] ⊆ Z q , i.e. the secret s is indeed a common solution of the M AG equations constructed as in [START_REF] Albrecht | Breaking an identity-based encryption scheme based on dhies[END_REF]. To this end, we set:

p f = M AG e O (C 2 AG )
. This is the probably that the secret s ∈ Z n q is not solution of the system S AG generated from M AG equations as in (3), i.e. the probability of failure of Arora-Ge approach. Let also D AG = 2C AG • σ + 1 be the degree of the equations occuring in S AG . According to [START_REF] Arora | New algorithms for learning in presence of errors[END_REF], taking C AG ∈ Õ (σ) allows to make the probability of failure negligible.

To summarize, Arora-Ge approach reduces to linearize at system of M AG equations of degree

D AG = 2C AG • σ + 1 ∈ Õ (σ 2 )
. Moreover, correctness of this approach can be proven: Theorem 6. [START_REF] Arora | New algorithms for learning in presence of errors[END_REF] Let D AG < q. The system obtained by linearizing

M AG = O q • log(q) n+D AG D AG σ = n O (D AG ) = 2 Õ (D AG )
equations as in (3) has at most one solution with high probability.

The time complexity of the basic Arora-Ge approach is then

C plx AG = n O (D AG ) = 2 Õ (σ 2 ) = 2 Õ (n 2ε ) .
Note also this algorithm also requires 2 Õ (n 2ε ) LWE samples for performing the linearization.

From Linerization to Gröbner Bases

The question we try to address here is whether the complexity C plx AG can be improved by using Gröbner bases instead of linearization. The rational is that you can decrease the constant C AG (and so the degree of the equations) to a value smaller than Õ (n2•ε ) by considering less equations (whilst keeping the probability p f of failure similar in bother approaches). However, the cost of the solving step increase since one has to compute a Gröbner basis. The question is then to find -if any -a tradeoff allowing to improve upon linearization.

To do so, we will consider a number of equations of the form θ √ M AG , with θ > 1 (θ = 1 is the basic Arora-Ge). We want to keep the probability of failure similar for the linearization and Gröbner basis approaches. As a consequence, we need to take a constant C θ such that:

p f = θ √ M AG e O (C 2 θ )
.

An easy calculation leads to C θ ∈ Õ C AG √ θ . Thus, decreasing the number of equations from M AG to θ √ M AG allows to divide the constant C AG by a factor √ θ. The degree of the equations we are doing to consider is then equal to 2σ

•C θ + 1 ∈ Õ σ 2 √
θ . The question is now to find a good candidate for θ. Typically, if θ is too big then you will greatly decrease the number of equations, but the cost of the solving step will become prohibitive and the total complexity will be worth than for a linearization.

We have considered a θ of the form: θ = n 2•β , for some β ≥ 0 (note that we get the basic Arora-Ge by taking β = 0). In this new setting, we get a constant C β = n ε-β . We have then to solve a system having

M β = n 2•β √ M AG ∈ 2 Õ (n 2(ε-β) ) equations of degree D β = Õ (n 2•ε-β )
. We denote such system by S GB (β).

The question is to determine the complexity C plx GB-AG (β) of solving S AG (β). This reduces to study its degree of regularity D β reg . Given current algorithms, the specific structure of the system does not allow to solve it faster than random systems. As a consequence, we assume that D β reg is not bigger than the degree of regularity of a semi-regular system of the same size 2 , namely:

D β reg ≤ 1 + deg(H β ),
where:

H β (z) = (1 -z D β ) M β (1 -z) n + ,
where [.] + denotes the series obtained by truncating before the index of its first non-positive coefficient. We present below some experiments performed for β = 1/5. We have computed explicitly the complexities for both approaches: linearization and Gröbner bases. As suggested in [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF], we considered q ≈ n 2 and α = 1/( √ n • log 2 n) We plotted below the speed-up we obtained, i.e. C plx AG (y-axis) for n, 0 ≤ n ≤ 5000. We can see that Gröbner bases allow to improve the complexity of the basic Arora-Ge when n ≤ 5000 (x-axis). Note that further experiments are required to confirm this behavior when n tends to infinity 3However, the form of the speed-up also tends to suggest that we only improve from a constant C plx AG . change the asymptotical behavior of the Arora&Ge approach. we mention that we are currently considering several forms for the β. In particular, β which is not a constant but a function of n. As a conclusion, we also emphasize that Arora-Ge needs exponential (or subexponetial) number of LWE samples. For most cryptosystems based on LWE, you have access to much less samples, typically polynomially-many. In this situation, you have then not enough samples to perform the linearization and the only option to mount the Arora&Ge approach is to solve the system by using Gröbner bases.

  and < be a monomial ordering. There exists a positive integer D for which Gaussian elimination on all M acaulay d,m = ( f 1 , . . . , f m ) matrices for d, 1 ≤ d ≤ D computes a Gröbner basis of f 1 , . . . , f m w.r.t. to <. The degree D will be called degree of regularity of f 1 , . . . , f m .

log 2 C

 2 plx GB-AG (β)

The reduction is quantum if q is polynomial but can be made[START_REF] Peikert | Public-key cryptosystems from the worst-case shortest vector problem: extended abstract[END_REF] classical if q is super polynomial.

We have performed few experiments for small parameters. The experiments seem to confirm this hypothesis.

Note that the degree of the equations involved being huge, it becomes rather costly to just expand the Hilbert series for the systems considered.


Walid Bechkit

Yacine Challal

Abdelmadjid Bouabdallah

A New Class of Hash-Chain Based Key Pre-distribution Schemes for WSN

Keywords: wireless sensor networks, security, key management, resilience

In the last decade, we witness a proliferation of potential application domains of wireless sensor networks (WSN). Therefore, a host of research works have been conducted by both academic and industrial communities. Nevertheless, given the sensitivity of the potential applications that are generally tightly related to the physical world and may be human beings, a large scale deployment of WSN depends on the dependability provided by these emerging networks. Particularly, security emerges as a challenging issue in WSN because of the resource limitations. Key management is one of the required building blocks of many security services, such as confidentiality, authentication, etc. Unfortunately, public key based solutions, which provide efficient key management services in conventional networks, are unsuitable for WSN because of resource limitations. Symmetric key establishment is then one of the most suitable paradigms for securing wireless sensor networks. In this paper, we tackle the resiliency of symmetric key pre-distribution schemes against node capture. We propose a hash-based mechanism which enhances the resiliency of key pre-distribution for WSN. Applied to existing key predistribution schemes, our solution gives birth to enhanced schemes which are more resilient against node capture attacks. We analyze and compare our solution against the existing schemes, with respect to some important criteria such as: the network resiliency against node capture, secure connectivity coverage, storage requirement, communication overhead and computation complexity. We show through analytical analysis that our solution enhances the network resiliency without introducing any new storage or communication overheads. Moreover, we show that our solution introduces insignificant computational overhead.

Introduction

A Wireless Sensor Network (WSN) is a wireless network which is composed of a set of tiny autonomous sensor nodes with sensing, computation, and wireless communication capabilities [START_REF] Akyildiz | Wireless sensor networks: a survey[END_REF]. The purpose of such networks is to collect information issued from a controlled environment or a target object and then send it to a base station usually called the sink. Because of size factor and cost considerations, wireless sensor networks suffer from resource constraints including energy, memory, computation power and communication bandwidth and range. Nowadays, wireless sensor networks are increasingly used in numerous fields such as military, medical, industrial and environmental sectors; they are more and more involved in several sensitive applications which require sophisticated security services. Due to the resource limitation, existing security solutions for conventional networks could not be used in wireless sensor networks. So, the security issues became then one of the main challenges for the resource restricted environment of WSN which requires new specific solutions.

Email addresses: wbechkit@hds.utc.fr (Walid BECHKIT), ychallal@hds.utc.fr (Yacine CHALLAL), bouabdal@hds.utc.fr (Abdelmadjid BOUABDALLAH) Key management is a corner stone service for many security services such as confidentiality and authentication which are required to secure communications in wireless sensor networks. The establishment of secure links between nodes is then one of the most challenging problems in WSN. The public key based solutions, which provide efficient key management services in conventional networks, are unsuitable for wireless sensor networks because of the energy, computation and storage limitations. Some public key schemes have been implemented on real sensors [START_REF] Watro | Tinypk: securing sensor networks with public key technology[END_REF][3], however most researchers believe that these techniques are still too heavyweight over actual sensors' technology because they induce an important communication and computation overhead [START_REF] Zhang | Wireless sensor network key management survey and taxonomy[END_REF]. Symmetric key establishment is then one of the most suitable paradigms for securing exchanges in wireless sensor networks. Because of the lack of infrastructure in WSN, we have usually no trusted third party which can attribute pairwise secret keys to neighboring nodes, that is why key pre-distribution is the most suitable paradigm for wireless sensor networks.

Many symmetric key pre-distribution schemes for wireless sensor networks have been proposed in literature [START_REF] Eschenauer | A key-management scheme for distributed sensor networks[END_REF][6] [START_REF] Du | A key management scheme for wireless sensor networks using deployment knowledge[END_REF][8] [START_REF] Liu | Establishing pairwise keys in distributed sensor networks[END_REF][10] [START_REF] Zhu | Leap: efficient security mechanisms for large-scale distributed sensor networks[END_REF] [START_REF] Yener | Combinatorial design of key distribution mechanisms for wireless sensor networks[END_REF] [START_REF] Maala | Hero: Hierarchcal key management protocol for heterogeneous wsn[END_REF]. We classify these schemes into two categories: deterministic schemes which ensure a to-tal secure connectivity coverage and probabilistic schemes where secure connectivity is not guaranteed and conditioned by the existence of shared keys. In order to evaluate the performances of key pre-distribution schemes, we consider five main metrics which are: network resiliency against node capture, secure connectivity coverage, communication overhead, computation complexity and storage overhead. In this paper, we consider in particular the resiliency of symmetric key pre-distribution schemes. Existing research works which addressed the network resiliency either introduce an important storage and communication overhead or degrade the secure connectivity coverage. In contrast to these solutions, our goal is to enhance the resiliency of WSN key management schemes without introducing any new storage or communication overheads while maintaining a high secure connectivity coverage.

In this work, we propose a hash-based mechanism which can be applied to existing pool based key pre-distribution schemes to enhance the network resiliency. To achieve this goal, we introduce a new method based on one way hash chain which conceals keys in such a way that the disclosure of some keys reveals only derived versions, which cannot be used to compromise other links in the network using backward keys. We call our solution: Hash-Chain class of key pre-distribution schemes and denote it by HC. Our class, applied to existing key pre-distribution schemes, gives birth to new schemes which are more resilient against node capture attacks. We carried out analytical analysis to compare the efficiency of our approach against basic schemes with respect to important performance criteria: the network resiliency against node capture, the secure connectivity coverage, the communication overhead, the computation complexity and the storage overhead. The obtained results show that our solution enhances the network resiliency and reduces the fraction of compromised links up to 40% compared to existing schemes while it guarantees the same secure connectivity coverage, storage and communication performance. Moreover, we show through analytical analysis and simulations that the induced computational overhead is insignificant and that the energy consumed by hash computations in our solution is negligible.

The contributions of our work are many folds and can be summarized in the following points:

• We review the state of the art of key management in wireless sensor network. Then, we propose a classification of symmetric key management schemes for WSN into two categories: probabilistic schemes and deterministic ones. We further refine the classification into sub-categories with respect to the underlying concepts and techniques used in key exchange and agreement.

• We introduce a mechanism to enhance the network resiliency of key pre-distribution schemes for WSN. The proposed solution is based on lightweight hash chains and improves the resiliency of existing poolbased key pre-distribution schemes.

• We analyze and compare our solution against the existing schemes, with respect to important criteria which are: the network resiliency against node capture, secure connectivity coverage, storage requirement, communication overhead and computation complexity. We show through analytical analysis that our solution enhances the network resiliency without introducing any new storage or communication overheads. Moreover, we show that our solution does not introduce significant computational overhead.

The remainder of this paper is organized as follows: section 2 presents related works on key management for wireless sensor networks. We define in section 3 the metrics used to evaluate our solution and to compare it to existing schemes. Section 4 gives a general idea of our class of pool based key pre-distribution schemes. In section 5, we present the resilient HC(q-composite) scheme issued from the application of our mechanism to the well known probabilistic q-composite scheme , we compare the performances of the two schemes and we discuss analytical results. In section 6, we apply our class to a deterministic scheme based on the combinatorial design which gives birth to a more resilient deterministic scheme; we also analyze and compare their performances. In section 7, we introduce a new smart attack against our mechanism and propose an enhanced version as countermeasures against this attack. Finally, section 8 ends up this paper with some conclusions.

Related works: key management schemes for WSN

Key management problem in wireless sensor networks have been extensively studied in the literature and several solutions have been proposed. Many classifications of symmetric key management schemes can be found in [START_REF] Kifayat | Security in wireless sensor networks[END_REF][15] [START_REF] Ouadjaout | Encyclopedia on Ad Hoc and Ubiquitous Computing, chapter Information Security in Wireless Sensor Networks[END_REF]. In this work, we mainly classify symmetric schemes into two categories: probabilistic schemes and deterministic ones. In deterministic schemes, each two neighboring nodes are able to establish a direct secure link which ensures a total secure connectivity coverage. In probabilistic schemes, the secure connectivity is not guaranteed because it is conditioned by the existence of shared keys between neighboring nodes.

Probabilistic schemes

In probabilistic key management schemes, each two neighboring nodes can establish a secure link with some probability. If two neighboring nodes cannot establish a secure link, they establish a secure path composed of successive secure links.

Eschenauer and Gligor proposed in [START_REF] Eschenauer | A key-management scheme for distributed sensor networks[END_REF] the basic Random Key Pre-distribution scheme denoted by RKP. In this scheme, each node is pre-loaded with a key ring of m keys randomly selected from a large pool S of keys. After the deployment step, each node i exchanges with each of its neighbor j the list of key identifiers that it maintains. This allows node j to identify the keys that it shares with node i. If two neighbors share at least one key, they establish a secure link and compute their session secret key which is one of the common keys. Otherwise, nodes i and j do not have common keys. So, they should determine secure paths which are composed by successive secure links. The values of the key ring size m and the key pool size |S| are chosen in such a way that the intersection of two key rings is not empty with a high probability p. This basic approach is CPU and energy efficient but it requires a large memory space to store the key ring. Moreover, if the network nodes are progressively corrupted, the attacker may discover a large part or the whole global key pool. Hence, a great number of links will be compromised. This is due to the fact that a given key may be used to secure different links if it is common between key rings of different pairs of nodes.

Chan et al. proposed in [START_REF] Chan | Random key predistribution schemes for sensor networks[END_REF] a protocol called q-composite scheme that enhances the resilience of RKP. In this solution, two neighboring nodes can establish a secure link only if they share at least q keys. The pairwise session key is calculated as the hash of all shared keys concatenated to each other: K i,j = Hash(K s1 K s2 ... K s q ′ ) where K s1 , K s2 , ...K s q ′ are the q ′ shared keys between the two nodes i and j (q ′ ≥ q). This approach enhances the resilience against node capture attacks because the attacker needs more overlap keys to break a secure link. However, this approach degrades the network secure connectivity coverage because neighboring nodes must have at least q common keys to establish a secure link.

Chan et al. proposed in [START_REF] Chan | Random key predistribution schemes for sensor networks[END_REF] another pairwise key predistribution scheme in which they aim to ensure a perfect resiliency and a given secure coverage probability p. Authors propose to use a distinct key to secure each link between each pair of nodes. They assign to each two neighboring nodes i and j a distinct key k i,j . Prior to deployment, each node is pre-loaded with p * N keys, where N is the network size (number of nodes in the network) and p is the desired secure coverage probability. Hence, the probability that the key k i,j belongs to the key set of the node i is p. Since we use distinct keys to secure each pair-wise link, the resiliency against node capture is perfect and any node that is captured reveals no information about links that are not directly connected to it. It is obvious that the main drawback of this scheme is the non scalability because the number of the stored keys depends linearly on the network size. In addition, this solution does not allow the node post-deployment because existing nodes do not have the new nodes' keys. Du et al. proposed in [START_REF] Du | A key management scheme for wireless sensor networks using deployment knowledge[END_REF] to enhance the secure connectivity and the resiliency of the basic random key predistribution schemes. Their solution requires deployment knowledge and uses several key pools instead of one. Nodes are organized in regional groups to which is assigned different key pools and each node selects its m keys from the corresponding key pool. The key pools are constructed in such a way that neighboring key pools share more keys while key pools far away from each other share fewer keys or no keys at all. This approach allows to enhance the secure connectivity coverage because the key pools become smaller. Moreover, the resiliency of Du et al. solution is improved since if some nodes of a given region are captured, the attacker could discover only a part of the corresponding group key pool. However, the application of this scheme is restrictive since the deployment knowledge of the wireless sensor network is not always possible.

In [START_REF] Castelluccia | A Robust Key Predistribution Protocol for Multi-Phase Wireless Sensor Networks[END_REF], Castelluccia and Spognardi adapted the basic scheme described above to the multi-stage wireless sensor networks where new nodes are periodically deployed to ensure the network connectivity. With a one-stage deployment, if the network is continuously attacked, the attacker could discover an important part of the global key pool and new established links will be immediately compromised. Authors in [START_REF] Castelluccia | A Robust Key Predistribution Protocol for Multi-Phase Wireless Sensor Networks[END_REF] proposed the use of keys with limited lifetimes and which are updated periodically. The proposed solution divides the lifetime of a node into k generations. Initially, each node has two key rings: a forward key ring (FKR) and a backward one (BKR). The forward key rings are updated at each generation using a secure hash function while the backward ones are updated using a hash-based Lamport chain, where they start by generating the keys of the last expected generation. If a node is deployed at generation i and will last at most until generation j, it will be configured with the FKR of generation i and the BKP of the generation j. The two key subsets are updated at each generation thanks to the two hash functions. Authors in [START_REF] Castelluccia | A Robust Key Predistribution Protocol for Multi-Phase Wireless Sensor Networks[END_REF] showed that by using limited lifetime keys, the network self-heals and recovers its initial state when attacks stop. In the other hand, the ratio of compromised links remains constant when the network is constantly attacked in contrast to the basic schemes.

In [START_REF] Liu | Establishing pairwise keys in distributed sensor networks[END_REF], Liu et Ning proposed a new pool based polynomial pre-distribution scheme for WSN based on previous work of Blundo et al. [17]. This approach can be considered as an extension of the basic RKP scheme where nodes are pre-loaded with polynomials instead of keys. Basic polynomial key management scheme proposed in [START_REF] Blundo | Perfectly-secure key distribution for dynamic conferences[END_REF] is based on symmetric bivariate λ-degree polynomials P(x,y) generated over a finite field F q where q is prime. The main property of symmetric bivariate polynomial is that P (x, y) = P (y, x). In this scheme, each node i is preloaded with the polynomial P i (y) = P (i, y). In order to establish a secure link between two neighbors i and j, each node evaluates its polynomial at the identifier of the other node. Hence the secret key between two nodes i and j is K ij = P i (j) = P j (i). The node identifiers are supposed to be unique. This approach was proved to be secure and λ-collusion resistant. In [START_REF] Liu | Establishing pairwise keys in distributed sensor networks[END_REF], Liu and Ning extended this approach to wireless sensor networks when they proposed a pool based polynomial pre-distribution scheme to establish secure links. A global pool of symmetric bivariate polynomials is generated off-line and each node is pre-loaded prior to deployment with a subset of polynomials. If two neighboring nodes share a common polynomial, they establish a direct secure link as described above; else, they try to find a secure path as proposed in the RKP scheme. This approach allows to compute distinct secret session, so the resilience against node capture is enhanced. However, this solution requires more memory to store the symmetric bivariate polynomials and induces more computational overhead.

In [START_REF] Blom | An optimal class of symmetric key generation systems[END_REF], Blom proposed a symmetric key generation system in which each node i stores a column i and a row i of size (λ + 1) of two matrices G and (D * G) T respectively where : D (λ+1)×(λ+1) is a symmetric matrix, G (λ+1)×n is a public matrix and (D * G) T is a secret matrix. The matrix of pairwise keys of a group of n nodes is then K = (D * G) T G. In other terms, each pair of nodes i and j compute their session key as K ij = row i * column j = row j * column i . This solution is proved to be λ-secure, which means that keys are secure if no more than λ nodes are compromised. The Blom's scheme cannot be applied to all the network nodes in a wireless sensor network because each node needs memory to store huge vectors. Yu and Guan [START_REF] Yu | A robust group-based key management scheme for wireless sensor networks[END_REF] adapted the Blom's scheme to group-based wireless sensor networks where they assume deployment knowledge. Nodes are deployed into a grid and each group is assigned a distinct secret matrix. Using deployment knowledge, the potential number of neighboring nodes decreases which requires less memory. We believe that this scheme is only adapted for some restrictive applications of wireless sensor networks since deployment knowledge is not always possible.

Deterministic schemes

Deterministic schemes ensure that each node is able to establish a pair-wise key with all its neighbors. Many solutions were proposed to guarantee determinism.

LEAP [START_REF] Zhu | Leap: efficient security mechanisms for large-scale distributed sensor networks[END_REF] make use of a common transitory key which is preloaded into all nodes prior to deployment of the WSN. The transitory key is used to generate pairwise session keys and is cleared from the memory of nodes by the end of a short time interval after their deployment. LEAP is based on the assumption that a sensor node, after its deployment, is secure during a time T min and cannot be compromised during this period of time. LEAP is vulnerable to node compromise. For instance, if the transitory initial key is discovered, the entire network could be compromised.

In [START_REF] Yener | Combinatorial design of key distribution mechanisms for wireless sensor networks[END_REF], C ¸amtepe and Yener proposed a deterministic pool based key pre-distribution scheme. Instead to select randomly a subset of keys from the global key pool, they propose a new construction methodology based on combinatorial design theory. The main purpose is that each two subsets of keys share exactly one common key which ensures a total secure connectivity coverage. To achieve this goal, authors make use of particular combinatorial design which is the Symmetric Balanced Incomplete Block Design theory. This scheme is presented with more details in section 6.

In [START_REF] Ruj | Key predistribution using combinatorial designs for grid-group deployment scheme in wireless sensor networks[END_REF], authors propose to use the C ¸amtepe scheme for key management in grid group WSN. Authors divide the deployment area into square regions. In each region, they propose to use the symmetric Balanced Incomplete Block Design based key pre-distribution in order to ensure the intra-region secure communications. Inter-region communications are guaranteed thanks to special nodes having plentiful resources and called agents. Furthermore, authors propose to enhance the C ¸amtepe scheme in order to avoid key identifier exchanges. For this purpose, they index all nodes and keys and propose a mapping between node indexes and key indexes. Perrig et al. proposed in [START_REF] Perrig | Spins: Security protocols for sensor networks[END_REF][21] a security suite for WSN having two blocks: i) SN EP which provides data confidentiality, two-party data authentication, and data freshness and ii) µT ESLA which provides authenticated broadcast. SPINS propose to use the base station (Sink) as a trusted third party (TTP) in order to establish secure links between nodes. If a node i wants to establish a session secret key with node j, it sends a request message to node j. Upon receiving this message, the node j sends a message to the sink (TTP) which verifies the authentication, generates the secret session key and sends it to the nodes i and j. The use of the sink as a third trust party leads to an important communication overhead and degrades the network performances.

We focus in this paper on probabilistic and deterministic pool based key management schemes as illustrated in figure 1. In what follows, we propose a mechanism to enhance the resilience of these schemes by concealing keys through the use of an efficient hash chaining mechanism. Our approach can be applied to any pool based key predistribution scheme including [START_REF] Eschenauer | A key-management scheme for distributed sensor networks[END_REF], [START_REF] Chan | Random key predistribution schemes for sensor networks[END_REF], [START_REF] Du | A key management scheme for wireless sensor networks using deployment knowledge[END_REF], [START_REF] Castelluccia | A Robust Key Predistribution Protocol for Multi-Phase Wireless Sensor Networks[END_REF], [START_REF] Yener | Combinatorial design of key distribution mechanisms for wireless sensor networks[END_REF] and all schemes derived from them. This allows to define a new resilient class of pool based key pre-distribution schemes. In this paper, we apply our class to two schemes: the well known probabilistic q-composite scheme proposed by Chan et al. [START_REF] Chan | Random key predistribution schemes for sensor networks[END_REF] and the deterministic scheme based on Symmetric Balanced Incomplete Block Design theory proposed by C ¸amtepe and Yener [START_REF] Yener | Combinatorial design of key distribution mechanisms for wireless sensor networks[END_REF]. We evaluate our hash chain class and compare it against the basic schemes with respect to important performance metrics that we define in the next section.

Evaluation Metrics

In this work, we consider five metrics to evaluate performances of wireless sensor network key management schemes:

Network resiliency against node capture : Due to the resource limitations in WSN, sensor nodes are usually not tamper resistant. If an adversary compromises a node, he can read all secret information from its memory. Such an attack can compromise not only adjacent links of compromised links but also external links that are independent of the compromised nodes. We define the resilience against node capture R x as the fraction of uncompromised external links when x sensor nodes are compromised. We note that we consider in a first time the oblivious attacks where nodes are randomly captured. We discuss later in section 7, possible smart attacks as well as countermeasures.

Secure connectivity coverage : We define the secure connectivity coverage as the fraction of secured direct links among possible links in the network which is the probability that a given pair of neighboring nodes are able to establish a secure link. Note that we focus in our metric on the direct (one hop) secure link establishment; some solutions propose to establish a multi-hop secure path when the direct secure link establishment fails which we do not consider in this metric.

Computation complexity : Some key management schemes like [START_REF] Chan | Random key predistribution schemes for sensor networks[END_REF], [START_REF] Liu | Establishing pairwise keys in distributed sensor networks[END_REF], [START_REF] Yu | A robust group-based key management scheme for wireless sensor networks[END_REF] and the approach that we propose in this work require to perform additional computational operations such as hash functions or modulo multiplications. The additional processing may consume more energy and may induce a computational delay. We calculate in this metric the average number of additional operations required to establish secure links.

Communication overhead : The communication overhead measures the size of data exchanged between a pair of nodes in order to establish direct secure links. This metric has a significant influence on the energy consumption because the most of the consumed energy is due to communication.

Storage overhead : Because of their small size, sensor nodes are very constrained in term of memory resource. In what relates to key management schemes, we focus on the memory required to store the keys.

The proposed classification of key pre-distribution schemes into deterministic schemes and probabilistic ones is based on the secure connectivity coverage metric. Deterministic schemes are those which ensure a total secure connectivity coverage (the probability of establishing direct secure links is one). However, the probabilistic schemes are those which have not a total secure connectivity coverage.

Our Solution: HC(x) A resilient class of hashchain based key pre-distribution schemes

As introduced before, we consider in this work the resiliency of symmetric key pre-distribution schemes against node capture. We propose a resilient class of key predistribution protocols that we denote by HC(x) for Hash-Chain(x), where x is an existing pool based key predistribution protocol. This class of protocols enhances the resilience of existing schemes through a lightweight hash chaining technique that conceals the same keys pre-loaded in different sensor nodes. A preliminary work and few discussions on the network resiliency were presented in [START_REF] Bechkit | Enhancing resilience of probabilistic key pre-distribution schemes for wsns through hash chaining[END_REF]. To conceal keys, we apply a one way hash function to the pre-distributed keys before deployment: a hash function h is applied to each node keys a number of times depending on the node identifier. As known, the main characteristic of hash functions is that knowing a value of the chain it is computationally infeasible to determine the backward values. So, with our approach, when an attacker corrupts one or more keys it can only discover a derived version (forward values).

Let us consider two neighboring nodes i and j. Node i applies i times the hash function h to each key of its key ring. Node j applies j times the hash function h to each key of its key ring. When nodes i and j discover a common key identifier id, the common key between i and j is then h max(i,j) (K id )). Node min(i, j) can calculate the common key by applying the hash function h, |i -j| times to the key having the identifier id. Figure 2 illustrates these steps applied to two nodes whose identifiers are 3, and 7 respectively. We notice that key having the identifier 5 is common to both nodes 3 and 7. The common key is then h 7 (K 5 ) and node 3 can then calculate this common key by applying again the hash function h, |3 -7| = 4 times to its key h 3 (K 5 ).

The application of this version of our class in large scale wireless sensor network may introduce an important hash computation overhead. Indeed, nodes may have high identifiers and should then apply the hash function a large number of times. In order to reduce the computation overhead, we introduce a parameter called L. Each node i applies the one way hash function h to their keys (i mod L) times instead of i times, the number of hash computation is then bounded by L. We discuss later how to choose the L parameter and its impact on the network resiliency and the hash computation overhead. We show in what follows that we enhance the network resiliency against node capture where the computational overhead remains insignificant. Our approach can be applied to any pool based key pre-distribution scheme. To facilitate the explanation of the concepts behind our approach, we have chosen to apply our mechanism to two concrete schemes. A probabilistic scheme which is the qcomposite scheme [START_REF] Chan | Random key predistribution schemes for sensor networks[END_REF] and a deterministic one which is the Symmetric Balanced Incomplete Block Design scheme [START_REF] Yener | Combinatorial design of key distribution mechanisms for wireless sensor networks[END_REF].

HC(q-composite):

A highly resilient qcomposite scheme

In this section, we develop a highly resilient key management solution by applying our solution to the q-composite scheme [START_REF] Chan | Random key predistribution schemes for sensor networks[END_REF]. The proposed protocol which we denote by HC(q-composite) is more resilient against node capture as we demonstrate in the following analysis.

Before the deployment of the WSN, a large pool S of keys and their identifiers are generated off-line. Each node is preloaded with a key ring of m keys randomly selected from the key pool S. Before the deployment phase, we apply a hash function h, (i mod L) times to the pre-loaded keys of each node, where i is the node identifier and L is a parameter of our class, which allows to reduce the number of hash operation as explained before. So, each node i is preloaded with the set of keys KR i such us:

KR i = h i mod L (K 1 ), h i mod L (K 2 ), ...h i mod L (K m )
where K 1 , K 2 , ...K m are the randomly selected keys from S.

After the deployment phase, each two neighboring nodes can establish a secure link only if they share q or more common keys. The pairwise secret key between two neighboring nodes is computed as the hash of all their shared keys concatenated to each other. Let us assume that the node i shares q ′ keys (q ′ >= q) with its neighbor j and that (i mod L) > (j mod L). The node i computes its shared secret key with j as follows:

K ij = Hash(K i s1 K i s2 ... K i s q ′ ) where K i s1 , K i s2 , .
.., K i s q ′ are the common keys with the node j.

The node j computes its key as :

K ji = Hash(h (i mod L)-(j mod L) (K j s1 ) h (i mod L)-(j mod L) (K j s2 ) ... h (i mod L)-(j mod L) (K j s q ′ ))
where K j s1 , K j s2 , ..., K j s q ′ are the common keys with the node i. Indeed, node j which have the minimum identifier may apply the hash function (i mod L) -(j mod L) times to each shared key (K j sp ) in order to compute the key having the same identifier and pre-loaded in node i which is (K i sp ). The session key between i and j is then

K ij = K ji .

Example:

To illustrate our idea, let us refer to the figure 3. To simplify the comprehension, we apply our approach to the 1-composite scheme (q-composite scheme with q=1) and we consider a network of seven nodes, a key pool containing six keys (|S| = 6) and each node is pre-loaded with m = 2 keys. In the basic 1-composite scheme (Figure 3(a)), the corruption of nodes 4 and 7 induces the disclosure of the keys K 1 ,K 3 and K 5 , and then the compromise of the three external links (1,2),(2,3) and [START_REF] Eschenauer | A key-management scheme for distributed sensor networks[END_REF][START_REF] Chan | Random key predistribution schemes for sensor networks[END_REF].

Using our protocol HC(1-composite) (Figure 3(b)), keys are hashed before the deployment phase (we assume in the example that L = 5). So the node 4 is pre-loaded with the keys h 4 (K 1 ) and h 4 (K 5 ) instead of K 1 and K 5 , the node 7 is pre-loaded with the keys h 2 (K 3 ) and h 2 (K 5 ) instead of K 3 and K 5 and so on. If we consider the same scenario as above, the corruption of the two nodes 4 and 7 induces the disclosure of the derived keys h 4 (K 1 ), h 4 (K 5 ), h 2 (K 3 ) and h 2 (K 5 ). In this case, the link (2,3) can be compromised because the attacker can compute h 3 (K 3 ) knowing h 2 (K 3 ). However, the two other external links (1,2) and (5,6) cannot be compromised because it is infeasible to calculate h 2 (K 1 ) knowing h 4 (K 1 ) and h(K 3 ) knowing h 2 (K 3 ).

Analysis

In this section, we will evaluate the performance of our protocol HC(q-composite), we compare it to the basic qcomposite scheme with respect to the metrics defined in section 3. We recall in table 1 the main symbols that we use in what follows:

S

The global key pool |S| The size of the global key pool m The size of the node key ring q The minimum number of common keys required to establish a secure link p(k) The probability that two nodes share exactly k keys in their subset of keys p The probability that two nodes can establish a secure link L The parameter of the HC approach n The network size (number of nodes)

Network resiliency against node capture

In this section, we compare the network resiliency of the two schemes: q-composite and HC(q-composite). As stated before, we define the network resiliency R x as the fraction of uncompromised links when x nodes are captured, we have then: R x = 1 -P (LC|N C x ) where :

• LC is the event that a link is compromised

• N C x is the event that x nodes are compromised Let us compute R x when we use the q-composite and the HC(q-composite) scheme and let us first compute P (LC|N C x ) in the two cases. We recall that we consider only external links which are independent of the compromised nodes.

When x nodes are captured, all their keys are compromised. In the two schemes, q-composite and HC(qcomposite), each external secure link is computed as the hash of k keys concatenated to each other where q ≤ k ≤ m. The probability of a link compromise when x nodes are captured is then given as follows :

P (LC|N C x ) = m k=q P (LC k |N C x )P (LS k ) (1)
where:

• LC k is the event that a link secured with k keys is compromised

• LS k is the event that a secure link is secured with k keys Proposition 1. In the basic q-composite scheme, the probability of link compromise when x nodes are captured is :

P (LC|N C x ) = m k=q (1 -(1 - m |S| ) x ) k p(k) p
Proof. In the basic q-composite scheme, the probability that a key is compromised when a node is captured is c = m |S| because each node is pre-loaded with m keys selected randomly from the global key pool S. The fraction of uncompromised keys is then 1 -c. When x nodes are compromised, the fraction of uncompromised Figure 4: Network resiliency depending on the number of compromised nodes (q-composite Vs HC(q-composite))

keys is (1 -c) x . So, the probability that a given key has been known is then 1

-(1 -c) x .
As a result, the probability that a given link is compromised when it is secured with k shared keys and when x nodes are compromised is:

P (LC k |N C x ) = (1 -(1 -c) x ) k (2)
On the other hand, p(k) which is the probability that two nodes share exactly k keys was given in [START_REF] Chan | Random key predistribution schemes for sensor networks[END_REF] as :

p(k) =   |S| k     |S| -k 2 (m -k)     2 (m -k) m -k     |S| m   2
The probability that two given nodes can establish a secure link is then: p = m k=q p(k) and the probability that a secure link is secured exactly with k keys is:

P (LS k ) = p(k) p (3)
From equation ( 2) and (3) the equation (1) becomes:

P (LC|N C x ) = m k=q (1 -(1 - m |S| ) x ) k p(k) p (4)
The resulting formula ( 4) is similar to the one calculated by Chan et al. in [START_REF] Chan | Random key predistribution schemes for sensor networks[END_REF]. Let us now compute P (LC|N C x ) of our HC(q-composite) scheme.

Lemma 1. Using the hash chain class with L ≥ 1, The probability that a given key is known when a node is randomly captured is:

c h = L + 1 2L m |S|
Proof. For any discovered key, it is initially hashed l times (0 ≤ l ≤ L -1) with a probability 1 L . When the initial key is hashed l times, the probability that a key having the same identifier can be discovered is L-l L . Indeed, forward values can be computed when it is impossible to compute backward values. Thus, we find that the probability to disclose a key having the same identifier with a compromised key is :

L-1 l=0 1 L × L -l L = L + 1 2L
Since each node has m keys, the probability that a key has been discovered when a node is compromised is

c h = L+1 2L m |S| .
Proposition 2. In the HC(q-composite) scheme, the probability of link compromise when x nodes are randomly captured is :

P (LC|N C x ) = m k=q (1 -(1 - L + 1 2L m |S| ) x ) k p(k) p
Proof. Based on the lemma 1 and following the same steps of the proof of proposition 1, we find that using our HC(q-composite) scheme, the fraction of compromised links when x nodes are captured is :

P (LC|N C x ) = m k=q (1 -(1 - L + 1 2L m |S| ) x ) k p(k) p (5)
Propositions 1 and 2 show that the probability of link compromise is reduced when we apply our hash chain mechanism. Thus, our scheme is more resilient than the basic one. As we have defined resiliency against node capture as the fraction of uncompromised links when x nodes are compromised, we plot in the figure 4 the fraction of uncompromised links depending on the number of captured nodes with the two schemes (q-composite and HC(q-composite) when q=1,2 and 3. In this analysis, we fixed |S| = 1000, m = 40 and L = 10 (we discuss the choice of L's value later). This figure shows clearly that the resilience against node capture attacks is better when using our approach.

For instance, with q = 3, when the number of compromised nodes is between 50 and 100, our approach reduces the fraction of compromised links up to 40%. The figure shows also that higher is the q value, better is the improvement.

Secure connectivity coverage

Since we maintain the same common key discovery phase based on the key identifier exchange, the secure connectivity coverage of the network when we use hash chain q-composite scheme is the same as the basic q-composite scheme. Indeed, each two neighbors can establish a secure link only if they share at least q keys. The secure connectivity is then given as:

p connect = p = m k=q p(k)
We plot in figure 5 (a) the secure connectivity coverage depending on the key ring size m when q=1 ,2 and 3 and |S| = 1000. The figure shows that the secure connectivity coverage increases when the key ring size increases because the probability of sharing at least q keys increases. Moreover, the figure shows that higher is q worse is the secure connectivity coverage. For instance, with q = 1 and m = 40, we ensure a network secure connectivity coverage of 80%. To reach the same connectivity, we need about 55 keys per ring when q = 2 and about 65 keys when q = 3. Indeed, the q value represents the minimum required number of common keys to establish secure links.

In addition to the secure connectivity coverage, we plot also in figure 5 (b) the network resiliency when 50 nodes are compromised (R 50 ) depending on the key ring size m when q = 2, |S| = 1000 and L = 10. This figure shows that the network resiliency decreases when m increases. It shows clearly that our solution is more resilient against node capture attacks depending on the key ring size. Indeed, the network resiliency is improved up to 40% when m ≥ 60.

Computation overhead

In the basic q-composite scheme, nodes apply a hash function one time on the common keys concatenated to each other in order to compute the secret key. With our solution, the node having the minimum hash degree should apply the hash function h a number of times before computing the secret key. In the example 3 (b) where L = 5, the node 7 for example should apply two times the hash function to compute h 4 (K 5 ) because it is initially pre-loaded with h 2 (K 5 ).

In order to evaluate this extra-computation overhead, we calculate the average number of times that a node applies the hash function per secure link in the initialization phase of our approach.

Lemma 2. Using the hash chain approach with (L ≥ 1), if two nodes can establish a secure link, then they have to apply on average N H avg = L 2 -1

6L times the hash function on their common keys before computing the session secret key.

Proof. Let us assume that two nodes i and j can establish a secure link (which means that they share q ′ keys with q ′ > q ).So, the node i is pre-loaded with keys hashed (i mod L) times where the node j is pre-loaded with keys hashed (j mod L) times. One of the nodes i or j would have to apply |(i mod L) -(j mod L)| times the hash function on their q ′ common keys. Note that i and j are natural numbers chosen randomly, which means that (i mod L) and (j mod L) are uniformly distributed over Z L . The average number of hash computation is then:

N H avg = 1 2 L-1 k=0 k × P (|(i mod L) -(j mod L)| = k) = 1 2 ( L-1 k=1 k × 2(L -k) L 2 ) = 1 L 2 ( L-1 k=1 k × L - L-1 k=1 k 2 ) = 1 L 2 ( L 2 (L -1) 2 - L(L -1)(2L -1) 6 ) = L 2 -1 6L
Proposition 3. In the HC(q-composite) scheme, Given L and m, if two nodes can establish a secure link, then they have to apply on average L 2 -1 6L m k=q (k × p(k) p ) hash functions.

Proof. Following the lemma 2, when using the HC(qcomposite) scheme, each node applies on average L 2 -1 6L times the hash function on all the q ′ shared keys where q ′ ≥ q. Since p(k) p is the probability that an established link is secured with k keys, the overall average number of hash computation is then:

m k=q ( L 2 -1 6L × k × p(k) p ) = L 2 -1 6L m k=q (k × p(k) p )
In table 2, we summarize the average number of hash computations for 1 ≤ L ≤ 15, when q=1, 2 and 3. Note that with L = 1 we have exactly the basic scheme where the pre-loaded keys are not hashed. This table shows that the average number of hash computations remains reasonable when L ≤ 15. Energy consumption overhead : We were interested in evaluating the energy consumed due to the execution of hash functions over a mote's processor. For this end, we developed a nesC component of SHA1 hash function [START_REF]Secure hash standard[END_REF]. Then, we compiled the component for a Mica2 platform [24] using TinyOS [25]. We used the AVRORA simulator [START_REF] Titzer | Avrora: Scalable sensor network simulation with precise timing[END_REF] to simulate and evaluate the consumed energy due to SHA1 calculation over a 160 bits string. The obtained results confirm our claims regarding the negligible induced energy overhead. Indeed, we found that the SHA1 calculations consume only 0.4 mJ. We also found that this is equivalent to only 4% of the energy consumed by a idle Atmel processor of a Mica2 node during 1 second. This means that 25 SHA1 executions consume only the equivalent energy required to maintain the node's processor idle during 1 second.

We have also evaluated the energy consumed by the radio module to send 128 bytes using 8 × 16 TOS messages. We found that the consumed energy is around 40 times the energy consumed by a hash function computation. We notice that this transmission takes about 600 milliseconds. In figure 6, we plot the average consumed energy by hash computations when using the HC(q-composite) scheme with q=1, 2 and 3. The figure shows that this energy is negligible compared to the energy consumed by the radio when sending 128 bytes. In addition, the hash function computation is done only one time during the common key discovery phase.

Choice of L's value:

As we have shown in the figures 4 and 5, our approach enhances the network resiliency. In addition, we notice from the proposition 2 that higher is L, better is the resilience. When L is too high, the value L+1 2L approaches 1 2 , so the optimal resiliency with our approach is reached when L+1 2L approaches 1 2 . However, we notice from proposition 3 that higher is L higher is the induced computational overhead. Indeed, the average number of hash computations depends linearly on the L value. We propose then to choose L = 10 which allows to approach the optimal resiliency ( L+1 2L = 0.55 which is close to 1/2), while the induced computational overhead is reasonable. For instance, with L = 10 the average hash computation is insignificant (3.255 for q=1, 4.346 for q=2 and 5.682 for q=3).

Storage overhead

The storage memory required by the q-composite scheme is mainly the memory used to store the m pairs (key identifier, secret key) where the keys are selected randomly from S. If we neglect the q value storage memory, the required storage memory is then M size = m × (K size + I size ) where K size is the size of a given key and I size is the size of the key identifier (I size = log 2 |S| bits). Our solution requires exactly the same storage memory as the basic scheme in addition to the L value which is a short integer.

Communication overhead

The communication overhead depends linearly on the value of m. Indeed, each node must exchange the key identifiers and its own identifier in order to determine the common keys and then establish the secure link. The number of exchanged bits in the basic q-composite scheme is m×(log 2 |S|) if we neglect the node identifier. As we maintain the same common key discovery phase with the basic scheme and which is based on the key identifier exchange, our scheme induces exactly the same communication overhead.

HC(SBIBD): A resilient combinatorial designbased key management scheme

In this section, we present a deterministic pool based key management scheme highly resilient against node capture. The latter results from the application of our hash chain class to the Symmetric Balanced Incomplete Block Design scheme proposed by C ¸amtepe and Yener [START_REF] Yener | Combinatorial design of key distribution mechanisms for wireless sensor networks[END_REF]. First, we present the basic scheme, then we explain how to apply our hash chain class to this scheme, and finally we compare the performances of the two schemes.

In [START_REF] Yener | Combinatorial design of key distribution mechanisms for wireless sensor networks[END_REF], C ¸amtepe and Yener introduced the use of combinatorial design for key pre-distribution in WSN. In order to guarantee the determinism when using a pool based key management scheme, authors made use of a particular combinatorial design which is the Symmetric Balanced Incomplete Block Design (SBIBD).

Given a finite set X of ν objects, a Balanced Incomplete Block Design (BIBD) is defined to be a set of k-distinct element subsets of X, called blocks, constructed is such a way that each object occurs in exactly r different blocks and every pair of distinct objects appears together in λ blocks. The number of resulting blocks is b. A BIBD (ν, b, r, k, λ) two properties: (i) λ(ν -1) = r(k -1) and (ii) bk = νr. It can then be identified by (ν, k, λ). A BIBD is called symmetric when b = v and in consequence r = k. A Symmetric BIBD (SBIBD) has the properties:

• every block contains k elements;

b = ν = k 2 -k + 1) Number of generated key rings (|S| = b = m 2 -m + 1)
Two blocks share (λ = 1) object Two key rings share (λ = 1) key

• each element occurs in exactly k blocks;

• each pair of elements occurs in λ blocks;

• each pair of blocks intersects in λ elements.

Let's take the example where we have 7 objects {1, 2, 3, 4, 5, 6, 7} (ν = 7).

With (k = 3) and λ = 1, a configuration of the SBIBD blocks can be: {1, 2, 3}{1, 4, 5}{1, 6, 7}{2, 4, 6}{2, 5, 7}{3, 4, 7}{3, 5, 6}. We have then 7 blocks (b = ν = 7). Each block contains k = 3 distinct objects. Each object appears in r = k = 3 blocks, each pair of distinct elements occurs in λ = 1 block, and each pair of blocks intersects in exactly (λ = 1) object.

C ¸amtepe and Yener introduce in [START_REF] Yener | Combinatorial design of key distribution mechanisms for wireless sensor networks[END_REF] a mapping from the SBIBD to the pool based key distribution. In this mapping, to each object is associated a distinct key, to the global set of objects is is associated the key pool and to each block is associated the node key ring (see table 3). We can then generate from a global key pool of |S| keys, |S| key rings of m keys in such a way that each two key rings shares exactly λ keys. Note that this generation has the property λ(|S| -1) = m(m -1). Therefore, |S| = m 2 -m + 1 when λ = 1. In other terms, thanks to the symmetric design we can generate m 2 -m + 1 key subsets of m keys each one in such a way that each two key rings share exactly one common key. We use for that a global key pool S of m 2 -m + 1 keys. This approach guarantees a total connectivity coverage when nodes are pre-loaded with the generated subsets of keys.

The application of our hash chain-based approach to the SBIBD scheme gives birth to a deterministic key predistribution scheme which enhances the resiliency while ensuring a total connectivity coverage. Before the deployment step, |S| key rings are generated from the key pool S where |S| = m 2 -m + 1. Instead of pre-loading each node with a distinct key ring, we propose to apply a hash function h, (i mod L) times on all the pre-loaded keys of each node, where i is the node identifier and L is a parameter of our class. Thanks to the symmetric balanced incomplete block design (with λ = 1), any two neighboring nodes i and j share exactly one key having the same identifier. Let us consider s the identifier of the common key between the key rings of the neighboring nodes i and j. In the basic scheme, the link secret key is k s = k i s = k j s . In our scheme HC(SBIBD), the node i is initially preloaded with k i s = h i mod L (k s ) where the node j is preloaded with k j s = h j mod L (k s ). The common secret key is then k j s if we suppose that (i mod L) > (j mod L). Then, the node i computes its secret key with the node j as follows: k ij = h (i mod L)-(j mod L) (K i s ).

Analysis

In this section, We compare the performance of our scheme HC(SBIBD) against the basic SBIBD-based scheme with respect to the metrics defined in section 3.

Network resiliency against node capture

In the two schemes, each secure link is composed of one secret key. The fraction of compromised external links when x nodes are compromised is given as follows:

P (LC|N C x ) = m 2 -m+1 k=1 P (LC k |N C x )P (L k ) (6)
where:

• LC is the event that a link is compromised

• N C x is the event that x nodes are compromised

• LC k is the event that a link secured with the key having the identifier k is compromised.

• L k is the event that a link is secured with a key having the identifier k.

Since keys having the identifier k occurs exactly in m key rings, the fraction of links secured with a key having the identifier k is then:

P (L k ) = m 2 m 2 -m + 1 2 = 1 m 2 -m + 1 (7)
So, equation ( 6) becomes:

P (LC|N C x ) = 1 m 2 -m + 1 m 2 -m+1 k=1 P (LC k |N C x ) (8)
Proposition 4. Using the basic SBIBD scheme, the probability that an external link is compromised when x nodes are compromised is:

P (LC|N C x ) = 1 -x-1 t=0 (1 - m m 2 -m+1-t )
Proof. The probability that a link secured with the key having the identifier k is compromised when x nodes are compromised is the probability that the key k occurs one or more times in the x discovered key rings. Let us denote by B 1 , B 2 , B 3 , ... and B x the x discovered key rings. Applying the bayes' theorem, we find that the probability that the key k occurs one or more times in the x discovered key rings is:

P (LC k |N C x ) = 1 -P (K k / ∈ B 1 ∩ .. ∩ k i / ∈ B x ) = 1 -P (K k / ∈ B 1 ) × P (K k / ∈ B 2 |K k / ∈ B 1 ) × ... P (K k / ∈ B x |(K k / ∈ B 1 ∩ .. ∩ K k / ∈ B x-1 ))
Since the key k occurs exactly in m key rings from the m 2 -m + 1 possible key rings, we have:

P (LC k |N C x ) = 1 -((1 - m m 2 -m + 1 ) × (1 - m m 2 -m + 1 -1 ) × ... ×(1 - m m 2 -m + 1 -(x -1) )) = 1 - x-1 t=0 (1 - m m 2 -m + 1 -t )
By replacing in equation ( 8), we find that the probability that an external link is compromised when x nodes are compromised is: We give in appendix A another proof which is similar to the one given by C ¸amtepe and Yener in [START_REF] Yener | Combinatorial design of key distribution mechanisms for wireless sensor networks[END_REF]. Proposition 5. Using the HC(SBIBD) scheme, the probability that an external link is compromised when x nodes are compromised is:

P (LC|N C x ) = 1 -x-1 t=0 (1 - m m 2 -m+1-t )
P (LC|N C x ) = 1 - x-1 t=0 (1 -L+1 2L m m 2 -m+1-t )
Proof. As proved in section 5.2.1, if a key having the identifier k is compromised, then the average fraction of discovered keys having the same identifier is L+1

2L (the attacker discovers only derived versions). Similar to the proof of proposition 4 and following the same steps, we find that the probability that an external link is compromised when x nodes are compromised in the HC(BIBD) scheme is:

P (LC|N C x ) = 1 - x-1 t=0 (1 -L+1 2L m m 2 -m+1-t )
From propositions 4 and 5, we notice that our solution reduces the fraction of compromised links, the resiliency is so enhanced. We plot in figure 7 the resiliency of the two schemes, SBIBD and HC(SBIBD) depending on the number of compromised nodes (R x = 1 -P (LC|N C x )). We choose m respectively: 20 (a), 40 (b) and 60(c). Notice that the size of the global pool (|S|) is therefore 379, 1559 and 3539 respectively. We have chosen L = 10 when using our hash chain scheme. The figure shows that the network resiliency against node capture is better when using the HC(SBIBD) scheme. For instance, with m = 40 we enhance the resilience up to 20% when x is between 40 and 80.

Secure connectivity coverage

As explained before, the use of SBIBD theory ensures a total secure connectivity coverage. Each two nodes share exactly one key in their key subsets. When using our hash chain approach, we have also this property. The only difference is that the node having the low hash degree should apply the hash function a number of times on its shared key. Therefore, the two schemes ensure a total secure coverage (secure connectivity coverage = 1) thanks to the SBIBD based construction.

Computation overhead

After the common key discovery phase in the basic scheme, each two neighboring nodes determine their common shared key which is unique. This key is then the secret pairwise key used to secure the link.

With our solution, each two neighboring nodes determine, after the common key discovery phase, the identifier of their shared key. However, the node having the minimum hash degree should apply the hash function h a number of times to compute the common secret key. We have proved in lemma 2 that nodes have to apply in average N H avg = L 2 -1 6L times the hash function on the their set of common keys before computing the secret key, where L is the parameter of our class. Using the SBIBD with λ = 1, each two nodes share exactly one key. Hence, nodes apply in average N H avg times the hash function on the single common key. In the table 4, we compute the average number of hash computations when (1 ≤ L ≤ 15). Note that L = 1 represents the basic scheme because we do not apply at all the hash function. This table shows that the number of hash computations is negligible when L ≤ 15. Since the energy consumption due to computation is negligible, we believe that the application of our solution to the SBIBD key management schemes does not degrade its performances. In order to confirm our claim, we have evaluated the energy consumed by the hash function computation of HC(SBIBD) over a mote's processor. We simulated the computation of SHA1 hash function [START_REF]Secure hash standard[END_REF] over a Mica2 platform [24] using TinyOS [25]. We used the AVRORA simulator [START_REF] Titzer | Avrora: Scalable sensor network simulation with precise timing[END_REF] to simulate and evaluate the consumed energy due to SHA1 calculation over a 160 bits string.

In figure 8, we plot the average consumed energy by hash computations when using the HC(SBIBD) scheme. This figure shows that this energy is negligible compared to the energy consumed by the radio when sending 128 bytes. We notice also that the consumed energy in HC(SBIBD) is lower than the energy consumed by hash computations when applying HC to probabilistic schemes. Indeed, the hash function in HC(SBIBD) is applied on only one key during the common key discovery phase.

As explained before, we propose to choose L = 10 to achieve a good tradeoff between the resilience improvement and the computational overhead.

Storage overhead

We give the memory required to store the pairs (key identifier, secret key) in the basic SBIBD scheme as: M size = m × (K size + I size ), where K size is the size of a given key and I size is the size of the key identifier: I size = log 2 m 2 -m + 1 bits. We summarize in table 5 the required storage memory when K size = 128 bits (16 bytes) and when m is between 10 and 100. Notice that our scheme requires exactly the same storage memory in addition to the L value which is a short integer.

Communication overhead

The communication overhead depends linearly on the value of m. In fact, each node must exchange the key identifiers and its own identifier in order to find the only common key and then establish the secure link. The number of exchanged bits in the basic SBIBD scheme is then m × (log 2 m 2 -m + 1 ) if we omit the node identifier. When applying our hash chain class, we maintain the same common key discovery phase with the basic scheme; our scheme induces then exactly the same communication overhead compared to the basic one.

Extensions and Enhancements

As shown above, the mechanism that we propose allows to enhance the resiliency of existing key pre-distribution schemes against oblivious node capture attacks. Nevertheless, the proposed scheme may incur unbalanced calculation overhead. Indeed, some nodes might hash their keys many times to deduce the shared key while others do not. Moreover, a smart attacker which captures nodes having the lowest values (i mod L) would allow a largest link compromise. In this section, we tackle these two issues and we propose countermeasures against both the smart attacks and the unbalanced overhead.

Smart node capture attacks:

The selective node capture attacks or smart attacks were proposed for the first time by Pietro et al. in [START_REF] Di Pietro | Efficient and resilient key discovery based on pseudo-random key pre-deployment[END_REF]. Authors proposed in this paper a new attack where the adversary greedily uses the information disclosed by compromised nodes in order to choose the next node to capture. Authors defined a random variable called key information gain G(s) for each potential node s. This variable is equal to the number of keys in the key ring of s which are not yet compromised. At each step, the attacker chooses the next node to compromise as the node which maximizes E[G(s)|I(s)], the expectation of the key information gain G(s) given the information I(s) that the attacker knows on the key ring of sensor s. This approach allows maximizing the number of useful keys to collect at each step.

This kind of vulnerability is due mainly to the exchanges of key identifiers which may allow an attacker to know which keys are pre-loaded in which node. Therefore, countermeasures must hide key identifiers while allowing nodes to determine the shared keys. A lot of solutions were proposed. For instance, the challenge response solution introduced in [START_REF] Eschenauer | A key-management scheme for distributed sensor networks[END_REF] and used later in many schemes, consists of encrypting a challenge α with each key of a node. After receiving the encrypted values, the second node can deduce the shared keys by trying to decrypt the challenge α with its own keys. This solution is known to be secure but induces a high communication and computation complexity of order O(m 2 ) where m is the key size. In pseudo-random key index transformation, used in [START_REF] Zhu | Establishing pairwise keys for secure communication in ad hoc networks: A probabilistic approach[END_REF] for instance, each node generates the key indexes using a pseudo-random generator initialized with a given node seed. Even this solution is communication efficient, it is not secure since the attacker can generate key indexes knowing the pseudorandom generator and the seeds which are usually supposed to be public. Authors in [START_REF] Ruj | Key predistribution using combinatorial designs for grid-group deployment scheme in wireless sensor networks[END_REF] propose to enhance the C ¸amtepe scheme in order to avoid key identifier exchanges and counter active attacks. For this purpose, they index all nodes and keys and propose a mapping between node indexes and key indexes. This solution remain efficient as long as the mapping algorithm is not known, otherwise, an attacker can easily reveal the key identifers knowing the node identifier.

Pietro et al. proposed in [START_REF] Di Pietro | Efficient and resilient key discovery based on pseudo-random key pre-deployment[END_REF][29] an efficient and secure shared key discovery way trading off communications for local computations. In the proposed solution, each node i is pre-loaded with keys from the global pool such as : f y (i K u ) ≡ 0 mod ( m S ) where f y is a one way pseudorandom function having y as a seed. So, each node can deduce the shared keys with a neighbor by verifying the relation on its own keys.

When using our hash function based mechanism, all the proposed countermeasures, presented above, can be adapted to face this kind of attacks. In addition, a particular smart attack can be launched and should be considered: the attacker may target nodes having lower hash degree (i mod L) in order to compute a larger number of derived keys and hence compromise more links. In the worst case, the attacker could target only the nodes having the identifier i such that (i mod L) = 0, in this case the attacker will have original keys which can be used to compute derived versions and so nullifies the effect of our solution.

Unbalanced calculation overhead

We proved in previous sections that the average introduced computational overhead, due to hash calculations, is insignificant. Nevertheless, it is obvious that the limited introduced workload is unbalanced. Indeed, most calculations are shifted to nodes having a low hash degree (i mod L), , where i is the node identifier and L is the parameter of our approach. Using the proposed mechanism HC, a node i have to perform hash computations with a probability L-1-(i mod L) L which is unbalanced.

Balanced and smart-attack free extension

We propose in this subsection an improvement of our hash-based mechanism which alleviates both the smart attack presented above and the computation overhead unbalance. For analysis simplicity, we assume that the key ring size m is an even number, we assume also that the key identifiers are totally ordered and that the keys within a key ring are distinct.

In order to balance hash computations and render the above smart attack inefficient, we divide the original keys, to be pre-loaded in each node i, to two subsets of size m 2 each. The first subset contains the keys having the lower identifers while the second one contains the keys having the higher identifers. Before de deployment, we propose to apply a hash function h, (i mod L) times to the keys of the lower subset and ((L -1) -(i mod L)) times to the keys of the higher subset. Thus, each node i is preloaded with the set of keys KR i such as: KR i = LKR i ∪ HKR i where: LKR i = h i mod L (K 1 ), ..., h i mod L (K m 2 ) and HKR i = h L-1-(i mod L) (K m 2 +1 ), ..., h L-1-(i mod L) (K m ) where K 1 , K 2 , ...K m are the distinct original keys to be pre-loaded in node i totaly ordered with respect to their identifiers.

After the deployment step, each node can determine the hash degree of a shared key thanks to the common key discovery phase. Hence, each node can deduce whether it applies the hash function on the stored key or it uses this key without hash computation.

The use of this enhanced version allows to balance the hash function computations between nodes. Indeed, for any given two nodes i and j, the node i will perform the hash function with probability 1 2 if we assume that any given shared key belongs to the lower set or the higher subset with the same probability 1 2 . Let us assume that s is the identifier of a given shared key and that (i mod L) = (j mod L) and that (i mod L) = L -1 -(j mod L). The probability that the node i has to apply the hash function is then given by : P = P (Ks ∈ LKR i ∩ Ks ∈ LKR j ) × P (i mod L < j mod L) + P (Ks ∈ LKR i ∩ Ks ∈ HKR Following a similar reasoning, we find that when (i mod L) = (j mod L) or (i mod L) = L -1 -(j mod L) exclusively, the probability that the node i has to apply the hash function is also equal to 1 2 . Finally, if (i mod L) = (j mod L) and (i mod L) = L-1-(j mod L), both nodes do not perform hash computations.

In addition to load balancing hash computations, the proposed enhancement allows to counteract the smart attack presented above. Indeed, when using the basic solution, the probability that a key is compromised following the capture of a node i is L-(i mod L) L m |S| . In other words, the capture of nodes having low values (i mod L) reveals a high number of pre-loaded keys while the capture of nodes having high values (i mod L) reveals low number of keys. The above smart attack relies on this unbalanced revealing of keys following a node capture.

When using the enhanced version presented in this subsection, the probability that a given key is compromised following the capture of a node is equal to L-(i mod L) L × m 2|S| due to the capture of the lower subset plus L-[(L-1)-(i mod L)] L × m 2|S| due the capture of the highest subset (the two subsets within a key ring are assumed to be distinct). Therefore, the capture of one node reveals a fraction of L+1 2L m |S| of keys independently of its identifier. Hence, the smart attack described above can no more be conducted against this enhanced scheme, since the number of keys revealed following a node capture is the same whatever the identifier of the node.

Conclusion

Asymmetric key management schemes are likely to be unsuitable for WSN because of resource limitations. Moreover, because of the lack of infrastructure in WSN, it is difficult to assume the existence of a trusted third party which can attribute pairwise secret keys to neighboring nodes. This is why symmetric key pre-distribution schemes are the most suitable paradigm for wireless sensor networks to secure exchanges.

In this paper, we presented a hash chain class of key management schemes highly resilient against node capture. We enhance resilience by concealing keys through the use of an efficient hash chaining mechanism. Our class can be applied to any pool based key pre-distribution scheme. In this work, we applied it to the well known probabilistic q-composite scheme in a first time and to the deterministic Symmetric Balanced Incomplete Bock Design scheme in a second time. The analytical study showed that our approach may enhance resiliency up to 40% without introducing any new storage or communication overheads, it induces an insignificant computational overhead.

Acknowledgement

This work is made as part of the Picardie regional project under reference I159C. The authors wish to thank the Picardie regional council in France and the European Regional Development Fund (ERDF) for funding and supporting this project.

Appendix A. proof of proposition 4

When using the SBIBD scheme, the probability that a link secured with the key having the identifier k is compromised when x nodes are compromised is the probability that the key k occurs one or more times in the x discovered key rings. Since the key occurs exactly in m key rings among the possible m 2 -m + 1 key rings, we have:

P (LC k |N Cx) = 1 - (m 2 -m + 1 -m) x m 2 -m + 1 x = 1 - m 2 -2m + 1 x m 2 -m + 1 x = 1 - (m 2 -2m + 1)! (m 2 -m + 1)! (m 2 -m + 1 -x)! (m -2m + 1 -x)! = 1 - x-1 t=0 m 2 -2m + 1 -t m 2 -m + 1 -t = 1 - x-1 t=0 (1 - m m 2 -m + 1 -t )
Following the equation ( 8), we find that the probability that an external link is compromised when x nodes are compromised is:

P (LC|N C x ) = 1 - x-1 t=0 (1 - m m 2 -m + 1 -t )

Figure 1 :

 1 Figure 1: Classification of symmetric key management schemes for WSN

Figure 2 :

 2 Figure 2: Illustration of the hash-chain based approach

Figure 3 :

 3 Figure 3: Example: 1-composite Vs HC(1-composite)

  Connectivity and resiliency (R 50 ) with q=2

Figure 5 :

 5 Figure 5: Network connectivity and resiliency depending on the key ring size

Figure 6 :

 6 Figure 6: Energy consumption overhead of HC(q-composite)

Figure 7 :

 7 Figure 7: Network resiliency depending on the number of compromised nodes (SBIBD Vs HC(SBIBD))

Figure 8 :

 8 Figure 8: Energy consumption overhead of HC(SBIBD)

4 × 4 ×

 44 j ) × P (i mod L < L -1 -(j mod L))+ P (Ks ∈ HKR i ∩ Ks ∈ LKR j ) × P (L -1 -(i mod L) < j mod L) + P (Ks ∈ HKR i ∩ Ks ∈ HKR j ) × P (L -1 -(i mod L) < L -1 -(j mod L)) = 1 [P (i mod L < j mod L) + P (L -1 -(i mod L) < L -1 -(j mod L))] + 1 [P (i mod L < L -1 -(j mod L)) + P (L -1 -(i mod L) < j mod L)] = 1 2

Table 1 :

 1 SUMMARY OF NOTATIONS

Table 2

 2

	: Average number of hash computation in HC(q-composite)
	L	N Havg	HC(q-composite)
			q=1	q=2	q=3
	1	0.0	0.0	0.0	0.0
	2	0.25	0.493	0.659	0.861
	3	0.444	0.877	1.171	1.531
	4	0.625	1.233	1.646	2.152
	5	0.8	1.578	2.107	2.755
	6	0.972	1.918	2.561	3.348
	7	1.143	2.255	3.01	3.936
	8	1.313	2.589	3.457	4.52
	9	1.481	2.923	3.902	5.102
	10	1.65	3.255	4.346	5.682
	11	1.818	3.587	4.789	6.261
	12	1.986	3.918	5.232	6.84
	13	2.154	4.249	5.673	7.417
	14	2.321	4.58	6.115	7.994
	15	2.489	4.91	6.556	8.571

Table 3 :

 3 Mapping from symmetric design to key distribution

	SBIBD	Key distribution
	X: Object set	S : Key pool
	ν: Size of the object set X	|S|: Size of the key pool S
	Blocks	Key rings
	Objects in a Block (k)	Keys in a key ring (m)
	number of generated blocks
	(

Table 4 :

 4 Average hash computation in HC(SBIBD)

	L	N Havg	HC(SBIBD)
	1	0.0	0.0
	2	0.25	0.25
	3	0.444	0.444
	4	0.625	0.625
	5	0.8	0.8
	6	0.972	0.972
	7	1.143	1.143
	8	1.313	1.313
	9	1.481	1.481
	10	1.65	1.65
	11	1.818	1.818
	12	1.986	1.986
	13	2.154	2.154
	14	2.321	2.321
	15	2.489	2.489

Table 5 :

 5 Required storage memory in SBIBD & HC(SBIBD) schemes

	m	I size	I size	M size
		(bits)	(bytes)	(bytes)
	10	7	1	170
	20	9	2	360
	30	10	2	540
	40	11	2	720
	50	12	2	900
	60	12	2	1080
	70	13	2	1260
	80	13	2	1440
	90	13	2	1620
	100	14	2	1800