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

Xiaole Fang
email: xiaole.fang@univ-fcomte.fr

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

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

Evaluating Quality of Chaotic Pseudo-Random Generators: Application to Information Hiding

Keywords: Internet security, Pseudo-random number generator, Chaotic sequences, Statistical tests, Discrete chaotic iterations, Information hiding

Guaranteeing the security of information transmitted through the Internet, against passive or active attacks, is a major concern. The discovery of new pseudo-random number generators with a strong level of security is a field of research in full expansion, due to the fact that numerous cryptosystems and data hiding schemes are directly dependent on the quality of these generators. At the conference Internet'09, we described a generator based on chaotic iterations which behaves chaotically as defined by Devaney. In this paper which is an extension of the work presented at the conference Internet'10, the proposal is to improve the speed, the security, and the evaluation of this generator, to make its use more relevant in the Internet security context. In order to do so, a comparative study between various generators is carried out and statistical results are improved. Finally, an application in the information hiding framework is presented with details, to give an illustrative example of the use of such a generator in the Internet security field.

I. INTRODUCTION

Due to the rapid development of the Internet in recent years, the need to find new tools to reinforce trust and security through the Internet has become a major concern. Its recent role in everyday life implies the need to protect data and privacy in digital world. This extremely rapid development of the Internet brings more and more attention to the information security techniques in all kinds of applications. For example, new security concerns have recently appeared because of the evolution of the Internet to support such activities as e-Voting, VoD (Video on demand), and the protection of intellectual property. In all these emerging techniques, pseudo-random number generators (PRNG) play an important role, because they are fundamental components of almost all cryptosystems and information hiding schemes [START_REF] Tong | Image encryption scheme based on 3d baker with dynamical compound chaotic sequence cipher generator[END_REF], [START_REF] Erclebi | Robust multi bit and high quality audio watermarking using pseudo-random sequences[END_REF]. PRNGs are typically defined by a deterministic recurrent sequence in a finite state space, usually a finite field or ring, and an output function mapping each state to an input value. Following [START_REF]Comparison of point sets and sequences for quasi-monte carlo and for random number generation[END_REF], this value is often either a real number in the interval (0, 1) or an integer in some finite range. PRNGs based on linear congruential methods and feedback shift-registers are popular for historical reasons [START_REF] Knuth | The Art of Computer Programming[END_REF], but their security level often has been revealed to be inadequate by today's standards. However, to use a PRNG with a high level of security is a necessity to protect the information contents sent through the Internet. This level depends both on theoretical properties and on statistical tests.

Many PRNGs have already been proven to be secure following a probabilistic approach [START_REF] Marchi | Polynomial pseudo-random number generator via cyclic phase[END_REF], [START_REF] Sachez | A generator of pseudo-random numbers sequences with a very long period[END_REF], [START_REF] Tan | The plfg parallel pseudo-random number generator[END_REF]. However, their performances must regularly be improved, among other things by using new mathematical tools. This is why the idea of using chaotic dynamical systems for this purpose has recently been explored [START_REF] Falcioni | Properties making a chaotic system a good pseudo random number generator[END_REF], [START_REF] Cecen | A new hybrid nonlinear congruential number generator based on higher functional power of logistic maps[END_REF]. The random-like and unpredictable dynamics of chaotic systems, their inherent determinism and simplicity of realization suggest their potential for exploitation as PRNGs. Such generators can strongly improve the confidence put in any information hiding scheme and in cryptography in general: due to their properties of unpredictability, the possibilities offered to an attacker to achieve his goal are drastically reduced in that context. For example, in cryptography, keys are needed to be unpredictable enough, to make sure any search optimization based on the reduction of the key space to the most probable values is impossible to work on. But the number of generators claimed as chaotic, which actually have been proven to be unpredictable (as it is defined in the mathematical theory of chaos) is very small.

II. OUTLINE OF OUR WORK

This paper extends the study initiated in [START_REF] Wang | Randomness quality of CI chaotic generators. application to internet security[END_REF], [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF], [START_REF] Wang | A novel pseudo-random generator based on discrete chaotic iterations for cryptographic applications[END_REF], and tries to fill this gap. In [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF], it is mathematically proven that chaotic iterations (CIs), a suitable tool for fast computing distributed algorithms, satisfies the topological chaotic property, following the definition given by Devaney [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF]. In the paper [START_REF] Wang | A novel pseudo-random generator based on discrete chaotic iterations for cryptographic applications[END_REF] presented at Internet'09, the chaotic behavior of CIs is exploited in order to obtain an unpredictable PRNG that depends on two logistic maps. We have shown that, in addition to being chaotic, this generator can pass the NIST (National Institute of Standards and Technology of the U.S. Government) battery of tests [START_REF] Publication | A statistical test suite for random and pseudorandom number generators for cryptographic applications[END_REF], widely considered as a comprehensive and stringent battery of tests for cryptographic applications. In this paper, which is an extension of [START_REF] Wang | Randomness quality of CI chaotic generators. application to internet security[END_REF], we have improved the speed, security, and evaluation of the former generator and of its application in information hiding. 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 characteristics and is capable to withstand attacks. After having presented the theoretical framework of the study and a security analysis, we will give a comparison based on statistical tests. Finally a concrete example of how to use these pseudo-random numbers for information hiding through the Internet is detailed.

The remainder of this paper is organized in the following way. In Section III, some basic definitions concerning chaotic iterations and PRNGs are recalled. Then, the generator based on discrete chaotic iterations is presented in Section IV. Section V is devoted to its security analysis. In Section VI, various tests are passed with a goal to achieve a statistical comparison between this new PRNG and other existing ones.

In Section VII, a potential use of this PRNG in some Internet security field is presented, namely in information hiding. The paper ends with a conclusion and intended future work.

III. REVIEW OF BASICS

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 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 C k n → the binomial coefficient n k = n! k!(n-k)!

⊕

→ bitwise exclusive or + → the integer addition ≪ and ≫→ the usual shift operators (X , d) → a metric space mod → a modulo or remainder operator ⌊x⌋→ returns the highest integer smaller than

x n! → the factorial n! = n × (n -1) × • • • × 1 N * → the set of positive integers {1,2,3,...}

B. XORshift

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

Input: the internal state z (a 32-bit word) Output: y (a 32-bit word)

z ← z ⊕ (z ≪ 13); z ← z ⊕ (z ≫ 17); z ← z ⊕ (z ≪ 5); y ← z; return y;

C. Continuous Chaos in Digital Computers

In the past two decades, the use of chaotic systems in the design of cryptosystems, pseudo-random number generators (PRNG), and hash functions, has become more and more frequent. Generally speaking, the chaos theory in the continuous field is used to analyze performances of related systems. However, when chaotic systems are realized in digital computers with finite computing precisions, it is doubtful whether or not they can still preserve the desired dynamics of the continuous chaotic systems. Because most dynamical properties of chaos are meaningful only when dynamical systems evolve in the continuous phase space, these properties may become meaningless or ambiguous when the phase space is highly quantized (i.e., latticed) with a finite computing precision (in other words, dynamical degradation of continuous chaotic systems realized in finite computing precision). When chaotic systems are realized in finite precision, their dynamical properties will be deeply different from the properties of continuous-value systems and some dynamical degradation will arise, such as short cycle length and decayed distribution. This phenomenon has been reported and analyzed in various situations [START_REF] Binder | Simulating chaotic behavior with finitestate machines[END_REF], [START_REF] Wheeler | Problems with chaotic cryptosystems[END_REF], [START_REF] Palmore | Computer arithmetic, chaos and fractals[END_REF], [START_REF] Blank | Discreteness and continuity in problems of chaotic dynamics[END_REF], [START_REF] Li | On the dynamical degradation of digital piecewise linear chaotic maps[END_REF].

Therefore, continuous chaos may collapse into the digital world and the ideal way to generate pseudo-random sequences is to use a discrete-time chaotic system.

D. Chaos for Discrete Dynamical Systems

Consider a metric space (X , d) and a continuous function f : X -→ X , for one-dimensional dynamical systems of the form:

x 0 ∈ X and ∀n ∈ N * , x n = f (x n-1 ),

the following definition of chaotic behavior, formulated by Devaney [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF], is widely accepted:

Definition 1 A dynamical system of Form ( 1) is said to be chaotic if the following conditions hold.

