Jacques M Bahi
email: jacques.bahi@univ-fcomte.fr

Christophe Guyeux
email: christophe.guyeux@univ-fcomte.fr

Abdallah Makhoul
email: abdallah.makhoul@univ-fcomte.fr

Secure Data Aggregation in Wireless Sensor Networks. Homomorphism versus Watermarking Approach

Keywords: Wireless Sensor Networks, Secure Data Aggregation, Authentication, Homomorphic Encryption, Elliptic Curves, Watermarking

Wireless sensor networks are now in widespread use to monitor regions, detect events and acquire information. Since the deployed nodes are separated, they need to cooperatively communicate sensed data to the base station. Hence, transmissions are a very energyconsuming operation. To reduce the amount of sending data, an aggregation approach can be applied along the path from sensors to the sink. However, usually the carried information contains confidential data. Therefore, an end-to-end secure aggregation approach is required to ensure a healthy data reception. End-to-end encryption schemes that support operations over cypher-text have been proved important for private party sensor network implementations. These schemes offer two main advantages: end-to-end concealment of data and ability to operate on cipher text, then no more decryption is required for aggregation. Unfortunately, nowadays these methods are very complex and not suitable for sensor nodes having limited resources. In this paper, we propose a secure end-to-end encrypted-data aggregation scheme. It is based on elliptic curve cryptography that exploits a smaller key size. Additionally, it allows the use of higher number of operations on cypher-texts and prevents the distinction between two identical texts from their cryptograms. These properties permit to our approach to achieve higher security levels than existing cryptosystems in sensor networks. Our experiments show that our proposed secure aggregation method significantly reduces computation and communication overhead and can be practically implemented in on-the-shelf sensor platforms. By using homomorphic encryption on elliptic curves, we thus have realized an efficient and secure data aggregation in sensor networks. Lastly, to enlarge the aggregation functions that can be used in a secure wireless sensor network, a watermarking-based authentication scheme is finally proposed.

Introduction

Wireless sensor networks have received enormous attention over past few years, due to a wide range of potential applications (environmental, ecological, military, etc.). A typical sensor network is expected to consist of a large number of sensor nodes deployed randomly in a large scale. Usually, these nodes have limited power, storage, communication, and processing capabilities, making energy consumption an issue.

A major functionality of a sensor node is to measure environmental values using embedded sensors, and transmit it to a base station called "sink". The sensed data needs to be analyzed, which eventually serves to initiate some action. Almost this analysis presumes computation of the maximum, minimum, average, etc. It can be either done at the base station or by the nodes themselves, in a hierarchical scenario. In order to reduce the amount of data to be transmitted to the sink, it is beneficial that this analysis can be done over the network itself. To save the overall energy resources of the network, it is agreed that the sensed data needs to be aggregated on the way to its final destination. Sensor nodes send their values to certain special nodes, i.e., aggregators. Each aggregator then condenses the data prior to sending it on. In terms of bandwidth and energy consumption, aggregation is beneficial as long as the aggregation process is not too CPU-intensive. The aggregators can either be special (more powerful) nodes or regular sensors nodes.

At the same time, sensor networks are often deployed in public or otherwise untrusted and even hostile environments, which prompts a number of security issues (e.g., key management, privacy, access control, authentication, etc.). Then, if security is a necessary in other (e.g., wired or MANET) types of networks, it is much more so in sensor networks. Actually, it is one of the more popular research topic and many advances have been reported on in recent years.

From the above observations, we can notice the importance of a cooperative secure data aggregation in sensor networks. In other terms, after the data gathering and during transmissions to the base station, each node along the routing path cooperatively integrates and secures the fragments messages. In this paper, we focus on security data aggregation and we propose a simple secure homomorphic cyphersystem that allows efficient aggregation of encrypted data.

Data encryption becomes necessary in sensor networks when this type of sensors can be subject of many types of attacks [START_REF] Chandramouli | Battery power-aware encryption[END_REF]. Without encryption, adversaries can monitor and inject false data into the network. In a general manner the encryption process is done as follows: sensor nodes must encrypt data on a hop-by-hop basis. An intermediate node (i.e., aggregator) possessing the keys of all sending nodes, decrypts the received encrypted value, aggregates all received values, and encrypts the result for transmission to the base station. Though viable, this approach is fairly expensive and complicated, due to the fact of decrypting each received value before aggregation, which generates an overhead imposed by key management. Encryption can solve the security problem, but how can we aggregate over encrypted data [START_REF] Chandramouli | Battery power-aware encryption[END_REF]? Some privacy homomorphism based works have been proposed recently [START_REF] Castelluccia | Efficient aggregation of encrypted data in wireless sensor networks[END_REF][START_REF] Girao | Cda: Concealed data aggregation in wireless sensor networks[END_REF][START_REF] Acharya | Secure comparison of encrypted data in wireless sensor networks[END_REF]] that, without participating in checking, the aggregators can directly aggregate the encrypted data. However, such schemes, for the moment, need high and complex computations to encrypt data and aggregate it, which leads to large cypher-texts. Sensor nodes cannot provide sufficient CPU, memory and bandwidth to address such complex operations. For instance, Rivest Shamir Adleman (RSA) cryptosystems [START_REF] Haodong | Elliptic curve cryptography-based access control in sensor networks[END_REF][START_REF] Liu | Tinyecc: A configurable library for elliptic curve cryptography in wireless sensor networks[END_REF] are used, which requires high CPU and memory capabilities to perform exponential operations. Therefore, in our study we adopt an elliptic curve encryption [START_REF] Boneh | Evaluating 2-dnf formulas on ciphertexts[END_REF] that al-lows nodes to generate a smaller key size while providing the same security level of existing complex schemes. The cypher-system we exploit permits N additions and one product, thus it is not limited to a single basic function. A major advantage of our method is the fact that it has been proved safe, and until now it has not been cryptanalized. To assess the practicality of our technique, we evaluate it and compare it to existing cypher-system. The obtained results show that we significantly reduce computation and communication overhead and that our secure aggregation method can be practically implemented in on-the-shelf sensor platforms.

The rest of this paper is organized as follows: in the next section we present a review of some previous related work. Section 1.3 presents our security model. Sections 1.4 and 1.5 discuss the details of the proposed aggregation scheme for sensor networks. In Section 1.6, we describe simulation and results of simulation experiments. In Section 1.7 is proposed a new authentication scheme based on a watermarking approach, to improve the variety of aggregation functions through the secure wireless sensor network. Finally, we end the paper by a conclusion.

Related Work

The benefit and vulnerability, as well as the need to secure in-network aggregation, have been identified by a number of schemes in the literature. One approach [START_REF] Przydatek | Sia: Secure information aggregation in sensor networks[END_REF] proposed a secure information aggregation protocol to answer queries over the data acquired by the sensors. Even though their method provided data authentication to provide secrecy, the data still sent in plain text format, which removes the privacy during transmission. Another one [START_REF] Cam | Espda: Energyefficient secure pattern based data aggregation for wireless sensor networks[END_REF] proposed a secure energy efficient data aggregation (ESPDA) to prevent redundant data transmission in data aggregation. Unlike conventional techniques, their scheme prevents the redundant transmission from sensor motes to the aggregator. Before transmitting sensed data, each sensor transmits a secure pattern to the aggregator. Only sensors with different data are allowed to transmit their data to the cluster-head. However, since each sensor at least needs to transmit a packet containing a pattern once, power cannot be significantly saved. In addition, each sensor mote uses a fixed encryption key to encrypt data; data privacy cannot be maintained in their scheme. In [START_REF] Huang | Secure encrypted-data aggregation for wireless sensor networks[END_REF], the authors presented a secure encrypted-data aggregation scheme for wireless sensor networks. The idea is based on eliminating redundant sensor readings without using encryption and maintains data secrecy and privacy during transmission. This scheme saves energy on sensor nodes but still do not guarantee the privacy of sent data.

The problem of aggregating encrypted data in sensor networks was introduced in [START_REF] Girao | Cda: Concealed data aggregation in wireless sensor networks[END_REF] and further refined in [START_REF] Castelluccia | Efficient aggregation of encrypted data in wireless sensor networks[END_REF]. The authors propose to use homomorphic encryption schemes to enable arithmetic operations over cypher-texts that need to be transmitted in a multi-hop manner. However, these approaches provide a higher level of system security, since nodes would not be equipped with private keys, which would limit the advantage gained by an attacker compromising some of the nodes. Unfortunately, existing privacy homomorphisms used for data aggregation in sensor networks have exponential bound in computation. It is too computationally expensive to implement in sensor nodes. Moreover, the expansion in bit size during the transformation of plain text to cypher-text introduces costly communication overhead, which directly translates to a faster depletion of the sensors energy. On the other hand and from security viewpoint, the cryptosystems [START_REF] Domingo-Ferrer | A provably secure additive and multiplicative privacy homomorphism[END_REF] used in these approaches were cryptanalized [START_REF] Cheon | Known-plaintext cryptanalysis of the domingo ferrer algebraic privacy homomorphism scheme[END_REF][START_REF] Wagner | Cryptanalysis of an algebraic privacy homomorphism[END_REF], which means they can't guarantee anymore high security levels.