• Topological transitivity:

∀U, V open sets of X \ ∅, ∃k > 0, f k (U ) ∩ V = ∅ (2)
• Density of periodic points in X : Let P = {p ∈ X |∃n ∈ N * : f n (p) = p} the set of periodic points of f . Then P is dense in X :

P = X (3)
• Sensitive dependence on initial conditions: ∃ε > 0, ∀x ∈ X , ∀δ > 0, ∃y ∈ X , ∃n ∈ N, d(x, y) < δ and d (f n (x), f n (y)) ε.

When f is chaotic, then the system (X , f ) is chaotic and quoting Devaney: "it is unpredictable because of the sensitive dependence on initial conditions. It cannot be broken down or decomposed into two subsystems which do not interact because of topological transitivity. And, in the midst of this random behavior, we nevertheless have an element of regularity." Fundamentally different behaviors are consequently possible and occur in an unpredictable way.

E. Discrete Chaotic Iterations

Definition 2 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 [START_REF] Robert | Discrete Iterations. A Metric Study[END_REF] are defined by x 0 ∈ B N and

∀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. (4)
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, describing for example delays transmission. 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.

The next section gives the outline proof that chaotic iterations satisfy Devaney's topological chaos property. Thus they can be used to define a chaotic pseudo-random bit generator.

IV. THE GENERATION OF CI PSEUDO-RANDOM SEQUENCE

A. A Theoretical Proof for Devaney's Chaotic Dynamical Systems

The outline proofs, of the properties on which our pseudorandom number generator is based, are given in this section.

Denote by δ the discrete Boolean metric, δ(x, y) = 0 ⇔ x = y. Given a function f , define the function

F f : 1; N ×B N -→ B N such that F f (k, E) = E j .δ(k, j) + f (E) k .δ(k, j) j∈ 1;N
, where + and . are the Boolean addition and product operations.

Consider the phase space: X = 1; N N × B N and the map

G f (S, E) = (σ(S), F f (i(S), E)) ,
then the chaotic iterations defined in (III-E) can be described by the following iterations [11]

X 0 ∈ X X k+1 = G f (X k ).
Let us define a new distance between two points (S, E), ( Š, Ě) ∈ X by

d((S, E); ( Š, Ě)) = d e (E, Ě) + d s (S, Š),
where

• d e (E, Ě) = N k=1 δ(E k , Ěk ) ∈ 0; N • d s (S, Š) = 9 N ∞ k=1 |S k -Šk | 10 k ∈ [0; 1].
It is then proven in [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF] by using the sequential continuity that Proposition 1 G f is a continuous function on (X , d).

Then, the vectorial negation f 0 (x 1 , . . . , x N ) = (x 1 , . . . , x N ) satisfies the three conditions for Devaney's chaos, namely, regularity, transitivity, and sensitivity in the metric space (X , d). This leads to the following result.

Proposition 2 G f0 is a chaotic map on (X , d) in the sense of Devaney.

B. Chaotic Iterations as Pseudo-Random Generator 1) Presentation:

The CI generator (generator based on chaotic iterations) is designed by the following process. First of all, some chaotic iterations have to be done to generate a sequence (x n ) n∈N ∈ B N N (N ∈ N * , N 2, N is not necessarily equal to 32) of Boolean vectors, which are the successive states of the iterated system. Some of these vectors will be randomly extracted and our pseudo-random bit flow will be constituted by their components. Such chaotic iterations are realized as follows. Initial state x 0 ∈ B N is a Boolean vector taken as a seed (see Section IV-B2) and chaotic strategy (S n ) n∈N ∈ 1, N N is an irregular decimation of a XORshift sequence (Section IV-B4). The iterate function f is the vectorial Boolean negation:

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

x n i = x n-1 i if i = S i , else x n i = x n-1 i
. Finally, some x n are selected by a sequence m n as the pseudorandom bit sequence of our generator. (m n ) n∈N ∈ M N is computed from a XORshift sequence (y n ) n∈N ∈ 0, 2 32 -1 (see Section IV-B3). So, the generator returns the following values: 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 . . .
or States:

x m 0 x m 0 +m 1 x m 0 +m 1 +m 2 . . .
2) The seed: The unpredictability of random sequences is established using a random seed that is obtained by a physical source like timings of keystrokes. Without the seed, the attacker must not be able to make any predictions about the output bits, even when all details of the generator are known [START_REF] Turan | On independence and sensitivity of statistical randomness tests[END_REF].

The initial state of the system x 0 and the first term y 0 of the XORshift are seeded either by the current time in seconds since the Epoch, or by a number that the user inputs. Different ways are possible. For example, let us denote by t the decimal part of the current time. So x 0 can be t (mod 2 N ) written in binary digits and y 0 = t.

3) Sequence m of returned states: The output of the sequence (y n ) is uniform in 0, 2 32 -1 , because it is produced by a XORshift generator. However, we do not want the output of (m n ) to be uniform in 0, N , because in this case, the returns of our generator will not be uniform in 0, 2 N -1 , as it is illustrated in the following example. Let us suppose that x 0 = (0, 0, 0). Then m 0 ∈ 0, 3 .

• If m 0 = 0, then no bit will change between the first and the second output of our PRNG. Thus x 1 = (0, 0, 0). • If m 0 = 1, then exactly one bit will change, which leads to three possible values for x 1 , namely (1, 0, 0), (0, 1, 0), and (0, 0, 1). • etc. As each value in 0, 2 3 -1 must be returned with the same probability, then the values (0, 0, 0), (1, 0, 0), (0, 1, 0), and (0, 0, 1) must occur for x 1 with the same probability. Finally we see that, in this example, m 0 = 1 must be three times more probable than m 0 = 0. This leads to the following general definition for m:

m n = g 1 (y n ) =                  0 if 0 y n 2 32 < C 0 N 2 N , 1 if C 0 N 2 N y n 2 32 < 1 i=0 C i N 2 N , 2 if 1 i=0 C i N 2 N y n 2 32 < 2 i=0 C i N 2 N , . . . . . . N if N-1 i=0 C i N 2 N y n 2 32 < 1. (5)
In order to evaluate our proposed method and compare its statistical properties with various other methods, the density histogram and intensity map of adjacent outputs have been computed. The length of x is N = 4 bits, and the initial conditions and control parameters are the same. A large number of sampled values are simulated (10 6 samples). Figure 1(a) shows

(a) m n = f (y n ) (b) m n = y n mod 4
Fig. 1: Histogram and intensity maps the intensity map for m n = g 1 (y n ). In order to appear random, the histogram should be uniformly distributed in all areas. It can be observed that a uniform histogram and a flat color intensity map are obtained when using our scheme. Another illustration of this fact is given by Figure 1(b), whereas its uniformity is further justified by the tests presented in Section VI.

4) Chaotic strategy: The chaotic strategy

(S k ) ∈ 1, N N is generated from a second XORshift sequence (b k ) ∈ 1, N N .
The only difference between the sequences S and b is that some terms of b are discarded, in such a way that ∀k ∈ N, (S M k , S M k +1 , . . . , S M k+1 -1 ) does not contain any given integer twice, where M k = k i=0 m i . Therefore, no bit will change more than once between two successive outputs of our PRNG, increasing the speed of the former generator by doing so. S is said to be "an irregular decimation" of b. This decimation can be obtained by the following process.

Let (d 1 , d 2 , . . . , d N ) ∈ {0, 1} N be a mark sequence, such that whenever N i=1 d i = m k , then ∀i, d i = 0 (∀k, the sequence is reset when d contains m k times the number 1). This mark sequence will control the XORshift sequence b as follows: To check the balance property, a set of 500 sequences are generated with and without decimation, each sequence containing 10 6 bits. Figure 2 shows the percentages of differences between zeros and ones, and presents a better balance property for the sequences with decimation. This claim will be verified in the tests section (Section VI).

• if d b j = 1, then S k = b j , d b j = 1, and k = k + 1, • if d b j = 1,
Another example is given in Table I, in which r means "reset" and the integers which are underlined in sequence b are discarded.

C. CI(XORshift, XORshift) Algorithm

The basic design procedure of the novel generator is summed up in Algorithm 2. The internal state is x, the output state is r. a and b are those computed by the two XORshift generators. The value g 1 (a) is an integer, defined as in Equation 5. Lastly, N is a constant defined by the user.

As a comparison, the basic design procedure of the old generator is recalled in Algorithm 3 (a and b are computed by logistic maps, N and c 3N are constants defined by the user). See [START_REF] Wang | A novel pseudo-random generator based on discrete chaotic iterations for cryptographic applications[END_REF] for further information.

D. Illustrative Example

In this example, N = 4 is chosen for easy understanding. As stated before, the initial state of the system x 0 can be seeded by the decimal part t of the current time. For example, if the current time in seconds since the Epoch is 1237632934.484088, so t = 484088, then x 0 = t (mod 16) in binary digits, i.e., x 0 = (0, 1, 0, 0).

To compute m sequence, Equation 5 can be adapted to this example as follows:

m n = g 1 (y n ) =              0 if 0 y n 2 32 < 1 16 , 1 if
y n 2 32 < 1, (6)
Input: the internal state x (N bits) Output: a state r of N bits for i = 0, . . . , N do , respectively. This m determines what will be the next output x. For instance,

d i ← 0; end a ← XORshif t1(); m ← g 1 (a); k ← m; for i = 0, . . . , k do b ← XORshif t2() mod N; S ← b; if d S = 0 then x S ← x S ; d S ← 1; end else if d S = 1 then k ← k + 1; end end r ← x; return r;
• If m = 0, the following x will be (0, 1, 0, 0).

• If m = 1, the following x can be (1, 1, 0, 0), (0, 0, 0, 0), (0, 1, 1, 0), or (0, 1, 0, 1).

• If m = 2, the following x can be (1, 0, 0, 0), (1, 1, 1, 0), (1, 1, 0, 1), (0, 0, 1, 0), (0, 0, 0, 1), or (0, 1, 1, 1).

• If m = 3, the following x can be (0, 0, 1, 1), (1, 1, 1, 1), (1, 0, 0, 1), or (1, 0, 1, 0).

• If m = 4, the following x will be (1, 0, 1, 1).

In this simulation, m = 0, 4, 2, 2, 3, 4, 1, 1, 2, 3, 0, 1, 4, ... Additionally, b is computed with a XORshift generator too, but with another seed. We have found b = 1, 4, 2, 2, 3, 3, 4, 1, 1, 4, 3, 2, 1, ... 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, which are here x 0 , x 0+4 , x 0+4+2 , . . . So, in this example, the output of the generator is: 10100111101111110011... or 4,4,11,8,1...

V. SECURITY ANALYSIS

PRNG should be sensitive with respect to the secret key and its size. Here, chaotic properties are also in close relation with the security.

A. Key Space

The PRNG proposed in this paper 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 new generator combines digits of two other PRNGs. We used two different XORshifts here. Let k be the key space of XORshift, so the total key space size is close to 2 N • k 2 . Lastly, the impact of Equation 5, in which is defined the (m n ) sequence with a selector function g 1 , must be taken into account. This leads to conclude that the key space size is large enough to withstand attacks.

Let us notice, to conclude this subsection, that our PRNG can use any reasonable function as selector. In this paper, g 1 () and g 2 () are adopted for demonstration purposes, where:

m n = g 2 (y n ) =                  N if 0 y n 2 32 < C 0 N 2 N , N -1 if C 0 N 2 N y n 2 32 < 1 i=0 C i N 2 N , N -2 if 1 i=0 C i N 2 N y n 2 32 < 2 i=0 C i N 2 N , . . . . . . 0 if N-1 i=0 C i N 2 N y n 2 32 < 1. (7)
We will show later that both of them can pass all of the performed tests.

B. Key Sensitivity

As a consequence of its chaotic property, this PRNG is highly sensitive to the initial conditions. To illustrate this fact, 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 3 (x axis is sequence lengths, y axis is variance ratio P ). For the two PRNGs, variance ratios approach 0.50, which indicates that the system is extremely sensitive to the initial conditions.

C. Linear Complexity

The linear complexity (LC) of a sequence is the size in bits of the shortest linear feedback shift register (LFSR) which can produce this sequence. This value measures the difficulty of generating -and perhaps analyzing -a particular sequence. Indeed, the randomness of a given sequence can be linked to the size of the smallest program that can produce it. LC is the size required by a LFSR to be able to produce the given sequence. The Berlekamp-Massey algorithm can measure this

m 0 4 2 2 k 0 4 +1 2 2 +1 b 1 4 2 2 3 3 4 1 1 4 d r r    1 0 0 0       1 0 0 1       1 1 0 1       1 1 1 1    r    0 0 1 0       0 0 1 1    r    1 0 0 0       1 0 0 1    S 1 4 2 3 3 4 1 4 x 0 x 0 x 4 x 6 x 8 0 0 1 -→ 1 1 1 1 -→ 0 0 1 1 2 -→ 0 0 0 0 0 0 3 -→ 1 1 3 -→ 0 0 0 0 0 4 -→ 1 1 4 -→ 0 0 4 -→ 1 1
Binary Output: LC, which can be used to evaluate the security of a pseudorandom sequence. It can be seen in Figure 4 that the LC curve of a sample sequence of 2000 bits is close to the ideal line C i = i/2, which implies that the generator has high linear complexity.

x 0 1 x 0 2 x 0 3 x 0 4 x

D. Devaney's Chaos Property

Generally speaking, the quality of a PRNG depends, to a large extent, on the following criteria: randomness, uniformity, independence, storage efficiency, and reproducibility. A chaotic sequence may satisfy these requirements and also other chaotic properties, as ergodicity, entropy, and expansivity. A chaotic sequence is extremely sensitive to the initial conditions. 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 fits the requirements of pseudo-random sequence well. Contrary to XORshift, our generator possesses these chaotic properties [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF], [START_REF] Wang | A novel pseudo-random generator based on discrete chaotic iterations for cryptographic applications[END_REF]. However, despite a large number of papers published in the field of chaos-based pseudo-random generators, 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, requiring considerably more storage space, and lose their chaotic properties during computations as mentioned earlier in this paper. These major problems restrict their use as generators [START_REF] Kocarev | Chaos-based cryptography: a brief overview[END_REF].

In this paper, we do not simply integrate chaotic maps hoping that the implemented algorithm remains chaotic. Indeed, the PRNG we conceive is just discrete chaotic iterations and we have proven in [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF] that these iterations produce a topological chaos as 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. Moreover, as only integers are manipulated in discrete chaotic iterations, the chaotic behavior of the system is preserved during computations, and these computations are fast.

Let us now explore the topological properties of our generator and their consequences concerning the quality of the generated pseudo-random sequences.

E. Topological Consequences

We have proven in [START_REF] Guyeux | Chaotic iterations versus spreadspectrum: chaos and stego security[END_REF] that chaotic iterations are expansive and topologically mixing. These topological properties are inherited by the generators we presented here. In particular, any error on the seed are magnified until being equal to the constant of expansivity. We will now investigate the consequences of being chaotic, as defined by Devaney. First of all, the transitivity property implies the indecomposability of the system:

Definition 3 A dynamical system (X , f ) is indecomposable if it is not the union of two closed sets A, B ⊂ X such that f (A) ⊂ A, f (B) ⊂ B.
Thus it is impossible to reduce the set of the outputs generated by our PRNG, in order to reduce its complexity. Moreover, it is possible to show that Old and New CI generators are strongly transitive:

Definition 4 A dynamical system (X , f ) is strongly transitive if ∀x, y ∈ X , ∀r > 0, ∃z ∈ X , d(z, x) r ⇒ ∃n ∈ N * , f n (z) = y.
In other words, for all x, y ∈ X , it is possible to find a point z in the neighborhood of x such that an iterate f n (z) is y. Indeed, this result has been established during the proof of the transitivity presented in [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF]. Among other things, the strong transitivity property leads to the fact that without the knowledge of the seed, all of the outputs are possible. Additionally, no point of the output space can be discarded when studying our PRNG: it is intrinsically complicated and it cannot be simplified.

Finally, these generators possess the instability property:

Definition 5 A dynamical system (X , f ) is unstable if for all x ∈ X , the orbit γ x : n ∈ N -→ f n (x) is unstable, that is: ∃ε > 0, ∀δ > 0, ∃y ∈ X , ∃n ∈ N, d(x, y) < δ and d (γ x (n), γ y (n)) ε.
This property, which is implied by the sensitive dependence to the initial condition, leads to the fact that in all of the neighborhoods of any x, there are points that are separate from x under iterations of f . We thus can claim that the behavior of our generators is unstable.