In this paper we try to relax the statements above by investigating elliptic curve cryptography that allows feasible and suitable data aggregation in sensor networks beside the security of homomorphisms schemes. First, our proposed scheme for secure data aggregation in sensor networks is based on a cryptosystem, which has been proved safe and has not been cryptanalyzed. Another property that enforces the security level of such approach is coming from the fact that, as it is the case in ElGamal cryptosystem, for two identical messages it generates two different cryptograms. This property suggested fundamental for security in sensor networks [START_REF] Boneh | Evaluating 2-dnf formulas on ciphertexts[END_REF][START_REF] Huang | Secure encrypted-data aggregation for wireless sensor networks[END_REF][START_REF] Lin | Cooperative secure data aggregation in sensor networks using elliptic curve based cryptosystems[END_REF], to the best of our knowledge, was not addressed in previous homomorphism-based security data aggregation works. Beside all these properties and due to the use of elliptic curves, our approach saves energy by allowing nodes to encrypt and aggregate data without the need of high computations. Lastly, the scheme we use allows more aggregations types over cypher data than the homomorphic cryptosystem used until now.

Security Model

In this work, we are primarily concerned with data privacy in sensor networks. Our goal is to prevent attackers from gaining any information about sensor data. Therefore, ensuring an end-to-end privacy between sensor nodes and the sink becomes problematic. This is largely because popular and existing cyphers are not additively homomorphic. In other words, the summation of encrypted data does not allow for the retrieval of the sum of the plain text values. Moreover, privacy existing homomorphisms have usually exponential bound in computation. To overcome this problem, in our model we propose a security scheme for sensor networks using elliptic curve based cryptosystem. We show that our model permits many operations on crypted data and does not demand high sensor capabilities and computation.

Operations over elliptic curves

In this section, we give a brief introduction to elliptic curve cryptography. The reader is referred to [START_REF] Hankerson | Guide to elliptic curve cryptography[END_REF] for more details.

Addition and multiplication

Elliptic curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields [START_REF] Hankerson | Guide to elliptic curve cryptography[END_REF]. Elliptic curves used in cryptography are typically defined over two types of finite fields: prime fields F p , where p is a large prime number, and binary extension fields F 2 m [START_REF] Cheung | Secure encrypted-data aggregation for wireless sensor networks[END_REF]. In our paper, we focus on elliptic curves over F p . Let p > 3, then an elliptic curve over F p is defined by a cubic equation y 2 = x 3 + ax + b as the set

E = (x, y) ∈ F p × F p , y 2 ≡ x 3 + ax + b (mod p)
where a, b ∈ F p are constants such that 4a 3 + 27b 2 0 (mod p). An elliptic curve over F p consists of the set of all pairs of affine coordinates (x, y) for x, y ∈ F p that satisfy an equation of the above form and an infinity point O.

The point addition and its special case, point doubling over E is defined as follows (the arithmetic operations are defined in F p ) [START_REF] Hankerson | Guide to elliptic curve cryptography[END_REF] :

Let P = (x 1 , y 1 ) and Q = (x 2 , y 2 ) be two points of E. Then:

P + Q = O if x 2 = x 1 and y 2 = -y 1 , (x 3 , y 3 )
otherwise.

where:

• x 3 = λ 2 -x 1 -x 2 , • y 3 = λ × (x 1 -x 3 ) -y 1 , λ = (y 2 -y 1 ) × (x 2 -x 1 ) -1 if P Q , (3x 2 1 + a) × (2y 1 ) -1 if P = Q.
Finally, we define P + O = O + P = P, ∀P ∈ E, which leads to an abelian group (E, +). On the other hand the multiplication n × P means P + P + .... + P n times and -P is the symmetric of P for the group law + defined above for all P ∈ E.

Public/Private keys generation with ECC

In this section we show how we can generate the public and private keys for encryption, following the cryptosystem proposed by Boneh et al. [START_REF] Boneh | Evaluating 2-dnf formulas on ciphertexts[END_REF]. The analysis of the complexity will be treated in a later section.

Let τ > 0 be an integer called "security parameter". To generate public and private keys, first of all, two τ-bits prime numbers must be computed. Therefore, a cryptographic pseudo-random generator can be used to obtain two vectors of τ bits, q 1 and q 2 . Then, a Miller-Rabin test can be applied for testing the primality or not of q 1 and q 2 . We denote by n the product of q 1 and q 2 , n = q 1 q 2 , and by l the smallest positive integer such that p = l × n -1. l is a prime number while p = 2 (mod 3).

In order to find the private and public keys, we define a group H, which presents the points of the super-singular elliptic curve y 2 = x 3 + 1 defined over F p . It consists of p + 1 = n × l points, and thus has a subgroup of order n, we call it G. In another step, we compute g and u as two generators of G and h = q 2 × u. Then, following [START_REF] Boneh | Evaluating 2-dnf formulas on ciphertexts[END_REF], the public key will be presented by (n, G, g, h) and the private key by q 1 .

Encryption and Decryption

After the private/public keys generation, we proceed now to the two encryption and decryption phases:

• Encryption : Assuming that our messages space consists of integers in the set {0, 1, ..., T}, where T < q 2 , and m the (integer) message to encrypt. First, a random positive integer is picked from the interval [0, n -1]. Then, the cypher-text is defined by

C = m × g + r × h ∈ G,
in which + and × refer to the additive and multiplication laws defined previously. • Decryption : Once the message C arrived to destination, to decrypt it, we use the private key q 1 and the discrete logarithm of (q 1 × C) base q 1 × g as follows:

m = log q 1 ×g q 1 × C.
This takes expected time √ T using Pollard's lambda method. Moreover, this decryption can be speed-up by precomputing a table of powers of q 1 × g.

Homomorphic properties

As we mentioned before, our approach ensures easy encryption/decryption without any need of extra resources. This will be proved in the next section. Moreover, our approach supports homomorphic properties, which gives us the ability to execute operations on values even though they have been encrypted. Indeed, it allows N additions and one multiplication directly on cryptograms, which prevents the decryption phase at the aggregators level and saves nodes energy, which is crucial in sensor networks.

Additions over cypher-texts are done as follows: let m 1 and m 2 be two messages and C 1 , C 2 their cypher-texts respectively. Then the sum of C 1 and C 2 , let call it C, is represented by C = C 1 + C 2 + r × h where r is an integer randomly chosen in [0, n -1] and h = q 2 × u as presented in the previous section. This sum operation guarantees that the decryption value of C is the sum m 1 + m 2 . The addition operation can be done several times, which means we can do sums of encrypted sums.

The multiplication of two encrypted values and its decryption are done as follows: let e be the modified Weil pairing on the curve and g, h the points of G as defined previously. Let us recall that this modified Weil pairing e is obtained from the Weil pairing E [START_REF] Boneh | Evaluating 2-dnf formulas on ciphertexts[END_REF], [START_REF] Boneh | Identity-based encryption from the weil pairing[END_REF] by the formula: e(P, Q) = E(x × P, Q), where x is a root of X 3 -1 on F p 2 . Then, the result of the multiplication of two encrypted messages

C 1 , C 2 is given by [C m = e(C 1 , C 2 ) + r × h 1 ]
, where h 1 = e(g, h) and r is a random integer pick in [1, n].

The decryption of C m is equal to the discrete logarithm of q 1 × C m to the base

q 1 × g 1 : m 1 m 2 = log q 1 * g 1 (q 1 × C m .)
where g 1 = e(g, g).

Our Secure Data Aggregation for Sensor Networks 1.4.1 Presentation

Data aggregation schemes aim to combine and summarize data packets of several sensor nodes so that amount of data transmission is reduced. An example data aggregation scheme is presented in Figure 1.1 where sensor nodes collect information from a region of interest. When the user (sink) queries the network, instead of sending each sensor node's data to the base station, aggregators collect the information from its neighboring nodes, aggregates them, and send the aggregated data to the base station over a multihop path. As the majority of wireless sensor network applications require a certain level of security, encryption of the sensed data before its transmission becomes necessary and it is preferable to decrypt the data only at the base station level (c.f. previous sections). In our work, we adopt the following scenario as shown in Figure 1.1: after collecting information, each sensor node encrypts its data according to elliptic curve encryption (c.f. Section 1.3.1) and sends it to the nearest aggregator. Then, aggregators aggregate the received encrypted data (without decryption) and send it to the base station, which in his turn decrypts the data and aggregates it. We notice that all aggregators can done N additions and the final layer of aggregators can done one multiplication on encrypted data.

Example of use

Computing the Arithmetic Mean

The arithmetic mean is the "standard" average, often simply called the "mean", defined for n values x 1 , . . . , x n by

x = 1 n • n i=1 x i .
To compute the average of nodes measurements, aggregators can calculate the sum of the encrypted measurements and the number of nodes took these measurements and send it to the base station. More precisely, when using our scheme, each sensor encrypts its data x i to obtain cx i . The sensor then forwards cx i to its parent, who aggregates all the cx j 's of its k children by simply adding them up. The resulting value is then forwarded. The sink ends up with value Cx = n i=1 cx i . It can then decrypt Cx, and divide the result by n to derive the average.

Computing the Variance

Another common aggregation is to estimate the variance of the sensed values. Let us recall that the variance of n values x 1 , ..., x n is defined by:

s 2 n = 1 n n i=1 (x i -x) 2 =        1 n n i=1 x 2 i        -x 2 .
Our scheme can also be used to derive the variance of the measured and encrypted data, by the same method as in [START_REF] Castelluccia | Efficient and provably secure aggregation of encrypted data in wireless sensor networks[END_REF]. In this case, each sensor i must compute y i = x 2 i , where x i is the measured sample, and encrypts y i to obtain cy i . x i must also be encrypted, as explained in the previous section. The sensor forwards cy i , together with cx i , to its parent. The parent aggregates all the cy j of its k children by simply adding them up. It also aggregates, separately, the cx j , as explained in the previous section. The two resulting values are then forwarded. The sink ends up with values Cx = n i=1 cx i and Cy = n i=1 cy i . Cx is used to compute the average Av, when Cy is used to compute the variance as follows: Var = Vy n -Av 2 , where Vy is the decryption of Cy.

Computing the Weighted Mean

The weighted mean of a non-empty set of data x 1 , x 2 , . . . , x n with non-negative weights w 1 , w 2 , . . . , w n , is the quantity

x = w 1 x 1 + w 2 x 2 + • • • + w n x n w 1 + w 2 + • • • + w n .
We suppose now that each aggregator i of the first aggregation layer has computed the mean x i of the encrypted values received from its sensor node. Additionally, we suppose that these aggregators are weighted, depending on their importance. For security reasons, this weight is also encrypted and the cypher value is denoted by w i . This w i can be proportional to the number of aggregated sensors. This weight can also illustrate the fact that two given regions have not the same relevance. To achieve weighted mean, each aggregator multiplies its encrypted mean x i with encrypted weight w i as it has been explained previously. The resulting value is then forwarded to the sink, which can decrypt w i × x i and sum all these decrypted values, to obtain the weighted mean defined above.

Security study

Due to hostile environments and unique characteristics of sensor networks, it is a challenging task to protect sensitive information transmitted by nodes to the end user. In addition, this type of networks has security problems that traditional networks do not face. In this section, we present a security study dedicated to wireless sensor networks. First we introduce the principal attacks that sensor networks can face and how our approach can support them, then we present some practical issues that improve the network security.

Related attacks and results

In a sensor network environment adversaries can commonly use the following attacks:

Known-plain text attack: They can use common key encryption to see when two readings are identical. By using nearby sensors under control, attackers can conduct a known-plain text attack. Chosen-plain text attack: Attackers can tamper with sensors to force them to predeterminated values. Man-in-the-middle: They can inject false readings or resend logged readings from legitimate sensor motes to manipulate the data aggregation process.

In Tables 1.1, 1.2 and similar to [START_REF] Cheung | Secure encrypted-data aggregation for wireless sensor networks[END_REF], we present a comparison between different encryption policies and possible attacks. In our method, as data are encrypted by public keys, and these public keys are sent by the sink to the sole authenticated motes, the wireless sensor network is then not vulnerable to a Man-in-the-middle attacks. On the other hand, our approach guarantees that for two similar texts gives two different cryptograms, which prevents the Chosen-plain text attacks and the Manin-the-middle attacks. Finally, as the proposed scheme possesses the homomorphic property, data aggregation is done without decryption, and no private key is used in the network.

Practical issues

In this section we present some practical issues to our security model. First we study the sizes of the encryption keys and we compare it to existing approaches. Then, we present how we can optimize the sizes of cryptograms in order to save more sensors energy.

Sizes of the keys

Cryptograms are points of the elliptic curve E. They are constituted by couples of integer coordinates lesser than or equal to p = lq 1 q 2 -1.

It is commonly accepted [19], [START_REF] Lenstra | Selecting cryptographic key sizes[END_REF] that for being secure until 2020, a cryptosystem:

• must have p ≈ 2 161 , for EC systems over F p , • must satisfy p ≈ 2 1881 for classical asymmetric systems, such as RSA or ElGamal on F p .

Thus, for the same level of security, using elliptic curve cryptography does not demand high keys sizes, contrary to the case of RSA or ElGamal on F p . The use of small keys leads to small cryptograms and fast operations for encryption.

Reducing the size of cryptograms

In this section we show how we can reduce the size of cryptograms while using ECC. This is benefit for sensor nodes in terms of reducing energy consumption by sending data with smaller size. The messages are encrypted with q 2 bits, which leads to cryptograms with a mean of 160 bits long.

Let us suppose that p ≡ 3 ( mod 4). As the cryptogram is an element (x, y) of E, which is defined by y 2 = x 3 + 1, we can compress this cryptogram (x, y) to (x, y mod 2)) before sending it to the aggregator (as the value of y 2 is known). In this situation, we obtain cryptograms with a mean of 81 bits long for messages between 20 and 40 bits long.

To decompress the cryptogram (x, i), the aggregator must compute z = x 3 + 1 mod p and y = √ z mod p, which can be written as y = z (p+1)/4 mod p, then :

• if y ≡ i(mod 2), then the decompression of (x, i) is (x, y).

• else the decompression is (x, py).

Experimental Results

To show the effectiveness of our approach we conducted a series of simulations comparing our method to another existing one based on RSA cryptosystem. We considered a network formed of 500 sensor nodes, each one is equipped by a battery of 100 units capacity. We consider that the energy consumption ′′ E ′′ of a node is proportional to the computational time t, i.e., E = kt. The same coefficient of proportionality k is taken while comparing the two encryption scenarii. Sensor nodes are then connected to 50 aggregators chosen randomly. Each sensor node choose the nearest aggregator. The running of each simulation is as follows: each sensor node takes a random value, encrypts it using one of the encryption methods then sends it to its aggregator. Aggregators compute the sum of the encrypted received data and send it to the sink. We compared our approach to the known RSA public-key cryptographic algorithms, and we evaluated the energy consumption of the network while varying the sizes of the keys and obviously the security levels. The energy consumption is the units of the battery used to do the encryption. Tables 1.3 and 1.4 show the energy consumption of sensor nodes to do the encryption operations using our encryption method and the RSA one respectively. We varied the keys sizes and obviously the security levels. We notice that for the same level of security in our approach we used small keys while saving more energy. For instance, for high security levels (4 for example) a node using our approach needs to use a key of 167 bits instead of 1891 in the case of RSA and consumes 0.1 % of the battery power instead of 3.63 %. 1.2 gives the comparison between RSA and elliptic curve based encryption, concerning the average energy consumption of an aggregating wireless sensor network. We can notice that our approach saves the energy largely greater than the case of RSA, where its depletion is so fast. Finally let us notice that, in addition of reducing the amount of energy units needed for encryption and aggregation, the sink receives many more values per second in EC-based networks than in RSA-based one.

Enlarging the number of allowing authentication functions

In the previous sections, we have proposed to use a homomorphism encryption scheme to support in-network processing while preserving privacy. Compared to existing secure aggregation schemes based on homomorphism encryption, our method has not been cryptanalysed. Moreover, due to the possibility to realize n additions and one product over the cypher values, this scheme enlarges the variety of allowing aggregation operations through cyphertexts. However, all of the homomorphism encryption schemes only allow some specific query-based aggregation functions, e.g., sum, average, etc.

Another way to achieve secure data aggregation in wireless sensor networks is to authenticate sensing values. In-network processing presents a critical challenge for data authentication in wireless sensor networks. Current schemes relying on Message Authentication Code (MAC) cannot provide natural support for this operation, because a MAC computation is a very energy-consuming operation. Additionally, even a slight modification to the data invalidates the MAC.

In [START_REF] Zhang | Secure data aggregation in wireless sensor networks: A watermark based authentication supportive approach[END_REF] a new way to achieve authentication through wireless sensor networks is introduced. It is based on digital watermarking and proposes an end-to-end, statistical approach for data authentication that provides inherent support for in-network processing. In this scheme, authentication information is modulated as watermark and superposed on the sensory data at the sensor nodes. The key idea formerly presented in [START_REF] Zhang | Secure data aggregation in wireless sensor networks: A watermark based authentication supportive approach[END_REF] is to visualize the sensory data at a certain time snapshot as an image. Each sensor node is viewed as a pixel and its value corresponds to the gray level of the pixel. Due to this equivalency, information hiding techniques can be used to authenticate a wireless sensor network. The watermarked data can be aggregated by the intermediate nodes without incurring any en route checking. Upon reception of the sensory data, the sink is able to authenticate the data by validating the watermark, thereby detecting whether the data has been illegitimately altered. In this way, the aggregation-survivable authentication information is only added at the sources and checked by the data sink, without any involvement of intermediate nodes.

In [START_REF] Zhang | Secure data aggregation in wireless sensor networks: A watermark based authentication supportive approach[END_REF] the authors proposes to use a data hiding scheme based on spread spectrum techniques to achieve authentication. In their proposal, "each sensor node embeds part of the whole watermark into its sensory data, while leaving the heavy computational load of watermark detection at the sink". Moreover, as stated before, their scheme supports in-network aggregation. However spread spectrum is known to be not robust: even if their scheme survives to a certain degree of distortion, spread-spectrum cannot face to elementary blind attack. Furthermore, spreadspectrum data hiding techniques are only stego-secure in the "Natural Watermarking" situation [START_REF] Cayre | Kerckhoffs-based embedding security classes for woa data hiding[END_REF]. The spread-spectrum subclass used in [START_REF] Zhang | Secure data aggregation in wireless sensor networks: A watermark based authentication supportive approach[END_REF] is related to classical SS, i.e. with BPSK modulation [START_REF] Cayre | Kerckhoffs-based embedding security classes for woa data hiding[END_REF]. This subclass is neither stego-secure [START_REF] Cayre | Kerckhoffs-based embedding security classes for woa data hiding[END_REF], nor chaos-secure [START_REF] Bahi | A chaos-based approach for information hiding security[END_REF]. Among the consequences of these lack of security is the fact that an attacker how observes the network can access to the secret embedding key in all of the following situations:

• Watermarked Only Attack (WOA): the attacker has access only to watermarked contents. • Known Message Attack (KMA): the attacker has access to pairs of watermarked contents and corresponding hidden messages. • Known Original Attack (KOA): occurs when an attacker has access to several pairs of watermarked contents and their corresponding original versions. • Constant-Message Attack (CMA): the attacker observes several watermarked contents and only knows that the unknown hidden message is the same in all contents.

To improve the security of the network in WOA setup, the use of Natural Watermarking instead of BPSK modulation is required [START_REF] Cayre | Kerckhoffs-based embedding security classes for woa data hiding[END_REF]. Indeed, this subclass of spread-spectrum techniques, recalled in [START_REF] Cayre | Kerckhoffs-based embedding security classes for woa data hiding[END_REF], is stego-secure and so can face WOA attacks. However, Natural Watermarking is less chaos-secure than the data hiding algorithm presented in [START_REF] Bahi | Hash functions using chaotic iterations[END_REF]. This algorithm, based on chaotic iterations, is able to withstand attacks in KMA, KOA and CMA setups [START_REF] Guyeux | Chaotic iterations versus Spread-spectrum: chaos and stego security[END_REF]. Moreover, this technique is more robust than spread-spectrum, as it is stated in [START_REF] Bahi | A new chaos-based watermarking algorithm[END_REF]. To sum up, the use of the scheme proposed in [START_REF] Bahi | Hash functions using chaotic iterations[END_REF] improves the security and robustness of the scheme presented in [START_REF] Zhang | Secure data aggregation in wireless sensor networks: A watermark based authentication supportive approach[END_REF].

Finally, an hybrid approach of secure data aggregation in wireless sensor networks can be obtained by combining homomorphic encryption and watermarkingbased authentication, as it is summed up in Figure 1.3.

Conclusion

In this paper, we presented an elliptic curve based approach for secure data aggregation in sensor networks. It is based on data encryption with homomorphic properties that provide the possibility to operate on cypher-text. It prevents the decryption phase at the aggregators layers and saves nodes energy. Existing works have exponential bound in computation and are not suitable for sensor networks, which we tried to relax in our approach. The proposed scheme permits the generation of shorter encryption asymmetric keys, which is so important in the case of sensor networks. The experimental results show that our method significantly reduces computation and communication overhead compared to other works, and can be practically implemented in on-the-shelf sensor platforms.

Fig. 1 . 1 .

 11 Fig. 1.1. Secure data aggregation in sensor networks

Fig. 1 . 2 .

 12 Fig. 1.2. Comparison of energy consumption

Fig. 1 . 3 .

 13 Fig. 1.3. Secure data authentication and aggregation in sensor networks

Table 1 . 1 .

 11 Encryption polices and vulnerabilities

	Encryption Policy	Possible attacks
	Sensors transmit readings without encryption Man-in-the-middle
	Sensors transmit encrypted readings	Known-plain text attack
	with permanent keys	Chosen-plain text attack
		Man-in-the-middle
	Sensors transmit encrypted readings	None of above
	with dynamic keys
	Our scheme	None of above
	Table 1.2. Encryption polices and aggregation
	Encryption Policy	Data aggregation
	Sensors transmit readings without encryption Generating wrong aggregated results
	Sensors transmit encrypted readings	Data aggregation is impossible,
	with permanent keys	unless the aggregator has encryption keys
	Sensors transmit encrypted readings	Data aggregation cannot be achieved
	with dynamic keys	unless the aggregator has encryption keys
	Our scheme	Data aggregation can be achieved

Table 1 . 3 .

 13 Our approach Tables 1.5 and 1.6 give the energy consumption E at the aggregation stage. The same hypothesis that above have been made, the sole difference is that aggregator nodes have a battery of 1000 units of energy. It can be seen that the energy needed by

	Security level Size p of the key E (battery units)
	1	46	0.02
	2	85	0.05%
	3	125	0.07
	4	167	0.10

Table 1 .

 1

		5. Our approach
	Security level Size of the key E (battery units)
	1	472	1.13
	2	945	8.09
	3	1416	24.74
	4	1891	56.27

Table 1 .6. RSA encryption Figure

 1


Christophe Guyeux
email: christophe.guyeux@univ-fcomte.fr

Qianxue Wang
email: qianxue.wang@univ-fcomte.fr

Jacques M Bahi
email: jacques.bahi@univ-fcomte.fr

A Pseudo Random Numbers Generator Based on Chaotic Iterations. Application to Watermarking

Keywords: Internet Security, Chaotic Sequences, Statistical Tests, Discrete Chaotic Iterations, Watermarking

In this paper, a new chaotic pseudo-random number generator (PRNG) is proposed. It combines the well-known ISAAC and XORshift generators with chaotic iterations. This PRNG possesses important properties of topological chaos and can successfully pass NIST and TestU01 batteries of tests. This makes our generator suitable for information security applications like cryptography. As an illustrative example, an application in the field of watermarking is presented.

Introduction

The extremely fast development of the Internet brings growing attention to information security issues. Among these issues, the conception of pseudo-random number generators (PRNGs) plays an important role. Secure PRNGs which can be easily implemented with simple software routines are desired. Due to the finiteness of the set of machine numbers, the sequences generated by numerous existing PRNGs are not actually random. For example, the use of stringent batteries of tests allows us to determine whether these sequences are predictable. Chaos theory plays an active role in the improvement of the quality of PRNGs [START_REF] Cecen | A new hybrid nonlinear congruential number generator based on higher functional power of logistic maps[END_REF], [START_REF] Po-Han | Evidence of the correlation between positive lyapunov exponents and good chaotic random number sequences[END_REF]. The advantage of using chaos in this field lies in its disordered behavior and its unpredictability.

This paper extends the study initiated in [START_REF] Bahi | Chaotic iterations and topological chaos[END_REF] and [START_REF] Wang | A novel pseudo-random generator based on discrete chaotic iterations for cryptographic applications[END_REF]. In [START_REF] Bahi | Chaotic iterations and topological chaos[END_REF], it is proven that chaotic iterations (CIs), a suitable tool for fast computing iterative algorithms, satisfy the topological chaotic property, as it is defined by Devaney [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF]. In [START_REF] Wang | A novel pseudo-random generator based on discrete chaotic iterations for cryptographic applications[END_REF], the chaotic behavior of CIs is exploited in order to obtain an unpredictable behavior for a new PRNG. This generator is based on chaotic iterations and depends on two other input sequences. These two sequences are generated by two logistic maps. Our generator has successfully passed the NIST (National Institute of Standards and Technology of the U.S. Government) battery of tests. However it appeared that it is a slow generator and it can't pass TestU01 because of the input logistic maps. Moreover this logistic map has revealed serious security lacks, which make it use inadequate for cryptographic applications [1]. That is why, in this paper, we intend to develop a new fast PRNG. It will pass TestU01, widely considered as the most comprehensive and stringent battery of tests. This goal is achieved by using the ISAAC and XORshift maps in place of the two logistic maps. Chaotic properties, statistical tests and security analysis [START_REF] Zheng | Pseudo-random sequence generator based on the generalized henon map[END_REF] allow us to consider that this generator has good pseudo-random characteristics and is capable to withstand attacks.

The rest of this paper is organized in the following way: in Section 2, some basic definitions concerning chaotic iterations and PRNGs are recalled. Then, the generator based on discrete chaotic iterations is presented in Section 3. Section 4 is devoted to its security analysis. In Section 5, we show that the proposed PRNG passes the TestU01 statistical tests. In Section 6 an application in the field of watermarking is proposed. The paper ends by a conclusion and some discussions about future work.

Basic recalls

This section is devoted to basic notations and terminologies in the fields of chaotic iterations and PRNGs.

Notations

1; N → {1, 2, . . . , N} S n → the n th term of a sequence S = (S 1 , S 2 , . . .) v i → the i th component of a vector v = (v 1 , v 2 , . . . , v n ) f k
→ k th composition of a function f strategy → a sequence which elements belong in 1; N S → the set of all strategies ⊕ → bitwise exclusive or + → the integer addition ≪ and ≫→ the usual shift operators

Chaotic iterations

Definition 1. The set B denoting {0, 1}, let f : B N -→ B N be an "iteration" function and S ∈ S be a chaotic strategy. Then, the so-called chaotic iterations are defined by [START_REF] Robert | Discrete Iterations. A Metric Study[END_REF] x 0 ∈ B N ,

∀n ∈ N * , ∀i ∈ 1; N , x n i = x n-1 i if S n i f (x n-1 ) S n if S n = i. (1)
In other words, at the n th iteration, only the S n -th cell is "iterated".

Input sequences