VI. STATISTICAL ANALYSIS

A. Basic Common Tests 1) Comparative test parameters:

In this section, five wellknown statistical tests [START_REF] Menezes | Handbook of applied cryptography[END_REF] are used as comparison tools. They encompass frequency and autocorrelation tests. In what follows, s = s 0 , s 1 , s 2 , . . . , s n-1 denotes a binary sequence of length n. The question is to determine whether this sequence possesses some specific characteristics that a truly random sequence would be likely to exhibit. The tests are introduced in this subsection and results are given in the next one.

a) Frequency test (monobit test):

The purpose of this test is to check if the numbers of 0's and 1's are approximately equal in s, as it would be expected for a random sequence. Let n 0 , n 1 denote these numbers. The statistic used here is:

X 1 = (n 0 -n 1 ) 2 n ,
which approximately follows a χ 2 distribution with one degree of freedom when n 10 7 .

b) Serial test (2-bit test):

The purpose of this test is to determine if the number of occurrences of 00, 01, 10, and 11 as subsequences of s are approximately the same. Let n 00 , n 01 , n 10 , and n 11 denote the number of occurrences of 00, 01, 10, and 11 respectively. Note that n 00 + n 01 + n 10 + n 11 = n -1 since the subsequences are allowed to overlap. The statistic used here is:

X 2 = 4 n -1 (n 2 00 + n 2 01 + n 2 10 + n 2 11 ) - 2 n (n 2 0 + n 2 1 ) + 1,
which approximately follows a χ 2 distribution with 2 degrees of freedom if n 21. c) Poker test: The poker test studies if each pattern of length m (without overlapping) appears the same number of times in s. Let ⌊ n m ⌋ 5 × 2 m and k = ⌊ n m ⌋. Divide the sequence s into k non-overlapping parts, each of length m. Let n i be the number of occurrences of the i th type of sequence of length m, where 1 i 2 m . The statistic used is

X 3 = 2 m k 2 m i=1 n 2 i -k,
which approximately follows a χ 2 distribution with 2 m -1 degrees of freedom. Note that the poker test is a generalization of the frequency test: setting m = 1 in the poker test yields the frequency test. d) Runs test: The purpose of the runs test is to figure out whether the number of runs of various lengths in the sequence s is as expected for a random sequence. A run is defined as a pattern of all zeros or all ones, a block is a run of ones, and a gap is a run of zeros. The expected number of gaps (or blocks) of length i in a random sequence of length n is e i = n-i+3 2 i+2 . Let k be equal to the largest integer i such that e i 5. Let B i , G i be the number of blocks and gaps of length i in s, for each i ∈ 1, k . The statistic used here will then be:

X 4 = k i=1 (B i -e i ) 2 e i + k i=1 (G i -e i ) 2 e i ,
which approximately follows a χ 2 distribution with 2k -2 degrees of freedom. e) Autocorrelation test: The purpose of this test is to check for coincidences between the sequence s and (non-cyclic) shifted versions of it. Let d be a fixed integer,

1 d ⌊n/2⌋. The value A(d) = n-d-1 i=0
s i ⊕ s i+d is the amount of bits not equal between the sequence and itself displaced by d bits. The statistic used here is: seconds) is related to the duration needed by each algorithm to generate a 2 × 10 5 bits long sequence. The test has been conducted using the same computer and compiler with the same optimization settings for both algorithms, in order to make the test as fair as possible. The results confirm that the proposed generator is a lot faster than the old one, while the statistical results are better for most of the parameters, leading to the conclusion that the new PRNG is more secure than the old one. Although the logistic map also has good results, it is too slow to be implemented in Internet applications, and this map is known to present various bias leading to severe security issues.

X 5 = |2(A(d) - n -d 2 )/ √ n -
As a comparison of the overall stability of these PRNGs, similar tests have been computed for different sequence lengths (see Figures 56789). For the monobit test comparison (Figure 5), Indeed, the new generator distributes very randomly the zeros and ones, whatever the length of the desired sequence. It can also be remarked that the old generator presents the second best performance, due to its use of chaotic iterations. Figure 6 shows the serial test comparison. The new generator outperforms this test, but the score of the old generator is not bad either: their occurrences of 00, 01, 10, and 11 are very close to each other.

The poker test comparison with m = 8 is shown in Figure 7. XORshift is the most stable generator in all of these tests, and the logistic map also becomes good when producing sequences of length greater than 1 × 10 5 . Our old and new generators present a similar trend, with a maximum in the neighborhood of 1.7 × 10 5 . These scores are not so good, even though the new generator has a better behavior than the old one. Indeed, the value of m and the length of the sequences should be enlarged to be certain that the chaotic iterations express totally their complex behavior. In that situation, the performances of our generators in the poker test can be improved.

The graph of the new generator is the most stable one can be explained by the fact that the improvements realized to define the new generator lead to a more randomly output.

To sum up we can claim that the new generator, which is faster than its former version, outperforms all of the other generators in these statistical tests, especially when producing long output sequences.

B. NIST Statistical Test Suite

1) Presentation: Among the numerous standard tests for pseudo-randomness, a convincing way to prove the quality of the produced sequences is to confront them with the NIST (National Institute of Standards and Technology) Statistical Test Suite SP 800-22, released by the Information Technology Laboratory in August 25, 2008.

The NIST test suite, SP 800-22, is a statistical package consisting of 15 tests. They were developed to measure the randomness of (arbitrarily long) binary sequences produced by either hardware or software based cryptographic pseudorandom number generators. These tests focus on a variety of different types of non-randomness that could occur in such sequences. These 15 tests include in the NIST test suite are described in the Appendix.

2) Interpretation of empirical results: P is the "tail probability" that the chosen test statistic will assume values that are equal to or worse than the observed test statistic value when considering the null hypothesis. For each statistical test, a set of Ps is produced from a set of sequences obtained by our generator (i.e., 100 sequences are generated and tested, hence 100 Ps are produced).

Empirical results can be interpreted in various ways. In this paper, we check whether the Ps are uniformly distributed, via an application of a χ 2 distribution and the determination of a P T corresponding to the Goodness-of-Fit distributional test on the Ps obtained for an arbitrary statistical test.

If P T ≥ 0.0001, then the sequences can be considered to be uniformly distributed. In our experiments, 100 sequences (s = 100) of 1,000,000 bits are generated and tested. If the value P T of a least one test is smaller than 0.0001, the sequences are considered to be not good enough and the generator is unsuitable.

Table III shows P T for the sequences based on discrete chaotic iterations using different schemes. If there are at least two statistical values in a test, this test is marked with an asterisk and the average is computed to characterize the statistical values.

We can conclude from Table III that the worst situations are obtained with the New CI (m n = y n mod N ) and New CI (no mark) generators. Old CI, New CI (m n = g 1 (y n )), and New CI (m n = g 2 (y n )) have successfully passed the NIST statistical test suite. These results and the conclusion obtained from the aforementioned basic tests reinforce the confidence that can be put in the good behavior of chaotic CI PRNGs, thus making them suitable for security applications as information hiding and digital watermarking.

VII. APPLICATION EXAMPLE IN INFORMATION HIDING

A. Introduction

Information hiding is now an integral part of Internet technologies. In the field of social search engines, for example, contents like pictures or movies are tagged with descriptive labels by contributors, and search results are determined by these descriptions. These collaborative taggings, used for example in Flickr [START_REF]The frick collection[END_REF] and Delicious [START_REF]Delicious social bookmarking[END_REF] websites, contribute to the development of a Semantic Web, in which any Web page contains machine-readable metadata that describe its content. Information hiding technologies can be used for embedding these metadata. The advantage of its use is the possibility to realize social search without websites and databases: descriptions are directly embedded into media, whatever their formats. Robustness is required in this situation, as descriptions should resist to modifications like resizing, compression, and format conversion.

The Internet security field is also concerned by watermarking technologies. Steganography and cryptography are supposed to be used by terrorists to communicate through the Internet. Furthermore, in the areas of defense or in industrial espionage, many information leaks using steganographic techniques have been reported. Lastly, watermarking is often cited as a possible solution to digital rights managements issues, to counteract piracy of digital work in an Internet based entertainment world [START_REF] Nakashima | Watermarked movie soundtrack finds the position of the camcorder in a theater[END_REF].

B. Definition of a Chaos-Based Information Hiding Scheme

Let us now introduce our information hiding scheme based on CI generator.

1) Most and least significant coefficients: Let us define the notions of most and least significant coefficients of an image.

Definition 1 For a given image, most significant coefficients (in short MSCs), are coefficients that allow the description of the relevant part of the image, i.e., its richest 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 four bits of each pixel (see Figure 10). In a discrete cosine frequency domain description, each 8 × 8 block of the carrier image is mapped onto a list of 64 coefficients. The energy of the image is mostly contained in a determined part of themselves, which can constitute a possible sequence of MSCs.

Definition 2 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 (see Figure 10). Discrete cosine, Fourier, and wavelet transforms can be used also to generate LSCs and MSCs. Moreover, these definitions can be extended to other types of media.

LSCs are used during the embedding stage. Indeed, some of the least significant coefficients of the carrier image will be chaotically chosen by using our PRNG. These bits will be either switched or replaced by the bits of the watermark. The MSCs are only useful in case of authentication; mixture 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. 2) Stages of the scheme: Our CI generator-based information hiding scheme consists of two stages: (1) mixture of the watermark and (2) its embedding.

a) Watermark mixture: Firstly, for security reasons, the watermark can be mixed before its embedding into the image. A first way to achieve this stage is to apply the bitwise exclusive or (XOR) between the watermark and the New CI generator. In this paper, we introduce a new mixture scheme based on chaotic iterations. Its chaotic strategy, which depends on our PRNG, will be highly sensitive to the MSCs, in the case of an authenticated watermarking.

b) Watermark embedding: Some LSCs will be switched, or substituted by the 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 M of LSCs corresponding to a chaotic sequence U , is generated from the chaotic strategy used in the mixture stage. Thus, the U k -th least significant coefficient of the carrier image is either switched, or substituted by the k th bit of the possibly mixed watermark. In case of authentication, such a procedure leads to a choice of the LSCs that are highly dependent on the MSCs [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF].

On the one hand, when the switch is chosen, the watermarked image is obtained from the original image whose LSBs L = B M are replaced by the result of some chaotic iterations. Here, the iterate function is the vectorial Boolean negation,

f 0 : (x 1 , ..., x M ) ∈ B M -→ (x 1 , ..., x M ) ∈ B M , (8)
the initial state is L, and the strategy is equal to U . In this case, the whole embedding stage satisfies the topological chaos properties [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF], but the original medium is required to extract the watermark. On the other hand, when the selected LSCs are substituted by the watermark, its extraction can be done without the original cover (blind watermarking). In this case, the selection of LSBs still remains chaotic because of the use of the New CI generator, but the whole process does not satisfy topological chaos [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF]. The use of chaotic iterations is reduced to the mixture of the watermark. See the following sections for more detail. c) Extraction: The chaotic strategy can be regenerated even in the case of an authenticated watermarking, because the MSCs have not changed during the embedding stage. Thus, the few altered LSCs can be found, the mixed watermark can be rebuilt, and the original watermark can be obtained. In case of a switch, the result of the previous chaotic iterations on the watermarked image should be the original cover. The probability of being watermarked decreases when the number of differences increase.

If the watermarked image is attacked, then the MSCs will change. Consequently, in case of authentication and due to the high sensitivity of our PRNG, 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.

The chaos-based data hiding scheme is summed up in Figure 11.

C. Application Example 1) Experimental protocol:

In this subsection, a concrete example is given: a watermark is encrypted and embedded into a cover image using the scheme presented in the previous section and CI(XORshift, XORshift). The carrier image is the well-known Lena, which is a 256 grayscale image, and the watermark is the 64 × 64 pixels binary image depicted in Figure 12.

The watermark is encrypted by using chaotic iterations: the initial state x 0 is the watermark, considered as a Boolean vector, the iteration function is the vectorial logical negation, and the chaotic strategy (S k ) k∈N is defined with CI(XORshift, XORshift), where initial parameters constitute the secret key and N = 64. Thus, the encrypted watermark is the last Boolean vector generated by these chaotic iterations. An example of such an encryption is given in Figure 13.

Let L be the 256 3 Booleans vector constituted by the three last bits of each pixel of Lena and U k defined by the sequence:

U 0 = S 0 U n+1 = S n+1 + 2 × U n + n [mod 256 3 ]. (9)
The watermarked Lena I w is obtained from the original Lena, whose three last bits are replaced by the result of 64 2 chaotic iterations with initial state L and strategy U (see Figure 13).

The extraction of the watermark can be obtained in the same way. Remark that the map θ → 2θ of the torus, which is the famous dyadic transformation (a well-known 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 strategy. As a consequence, (U k ) k 64 2 is highly sensitive to the alteration of the image: any significant modification of the watermarked image will lead to a completely different extracted watermark, thus giving a way to authenticate media through the Internet.

Let us now evaluate the robustness of the proposed method.

2) Robustness evaluation:

In what follows, the embedding domain is the spatial domain, CI(XORshift,XORshift) has been used to encrypt the watermark, MSCs are the four first bits of each pixel (useful only in case of authentication), and LSCs are the three next bits.

To prove the efficiency and the robustness of the proposed algorithm, some attacks are applied to our chaotic watermarked image. For each attack, a similarity percentage with the watermark is computed, this percentage is the number of equal bits between the original and the extracted watermark, shown as a percentage. Let us notice that a result less than or equal to 50% implies that the image has probably not been watermarked. a) Zeroing attack: In this kind of attack, a watermarked image is zeroed, such as in Figure 14(a). In this case, the results in Table 1 In Figure 15, 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 case of unauthentication, the watermark still remains after a zeroing attack: the desired robustness is reached. It can be noticed that zeroing sizes and percentages are rather proportional.

In 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, the image is well authenticated.

b) 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, which is altered as in Figure 14. The results in Table 2 The same conclusion as above can be declaimed: this watermarking method satisfies the desired properties. c) JPEG compression: A JPEG compression is applied to the watermarked image, depending on a compression level. Let us notice that this attack leads to a change of the representation domain (from spatial to DCT domain). In this case, the results in Table 3

Table. 3. JPEG compression attacks

A very good authentication through JPEG attack is obtained. 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. d) Gaussian noise: 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 4

Table. 4. Gaussian noise attacks

Once again we remark that good results are obtained, especially if we keep in mind that a spatial representation domain has been chosen.

VIII. CONCLUSION AND FUTURE WORK

In this paper, the pseudo-random generator proposed in [START_REF] Wang | A novel pseudo-random generator based on discrete chaotic iterations for cryptographic applications[END_REF] has been improved. By using XORshift instead of logistic map and due to a rewrite of the way to generate strategies, the generator based on chaotic iterations works faster and is more secure. The speed and randomness of this new PRNG has been compared to its former version, to XORshift, and to a generator based on logistic map. This comparison shows that CI(XORshift, XORshift) offers a sufficient speed and level of security for a wide range of Internet usages as cryptography and information hiding.

In future work, we will continue to try to improve the speed and security of this PRNG, by exploring new strategies and iteration functions. Its chaotic behavior will be deepened by using the numerous tools provided by the mathematical theory of chaos. New statistical tests will be used to compare this PRNG to existing ones. Additionally a probabilistic study of its security will be done. Lastly, new applications in computer science will be proposed, especially in the Internet security field.

Algorithm 1 :

 1 An arbitrary round of XORshift algorithm

Fig. 2 :

 2 Fig. 2: Balance property

Algorithm 2 :Algorithm 3 :

 23 An arbitrary round of the new CI(XORshift,XORshift) generator Input: the internal state x (N bits) Output: a state r of N bits a ← Logisticmap1(); if a > 0.5 then d ← 1 end else d ← 0 end m ← d + c; for i = 0, . . . , m do b ← Logisticmap2(); S ← 100000b mod N; x S ← x S ; end r ← x; return r; An arbitrary round of the old CI PRNG where y is generated by XORshift seeded with the current time. We can see that the probabilities of occurrences of m = 0, m = 1, m = 2, m = 3, m = 4, are