In [START_REF] Wang | A novel pseudo-random generator based on discrete chaotic iterations for cryptographic applications[END_REF], we have designed a PRNG which has successfully passed the NIST tests suite. Unfortunately, this PRNG is too slow to pass the TestU01 battery of tests. Our ancient PRNG which is called CI(Logistic, Logistic) PRNG is based on chaotic iterations and uses logistic maps as input sequences. However, chaotic systems like logistic maps work in the real numbers domain, and therefore a transformation from real numbers into integers is needed. This process leads to a degradation of the chaotic behavior of the generator and a lot of time wasted during computations. Moreover, a recent study shows that the use of logistic map for cryptographic applications is inadequate and must be discouraged [1]. Our purpose is then to design a new, faster, and more secure generator, which is able to pass the TestU01 battery of tests. This is achieved by using some faster PRNGs like ISAAC [START_REF] Jenkins | Isaac. Fast Software Encryption[END_REF] and XORshift [START_REF] Marsaglia | Xorshift rngs[END_REF] as input sequences.

3 Design of CI(ISAAC,XORshift)

Chaotic iterations as PRNG

The novel generator is designed by the following process. Let N ∈ N * , N 2. Some chaotic iterations are fulfilled to generate a sequence (x n ) n∈N ∈ B N N of boolean vectors: the successive states of the iterated system. Some of these vectors are randomly extracted and their components constitute our pseudo-random bit flow. Chaotic iterations are realized as follows. Initial state x 0 ∈ B N is a boolean vector taken as a seed and chaotic strategy (S n ) n∈N ∈ 1, N N is constructed with XORshift. Lastly, iterate function f is the vectorial boolean negation

f 0 : (x 1 , ..., x N ) ∈ B N -→ (x 1 , ..., x N ) ∈ B N .
To sum up, at each iteration only S i -th component of state X n is updated, as follows

x n i =            x n-1 i if i S i , x n-1 i if i = S i . (2)
Finally, let M be a finite subset of N * . Some x n are selected by a sequence m n as the pseudo-random bit sequence of our generator. The sequence (m n ) n∈N ∈ M N is computed with ISAAC. So, the generator returns the following values: the components of x m 0 , followed by the components of x m 0 +m 1 , followed by the components of x m 0 +m 1 +m 2 , etc. In other words, the generator returns the following bits:

x m 0 1 x m 0 2 x m 0 3 . . . x m 0 N x m 0 +m 1 1 x m 0 +m 1 2 . . . x m 0 +m 1 N x m 0 +m 1 +m 2 1 x m 0 +m 1 +m 2 2 . . .
or the following integers:

x m 0 x m 0 +m 1 x m 0 +m 1 +m 2 . . .
The basic design procedure of the novel generator is summed up in

- → 0 1 - → 1 1 1 0 2 - → 1 2 - → 0 2 - → 1 1 1 2 - → 0 0 1 1 1 3 - → 0 3 - → 1 3 - → 0 0 0 4 - → 1 1 1 1 0 0 5 - → 1 5 - → 0 5 - → 1 1 1 Binary Output: x 0 1 x 0 2 x 0 3 x 0 4 x 0 5 x 4 1 x 4 2 x 4 3 x 4 4 x 4 5 x 9 1 x 9 2 x 9 3 x 9 4 x 9 5
x 13 1 x 13 2 ... = 10100111101111110... Integer Output: x 0 , x 0 , x 4 , x 6 , x 8 ... = 20, 30, 31, 19... Table 1. Application example

Example

In this example, N = 5 and M = {4,5} are chosen for easy understanding. The initial state of the system x 0 can be seeded by the decimal part of the current time. For example, the current time in seconds since the Epoch is 1237632934.484084, so t = 484084.

x 0 = t (mod 32) in binary digits, then x 0 = (1, 0, 1, 0, 0). m and S can now be computed from ISAAC and XORshift:

-m = 4,

Chaotic iterations and chaos

Generally the success of a PRNG depends, to a large extent, on the following criteria: uniformity, independence, storage efficiency, and reproducibility. A chaotic sequence may have these good pseudo-random criteria and also other chaotic properties, such as: ergodicity, entropy, and expansivity. A chaotic sequence is extremely sensitive to the initial states. That is, even a minute difference in the initial state of the system can lead to enormous differences in the final state even over fairly small timescales. Therefore, chaotic sequence well fits the requirements of pseudo-random sequence. Contrary to ISAAC or XORshift, our generator possesses these chaotic properties. However, despite a huge number of papers published in the field of chaos-based PRNGs, the impact of this research is rather marginal. This is due to the following reasons: almost all PRNG algorithms using chaos are based on dynamical systems defined on continuous sets (e.g., the set of real numbers). So these generators are usually slow, require considerably more storage spaces, and lose their chaotic properties during computations. These major problems restrict their use as generators [START_REF] Kocarev | Chaos-based cryptography: a brief overview[END_REF]. Moreover, even if the algorithm obtained by the inclusion of chaotic maps is itself chaotic, the implementation of this algorithm on a machine can cause it lose its chaotic nature. This is due to the finite nature of the machine numbers set. In this paper we don't simply integrate chaotic maps hoping that the implemented algorithm remains chaotic. The PRNG algorithms we conceive are constituted by discrete chaotic iterations that we mathematically proved in [START_REF] Bahi | Chaotic iterations and topological chaos[END_REF], that produce topological chaos as defined by Devaney. In the same paper, we raised the question of their implementation, proving in doing so that it is possible to design a chaotic algorithm and a chaotic computer program. In conclusion, the generator proposed in this paper does not inherit its chaotic properties from a continuous real chaotic map, but from discrete chaotic iterations defined in Section 2.2. As quoted above, it has been proven in [START_REF] Bahi | Chaotic iterations and topological chaos[END_REF] that chaotic iterations behave as chaos, as it is defined by Devaney: they are regular, transitive and sensitive to initial conditions. This famous definition of a chaotic behavior for a dynamical system implies unpredictability, mixture, sensitivity and uniform repartition. This allows the conception of a new generation of chaotic PRNGs. Because only integers are manipulated in discrete chaotic iterations, the chaotic behavior of the system is preserved during computations, and these computations are fast.

Security analysis

In this section a security analysis of the proposed generator is given.

Key space

The PRNG proposed in this document is based on discrete chaotic iterations. It has an initial value x 0 ∈ B N . Considering this set of initial values alone, the key space size is equal to 2 N . In addition, this PRNG combines digits of two other PRNGs: ISAAC and XORshift. Let k 1 and k 2 be the key spaces of ISAAC and XORshift. So the total key space size is close to 2 N • k 1 • k 2 . Finally, the impact of M must be taken into account. This leads to conclude that the key space size is large enough to withstand attacks.

Key sensitivity

This PRNG is highly sensitive to the initial conditions. To illustrate this property proved in [START_REF] Bahi | Chaotic iterations and topological chaos[END_REF], several initial values are put into the chaotic system. Let H be the number of differences between the sequences obtained in this way. Suppose n is the length of these sequences. Then the variance ratio P, defined by P = H/n, is computed. The results are shown in Figure 1a (x axis is sequence lengths, y axis is variance ratio P). Variance ratios approach 0.50, which indicates that the system is extremely sensitive to the initial conditions.

Uniform distribution

Figure 1b gives a 3D graphic representation of the distribution of a random sequence obtained by our generator. The point cloud presents a uniform distribution that tends to fill the complete 3D space, as expected for a random signal. To obtain this cloud, we have first changed the binary sequence to a N-bit integer sequence x 1 , x 2 , x 3 , x 4 ... Then we have plot

x 1 2 N , x 2 2 N , x 3 2 N , x 2 2 N , x 3 2 N , x 4 2 N ...

TestU01 Statistical Test Results

In a previous section, we have shown that the proposed PRNG has strong chaotic properties, as Devaney's chaos. In particular, this generator is better than the well-known XORshift and ISAAC, in the topological point of view. In addition to being chaotic, we will show in this section that CI(ISAAC,XORshift) is better than XORshift, and at least as good as ISAAC [START_REF] Wichmanna | Generating good pseudo-random numbers[END_REF] in the statistical point of view. Indeed, similarly to ISAAC and contrary to XORshift, CI(ISAAC,XORshift) can pass the stringent Big Crush battery of tests included in TestU01. In addition, our generator achieves to pass all the batteries included in TestU01. To our best knowledge, this result has not been proven for ISAAC, and only one other generator is capable of doing this [START_REF] Corsaro | On parallel asset-liability management in life insurance: a forward risk-neutral approach[END_REF]

TestU01

Indeed, the quality of a PRNG should be based on theoretical fundamentals but should also be tested empirically. Various statistical tests are available in the literature that test a given sequence for some level of computational indistinguishability. Major test suites for RNGs are TestU01 [START_REF] Simard | Testu01: A software library in ansi c for empirical testing of random number generators[END_REF], the NIST suite [15], and the DieHARD suites [START_REF] Marsaglia | Diehard: a battery of tests of randomness[END_REF]. The proposed PRNG has been tested using TestU01 for its statistical pseudo randomness.

Batteries of tests

Analysis

In a sound theoretical basis, a PRNG based on discrete chaotic iterations (ICs) is a composite generator which combines the features of two PRNGs. The first generator constitutes the initial condition of the chaotic dynamical system. The second generator randomly chooses which outputs of the chaotic system must be returned. The intention of this combination is to cumulate the effects of chaotic and random behaviors, to improve the statistical and security properties relative to each generator taken alone. This PRNG based on discrete chaotic iterations may utilize any reasonable RNG as inputs. For demonstration purposes, XORshift and ISAAC are adopted here. The PRNG with these inputs can pass all of the performed tests.