Fig. 3 Fig. 4 :

 34 Fig. 3: Sensitivity analysis

Fig. 8 :Fig. 9 :

 89 Fig. 8: Comparison of runs tests

  (a) Lena. (b) MSCs of Lena.(c) LSCs of Lena (×17).

Fig. 10 :

 10 Fig. 10: Example of most and least significant coefficients of Lena.

Fig. 11 :

 11 Fig. 11: The chaos-based data hiding decision tree.

Fig. 12 :

 12 Fig. 12: Original images

  (a) Unauthentication (50 × 50).

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

Fig. 15 :

 15 Fig. 15: Extracted watermark after a cropping attack.

  Integer Output: x 0 , x 4 , x 6 , x 8 ... = 4, 11, 8, 1...

	4 1 x 4 2 x 4 3 x 4 4 x 6 1 x 6 2 ... = 0100101110000001...

TABLE I :

 I Example of New CI(XORshift,XORshift) generation

							Sensitivity analysis
		0.51
		0.508								New CI(XORshift,XORshift)
		0.506								Old CI(Logistic, Logistic)
		0.504
		0.502
	P	0.5
		0.498
		0.496
		0.494
		0.492
		0.49	0	1	2	3	4	5	6	7	8	9	10
								n					x 10 4

  We show inTable II a comparison among our new generator CI(XORshift, XORshift), its old version denoted Old CI(Logistic, Logistic), a basic PRNG based on logistic map, and a simple XORshift. In this table, time (in

d|, which approximately follows a normal distribution N (0, 1) if nd 10. Since small values of A(d) are as unexpected as large values, a two-sided test should be used.

2) Comparison:

TABLE II :

 II Comparison with Old CI(Logistic, Logistic) for a 2 × 10 5 bits sequence

						Method			Monobit (X 1 )	Serial (X 2 )	Poker (X 3 )	Runs (X 4 )	Autocorrelation (X 5 )	Time
						Logistic map			0.1280	0.1302	240.2893	26.5667	0.0373	0.965s
						XORshift			1.7053	2.1466	248.9318	18.0087	0.5009	0.096s
					Old CI(Logistic, Logistic)		1.0765	1.0796	258.1069	20.9272	1.6994	0.389s
				New CI(XORshift,XORshift)		0.3328	0.7441	262.8173	16.7877	0.0805	0.197s
							Monobits test
	5
											Old CI (Logistic, Logistic)
	4.5										XORshift Logistic map
											New CI (XORshift, XORshift)
	4
	3.5
	3
	2.5
	2
	1.5
	1
	0.5
	0	0	0.2	0.4	0.6	0.8	1	1.2	1.4	1.6	1.8	2
												x 10 5
				Fig. 5: Comparison of monobits tests
							Serial test
	8
											Old CI (Logistic, Logistic)
											XORshift
											Logistic map
	7									New CI (XORshift, XORshift)
	6
	5
	4
	3
	2
	1
	0	0	0.2	0.4	0.6	0.8	1	1.2	1.4	1.6	1.8	2
												x 10 5

Fig. 6: Comparison of serial tests almost all of the PRNGs present the same issue: the beginning values are a little high. However, for our new generator, the values are stable in a low level which never exceeds 1.2.

  have been obtained.

	(a) Cropping attack	(b) Rotation attack
	Fig. 14: Watermarked Lena after attacks.
	UNAUTHENTICATION	AUTHENTICATION
	Size (pixels)	Similarity	Size (pixels)	Similarity
	10	99.08%	10	91.77%
	50	97.31%	50	55.43%
	100	92.43%	100	51.52%
	200	70.75%	200	50.60%

Table . 1. Cropping attacks

 .

  have been obtained.

	UNAUTHENTICATION	AUTHENTICATION
	Angle (degree)	Similarity	Angle (degree)	Similarity
	2	96.44%	2	73.40%
	5	93.32%	5	60.56%
	10	90.68%	10	52.11%
	25	78.13%	25	51.97%

TABLE III :

 III SP 800-22 test results (P T )

	Method	New CI (m n = y n mod N )	New CI (no mark)	Old CI	New CI (g 1 ())	New CI (g 2 ())
	Frequency (Monobit) Test	0.0004	0.0855	0.595549	0.474986	0.419
	Frequency Test within a Block	0	0	0.554420	0.897763	0.6786
	Runs Test	0.2896	0.5544	0.455937	0.816537	0.3345
	Longest Run of Ones in a Block Test	0.0109	0.4372	0.016717	0.798139	0.8831
	Binary Matrix Rank Test	0	0.6579	0.616305	0.262249	0.7597
	Discrete Fourier Transform (Spectral) Test	0	0	0.000190	0.007160	0.0008
	Non-overlapping Template Matching Test*	0.020071	0.37333	0.532252	0.449916	0.51879
	Overlapping Template Matching Test	0	0	0.334538	0.514124	0.2492
	Maurer's "Universal Statistical" Test	0.6993	0.9642	0.032923	0.678686	0.1296
	Linear Complexity Test	0.3669	0.924	0.401199	0.657933	0.3504
	Serial Test* (m=10)	0	0.28185	0.013396	0.425346	0.2549
	Approximate Entropy Test (m=10)	0	0.3838	0.137282	0.637119	0.7597
	Cumulative Sums (Cusum) Test*	0	0	0.046464	0.279680	0.34245
	Random Excursions Test*	0.46769	0.34788	0.503622	0.287409	0.18977
	Random Excursions Variant Test*	0.28779	0.46505	0.347772	0.486686	0.26563
	Success	8/15	11/15	15/15	15/15	15/15

  have been obtained.

	UNAUTHENTICATION	AUTHENTICATION
	Compression	Similarity	Compression	Similarity
	2	85.76%	2	56.42%
	5	67.62%	5	52.12%
	10	62.43%	10	48.22%
	20	54.74%	20	49.07%

  have been obtained.

	UNAUTHENTICATION	AUTHENTICATION
	Standard dev.	Similarity	Standard dev.	Similarity
	1	81.14%	1	55.57%
	2	75.01%	2	52.63%
	3	67.64%	3	52.68%
	5	57.48%	5	51.34%

APPENDIX

The NIST Statistical Test Suite

In what follows, the objectives of the fifteen tests contained in the NIST Statistical tests suite are recalled. A more detailed description for those tests can be found in [START_REF] Publication | A statistical test suite for random and pseudorandom number generators for cryptographic applications[END_REF].

Frequency (Monobit) Test is to determine whether the number of ones and zeros in a sequence are approximately the same as would be expected for a truly random sequence.

Frequency Test within a Block is to determine whether the frequency of ones in an M-bits block is approximately M/2, as would be expected under an assumption of randomness (M is the length of each block).

Runs Test is to determine whether the number of runs of ones and zeros of various lengths is as expected for a random sequence. In particular, this test determines whether the oscillation between such zeros and ones is too fast or too slow.

Test for the Longest Run of Ones in a Block is to determine whether the length of the longest run of ones within the tested sequence is consistent with the length of the longest run of ones that would be expected in a random sequence.

Binary Matrix Rank Test is to check for linear dependence among fixed length substrings of the original sequence.

Discrete Fourier Transform (Spectral) Test is to detect periodic features (i.e., repetitive patterns that are near each other) in the tested sequence that would indicate a deviation from the assumption of randomness.

Non-overlapping Template Matching Test is to detect generators that produce too many occurrences of a given nonperiodic (aperiodic) pattern.

Overlapping Template Matching Test is the number of occurrences of pre-specified target strings.

Maurer's "Universal Statistical" Test is to detect whether or not the sequence can be significantly compressed without loss of information.

Linear Complexity Test is to determine whether or not the sequence is complex enough to be considered random.

Serial Test is to determine whether the number of occurrences of the 2 m m-bit (m is the length in bits of each block) overlapping patterns is approximately the same as would be expected for a random sequence.

Approximate Entropy Test is to compare the frequency of overlapping blocks of two consecutive/adjacent lengths (m and m+1) against the expected result for a random sequence (m is the length of each block).

Cumulative Sums (Cusum) Test is to determine whether the cumulative sum of the partial sequences occurring in the tested sequence is too large or too small relative to the expected behavior of that cumulative sum for random sequences.

Random Excursions Test is to determine if the number of visits to a particular state within a cycle deviates from what one would expect for a random sequence.

Random Excursions Variant Test is to detect deviations from the expected number of visits to various states in the random walk.


Claude Henri Picard

ON SOME SERIES FORMED BY VALUES OF THE RIEMANN ZETA FUNCTION

The partial fraction expansion of coth(πz), due to Euler, is generalized to power series having for coefficients the Riemann zeta function evaluated at certain arithmetic sequences. A further generalization using arbitrary Dirichlet series is also proposed. The resulting formulas are new, as far as we know, since they could not be found in any of the classical or recent handbooks of formulas that were at our disposal.

Origin of the series

The starting point for this paper is the known formula [10, p. 49]:

∞ n=1 1 n 2 + z 2 =      π 2 6 if z = 0, π 2z coth(πz) - 1 2z 2 if 0 < |z| < 1.
These two values must obviously be connected. Indeed, from the Taylor series for z = 0, we obtain the expansion

∞ n=1 1 n 2 + z 2 = π 2 6 - π 4 90 z 2 + π 6 945 z 4 + O(z 6 ), (z → 0),
where the classical values of the Riemann's zeta function for the even integers can be recognized immediately. The same question can now be asked for similar partial fraction expansions such as

∞ n=1 1 n 3 + z 3 , ∞ n=1 1 n 4 + z 4 , . . .
Our results presented below extend significantly some particular formulas published recently in [START_REF] Choi | Sums associated with the zeta function[END_REF] and [START_REF] Jameson | Series involving ζ(n)[END_REF] (although it was written before knowing these papers), notably by considering Cesàro summation and more general Dirichlet series.

2. Formula of order p Theorem 1. For a complex z of modulus less or equal to 1, z = -1:

(1)

∞ n=1 1 n 2 + z = ∞ k=0 (-1) k ζ(2k + 2)z k , (2)
∞ n=1 1 n 3 + z = ∞ k=0 (-1) k ζ(3k + 3)z k ,
and generally for p ∈ C such that ℜe(p) > 1 (formula of order p) : For all complex numbers z of modulus less or equal to 1, z = -1:

(3)

∞ n=1 1 n p + z = ∞ k=0 (-1) k ζ(pk + p)z k .
Date: 28 may 2015.

Proof. We prove only the formula of order p, since the first two formulas are special cases. Let us first assume |z| < r 0 < 1. This condition implies the normal convergence1 of the series and hence the legitimate inversion of the summations [9, p. 104].

We have

∞ n=1 1 n p + z p = ∞ n=1 1 n p 1 1 + (z/n) p = ∞ n=1 1 n p ∞ k=0 (-1) k z n kp
and we obtain, with the inversion of summations,

∞ n=1 1 n p + z p = ∞ k=0 (-1) k z pk ∞ n=1 1 n p(k+1) = ∞ k=0 (-1) k ζ(pk + p)z pk
Substituting z to z p yields the formula of order p. We thus have an analytical function of z in D(0, r 0 ) which can be extended to the whole open disc D(0, 1) because the convergence radius is 1 from the Cauchy-Hadamard formula.

On the convergence circle, the analytical function

f p (z) = ∞ k=0 (-1) k ζ(pk + p)z pk
has a pole at z = -1. From the formula, the only problematic term in the left hand side is the first term whose denominator is zero if z = -1. We conclude that the function f p (z) has a simple pole on the convergence circle |z| = 1 at z = -1.

Theorem 2. The function f p (z) is meromorphic on C, and its singularities are an infinity of simple poles at z = -n p (n ∈ N * ) with residue 1.

Proof. All the singularities of f p must appear in the left hand side of the formula of order p. We begin by the pole at -1. We have to calculate the residue by the formula lim z→-1

(z + 1)f p (z).
From the formula of order p, we have lim z→-1

(z + 1)f p (z) = lim z→-1 ∞ n=1 1 n p + z = lim z→-1 (z + 1) 1 1 + z + lim z→-1 (z + 1) ∞ n=2 1 n p + z = 1 + 0 = 1.
Hence this pole is simple and has residue 1. For the other poles, the same demonstration can be given by considering n p + z instead of 1 + z. Remark 1. When p is not real, the poles of f p (z) are on a logarithmic spiral. The poles are on a straight line (the real axis) only when p is real. It is the only analytical function that we know of whose poles are on a spiral, without being specially constructed by using the Mittag-Leffler's theorem on the principal parts.

First generalization

Let m and p be two complex numbers such that ℜe(m) < ℜe(p) -1. We have,

for |z| < 1, ∞ n=1 n m n p + z p = ∞ n=1 1 n p-m 1 1 + (z/n) p = ∞ n=1 1 n p-m ∞ k=0 (-1) k z n kp
and then, since the condition on m ensures the absolute convergence of the series,

∞ n=1 n m n p + z p = ∞ k=0 (-1) k z pk ∞ n=1 1 n p(k+1)-m ,

Hence

Theorem 3. Let m and p be two complex numbers such that ℜe(m) < ℜe(p) -1.

Then, for |z| ≤ 1, z = -1, (4) ∞ n=1 n m n p + z = ∞ k=0 (-1) k ζ(pk + p -m)z k ,
and the power series

∞ k=0 (-1) k ζ(pk + p -m)z k
defines a meromorphic function which can be extended to the whole complex plane, except for an infinity of simple poles at z = -n p (n ∈ N * ) with residue n m .

Second generalization

Let m be an integer. For |z| < 1, we have

∞ n=1 ln m (n) n p + z p = ∞ n=1 ln m (n) n p 1 1 + (z/n) p = ∞ n=1 ln m (n) n p ∞ k=0 (-1) k z n kp and then ∞ n=1 ln m (n) n p + z p = ∞ k=0 (-1) k z pk ∞ n=1 ln m (n) n p(k+1) . Hence Theorem 4. Let m an integer. For |z| ≤ 1, z = -1, (5)
∞ n=1 ln m (n) n p + z = (-1) m ∞ k=0 (-1) k ζ (m) (pk + p)z k ,
and the power series

∞ k=0 (-1) k ζ (m) (pk + p)z k
defines a meromorphic function which can be extended to the whole complex plane, except for an infinity of simple poles at z = -n p (n ∈ N * ) with residue (-1) m ln m (n).

By combining the two previous theorems, we get a more general result.

Theorem 5. Let m be an integer, and p, q be two complex numbers such that ℜe(q) < ℜe(p) -1.

For |z| ≤ 1, z = -1, (6)
∞ n=1 n q ln m (n) n p + z = (-1) m ∞ k=0 (-1) k ζ (m) (pk + p -q)z k ,
and the power series

∞ k=0 (-1) k ζ (m) (pk + p -q)z k
defines a meromorphic function which can be extended to the whole complex plane, except for an infinity of simple poles at z = -n p (n ∈ N * ) with residue (-1) m n q ln m (n).

Third generalization

The same principle works with more complex expressions. We have, with two terms, for |z| < 1/ max(|a|, |b|), ℜe(p) > 1, ℜe(q) > 1,

∞ n=1 1 (n p + az)(n q + bz) = ∞ l=0 ∞ k=0 (-1) k+l ζ(p + q + pk + lq)a k b l z k+l . (7)
With three terms, for |z|

< 1/ max(|a|, |b|, |c|), ℜe(p) > 1, ℜe(q) > 1, ℜe(r) > 1, (8)
∞ n=1 1 (n p + az)(n q + bz)(n r + cz) = ∞ m=0 ∞ l=0 ∞ k=0 (-1) k+l+m ζ(p + q + r + pk + lq + mr)a k b l c m z k+l+m .
And so on.

General formulas

As previously we work with expressions of the form a n /(b n + z) with a n /b n absolutely summable. We remark that these expressions, as function of z, are absolutely summable for z ∈ C -{b n |n ∈ N * }.

We have also Lemma 1. (Abel, 1826) Let the entire series

f (z) = ∞ k=0 a k z k of convergence radius 1. If ∞ k=0 a k converge to L then, for z in an Stolz angle of vertex 1, lim z→1 ∞ k=0 a k z k = L = f (1).
Theorem 6. Consider the Dirichlet's series

f (s) = ∞ n=1 a n n s
having σ a = +∞ as abscissa of absolute convergence. Let s a complex number such that ℜe(s) > σ a .

For