In this section, an application example is given in the field of digital watermarking: a watermark is encrypted and embedded into a cover image using chaotic iterations and our PRNG. The carrier image is the famous Lena, which is a 256 grayscale image, and the watermark is the 64 × 64 pixels binary image depicted in watermark by using chaotic iterations. The initial state x 0 of the system is constituted by the watermark, considered as a boolean vector. The iteration function is the vectorial logical negation f 0 . The PRNG presented previously is used to obtain a sequence of integers lower than 4096, which will constitute the chaotic strategy (S k ) k∈N . Thus, the encrypted watermark is the last boolean vector generated by the chaotic iterations. An example of such an encryption, with 5000 iterations, is given in Fig. 2e.

Let L be the 256 3 booleans vector constituted by the three last bits of each pixel of Lena. We define U k by U 0 = S 0 and U n+1 = S n+1 + 2 × U n + n [mod 256 3 ]. The watermarked Lena I w is obtained from the original Lena I o , the three last bits of which are replaced by the result of 64 2 chaotic iterations with initial state L, and strategy U k (see Fig. 2b). Spatial domain embedding has been chosen here for easy understanding, but this watermarking scheme can be adapted to frequency domain (for an example of its use in DWT domain, see [START_REF] Bahi | A new chaos-based watermarking algorithm[END_REF]). The extraction of the watermark can be obtained in the same way [START_REF] Bahi | A new chaos-based watermarking algorithm[END_REF]. Remark that the map θ → 2θ of the torus, which is the well-known dyadic transformation (an example of topological chaos [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF]), has been chosen to make (U k ) k 64 2 highly sensitive to the chaotic encryption strategy.

The robustness of this data hiding scheme through geometric and frequency attacks has been studied in [START_REF] Bahi | A new chaos-based watermarking algorithm[END_REF]. The chaos-security and stego-security are proven in [START_REF] Guyeux | A more secure information hiding scheme than spreadspectrum obtained by chaos-security[END_REF]. The difference with the scheme presented in these papers is the way to generate strategies, i.e., the choice of the initial conditions for chaotic iterations, in the encryption and embedding stages. This improvement does not alter robustness and subspace-security. We have shown in this study that this replacement enhances the speed of the scheme. Moreover, it resolves a potential security lack related to the use of a logistic map [1] when generating the strategies: this lack might be exploited by an attacker in Watermark-Only-Attack and Known-Message-Attack setups [START_REF] Cayre | Kerckhoffs-based embedding security classes for woa data hiding[END_REF]. Instead of logistic map, our PRNG has good statistical properties and can withstand such attacks. This claim will be deepened in future work.

Fig. 1 .

 1 Fig. 1. Security analysis

Fig. 2 .

 2 Fig. 2. Original and watermarked Lena

Table 1 .

 1 The internal state is x, the output array is r. a and b are those computed by ISAAC and XORshift generators. Lastly, c and N are constants and M = {c, c+1} (c 3N is recommended).

	S ← b mod N;
	x S ← x S ;
	end
	r ← x;
	return r;
	Algorithm 1: An arbitrary round of CI(ISAAC, XORshift)
	m :	4	5	4
	S	2 4 2 2	5 1 1 5 5	3 2 3 3
	In thisx 0	x 4	x 9	x 13
	1	1	1

Input: the internal state x (an array of N bits) Output: an array r of N bits a ← IS AAC( ); m ← a mod 2 + c; for i = 0, . . . , m do b ← XORshi f t( );

  Chaotic iterations are done with initial state x 0 , vectorial logical negation f 0 and strategy S . The result is presented in Table3. Let us recall that sequence m gives the states x n to return: x 4 , x 4+5 , x 4+5+4 , . . . So, in this example, the generated binary digits are: 10100111101111110011... Or the integers are: 20, 30, 31, 19...

	5, 4, 4, 4, 4, 5, 5, 5, 5, 4, 5, 4,...
	-S = 2, 4, 2, 2, 5, 1, 1, 5, 5, 3, 2, 3, 3,...

Table 2 .

 2 TestU01 Statistical Test

	Battery	Parameters Statistics
	Rabbit	32 × 10 9 bits	40
	Alphabit	32 × 10 9 bits	17
	Pseudo DieHARD	Standard	126
	FIPS 140 2	Standard	16
	Small Crush	Standard	15
	Crush	Standard	144
	Big Crush	Standard	160

  The DieHARD suites, which implement many classical RNG tests, have some drawbacks and limitations. The National Institute of Standards and Technology (NIST), in the United States, has implemented a test suite (16 tests) for RNGs. It is geared mainly for the testing and certification of RNGs used in cryptographic applications. TestU01 is extremely diverse in implementing classical tests, cryptographic tests, new tests proposed in the literature, and original tests. In fact, it encompasses most of the other test suites.

Table 2

 2 lists seven batteries of tests in the TestU01 package. "Standard" parameter in this Table refers to the built-in parameters of the battery. TestU01 suite implements 518 tests and reports p-values. If a p-value is within [0.001, 0.999], the associated test is a success. A p-value lying outside this boundary means that its test has failed.

Conclusions and future work

In this paper, the PRNG proposed in [17] is improved. This is achieved by using the famous ISAAC and XORshift generators and by combining these components with chaotic iterations. Thus we obtain a faster generator which satisfies chaotic properties. In addition to passing the NIST tests suite, this new generator successfully passes all the stringent TestU01 battery of tests. The randomness and disorder generated by this algorithm has been evaluated. It offers a sufficient level of security for a whole range of applications in computer science. An application example in the field of data hiding is finally given. In future work, the comparison of different chaotic strategies will be explored and other iteration functions will be studied. Finally, other applications in computer science security field will be proposed, especially in cryptographic domains.


Christophe Guyeux
email: christophe.guyeux@univ-fcomte.fr

Qianxue Wang
email: qianxue.wang@univ-fcomte.fr

Jacques M Bahi
email: jacques.bahi@univ-fcomte.fr

Improving random number generators by chaotic iterations Application in data hiding

Keywords: Topological chaos, Pseudo-random number generator, Statistical tests, Internet security, data hiding, Discrete chaotic iterations

In this paper, a new pseudo-random number generator (PRNG) based on chaotic iterations is proposed. This method also combines the digits of two XORshifts PRNGs. The statistical properties of this new generator are improved: the generated sequences can pass all the DieHARD statistical test suite. In addition, this generator behaves chaotically, as defined by Devaney. This makes our generator suitable for cryptographic applications. An illustration in the field of data hiding is presented and the robustness of the obtained data hiding algorithm against attacks is evaluated.

I. INTRODUCTION

A pseudo-random number generator (PRNG) is an algorithm for generating a sequence of numbers that is supposed to be indistinguishable from a uniformly chosen random sequence [START_REF] Diro | Comparison of point sets and sequences for quasi-monte carlo and for random number generation[END_REF]. The sequence is not truly random in that it is completely determined by a relatively small set of initial values, called the PRNG's seed. Compare to hardware-based approaches, these PRNGs must be easy to generate and process, but are less closer to truly random behavior. PRNGs play an important role in practice for a whole range of applications such as information security, statistics (samplings, simulations and Monte-Carlo techniques), video games and gambling machines, to name a few [START_REF] Gonzaleza | Statistical complexity measure of pseudorandom bit generators[END_REF]. These PRNGs are often based on logical operations like bitwise exclusive or (XOR) and on circular shift of bit vectors. XORshift, designed by George Marsaglia [START_REF] Marsaglia | Xorshift rngs[END_REF], is a popular example of such generators. However, the security level of some PRNGs of this kind has been revealed to be inadequate by today's standards. We investigated whether it would be possible to combine two generators in some way that would give better properties than the individual components alone. This paper extends the study started in [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF] and [START_REF] Wang | A novel pseudo-random generator based on discrete chaotic iterations for cryptographic applications[END_REF]. In [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF], it is proven that chaotic iterations (CIs), a suitable tool for fast computing iterative algorithms, satisfies the chaos property, as it is defined by Devaney [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF]. In [START_REF] Wang | A novel pseudo-random generator based on discrete chaotic iterations for cryptographic applications[END_REF], the chaotic behavior of CIs are exploited in order to obtain an unpredictable PRNG. This generator, based on chaotic iterations, depends on two input sequences. In [START_REF] Wang | A novel pseudo-random generator based on discrete chaotic iterations for cryptographic applications[END_REF], these two sequences are constituted by two logistic maps. This novel generator has successfully passed the NIST (National Institute of Standards and Technology of the U.S. Government) battery of tests [10]. In this new paper, we achieve to improve the speed of the former PRNG, by using two XORshifts in place of the logistic map. In addition, this new version of our PRNG is able to pass the famous DieHARD statistical battery of tests [START_REF] Marsaglia | Diehard: a battery of tests of randomness[END_REF]. And its security is improved compared to XORshift alone, and to our former PRNG. After presenting the theoretical framework of the study, a concrete example of how to use these pseudo-random numbers in the field of data hiding is detailed. An analysis focuses on the watermarked images which have already been subjected to common image distortion attacks. It is shown that sequences generated from this generator have a good robustness in the presence of such attacks. The rest of this paper is organized in the following way: in Section II, some basic definitions concerning chaotic iterations and PRNGs are recalled. Then, the generator based on discrete chaotic iterations is presented in Section III. In Section IV, we show that the proposed PRNG passes the DieHARD statistical tests. In Sections V and VI, there is a discussion on a potential application scenario to watermarking. Finally, some conclusions and future work are drawn in Section VII.