|z| ≤ 1, z = -1, (9)
∞ n=1 a n n s + z = ∞ k=0 (-1) k f (ks + s)z k .
The power series

g(z) = ∞ k=0 (-1) k f (ks + s)z k
defines a meromorphic function g which can be extended to the whole complex plane, except for an infinity 2 of simple poles at z = -n s (n ∈ N * ) with residue a n if a n = 0.

Proof. We have, for |z| < 1,

∞ n=1 a n n s + z s = ∞ n=1 a n n s 1 1 + (z/n) s = ∞ n=1 a n n s ∞ k=0 (-1) k z n ks
and we obtain, with the inversion of summations, legitimated by absolute convergence,

∞ n=1 a n n s + z s = ∞ k=0 (-1) k z sk ∞ n=1 a n n s(k+1) = ∞ k=0 (-1) k f (ks + s)z sk
Substituting z to z s yields the formula [START_REF] Remmert | Theory of complex functions[END_REF].

To extend to |z| ≤ 1, z = -1, we apply the Abel's lemma 1.

All the singularities of g must appear in the left hand side of ( 9). We have

lim z→-n s (z + n s )g(z) = lim z→-n s ∞ n=1 a n n s + z = lim z→-n s (z + n s ) a n n s + z + lim z→-n s (z + n s ) k =n a k k s + z = a n + 0 = a n . Hence z = -n s is a simple pole if a n = 0. For a point α not of the form -n s , lim z→α (z -α)g(z) = lim z→α (z -α) ∞ n=1 a n n s + z = 0,
so there is not other singularity in C.

Remark 2. We can work with expressions as

∞ n=1 a n n s (n s + z) = ∞ k=0 (-1) k f (ks + 2s)z k , or ∞ n=1 a n n s1 (n s2 + αz) = ∞ k=0 (-1) k f (ks 2 + s 1 + s 2 )α k z k ,
and so on.

Corollary 1. Under the previous hypotheses, for an integer m ≥ 0, we have

(10) ∞ n=1 a n (n s + z) m+1 = ∞ k=m (-1) k+m f (ks + s) k! m!(k -m)! z k-m .
Proof. This is the derivative of order m of the formula ( 9) with respect to z.

Corollary 2. Let (α i ) a sequence of m > 1 complex numbers, (β i ) a sequence of m complex numbers such that ℜe(β i ) > 1 and f as in the previous theorem 6.

We have, for |z| < 1/ max i=1,...,m

(α i ) (11) ∞ n=1 a n m i=1 1 (n βi + α i z) = ∞ m1=0 ∞ m2=0 . . . ∞ mm=0 (-1) m i=1 mi f m i=1 (m i + 1)β i m i=1 α mi i z m i=1 mi .
2 We assume the existence of an infinite subsequence of non-zero numbers an.

Remark 3. If α l = 0 then m l = 0 in the formula.

Theorem 7. Let the analytical function f (s) be defined in the disc D(0, R), R > 0, by its power series :

f (s) = ∞ k=1 a k s k ,
and zero in 0. Fix a complex s such that ℜe(s) > 1.

For |z| < R, (12)
∞ n=1 f z n s = ∞ k=1 a k ζ(ks)z k .
If a 1 = 0, and s such that ℜe(s)

> 1 2 , (13)
∞ n=1 f z n s = ∞ k=2 a k ζ(ks)z k .
Remark 4. This theorem contents the formulas of [START_REF] Jameson | Series involving ζ(n)[END_REF] when s = 1 and z = 1 or z = -1.

Proof. The conditions ensure the absolute convergence of the series. We have

∞ n=1 f z n s = ∞ n=1 ∞ k=1 a k z n s k = ∞ k=1 a k ∞ n=1 z n s k = ∞ k=1 a k ζ(ks)z k .
By combining the last two theorems, we get a more general result.

Theorem 8. Let the analytical function f , defined in the disc D(0, R) by the series

f (z) = ∞ k=1 a k z k ,
and zero in 0. Let g(s) the complex analytical function defined by the Dirichlet's series

g(s) = ∞ n=1 b n n s in the half-plane ℜe(s) > σ a .
Let a complex number s such that ℜe(s) ≥ 1, |z| < R, another number s ′ such that ℜe(s + s ′ ) > σ a .

We have

(14) ∞ n=1 b n n s ′ f z n s = ∞ k=1 a k g(ks + s ′ )z k .
Theorem 9. Let the analytical function f (s) be defined in the disc D(0, R), R > 0, by its power series :

f (s) = ∞ k=1 a k s k ,
and zero in 0.

Let (λ n ) a sequence of positive real numbers whose are increasing up to infinity such that the sum Theorem 10. Let (b n ) a sequence of complex numbers whose moduli are increasing up to infinity and (a n ) an infinite sequence of complex numbers such that the sum

∞ n=1 |a n /b n | converges. Then (16) ∞ n=1 a n b n -z = ∞ k=0 ∞ n=1 a n b k+1 n z k for |z| ≤ |b 1 |, z = b 1 .
The power series

∞ k=0 ∞ n=1 a n b k+1 n z k
defines a meromorphic function which can be extended to the whole complex plane, except for simple poles at z = b n (n ∈ N * ) with residue -a n when a n = 0. Corollary 3. Under the previous hypothesis, for an integer m ≥ 0, we have

(17) ∞ n=1 a n (b n -z) m+1 = ∞ k=m ∞ n=1 a n b k+1 n k! m!(k -m)! z k-m
Proof. This is the derivative of order m of the formula (16) with respect to z. Acknowledgements. The author would like to thank Jacques Gélinas for his help with this English translation of the original French version of the paper and the bibliography.

∞ n=1 |a

 n=1 exp(-λ n s)| converges for ℜe(s) > σ a . Let D(s) = ∞ n=1 exp(-λ n s) and a complex s such that ℜe(s) > σ a . For |z| < R, k D(ks)z k .

7. The inverse problem 8 . 8 . 1 . 8 . 2 . 8 . 3 .

 8818283 Applications of the previous formulas The notation (C, k) means the Cesàro summation method of order k [5, p. 96]. First formula (1), z = 1 in the Cesàro's sense [1, p. 205] Second formula (2), z = 1 in the Cesàro's sense Partial derivative of the first formula (1) with respect to z, z = 1 in the Cesàro's sense ∞ n=1 1 (n 2 + 1) 2 = ∞ k=1 (-1) k+1 kζ(2k) (C, 2).

8. 14 . 9 . 7 #

 1497 Theorem 10 for a n = 1, b n = n 2 + n, z = 1 Code for Maple For theorem Definition of the function f := x -> exp(x); #The function must be 0 for x=0 g:= x -> f(x ) -f( 0); #We calculate the coefficient of the entire series a := n->eval(diff(g(x), x$n), x = 0)/factorial(n); #Values of s and z z := 1/3; s := 2; #Left hand side s1 := sum(g(z/n^s), n = 1 .. infinity); evalf(s1, 20); #Right hand side ss2 := sum(a(k)*Zeta(k*s)*z^k, k = 1 .. infinity); evalf(ss2, 20);

  Some similar formulas are already known, for example [3, p. 691, §5.1.27] (with the sign of the fraction1 2 corrected to be negative)

	8.11. From
					∞ n=1	1 4n 2 -1		=	1 2	,
	and z = -1/4 in the first formula (1), we have
					∞ n=1	ζ(2n) 4 n =	1 2	.
	8.12. With z = -1/16, the first formula (1) gives
					∞ n=1	ζ(2n) 16 n =	1 2	-	π 8	.
	8.13. ∞ n=1	1 n 4 + 1	=	∞ k=0	(-1) k ζ(4k + 4) = -	1 2	+	π	√ 4	2	sinh(π cosh(π	√ √	2) + sin(π 2) -cos(π √ √ 2) 2)	.

[2, p. 124] "Series wich satisfy the M-test have been called normally convergent by Baire."

avenue de Mortières, 71640 Givry, France E-mail address: claudeh5@free.fr

8.4. Theorem 7 for f (s) = ln(1 + s), ℜe(s)

where

where ϕ(n) is the Euler's totient function. So

8.10. We can use the theorems 6, 8 and the two corollaries with the L-Dirichlet functions. With a n = χ(n), we have by the theorem 6

and by the theorem 8

For example, with the Catalan's zeta-function