II. BASIC RECALLS

This section is devoted to basic notations and terminologies in the fields of chaotic iterations and PRNGs.

A. Notations

1; N → {1, 2, . . . , N} s n → the n th term of a sequence s = (s 1 , s 2 , . . .)

v i → the i th component of an array v = (v 1 , v 2 , . . .) f k → k th composition of a function f f k = f • ... • f
k times strategy → a sequence which elements belong in 1; N S → the set of all strategies ⊕ → bitwise exclusive or + → the integer addition ≪ and ≫→ the usual shift operators

B. Chaotic iterations

Definition 1 The set B denoting {0, 1}, let f : B N -→ B N be an "iteration" function and S ∈ S be a chaotic strategy. Then, the so-called chaotic iterations are defined by

x 0 ∈ B N , ∀n ∈ N * , ∀i ∈ 1; N , x n i = x n-1 i if S n i f (x n-1 ) S n if S n = i. (1)
In other words, at the n th iteration, only the S n -th cell is "iterated". Note that in a more general formulation, S n can be a subset of components and f (x n-1 ) S n can be replaced by f (x k ) S n (where k < n), thus describing for example, delays due to transmissions (see e.g. [1]). For the general definition of such chaotic iterations, see, e.g. [START_REF] Robert | Discrete Iterations. A Metric Study[END_REF]. Chaotic iterations generate a set of vectors (boolean vector in this paper), they are defined by an initial state x 0 , an iteration function f and a chaotic strategy S .

C. XORshift

XORshift is a category of very fast PRNGs designed by George Marsaglia [START_REF] Marsaglia | Xorshift rngs[END_REF]. It repeatedly uses the exclusive or (XOR) on a number, with a bit shifted copy of itself by a positions either to the right or to the left, where 0 < a < w and w = 32 or 64. The initial state of a XORshift generator is a given vector of bits. At each step, the next state is obtained by applying a given number of XORshift operations as defined in Algorithm 1. This algorithm has a period of 2 32 -1 = 4.29×10 9 .

Input: x (a 32-bit word) Output: r (a 32-bit word)

x ← x ⊕ (x ≪ 13); x ← x ⊕ (x ≫ 17); x ← x ⊕ (x ≪ 5); r ← x; return r;
Algorithm 1: An arbitrary round of XORshift

D. Input sequences

In [START_REF] Wang | A novel pseudo-random generator based on discrete chaotic iterations for cryptographic applications[END_REF], we have used two logistic maps [START_REF] Ulam | On combination of stochastic and deterministic processes[END_REF] as input sequences to define a novel PRNG (called CI PRNG) based on chaotic iterations. We have mathematically proven that it behaves chaotically, as defined by Devaney. In addition, this generator can successfully pass the NIST tests suite. However, chaotic systems like logistic maps work the real numbers domain, and therefore a transformation from real numbers into integers is needed. This process leads to a degradation of the chaotic behavior of the generator and a lot of time wasted during computations [START_REF] Kanso | Logistic chaotic maps for binary numbers generations[END_REF]. Our purpose is then to improve the speed of this former generator and grant its chaotic properties by using a faster PRNG, namely XORshift. Moreover, we will show in Section IV-B that this new generator can pass the famous DieHARD battery of tests.

III. THE GENERATION OF CI PSEUDO-RANDOM SEQUENCE

The design of the PRNG based on discrete chaotic iterations is proposed in this section, while its performance is evaluated in the next one.

A. Chaotic iterations as PRNG

The novel generator is designed by the following process. Let N ∈ N * , N 2. Some chaotic iterations are done, which generate a sequence (x n ) n∈N ∈ B N N of boolean vectors: the successive states of the iterated system. Some of those vectors are chaotically extracted and their components constitute our pseudo-random bit flow. Chaotic iterations are realized as follows: initial state x 0 ∈ B N is a boolean vector taken as a seed and chaotic strategy (S n ) n∈N ∈ 1, N N is constructed with XORshift. Lastly, iterate function f is the vectorial boolean negation

f 0 : (x 1 , ..., x N ) ∈ B N -→ (x 1 , ..., x N ) ∈ B N .
To sum up, at each iteration, only S i -th component of state x n is updated as follows

x n i =            x n-1 i if i S i , x n-1 i if i = S i . (2)
Finally, let M be a finite subset of N * . Some x n are selected by a sequence m n as the pseudo-random bit sequence of our generator. The sequence (m n ) n∈N ∈ M N is computed with XORshift. So, the generator returns the following values:

• the components of x m 0 ,

• following by the components of x m 0 +m 1 ,

• following by the components of x m 0 +m 1 +m 2 ,

• etc. In other words, the generator returns the following bits:

x m 0 1 x m 0 2 x m 0 3 . . . x m 0 N x m 0 +m 1 1 x m 0 +m 1 2 . . . x m 0 +m 1 N x m 0 +m 1 +m 2 1 x m 0 +m 1 +m 2 2
. . . and its k th bit is equal to

x ⌊k/N⌋ i=0 m i k+1 (mod N) .
The basic design procedure of the novel generator is summed up in Algorithm 2. The internal state is x, the output array is r; a and b are those computed by the two XORshift generators. Lastly, c and N are constants and M = {c,c+1} (c 3N is recommended).

Input: the internal state x (x is an array of N 1-bit words) Output: an array r of N 1-bit words a ← XORshi f t1(); m ← a mod 2 + c; for i = 0, . . . , m do b ← XORshi f t2(); S ← b mod N; x S ← x S ; end r ← x; return r;
Algorithm 2: An arbitrary round of CI generator

B. Example

In this example, N = 5 and M = {4,5} are adopted for easy understanding. The initial state of the system x 0 can be seeded by the decimal part of the current time. For example, the current time in seconds since the Epoch is 1237632934.484084, so t = 484084. x 0 = t (mod 32) in binary digits, then x 0 = (1, 0, 1, 0, 0). m and S can now be computed from two XORshift PRNGs: m = 4, 5, 4, 4, 4, 4, 5, 5, 5, 5, 4, 5, 4,... S = 2, 4, 2, 2, 5, 1, 1, 5, 5, 3, 2, 3, 3,... Chaotic iterations are made with initial state x 0 , vectorial logical negation f 0 and strategy S . The result is presented in Table I. Let us recall that sequence m gives the states x n to return: x 4 , x 4+5 , x 4+5+4 , . . . So, in this example, the output of the generator is: 10100111101111110011...

x 0 x 4 x 9 x 13 1 1 1 - → 0 1 -→ 1 1 1 0 2 - → 1 2 - → 0 2 - → 1 1 1 2 -→ 0 0 1 1 1 3 -→ 0 3 -→ 1 3 -→ 0 0 0 4 - → 1 1 1 1 0 0 5 - → 1 5 -→ 0 5 -→ 1 1 1 Output: x 0 1 x 0 2 x 0 3 x 0 4 x 0 5 x 4 1 x 4 2 x 4 3 x 4 4 x 4 5 x 9 1 x 9 2 x 9 3 x 9 4 x 9 5
x 13 1 x 13 2 x 13 3 x 13 4 x 13 5 ... = 10100111101111110011...

C. Chaotic properties

Despite a large number of papers published in the field of chaos-based PRNGs, the impact that this research has made on conventional information security is rather marginal. This is due to the following reasons: almost all chaotic algorithms are based on dynamical systems defined on the set of real numbers. So these generators are usually slow, require considerably more storage space and lose some of their chaotic properties during computations. These major problems restrict their use in security fields as cryptography [START_REF] Kocarev | Chaos-based cryptography: a brief overview[END_REF]. The PRNG proposed in this paper does not inherit its chaotic properties from a real chaotic map, but from chaotic iterations defined in Section II-B. It has been proven in [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF] that CIs behave as chaos, as it is defined by Devaney: they are regular, transitive and sensitive to initial conditions. This most famous definition of chaotic behavior for a dynamical system implies various desired properties in information security, such as: unpredictability, mixture, sensitivity, and uniform repartition. The principal interest of CIs is that they can be used without real numbers. Indeed, the sequence inputed in chaotic iterations constitutes a coordinate of its initial state, and the chaotic behavior of a dynamical system does not depend on this initial state. So if we take integer sequences as input instead, then CIs become faster while preserving their chaotic properties. This allows the conception of a new generation of fast and chaotic PRNGs IV. TESTING A GENERATOR Here, the empirical tests have been carried out, making use of the DieHARD statistical test suite. In this section we will briefly review the approach taken together with key results and conclusions. It is not our intention to document these tests in detail in the present section, since it has been done several times in many other papers [START_REF] Marsaglia | Diehard: a battery of tests of randomness[END_REF], [START_REF] Tan | Randomness quality of permuted pseudorandom binary sequences[END_REF], [START_REF] Turan | On independence and sensitivity of statistical randomness tests[END_REF].

A. DieHARD battery of tests

DieHARD battery of tests has been a stringent standard for evaluating PRNGs for over a decade. Passing this battery is considered as a good rule of thumb to validate a PRNG. DieHARD battery consists of 18 different independent statistical tests. This collection of tests is based on assessing the randomness of bits comprising 32-bit integers obtained from a random number generator. Each test requires 2 23 32-bit integers in order to run the full set of tests. Most of the tests in DieHARD return a p-value, which should be uniform on [0, 1) if the input file contains truly independent random bits. Those p-values are obtained by p = F(X), where F is the assumed distribution of the sample random variable X-often supposed as normal distribution. But that assumed F is just an asymptotic approximation, for which the fit will be worst in the tails. Thus occasional p-values near 0 or 1, such as 0.0012 or 0.9983, are not surprising. An individual test is considered to be a failure if its p-value approaches 1 more closely, for example p > 0.9999.

B. Analysis

Table II gives the results derived from applying the DieHARD battery of tests to the RNGs considered in this work. As it can be observed, the results of the individual tests Count the ones 1, Binary Rank 31 × 31 and Binary Rank 32 × 32 show that in the random numbers obtained with the XORshift generator only the least significant bits seem to be independent. This explains the poor behavior of this RNG in the aforementioned basic tests that evaluate the independence of real numbers. But the generator based on discrete chaotic iterations can pass all the DieHARD battery of tests. This proves that the security of the given generator has been improved by CIs.

V. APPLICATION EXAMPLE IN DIGITAL WATERMARKING

Information hiding has recently become a major information security technology, especially with the increasing importance and widespread distribution of digital media through the Internet [START_REF] Wu | A novel digital watermark algorithm based on chaotic maps[END_REF]. It includes several techniques like digital watermarking. The aim of digital watermarking is to embed a piece of information into digital documents, such as pictures or movies. This is for a large panel of reasons, such as: copyright protection, control utilization, data description, content authentication, and data integrity. For these reasons, many different watermarking schemes have been proposed in recent years. Digital watermarking must have essential characteristics, including: security, imperceptibility, and robustness. Chaotic methods have been proposed to encrypt the watermark before embedding it in the carrier image for these security reasons. In this paper, a new watermarking algorithm is given. It is based on the chaotic PRNG presented above.

A. Most and least significant coefficients

Let us first introduce the definitions of most and least significant coefficients. Definition 2 For a given image, the most significant coefficients (in short MSCs), are coefficients that allow the description of the relevant part of the image, i.e. its most rich part (in terms of embedding information), through a sequence of bits.

For example, in a spatial description of a grayscale image, a definition of MSCs can be the sequence constituted by the first three bits of each pixel as shown in Fig. 1(a). In a discrete cosine frequency domain description, each 8 × 8 block of the carrier image is mapped to a list of 64 coefficients. The energy of the image is contained in the first of them. After binary conversion, the first fourth coefficients of all these blocks can constitute a possible sequence of MSCs.

Definition 3 By least significant coefficients (LSCs), we mean a translation of some insignificant parts of a medium in a sequence of bits (insignificant can be understand as: "which can be altered without sensitive damages").

These LSCs can be for example, the last three bits of the gray level of each pixel, in the case of a spatial domain watermarking of a grayscale image, as in Fig. 1 Fourier, and wavelet transform can be used to define LSCs and MSCs, in the case of frequency domain watermarking, among other possible choices. Moreover, these definitions are not limited to image media, but can easily be extended to the audio and video media as well.

LSCs are used during the embedding stage: some of the least significant coefficients of the carrier image will be chaotically chosen and replaced by the bits of the mixed watermark. With a large number of LSCs, the watermark can be inserted more than once and thus the embedding will be more secure and robust, but also more detectable.

The MSCs are only useful in the case of authentication: encryption and embedding stages depend on them. Hence, a coefficient should not be defined at the same time, as a MSC and a LSC; the last can be altered, while the first is needed to extract the watermark.

B. Stages of the algorithm

Our watermarking scheme consists of two stages: (1) mixture of the watermark and (2) its embedding.

1) Watermark mixture.: Firstly, for safety reasons, the watermark can be mixed before its embedding into the image. A common way to achieve this stage is to use the bitwise exclusive or (XOR), for example, between the watermark and the above PRNG. In this paper, we will use another mixture scheme based on chaotic iterations. Its chaotic strategy, defined with our PRNG, will be highly sensitive to the MSCs, in the case of an authenticated watermark, as stated in [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF].

2) Watermark embedding.: Some LSCs will be substituted by all bits of the possibly mixed watermark. To choose the sequence of LSCs to be altered, a number of integers, less than or equal to the number N of LSCs corresponding to a chaotic sequence U k k , is generated from the chaotic strategy used in the mixture stage. Thus, the U k -th least significant coefficient of the carrier image is substituted by the k th bit of the possibly mixed watermark. In the case of authentication, such a procedure leads to a choice of the LSCs which are highly dependent on the MSCs. For the detail of this stage see Section VI-A2.

3) Extraction.: The chaotic strategy can be regenerated, even in the case of an authenticated watermarking because the MSCs have not been changed during the stage of embedding the watermark. Thus, the few altered LSCs can be found, the mixed watermark can then be rebuilt, and the original watermark can be obtained. If the watermarked image is attacked, then the MSCs will change. Consequently, in the case of authentication and due to the high sensitivity of the embedding sequence, the LSCs designed to receive the watermark will be completely different. Hence, the result of the recovery will have no similarity with the original watermark: authentication is reached.

VI. EVALUATION OF ROBUSTNESS

In this section, a complete application example of the above chaotic watermarking method is given and its robustness to some attacks is studied. This case study enables us to precise the details of the algorithm and evaluate it. pixels binary image depicted in Fig. 2(a). The embedding domain will be the spatial domain. The selected MSCs are the four most significant bits of each pixel and the LSCs are the three last bits (a given pixel will at most be modified of four levels of gray by an iteration). Before its embedment, the watermark is mixed with chaotic iterations. The system to iterate, chaotic strategy S n and iterate function are defined below. 2) Embedding of the watermark.: To embed the watermark, the sequence (U k ) k∈N of altered bits taken from the M LSCs must be defined. To do so, the strategy (S k ) k∈N of the encryption stage is used as follows

U 0 = S 0 U n+1 = S n+1 + 2 × U n + n (mod M) (3)
to obtain the result depicted in Fig. 2(b). The map θ → 2θ of the torus, which is a famous example of topological Devaney's chaos [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF], has been chosen to make (U k ) k∈N highly sensitive to the chaotic strategy (S k ) . As a consequence, (U k ) k∈N is highly sensitive to the alteration of the MSCs. In case of authentication, any significant modification of the watermarked image will lead to a completely different extracted watermark.

B. Simulation results

To prove the efficiency and the robustness of the proposed algorithm, some attacks are applied to our chaotically watermarked image. For each attack, a similarity percentage with the original watermark is computed. This percentage is the number of equal bits between the original and the extracted watermark, shown as a percentage. A result less than or equal to 50% implies that the image has probably not been watermarked.

1) Cropping attack: In this kind of attack, a watermarked image is cropped. In this case, the results in Table III In Fig. 3, the decrypted watermarks are shown after a crop of 50 pixels and after a crop of 10 pixels, in the authentication case. By analyzing the similarity percentage between the original and the extracted watermark, we can conclude that in the case of unauthentication, the watermark still remains after a cropping attack. The desired robustness is reached. It can be noticed that cropping sizes and percentages are rather proportional. In the case of authentication, even a small change of the carrier image (a crop by 10 × 10 pixels) leads to a really different extracted watermark. In this case, any attempt to alter the carrier image will be signaled, thus the image is well authenticated.

2) Rotation attack: Let r θ be the rotation of angle θ around the center (128, 128) of the carrier image. So, the transformation r -θ • r θ is applied to the watermarked image. The results in Table IV have been obtained. The same conclusion as above can be declaimed.

3) JPEG compression: A JPEG compression is applied to the watermarked image, depending on a compression level. This attack leads to a change of the representation domain (from spatial to DCT domain). In this case, the results in Table V have been obtained, illustrating a good authentication through JPEG attack. As for the unauthentication case, the watermark still remains after a compression level equal to 10. This is a good result if we take into account the fact that we use spatial embedding. 4) Gaussian noise: A watermarked image can be also attacked by the addition of a Gaussian noise, depending on a standard deviation. In this case, the results in Table VI are obtained.

VII. CONCLUSIONS AND FUTURE WORK

In this paper, the PRNG proposed in [START_REF] Wang | A novel pseudo-random generator based on discrete chaotic iterations for cryptographic applications[END_REF] is improved, by using the famous XORshift generator. By combining these components with chaotic iterations, we define a faster generator with chaotic properties. In addition to achieving the NIST tests suite, this new generator successfully passes all the stringent DieHARD battery of tests. The randomness and disorder generated by this algorithm has been evaluated. It offers a sufficient level of security for a whole range of computer usages. An application example in the field of data hiding is given and its robustness through attacks is studied. In future work, the speed of our generator will be improved again, the comparison of different chaotic strategies will be explored, and other iteration functions will be studied. Finally, new applications in computer science security field will be proposed.

  Fig. 1. Spatial MSCs and LSCs of Lena.

A. Stages and details 1 )

 1 Images description.: Carrier image is Lena, a 256 grayscale image of size 256×256. The watermark is the 64×64

  Watermarked Lena (c)Differences with original.

Fig. 2 .

 2 Fig. 2. Watermarked Lena and differences

  (a) Unauthentication (10 × 10). (b) Authentication (10 × 10). (c) Unauthentication (50 × 50).

Fig. 3 .

 3 Fig. 3. Extracted watermark after a cropping attack.