Bruno Martin
email: bruno.martin@unice.fr

A Walsh exploration of elementary CA rules

Keywords: Cellular automata, elementary rules, secret key cryptography, pseudorandom generation, Walsh transform

In this paper, we explore the 256 elementary cellular automata rules by a Walsh transform in order to find out correlation-immune rules for generating good pseudo-random sequences. We prove that, except the 8 linear rules, there is no correlation-immune rule among the 256 rules. Thus, Wolfram cellular automata cannot be used as a cryptographic pseudo-random generator since the generated pseudo-random sequences are susceptible of correlation attacks. We conclude with some remarks on cryptography with cellular automata.

Introduction

In his seminal paper [START_REF] Wolfram | Cryptography with cellular automata[END_REF], Wolfram proposed to use cellular automata (CA for short) to build a pseudo-random generator. He suggested that pseudo-random sequences generated by rule 30 could be used for cryptographic purposes as keys for a Vernam-type cipher when run on an initial configuration of 127 cells arranged on a ring. More recently, B. Preneel in [START_REF] Preneel | Analysis and Design of Cryptographic Hash Functions[END_REF] quantifies the security of this pseudo-random generator and claims that it is insecure for an initial configuration of size smaller than 1000. Actually, the pseudo-random sequence generated passed all classical statistical tests, suggesting a good pseudo-random quality. Unfortunately, a few years later, Meier and Staffelbach [START_REF] Meier | Analysis of pseudo random sequences generated by cellular automata[END_REF] proved that the Wolfram pseudo-random generator is in fact very weak. The reason why their attack was successful comes from the fact that there are correlations between the inputs and the output of rule 30. This correlation is used in the attack to recover an initial configuration leading to the same pseudo-random sequence.

In this paper, we propose to use a discrete transform, the Walsh transform, to explore the set of all the 256 elementary CA rules. The Walsh transform is a well-known tool in the field of cryptology for studying the correlation-immunity of Boolean functions: Xiao and Massey [START_REF] Xiao | A spectral characterization of correlationimmune combining functions[END_REF] have characterized the notion of correlation-immunity with the Walsh transform. We apply this technique to the pseudo-random sequences generated by all of the 256 binary rules and we provide evidence that there does not exist a non-linear rule which generates a correlation-immune pseudo-random sequence.

The paper is organized as follows: in section 1, we recall the definition of CA and how they are used by Wolfram to generate pseudo-random sequences; we also define the Walsh transform and its relation with correlation-immunity. Section 2 applies the Walsh transform to the set of the 256 binary rules and shows firstly that the choice of rule 30 was the best choice Wolfram could make and, secondly, that this choice does not provide a correlation-immune function. Finally, in section 3, we make final remarks on the generation of pseudo-random sequences with cellular automata and their use in cryptography. We assume the reader familiar with basic concepts of cryptology for which a good introduction is [START_REF] Stallings | Cryptography and Network Security[END_REF][START_REF] Martin | Codage, cryptologie et applications[END_REF].

Definitions and notation

In this section, we briefly recall the definition of cellular automata and we focus on the so called elementary rules (or Wolfram rules). We also define a discrete transform, the Walsh-Hadamard transform which allows to quickly study the space of the rules in order to find rules with low correlation.

Cellular automata

A cellular automaton is generally a bi-infinite array of identical cells which evolve synchronously according to a local transition function and communicate with their nearest neighbors. Here, we consider a ring of N cells which are indexed by Z N . All the cells are identical finite state machines with a finite number of states and a transition function which gives the new state of a cell according to its current state and the current states of its nearest neighbors.

Definition 1 A cellular automaton is a finite array of identical cells indexed by Z N . Each cell is a finite state machine C = (Q, f ) where Q is a finite set of states and f a mapping f :

Q × Q × Q → Q.
The mapping f , called local transition function, has the following meaning: the state of cell i at time t+1 (denoted by x t+1 i ) depends upon the state of cells i-1, i and i + 1 at time t. We have the following equality:

x t+1 i = f (x t i-1 , x t i , x t i+1
). For a fixed t, the sequence of all the values x i for i ∈ Z N , is the configuration at time t. It is a mapping c : Z N → Q which assigns a state of Q to each cell of the cellular automaton.

We will restrict ourselves to the case where the set of states Q = F 2 and f is a Boolean predicate with 3 variables, also called an elementary rule. These cellular automata have been considered by Wolfram in [START_REF] Wolfram | Theory and applications of cellular automata[END_REF]: he considers the 256 different binary cellular automata and associates a natural number to each rule as follows:

(x t i-1 x t i x t i+1
) 111 110 101 100 011 010 001 000

x t+1 i 0 1 0 1 1 0 1 0
The top line gives all possible preimages for f while the bottom line gives the images by f of the three binary values. Thus, f is fully specified by the 8-bit number written on the bottom line (01011010 in our example) which can be translated in basis 10 (as rule number 90 in our example). Equivalently, this rule can be considered as a Boolean function with (at most) 3 variables. Taking rule 90 again, the corresponding Boolean function is

x t+1 i = x t i-1 ⊕ x t i+1 with ⊕ denoting the Boolean XOR function.
More specifically in [START_REF] Wolfram | Cryptography with cellular automata[END_REF][START_REF] Wolfram | Random sequence generation by cellular automata[END_REF], Wolfram uses a one-dimensional cellular automaton for pseudo-random bit generation by selecting the values taken by a single cell when iterating the computation of rule 30 from an initial finite configuration where the cells are arranged on a ring of N cells. Mathematically, Wolfram claims the sequence {x t i } t≥0 is pseudo-random for a given i. Wolfram studied this particular rule extensively, demonstrating its suitability as a high performance randomizer which can be efficiently implemented in parallel; indeed, this is one of the pseudo-random generators which was shipped with the connection machine CM2.

Since we are dealing with pseudo-random generators, some rules are equivalent from this point of view by three transformations. To define the transformations, just recall that a transition is f (x) = y with x ∈ F 3 2 and y ∈ F 2 . In the sequel, we denote by w the mirror image of word w = w 1 . . . w n , w = w n . . . w 1 and by w the word obtained from w by exchanging the 0's by 1's (and conversely) w = w 1 . . . w n . The first is the conjunctive transformation which takes as an input rule r written in binary and returns r. For instance, the conjunctive transformation turns rule 30 into rule 135. The second transformation, called reflexive just changes the order of the x's by: y i = f ( xi ) for i ∈ [[0, 7]]. As an example, with reflexive transformation, rule 30 is changed into rule 86. The last transformation combines both and is called conjunctive-reflexive: [START_REF] Meier | Analysis of pseudo random sequences generated by cellular automata[END_REF]] and it changes rule 30 into rule 149. All these transformations keep the spectral values of the cellular automata dynamics and are thus statistically equivalent.

y i = f ( xi ) for i ∈ [[0,

Walsh transform

Walsh transform allows to compute the correlation between the inputs and the outputs of the iterations of a cellular automaton. One of the great advantages of the Walsh transform is that its computation is even faster than computing a FFT (see [START_REF] Elliott | Fast transforms, algorithms, analysis[END_REF] for instance).

Let us denote by f (x) the value of function f at x = (x 0 , x 1 , x 2 , . . . , x n-1 ) ∈ F n 2 or, equivalently, f (x), the value of f at x = n-1 i=0 x i .2 i , the decimal value corresponding to x. Analogously, let ω = (ω 0 , . . . , ω n-1 ) ∈ F n 2 and ω its corresponding decimal value. The Walsh transform of f is defined by:

S f (ω) = 2 n -1 x=0 f (x) × (-1) x•ω with x • ω = n-1 i=0
x i .ω i denoting the Cartesian product of the two binary vectors. From the spectral values of the Walsh transform, one can recover the function f with the inverse Walsh transform:

f (x) = 2 -n 2 n -1 ω=0 S f (ω) × (-1) x•ω
The Walsh transform has some interesting statistical properties. For instance, the value of the transform at point 0 equals the mean value of the function:

S f (0) = E[f (x)] = 2 n-1
. This property permits to test whether f is balanced (the number of 0 equals the number of 1 in the image domain of f ). In addition, Walsh transform is the main tool to study the correlation-immunity of a function.

Definition 2 A function f : F n 2 → F 2 is k-th order correlation-immune if, given n independent binary random variables X 0 , X 1 , • • • , X n-1 such that P [X i = 0] = P [X i = 1] = 1 2 for i ∈ [[0, n -1]],
then the random variable Z = f (X 0 , X 1 , . . . , X n-1 ) is independent from any random vector (X i1 , X i2 , . . . ,

X i k ), 0 ≤ i 1 < • • • < i k < n.
In [START_REF] Xiao | A spectral characterization of correlationimmune combining functions[END_REF], Xiao and Massey have characterized (k-th order) correlation-immunity with the Walsh transform. We recall this result in Theorem 1 in which the Hamming weight just counts the number of non-zero values in a vector.

Theorem 1 A function f : F n 2 → F 2 is k-th order correlation-immune if and only if S f (ω) = 0 for all ω = (ω 0 , ω 2 , • • • , ω n-1 ) = 0 whose Hamming weight is at most k.
For readers interested in a readable proof of theorem 1, one can refer to [START_REF] Zémor | Cours de cryptographie[END_REF].

Actually, the idea of using Walsh transform to test pseudo-random generators comes from [START_REF] Yuen | Testing random number generators by Walsh transform[END_REF]. In this paper, Yuen observed that a truly random sequence has an asymptotically flat Walsh power spectrum. This observation was used to devise a new test for randomness of the output of pseudo-random generators. It was an improvement of the tests described in Knuth [START_REF] Knuth | Seminumerical Algorithms[END_REF] who does not deal with cryptographic pseudo-random generation.

A correlation study of Wolfram rules

We use a Walsh transform to study all the 256 elementary CA rules in order to find the best (non-linear) rules for generating pseudo-random sequences. To Table 1: "Good" rules after selection and their equivalent rules.

check the rules, we use the fast Walsh transform algorithm proposed in [START_REF] Elliott | Fast transforms, algorithms, analysis[END_REF] whose time complexity is O(n log n). We proceed step by step.

We first remove all non-balanced rules by computing their Walsh transform; we only select rules f for which S f (0) = 4; there are only 70 remaining balanced rules.

Among the 70 balanced rules f i , we compute the maximum absolute value of the Walsh transform of the t th -iterate of f i at all the points ω of Hamming weight 1 and we select the rules with a minimum spectral value. That is, we select rules f i such that: min

fi max ω=2 ℓ |S f (t) i (ω)|
where t denotes the iteration number and ω is the binary expansion of 2 ℓ for ℓ ∈ [[0, 2t + 1]], all the t bit vectors of Hamming weight one. Equivalently, we just test if, among the 70 balanced rules, there are some which are first order correlation-immune. After this, there are only the 12 remaining rules listed in table 1 still containing linear rules which we recall in table 2. In table 2, the binary value encoding Wolfram's rule is written with the most signifiant bit on the rightmost part.

Finally, if we remove the 8 linear rules, the best remaining rules are 30, 135, 86 and 149 which are all equivalent by conjunctive, reflexive and conjunctivereflexive transformations. None of them is first order correlation-immune nor correlation-immune as well. Thus, we can state that: Theorem 2 There is no non-linear correlation-immune elementary cellular automaton.

That is the reason why pseudo-random sequences generated in this way can be reversed by a correlation attack like the one proposed in [START_REF] Meier | Analysis of pseudo random sequences generated by cellular automata[END_REF], although pseudorandom sequences generated by rule 30 (or, equivalently by rules 86, 135 and Boolean function binary decimal

x i ⊕ x i+1 00111100 60 x i-1 ⊕ x i 01100110 102 x i-1 ⊕ x i+1 01011010 90 x i-1 ⊕ x i ⊕ x i+1 01101001 150 x i-1 ⊕ x i 10011001 153 x i ⊕ x i+1 11000011 195 x i-1 ⊕ x i+1 10100101 165 x i-1 ⊕ x i ⊕ x i+1 10010110 105
Table 2: Linear rules and their corresponding Boolean functions.

149) pass classical statistical tests like the ones proposed in [START_REF] Knuth | Seminumerical Algorithms[END_REF]. The attack proposed by Meier and Staffelbach in [START_REF] Meier | Analysis of pseudo random sequences generated by cellular automata[END_REF] is simple. It suffices to write the way to obtain the sequence generated by rule 30:

x t+1 i = x t i-1 ⊕ (x t i ∨ x t i+1 ) (1)
and to use the partial linearity to rewrite equation 1 as:

x t i-1 = x t+1 i ⊕ (x t i ∨ x t i+1 ) (2)
From equation 1, the site values corresponding to the pseudo-random sequence are build from a triangle in the time-space diagram. And, from equation 2, one can guess the values of the leftmost part of the triangle (or equivalent partial configurations) and then find an initial configuration for generating the pseudorandom sequence, exploiting the correlation.

Conclusion

So, does theorem 2 destroy any hope to design a good pseudo-random generator by the means of cellular automata? Not necessarily. For instance, in [START_REF] Sipper | Co-evolving parallel random number generators[END_REF] it was proposed to use co-evolving non-uniform cellular automata for that purpose. In this model, each cell may contain a different rule obtained by an evolutionary approach (genetic algorithm), usually 2-3 rules for the cellular automaton. A series of tests (including χ 2 test, serial correlation coefficient, entropy and Monte Carlo, but no correlation-immunity analysis) was made with good results, showing that co-evolving generators are at least as good as the best available CA randomizer. The drawback here is that the authors also use Wolfram-like rules which we proved to be not correlation-immune. This approach was further investigated more recently in [START_REF] Seredynski | Cellular automata computations and secret key cryptography[END_REF]. In this paper, the authors generalize the former approach by considering also rules of radius 1 and 2 for non-uniform cellular automata. They find a new set of rules that were tested by a number of statistical tests required by the FIPS 140-2 standard [START_REF]Security requirements for cryptographic modules[END_REF] and the Marsaglia tests implemented in the Diehard program but no correlation-immunity analysis was made. And, for both approaches, it is recalled in [START_REF] Zémor | Cours de cryptographie[END_REF] that it can be dangerous to combine "bad rules". Last but not least, there is currently a great challenge in the use of a good pseudo-random generators; not only for use as a key for a Vernam-type cipher but also for computing a cryptographic hash function. Actually, from the collision attacks on MD5 and other hash functions (see [START_REF] Klima | Finding MD5 collisions -a toy for a notebook[END_REF] and [START_REF] Wang | How to break MD5 and other hash functions[END_REF]), one could use the improvements proposed by [START_REF] Daemen | A framework for the design of one-way hash functions including cryptanalysis of Damgård's one-way function based on a cellular automaton[END_REF] and later by [START_REF] Mihaljevic | A cellular automaton based fast one-way hash function suitable for hardware implementation[END_REF] of the hash function based on cellular automata which was originally suggested by Damgård in [START_REF] Damgård | A design principle for hash functions[END_REF]. And, in order to design a secure cryptographic hash function, we need to have a robust pseudo-random generator.


Patrick Lacharme

Bruno Martin

Patrick Solé

Boolean Functions: Cryptography and Applications BFCA'08 Fonctions Booléennes : Cryptographie & Applications PSEUDO-RANDOM SEQUENCES, BOOLEAN FUNCTIONS AND CELLULAR AUTOMATA

Keywords: Cellular automata, pseudo-random sequences, resilience, nonlinearity

Generation of pseudo-random binary sequences by one-dimensional cellular automata is surveyed using both uniform and hybrid automata. The updating function is a Boolean function that must satisfy criteria of resilience and nonlinearity for the sequence they generate to be secure for a stream cipher application.

Introduction

Cellular automata (CA) are models of finite state machines used in many applications of computer science. In particular, they are is employed for the generation of binary pseudo-random sequences in cryptography. In the present work, we survey methods to generate binary pseudo-random sequences with cellular automata. We particularly focus on the search for good updating functions.

Section 1 presents the different cellular automata for sequence generation and a surveys their cryptographic applications. Section 2 concentrates on uniform cellular automata, particularly on the properties required for the updating function. An exhaustive list of rules satisfying the properties is given. Section 3 surveys the generation of pseudo-random sequences by hybrid cellular automata and proposes the generation of classical sequences by CA synthesis. At last, cryptographic applications of hybrid cellular automata are sketched.

Cellular automata and pseudo-random generation

Uniform cellular automata

One-dimensional binary cellular automata consist of a line of cells with binary values. For practical implementations, the number of cells is finite. There are two cases: a CA is boundary if the cells are arranged in a circular register and it is null-boundary when both extremal cells are fed with zeroes. All the cells are finite state machines with an updating function which gives the new state of the cell according to its current state and the current state of its nearest neighbors.

S. Wolfram proposes in [START_REF] Wolfram | Random sequence generation by cellular automata[END_REF] to use cellular automata to produce pseudo-random sequences. He considers one-dimensional binary cellular automata with ℓ cells with ℓ = 2N + 1. All the cells are identical finite state machines with binary states. For an uniform CA, the values of the cells at time t are updated synchronously with a Boolean function f with n = r 1 + r 2 + 1 variables by the rule x i (t + 1) = f (x i-r 1 (t), . . . , x i (t), . . . , x i+r 2 (t)) .

For a fixed t, the sequence of the values x i for 1

≤ i ≤ 2N + 1, is the configuration at time t. It is a mapping c : [[1, 2N + 1]] → F 2
which assigns a state of F 2 to each cell of the cellular automaton. The initial configuration (at time 0) x 1 (0), . . . , x ℓ (0) is the seed of the generator, the sequence (x N (t)) t is the output sequence and, when r 1 = r 2 = r, the number r denotes the radius of the rule. For example, let us consider the following updating function f :

f (x i-1 , x i , x i+1 ) = x i-1 XOR (x i OR x i+1 ).
The truth table of the Boolean function f is

x 3 0 1 0 1 0 1 0 1 x 2 0 0 1 1 0 0 1 1 x 1 0 0 0 0 1 1 1 1 f (x 1 , x 2 , x 3 ) 0 1 1 1 1 0 0 0 J-F. Michon, P. Valarcher, J-B. Yunès (Eds.): BFCA'08
The binary sequence 00011110 is the binary representation of the natural number 30 and allows to give a numbering of the rules (rule [START_REF] Wolfram | Cryptography with cellular automata[END_REF] in this case). In this paper, this notation is kept to describe a Boolean function. In the rest of this paper the additions of integers in Z will be denoted by + and Σ and additions in F 2 will be denoted by ⊕ and . For simplicity and when there will be no ambiguity, we shall denote by + the addition of binary vectors.

f (x) = u∈F n 2 a u ( n i=1 x u i i ).
If we consider rule (30) again, its ANF is the polynomial

x 1 ⊕ x 2 ⊕ x 3 ⊕ x 2 x 3 .
The degree of the ANF denoted by d • f is called the algebraic degree of the function. This makes sense thanks to the existence and uniqueness of the ANF. The Hamming weight w

H (f ) of f is the number of vectors x in F n 2 such that f (x) = 1. A function is balanced if w H (f ) = w H (1⊕f ), i.e. w H (f ) = 2 n-1 . The Hamming distance between f and g is d H (f, g) = w H (f ⊕ g).

Hybrid cellular automata

When the rules are not identical for all the cells, the automaton is called non uniform, (or hybrid ) and is denoted HCA. Moreover if the rules are linear, the automaton is called linear hybrid cellular automata (LHCA).

In [START_REF] Cattell | Synthesis of one-dimensional linear hybrid cellular automata[END_REF][START_REF] Serra | The analysis of one dimensional cellular automata and their aliasing properties[END_REF], Muzio et al. consider linear hybrid cellular automata using two different linear rules. They assume the CA null-boundary and the linear updating rules are (90) and (150). A similarity transform between LHCA and linear feedback shift register is proposed in [START_REF] Cattell | An explicit similarity transform between CA and LFSR matrices[END_REF] and was recently improved in [START_REF] Kagaris | A similarity transform for linear finite state machines[END_REF].

Cellular programming approach

Tomassini and Sipper [START_REF] Sipper | Co-evolving parallel random number generators[END_REF] proposed to use hybrid cellular automata for generating better pseudo-random sequences. In this model, the rules are obtained by an evolutionary approach (a genetic algorithm). They have designed a cellular programming algorithm for cellular automata to perform computations, and have applied it to the evolution of pseudo-random sequence generators. Their approach uses Koza's entropy E h = -k h j=1 p h j log 2 p h j where k denotes the number of possible values per sequence position, h a subsequence length and p h j is a measured probability of occurrence of a sequence h j in a pseudo-random sequence.

Tomassini and Sipper have selected four rules of radius r = 1 for use in non-uniform cellular automata. The best rules selected by the genetic algorithm were rules 90, 105, 150 and 165 (all linear).

A series of tests (including χ 2 test, serial correlation coefficient, entropy and Monte Carlo, but no correlation-immunity analysis) were made with good results, showing that co-evolving generators are at least as good as the best available CA randomizer. The authors also use elementary rules which were proved to be not correlation-immune. This was further investigated in [START_REF] Seredynski | Cellular automata computations and secret key cryptography[END_REF].

Following the same kind of approach, Seredynski et al. in [START_REF] Seredynski | Cellular automata computations and secret key cryptography[END_REF] have generalized the selection process to radius 2 rules. They use then both radius 1 and radius 2 rules in hybrid cellular automata. The rules selected by their genetic algorithm were 30, 86, 101 and 869020563, 1047380370, 1436194405, 1436965290, 1705400746, 1815843780, 2084275140 and 2592765285.

Their new set of rules was tested by a number of statistical tests required by the FIPS 140-2 standard [START_REF]Security requirements for cryptographic modules[END_REF] and the Marsaglia tests implemented in the Diehard program but no correlation-immunity analysis was made either.

Moreover, the entropy calculation used in cellular programming approach reduces the efficiency of the algorithm.

Cryptographic applications

In [START_REF] Wolfram | Cryptography with cellular automata[END_REF] Wolfram proposed to use cellular automata for a stream cipher application. In this case, it must be hard to find the current state (and the seed in particular) from the output sequence (known plaintext attack). An exhaustive search can be done over the 2 ℓ possible initial states, but for large ℓ, exhaustive search becomes impossible. In [START_REF] Wolfram | Cryptography with cellular automata[END_REF], the cellular automaton is a simple one-dimensional uniform cellular automaton with a 3-variable updating rule.

Next, cellular automata are used in many area in cryptography. In symmetric cryptography, a block cipher proposed in [START_REF] Kar | Theory and applications of cellular automata in cryptography[END_REF] has been broken in [START_REF] Blackburn | Comments on "theory and applications of cellular automata in cryptography[END_REF], using the linearity of the updating function and the block cipher of [START_REF] Sen | Cellular automata based cryptosystem (CAC)[END_REF] using linear and non linear rules has been successfully cryptanalysed in [START_REF] Bao | Cryptanalysis of a new cellular automata cryptosystem[END_REF]. Other propositions of block ciphers are [START_REF] Mukhopadhyay | Cellular automata : an ideal candidate for a block cipher[END_REF] and [START_REF] Joshi | Design and analysis of a robust and efficient block cipher using cellular automata[END_REF]. Some hash functions are proposed in [START_REF] Damgard | Design principle for hash functions[END_REF] (broken in [START_REF] Daemen | A framework for the design of one-way hash functions including cryptanalysis of damgard's one-way function based on a cellular automaton[END_REF]) and [START_REF] Mihaljevic | A cellular automaton based fast one-way hash function suitable for hardware implementation[END_REF] and stream cipher in [START_REF] Mihaljevic | An improved key stream generator based on the programmable cellular automata[END_REF] [START_REF] Mihaljevic | A fast and secure stream cipher based on cellular automata over GF(q)[END_REF].

For the design of cryptographic cellular automata, updating rules should have an adapted radius and desired properties. In all cases, the choice of the updating rules in the cellular automaton is a fundamental criterion for the security of the crypto-system.

Uniform cellular automata

3-variable updating function and rule (30)

The investigation of S. Wolfram [START_REF] Wolfram | Cryptography with cellular automata[END_REF] is concentrated on updating functions f with 3 variables, i.e. r 1 = r 2 = 1. In particular, he considered rule (30) defined by

f (x i-1 , x i , x i+1 ) = x i-1 XOR (x i OR x i+1 ), or equivalently f (x i-1 , x i , x i+1 ) = x i-1 + x i + x i+1 + x i x i+1 mod 2.
S. Wolfram claims the sequence (x t i ) t≥0 is pseudo-random for a given i. He extensively studied this particular rule, demonstrating its suitability as a high performance randomizer which can be efficiently implemented in parallel; this is one of the pseudo-random generators which was shipped with the connection machine CM2 and which is currently used in the Mathematica software.

Attack of Meier and Staffelbach

The first attack on this pseudo-random generator is proposed by W. Meier and O. Staffelbach in [START_REF] Meier | Analysis of pseudo random sequences generated by cellular automata[END_REF]. The output sequence (x N (t)) t is known for t = 0, . . . , N . The sequence (x N +1 (t)) t is called right adjacent sequence. The principle is that if the right adjacent sequence is known for t = 0, . . . , N -1, then half of the seed x 0 (0), . . . , x N -1 (0) is known, using the partial linearity of f :

x i-1 (t) = x i (t + 1) XOR (x i (t) OR x i+1 (t)).
This attack is successfull if the right adjacent sequence is easily constructed. Statistical experiments show that there are only few possibilities for the right adjacent sequence. As noted in [START_REF] Martin | A Walsh exploration of elementary CA rules[END_REF], this phenomenon comes from the correlation between the inputs and the outputs of rule [START_REF] Wolfram | Cryptography with cellular automata[END_REF]. Indeed, we have

P r (x i (t + 1) = 1 ⊕ x i-1 (t)) = 3 4 .
In order to counter this attack, the updating function must be resilient. This concept is introduced by T. Siegenthaler, in relation with correlation attacks on stream ciphers [START_REF] Siegenthaler | Correlation-immunity of nonlinear combining functions for cryptographic applications[END_REF].

Definition 2.1 (Resilient functions). A Boolean function f mapping F n

2 to F 2 is t-resilient if for any coordinates i 1 , . . . i t , for any binary constant c 1 , . . . , c t and for all y ∈ F 2 ,

P r(f (x) = y | x i 1 = c 1 , . . . , x it = c t ) = 1 2 ,
where x i with i / ∈ {i 1 , . . . , i t } verifies P r(x i = 1) = P r(x i = 0) = 0.5.

For a Boolean function f with n variables, the Walsh transform

f of f is defined over F n 2 by f (u) = x∈F n 2 (-1) f (x)⊕u•x .
The Walsh transform of f is related to the Hamming weight of the function f ⊕ l b (where

l b (x) = b • x) via the relation: f (b) = 2 n -2w H (f ⊕ l b ). It satisfies Parseval's relation: b∈F n 2 f 2 (b) = 2 2n . (1)
G.Z. Xiao and J.L. Massey give a spectral characterization of resilient functions [START_REF] Xiao | A spectral characterization of correlationimmune combining functions[END_REF] Theorem 2.2. A Boolean function in n variables is t-resilient iff for all u whose Hamming weight verifies 0 ≤ w H (u) ≤ t, we have f (u) = 0.

J-F. Michon, P. Valarcher, J-B. Yunès (Eds.): BFCA'08

Theorem 2.3. For a t-resilient (0 ≤ t < n -1) Boolean function with n variables, there is an upper bound for its algebraic degree

d: d ≤ n -t -1 if t < n -1 and d = 1 if t = n -1.
Theorem 2.3 shows that the algebraic degree of a 1-resilient function with 3 variables is at most 1, i.e. the Boolean function is linear. B. Martin has explored all the Boolean functions in 3 variables and concludes that there is no non linear function in 3 variables which is 1-resilient [START_REF] Martin | A Walsh exploration of elementary CA rules[END_REF] which is also a consequence of the Siegenthaler bound [START_REF] Siegenthaler | Correlation-immunity of nonlinear combining functions for cryptographic applications[END_REF].

Attack of Koç and Apohan

The second attack against rule (30) is proposed by C.K. Koç and A.M. Apohan [START_REF] Apohan | Inversion of cellular automata iterations[END_REF].

The algorithm is based on the linear approximation of the updating function. The resistance to this attack depends on the distance between the updating function and the set of all linear functions. Let l be the best linear approximation of the updating function f with n variables and A the number of points such that f (x) = l(x). Let α = A/2 n be the probability than f (x) = l(x). Then the algorithm requires at most 2 (n-1)(1-α)l trials for arbitrary nonlinear functions and seed. Under these conditions, the number α must be small. Definition 2.4 (Nonlinearity). Let f be a Boolean function mapping F n 2 to F 2 . The nonlinearity N f of f is defined by

N f = min (a 0 ,...,an)∈{0,1} n+1 d H (f (x), a 0 ⊕ a 1 x 1 ⊕ • • • ⊕ a n x n ) .
The relation between Walsh transform and nonlinearity comes from W. Meier and O. Staffelbach [START_REF] Meier | Nonlinearity criteria for cryptographic functions[END_REF].

Theorem 2.5. Let f be a function mapping F n 2 to F 2 . Then

N f = 2 n-1 - 1 2 max u∈F n 2 | f (u)| ,
and

N f ≤ 2 n-1 -2 n 2 -1 . (2)
A cellular automaton resists the attack of [START_REF] Apohan | Inversion of cellular automata iterations[END_REF] if the nonlinearity of its updating function is high. Boolean functions where nonlinearity meet the bound (2) are called bent functions. Bent functions in an even number of variables exist but are never balanced. Moreover, there is a tradeoff between resilience order and nonlinearity [START_REF] Sarkar | Nonlinearity bounds and constructions of resilient boolean functions[END_REF] : Theorem 2.6. Let f be a Boolean function t-resilient over F n 2 . Then there is an upper bound on the nonlinearity of f :

N f ≤ 2 n-1 -2 t+1 .
By [START_REF] Yuriy | On resilient Boolean functions with maximal possible nonlinearity[END_REF] this bound is tight for t ≥ 0.6n.

4-variable updating functions

In this section, we investigate the 2 16 = 65536 elementary CA rules with 4 variables and give a complete classification of the functions which have good resilience and nonlinearity properties. These functions are used to get cellular automata for generating cryptographic pseudorandom sequences.

An exhaustive search by the Walsh transform of all Boolean functions with 4 variables is realized, to find a list of 1-resilient functions, with high nonlinearity.

There are exactly 200 non linear balanced functions which are 1-resilient and all are quadratics (cubics balanced functions are not resilient by Siegenthaler bound (Theorem 2.3)).

A Boolean function in 4 variables is defined by an integer between 0 and 65536, keeping Wolfram's notation for CA rules with 3 variables. For example, the function (34680), with binary representation 100001110111000 corresponds to the following truth table:

x 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 x 2 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 x 3 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 x 4 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 f (x 1 , x 2 , x 3 , x 4 ) 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 1
For classifying the functions, we use their algebraic normal form (ANF). For instance the ANF of rule (280) (=100011000 in binary) corresponds to the polynomial

f (x 1 , x 2 , x 3 , x 4 ) = x 1 x 2 ⊕ x 3 ⊕ x 4 .
(3)

J-F. Michon, P. Valarcher, J-B. Yunès (Eds.): BFCA'08

For the classification of these functions, let σ denote a 4 by 4 permutation matrix. Two Boolean functions f and g are equivalent if there exists a permutation σ such that f (x) = g(σ(x)) or g(σ(x)) + 1.

The following table gives the set of all 1-resilient function, with a representant of each class f , its corresponding ANF and the cardinal of each class:

f ANF ANF card. 34680 280 x 1 x 2 ⊕ x 3 ⊕ x 4 12 6120 360 x 4 ⊕ x 1 x 2 ⊕ x 1 x 3 ⊕ x 2 x 3 8 7140 300 x 2 ⊕ x 4 ⊕ x 1 x 2 ⊕ x 1 x 3 48 11730 282 x 1 ⊕ x 3 ⊕ x 4 ⊕ x 1 x 2 24 34740 1308 x 2 ⊕ x 3 ⊕ x 4 ⊕ x 1 x 2 ⊕ x 4 x 2 48 39318 4374 x 1 ⊕ x 2 ⊕ x 3 ⊕ x 4 ⊕ x 3 x 4 12 7128 5432 x 3 ⊕ x 4 ⊕ x 1 x 2 ⊕ x 3 x 1 ⊕ x 4 x 2 ⊕ x 4 x 3 24 11220 380 x 2 ⊕ x 3 ⊕ x 1 x 2 ⊕ x 3 x 1 ⊕ x 4 x 2 24
The nonlinearity of these functions is computed for an evaluation of the resistance against the attack of [START_REF] Apohan | Inversion of cellular automata iterations[END_REF]. The 200 1-resilient Boolean functions with 4 variables have a nonlinearity equal to 4. There exist some Boolean function with 4 variables with nonlinearity 6, but they are not resilient, according Theorem 2.6.

Two classes of functions are more interesting because these functions can be inplemented with only 3 logical gates. These functions are (34680) and (39318) or equivalently

f (x 1 , x 2 , x 3 , x 4 ) = x 1 ⊕ x 2 ⊕ (x 3 OR x 4 )
In this case, the two CA are described by the updating function

x i (t + 1) = x i-1 (t) XOR x i (t) XOR (x i+1 (t) AND x i+2 (t)) , and
x i (t + 1) = x i-1 (t) XOR x i (t) XOR (x i+1 (t) OR x i+2 (t)) .
If the resilience order of the updating function must be greater than 1 (for example with a generalization of [START_REF] Meier | Analysis of pseudo random sequences generated by cellular automata[END_REF]), then Boolean functions with 5 variables should be used.

Hybrid Cellular automata

Linear hybrid cellular automata

In the context of sequence generation, several authors consider the case where different cells of the CA use different rules. This model is called hybrid cellular automata. In [START_REF] Cattell | Synthesis of one-dimensional linear hybrid cellular automata[END_REF][START_REF] Serra | The analysis of one dimensional cellular automata and their aliasing properties[END_REF], Muzio et al. consider linear hybrid cellular automata using two different linear rules. The automata are null-boundary and the linear updating rules are (90) and (150). In [START_REF] Cattell | An explicit similarity transform between CA and LFSR matrices[END_REF], LHCA are proved equivalent to linear feedback shift registers.

Let D = [d 0 , . . . , d ℓ-1 ] be a binary vector with the following properties : if d i = 0 then cell i uses rule (90), else cell i uses rule (150). In other terms,

x i (t + 1) = x i-1 (t) + d i .x i (t) + x i+1 (t) mod 2 .
Using this rule, it is possible to a matrix representation of the transition between two consecutive states. Let the current state be s(t) = (x 0 (t), . . . , x ℓ-1 (t)), then

s(t + 1) = A.s(t) , (4)
where the binary matrix A, called transition matrix, is defined by

        d 0 1 0 . . . 0 1 d 1 1 . . . . . . 0 1 d 2 . . . . . . . . . . . . . . . 1 0 . . . 0 1 d l-1        
Let ∆ be the characteristic polynomial of A, that is ∆ = |xId -A|. A polynomial is said to be a HCA polynomial if it is the characteristic polynomial of some HCA. The following theorem gives a property on HCA polynomial [START_REF] Cattell | Synthesis of one-dimensional linear hybrid cellular automata[END_REF][START_REF] Cho | New synthesis of one-dimensional 90/150 linear hybrid group CA[END_REF] :

Theorem 3.1. Let p ∈ F 2 [X]
of degree n and p ′ its formal derivative. Then p is a HCA polynomial if and only if for some solution q for y of the congruence

y 2 + (x 2 + x)p ′ y + 1 ≡ 0 mod p , (5)
J-F. Michon, P. Valarcher, J-B. Yunès (Eds.): BFCA'08

Euclid's greatest division algorithm on p and q results in n degree one quotients.

If the polynomial p is irreducible, then equation ( 5) has exactly two solutions, both of which result in n degree one quotient : Theorem 3.2. Let p ∈ F 2 [X] be an irreducible polynomial. Then p has exactly two HCA realizations with one being reversal of the other.

Given a polynomial, the construction of the corresponding HCA is called the synthesis approach. A detailed method is described in [START_REF] Cattell | Synthesis of one-dimensional linear hybrid cellular automata[END_REF] using this theorem to find HCA polynomial. Moreover, given p and q two irreducible polynomials with corresponding transition matrix P and Q, the transition matrix corresponding to p.q is given by P 0 0 Q . This operation corresponds to concatenation of two LHCA [START_REF] Cattell | Onedimensional LHCA: their synthesis, properties and applications in VLSI testing[END_REF].

Synthesis of classical sequences by LHCA

A semi-bent functions is a Boolean functions in an odd number n of variables, the Walsh transform of which takes only three values 0, ±2 (n+1)/2 . Some of these are traces of AB vectorial functions [START_REF] Carlet | Codes, bent functions and permutations suitable for DES-like cryptosystems[END_REF] in the form f (x) = T r(ax + bx s ), where a, b are scalars of the extension field F 2 n and T r the trace function from F 2 n down to F 2 . For monomial AB functions, the exponents s are in the list of Gold, Kasami, Welch, Niho (see Table 1).

Name s Conditions Gold 2 i + 1 i ∧ n = 1, 1 ≤ i ≤ n/2 Kasami 2 2i -2 i + 1 i ∧ n = 1, 1 ≤ i ≤ n/2 Welch 2 (n-1)/2 + 3 Niho 2 2r + 2 r -1 r = t/2 for t even r = (3t + 1)/2 for t odd with 1 ≤ r ≤ n = 2t + 1 Table 1.

Exponents of Almost Bent monomials

In all cases, for α a primitive element on F 2 n and m α the minimal polynomial of α, the polynomial m α m α s , is used to synthesize HCA. Using these polynomials, sequences with good correlation properties can be synthesized by linear hybrid cellular automata.

Cryptography with LHCA

Linear HCA cannot serve directly as pseudo-random sequence generators for cryptography. Equation ( 4) is used to describe any current state of the CA in terms of the initial state by the relation

s(t) = A .s(0) . (6)
Let N be the index of the cell which gives the output sequence (s N (t)) t of the CA. Then

s N (t) = a N (t).s(0) , (7)
where a N (t) denotes the ℓ-bit vector corresponding to the row N of the matrix A t . In this case, the initial state is known by the inversion of the binary linear system according to [START_REF] Cattell | Onedimensional LHCA: their synthesis, properties and applications in VLSI testing[END_REF].

In these conditions, the binary vector D = [d 0 , . . . , d ℓ-1 ] must be non constant. If the vector D changes in function of s(t), e.g.

d i (t) = s i+2 (t), then s i (t + 1) = s i-1 (t) ⊕ s i (t) ⊕ d i (t).s i+1 (t) . (8)
In this case, we get the non linear Boolean function (280) of section 2 again. In fact, if d i (t) is a linear combination of bits of the current state s(t), then the updating function corresponds to a quadratic Boolean function.

An other possibility is to consider the vector [d 0 , ..d n-1 ] = [y 0 (t), .., y n-1 (t)], where the bits y i (t) are the internal state of an other CA. Generalizing this system, a cascade of n CA is constructed, where the state of the nth CA corresponds to the vector D of the n + 1th CA. This cascade provides high quality pseudo random sequence and a possibility for larger cycles.

We illustrate our previous proposition by an example: let CA 1 be a uniform CA using rule (39318) of length ℓ. The internal state of CA 1 corresponds to the binary vector D = [d 0 , . . . , d ℓ-1 ] and the rule of the second automaton CA 2 is described by equation [START_REF] Cho | New synthesis of one-dimensional 90/150 linear hybrid group CA[END_REF].

The output sequence of this generator is given by the sequence (s N (t)) t where s is the internal state of CA 2 and ℓ = 2N + 1.

In this case, the cryptanalysis of the pseudo random generator of proposed in [START_REF] Blackburn | Comments on "theory and applications of cellular automata in cryptography[END_REF] is not possible because rules are non linear and the output of the generator consists in just one bit.

As proposed in [START_REF] Mihaljevic | An improved key stream generator based on the programmable cellular automata[END_REF], it is suitable that the output sequence is not directly one (or several) bit of the current state. In this case the output sequence is filtered by a Boolean function. This scheme is a variant of the classical filtered linear shift register. The Boolean function must have the same properties as high nonlinearity or resilience order.

Conclusion

We have used the synthesis approach to give an effective CArealization of classical sequences with good correlation properties. We have also presented good and bad ways to construct pseudorandom binary sequences for cryptographic applications with cellular automata.

The main interest of this work concerns the hardware implementation. The target hardware model of CAs is the Field Programmable Gate Arrays (known as FPGAs).These devices consist of an array of uncommitted logic gates whose function and interconnection is determined by downloading information to the device. When the programming configuration is held in static RAM, the logic function implemented by those FPGAs can be dynamically reconfigured in fractions of a second by rewriting the configuration memory contents. Thus, the use of FPGAs can speed up the computation done by the cellular automata.

These results can be extended in many directions. If the number of variables of the Boolean function must be increased, the research of good updating rules is a classical problem in symmetric cryptography. Other applications of CA than pseudo random generation (e.g. hash functions) can also be investigated.

  If x and b are two binary vectors, we denote by x • b their usual inner product x • b = n i=1 x i b i . We also recall the definition of the algebraic normal form as an alternative representation of Boolean functions. Definition 1.1. A Boolean function f with n variables is represented by a binary polynomial in n variables, called algebraic normal form (ANF):

J-F. Michon, P. Valarcher, J-B. Yunès (Eds.): BFCA'08

Acknowledgements

The authors thank Sihem Mesnager for helpful comments.

J-F. Michon, P. Valarcher, J-B. Yunès (Eds.): BFCA'08


Thamyres Fernandes

Messa Moreira Ab

Sidney Aquino Neto

Charly Lemoine

Boniface Kokoh

Cláudia Morais

Wilhelmin Napporn
email: teko.napporn@univ-poitiers.fr

Paulo Olivi
email: olivip@usp.br

Rhodium effects on Pt anode materials in a Direct Alkaline Ethanol fuel cell

The development of efficient catalysts for ethanol oxidation in alkaline medium requires a synthetic approach that may prevent the surfactant molecules from being adsorbed at the catalytic sites and decreasing the electrochemical performance of the final direct ethanol fuel cell. To this goal, the recently reported surfactant-less Bromide Anion Exchange (BAE) method, appears as a promising route to conveniently aim at preparing PtRh alloys dispersed on carbon substrate. The catalysts prepared herein by the BAE method were characterized physicochemically to obtain structural information on the PtRh/C nanomaterials, their morphology (size and shape), and their chemical and surface composition. Electrochemical behavior and properties of these electrodes were then investigated in a halfcell before the implementation of a direct ethanol fuel cell (DEFC) in a home-made anion exchange membrane Teflon cell. The analysis of the electrolytic solution in the anodic compartment by chromatography revealed that acetate was the major reaction product and the carbonate amount increased with the Rh content in the bimetallic composition. With 2.8-3.6 nm particle sizes, the Pt50Rh50/C catalyst exhibited the highest activity towards the ethanol electrooxidation.

Introduction

The interest in sustainable energy sources and converter systems that combine efficiency and reduction of environmental footprint is increasing 1 . In this diversification of the energy resources to face the growing energy demand, the development of Direct Ethanol Fuel cell (DEFC) in the domain of renewable and green energy devices constitutes a breakthrough 1,2 . Indeed, ethanol can be produced from biomass (sugar cane, corn, and wheat) 3 . Particularly in Brazil, there is a great interest in the development of ethanol containing devices because of its current large-scale production and distribution [4][5][6][7] . Furthermore, as in a fuel cell the chemical energy is converted directly into electrical energy, the energy density of ethanol is close to that of gasoline without the toxicity of the latter fossil fuel (8.0 vs. 10.5 kWh kg -1 ) 4,8,9 .

The key issue to improve the performance of DEFCs is the complete oxidation of ethanol to CO2 which involves 12 electrons 6,7 . However, the sluggish kinetics of ethanol oxidation reaction (EOR) and the 2 or 4 electron-pathway efficiency still remain the main obstacle for the development of this sustainable fuel cell [10][11][12][13] . Importantly, this partial oxidation of ethanol is due to the weak cleavage rate of the C-C bond through the electrochemical process at low temperature 14,15 . Thereby, acetaldehyde and acetic acid (or acetate) are the main reaction compounds obtained and often CO2 (or carbonate) is obtained under traces state 8,16 . Accordingly, the enhancement of the ethanol-to-CO2 conversion requires a dissociative adsorption at lower potentials and at the same time the removal of poison species with an effective bifunctional catalyst [17][18][19] .

Platinum appears to be the most active catalyst material used in EOR 20,21 . However, it has a catalytic activity loss throughout the reaction process due to the strong adsorption of intermediates such as carbon monoxide (CO), which progressively blocks the electrode surface 3,22 . One way to avoid this poisoning effect or at considerably decrease its effect is to combine Pt with other metals such as ruthenium (Ru), iridium (Ir), molybdenum (Mo), nickel (Ni), cobalt (Co), bismuth (Bi), tungsten (W), and rhodium (Rh) 11,20,[22][23][24][25][26][27] . These latter elements act as co-catalysts to enhance the EOR rate and the CO tolerance of Pt, which has been explained by a bifunctional mechanism or an electronic effect 3 . Rh is reported to be an active co-catalyst in the C-C bond cleavage during the EOR. Indeed, its presence in the Pt-based electrode composition leads to the shift of the onset potential towards lower values 24,28,29 . In acid medium, this modification can be noticed in the reaction products distribution in which the concentration of acetaldehyde decreases when that of CO2 increases, compared to the findings at the surface of Pt alone 12,30,31 . Recently, Mukherjee et al. 26 investigated the EOR in alkaline medium using Pt-Rh alloys supported on nickel. They showed that the addition of Rh promotes remarkably the reaction process, including the formation of carbonate-like final reaction product. The authors concluded that the molar ratio Pt/Rh influenced the equilibrium of the current density for EOR. However, more studies and understandings in alkaline medium are required for bimetallic PtRh catalysts. Catalysts for EOR can be more active in alkaline medium than in acid medium 17,32,33 because working at high pH values increments the hydroxyl ions (OH -) concentration in the system and provides an additional OH -adsorption on the catalyst surface, enhancing the oxidation reaction 11,34 . Additionally, properties such as particle size, morphology and porosity also influence directly the performance of the electrocatalyst and can be controlled by the synthesis method 12,23 . Several preparation methods of PtRh catalysts were proposed in the literature such as electrodeposition 17, 35 microwave-assisted 12 , hydrothermal synthesis 36 , polyol method 31,[37][38][39] , and, borohydridereduction method [40][41][42][43][44] . However, to avoid any limitation in activity due to the remained organic surfactants on the catalysts, a suitable synthesis approach is required 45 . Therefore, the Bromide Anion Exchange (BAE) method considered as a cleaner and simple approach using water as solvent [45][46][47] was used to develop the electrocatalysts 45,47,48 . It consists in exchanging chloride anion by the bromide one as ligand in the complex structure of the metal salt in order to efficiently control the particles growth. Differently from the direct borohydride reduction method, in the BAE synthesis route the use of bromide anion promotes through its size a great steric effect, which stabilizes the particle during the reduction process with sodium borohydride 47 . Thereby, it controls the particle size as well as nanoparticles dispersion on the carbon support. Therefore, BAE method was revisited and adapted for the first time to the development of PtxRhy alloys. In the present work, we investigated in alkaline medium the electroactivity of PtxRhy catalysts prepared by BAE method. The EOR was evaluated in alkaline medium to understand the central role of Rh in high pH conditions and to determine the key parameters in the reaction products distribution.

Results and Discussions

Physical characterizations

PtxRhy/C electrocatalysts were elaborated by using the bromide anion exchange method. This method was revisited and optimized for PtxRhy/C nanomaterials. The optimized synthesis procedure is extensively described in the electronic supplementary information (ESI) as well as their corresponding characterizations.

The XRD patterns of the PtxRhy/C materials are shown in Figure 1. The diffractogram peaks of the PtxRhy/C can be referred to the (111), ( 200), (220), and (311) reflection planes of platinum fcc-type structure 12 and those of Rh/C correspond to the (111), ( 200), (220), and (311) reflection planes of rhodium. Pt and Rh have similar crystallographic profiles, with very close lattice parameters (0.39231 nm for Pt and 0.38031 nm for Rh) 38 . Figure 1 Table 1 summarizes the data related to the structural properties and the morphology (Figure SI-1) of the PtxRhy/C catalysts obtained by the BAE surfactant-free route. In comparison with recent literature, the proposed synthetic approach displays a good correlation of crystallite size values and permitted to recover lower particle sizes, which is synonymous to a gain of surface area and thus, an increase of the catalytic activity of the resulting electrode materials 35 . Figure 2a illustrates a TEM micrograph and a particle EDX analysis (Figure 2b) for the Pt50Rh50/c catalyst. The TEM images show that the catalyst particles are well dispersed. The formation of Pt and Rh alloy is evidenced by EDX spectra which results were summarized in Table 1. The other PtxRhy/C compositions are depicted in Figure SI-4 for comparison. As an example, the impregnation route led to PtxRhy/C materials with crystallite sizes comprised between 5 and 12 nm diameter 28,49 . It can be also noticed in Table 1 an increase in the alloying degree [50][51][52] in the PtxRhy/C catalysts as a function of the Rh content, which may be deduced from the lattice contraction with an incorporation of smaller Rh atoms into the Pt fcc-structure during the synthesis process 53,54 . As the measurements above reveal that the Pt50Rh50/C catalyst contains the highest alloying degree and as its physical properties (good dispersion and distribution size of the particles) are well correlated with the electrochemical ones (highest SECSA), the XPS analysis is first addressed to probe its surface chemical composition. Table 2 summarizes the surface composition analyses based on the intensities of XPS peaks. The results indicated that Pt/Rh atomic ratios are quite different from the nominal values. This can be attributed mainly to the difference in the reduction potentials between Rh and Pt (for Rh E 0 ~ 0.4 V and Pt E 0 ~ 0.74 V in the presence of chloride ions) affecting the reduction species in case of simultaneous process, like in BAE method 55,56 .

Table 1: Physicochemical parameters issued from XRD, TEM and EDX measurements for the PtxRhy/C catalyst compositions prepared from the revisited BAE synthesis method. 3f displaying the ethanol oxidation reaction (EOR) at the bimetallic Pt50Rh50/C electrode surface: i) the fuel oxidation starts earlier (at 0.14 V) than its oxidative transformation on Pt/C (0.29 V) or on Rh/C (0.22 V vs. RHE). This shift toward lower potential values is well-known and attributed to the electronic effect herein evidenced both with the 51% alloying degree (XRD) and the shift observed in the binding energies of Pt4f (XPS) [2, 12, 21]; ii) at the same time, the 2.5 times increase in the current densities, compared to those on Pt/C, reveals a surface structure effect due to the presence of Rh atoms on the Pt based structure. The EOR on the Pt50Rh50/C electrode during the forward scan covers a large potential domain. It hides various peaks at different Pt and Rh surface states, which involve reactive oxygenated species for enhancing ethanol oxidation through the bifunctional or Langmuir-Hinshelwood mechanisms. Interestingly, Figure 3e shows a remarkable ethanol oxidation at the surface of Rh/C which was reported to be practically inactive towards the EOR in acid media 17,57 . This activity of the Rh/C catalyst may be due to an ability of hydroxides formation at low potential on the material surface in alkaline medium (Figure 3b). Taking into account only the reaction products detected by chromatographic analysis, a general mechanism for the conversion of ethanol to acetate on Pt50Rh50/C can be proposed according to the following equation:

𝐶𝐻 3 -𝐶𝐻 2 𝑂𝐻 + 5𝐻𝑂 -𝑃𝑡 50 𝑅ℎ 50 → 𝐶𝐻 3 𝐶𝑂𝑂 -+ 4𝐻 2 𝑂 + 4𝑒 - (1)
In alkaline medium, the reaction can take place at both Pt and Rh sites, since in Figures 3e and3f, it can be seen that ethanol is reactive on the two metals comprising the bimetallic anode. On the other hand, the increase in the carbonate concentration can undoubtedly be explained by the presence of Rh which provides a beneficial effect to Pt. It can be assumed that during the dissociative adsorption of ethanol, a bifunctional catalysis occurs to facilitate the desorption of poison species such as CO, as follows:

𝑃𝑡 -𝐶𝑂 𝑎𝑑𝑠 + 𝑅ℎ -𝑂𝐻 𝑎𝑑𝑠 + 3𝐻𝑂 -→ 𝐶𝑂 3 2-+ 2𝐻 2 𝑂 + 𝑒 - (2)
It was reported that bridge CO adsorbs on Rh 38 , and in this case the CO oxidative removal can be achieved with the contribution of neighboring Pt:

𝑅ℎ -𝐶𝑂 -𝑅ℎ + 𝑃𝑡 -𝑂𝐻 𝑎𝑑𝑠 + 3𝐻𝑂 -→ 𝐶𝑂 3 2-+ 2𝐻 2 𝑂 + 𝑒 - (3)
Chronoamperometric measurements were also depicted in supplementary information (Figure SI-7).

Although over the long term the activities of all catalysts are undifferentiated, Pt50Rh50 has the highest current densities within the first ten minutes.

Electrochemical performances of PtxRhy/C in DEFC

The direct ethanol fuel cell (DEFC) testing was undertaken in a home-made Teflon cell. Although the two compartments were separated with an AEM (from Fumatech) as reported recently 58 , and here showed in the supplementary material, the electrode materials were not coated on the membrane as a MEA; the investigation is herein focused on the behavior of each component during the operation of the EOR and the analysis of electrolytic solution by liquid chromatography to obtain the reaction products distribution. On this way, a reference electrode (AgCl/Ag/Cl -) was included in each compartment for recording separately the polarization curves of each electrode (Figure 3). The Pt50Rh50/C catalyst deposited onto a carbon Toray paper composes the anode in the two performed testing. In Figure 4a, the Pt/C prepared from the BAE method is used as cathode. As can be noticed, the oxygen reduction reaction (ORR) polarization curve starts at potential ca 0.95 V vs. RHE while that of the EOR is at ca. 0.26 V vs. RHE. Beyond 1000 µA cm -2 , the polarization curve of the cathode decreases dramatically, while that of the anode profile increases resulting in a cell voltage drop. HPLC analysis of the electrolytic solution in each compartment allowed to explain that the unexpected behavior in the ORR curve was due to the ethanol crossover through the membrane to start depolarizing the Pt/C cathode. Therefore, a selenium-based catalyst well-known for its alcohol tolerance, 59,60 (herein PdSe/C), was used in place of Pt/C, which mitigated the depolarization of the cathode as can be noticed in Figure 4b. The polarization curves have similar profiles than those obtained by Fujiwara et al. 61 with a PtRu anode in a real fuel cell. Figure 5 depicts the cell voltage profile of the DEFC operating in alkaline medium and in which the Pt50Rh50/C and PdSe/C catalysts constitute the anode and the cathode, respectively. The power density reaches an optimum of 343 W cm -2 at 1250 µA cm -2 ; furthermore, the open circuit voltage (OCV) obtained at 25 °C is 0.58 V. This value is 0.1 V higher than that obtained by Soares et al. 12 in acid medium at 80 °C with a Pt80Rh20/C anode catalyst (40 wt.% metal loading).

Figure 5: Electrochemical performances of a DEFC at 25 °C using Pt50Rh50/C (0.13 mg cm -2 ) and PdSe/C (0.13 mg cm -2 ) as anode and cathode catalysts, respectively; the anodic compartment contains 1 mol L -1 NaOH and 1 mol L -1 ethanol separated to the cathodic one by an AEM from Fumatech.

Determination of the reaction products of ethanol oxidation

Considering the remarkable driving force obtained herein as compared to the literature, analysis of the resulting reaction production should be addressed. Therefore, a chronoamperometry experiment was undertaken at 0.6 V vs. RHE for 4 hours in a 1 mol L -1 NaOH electrolytic solution containing 0.2 mol L -1 ethanol. The refractive index detector (RID) enabled to determine 65% conversion of ethanol. The concentration of carbonate, which is the form of CO2 in basic solution, was also quantified thanks to this RID. It can be observed in Table 3 that the products distribution is strongly associated with the Rh content in the bimetallic anode composition; and whatever the electrode, acetate, a 4-electron reaction product, remains the major produced compound. The carbonate production is specifically high and attains 15.3% on the Pt50Rh50/C surface instead of 4% on Pt/C. This trend is in fair line with the previous results showing that the Rh content strongly contributes to the activity of the catalyst, and particularly, to the C-C bond cleavage 17,31,49 .

Although their distribution is varying depending on the electrocatalyst, the two reported pathways of the EOR must be considered on the PtxRhy/C anodes 26,27,62,63 : i) the acetate formation that involves 4 electrons and keeps the initial skeleton of the molecule.

It should be noted that acetaldehyde was not detected in the electrolytic solution. However, at the end of the experiment, the electrolytic solution was slightly yellow suggesting the polymerization of acetaldehyde through aldol condensation 64 . To improve the mass balance the remaining reaction products must still be determined, which must concern a low amount of compounds because a large part of acetaldehyde is either transformed electrochemically into acetate or a nucleophilic attack by HO -leads to acetate suddenly 16 . In situ infrared spectroscopy measurements are ongoing to scrutinize the eventual existence of this intermediate. ii) The second route involves the C-C bond cleavage. One of the two carbonaceous groups contains the alcohol function; one can easily imagine its conversion to CO and then, carbonate at higher potential values. But the other one (CHx) which is difficult to oxidize to CO or carbonate at room temperature may induce a deficiency in the mass balance 16,65 . Other complementary advanced techniques are needed to scrutinize the eventual existence of this CHx intermediate or final product.

Experimental

Chemicals

Chloroplatinic acid hydrate (H2PtCl6.6H2O, > 37.5% Pt Basis), rhodium chloride (RhCl3.xH2O, 38-40% Rh basis), potassium bromide (KBr, 99%), acetaldehyde and sodium borohydride (NaBH4) were purchased from Sigma-Aldrich and used as received. Carbon Vulcan XC 72R from Cabot was utilized as conducting substrate to dilute the noble elements amounts in the catalyst compositions. Nafion ® 1100 EW 5% wt. suspension, in a mixture of aliphatic alcohols and water permitted the catalytic ink formulation. Acetic acid, acid formic and isopropanol used was purchased from Merck. All the solutions were prepared with Millipore Milli -Q ® water (18.2 MΩ cm at 20 °C).

Catalysts synthesis

The bromide anion exchange (BAE) method can be explained as the reduction of a precursor metal ion (in the complex state) in aqueous solution using bromide ion as capping agent. While the parameters such as the metal salt concentration, the volume of reaction, the amount of reducing agent and the temperature were set as reported in the state-of-the-art BAE protocol 9,47 (1.0 mmol L -1 , 100.0 mL, 15-fold excess and 40.0 °C, respectively), the ratio ϕ = n(KBr)/n(metal (s)) was slightly modified and varied from 0.0 to 6.5 in order to optimize the preparation of the Pt based electrode materials. Accordingly, the prepared catalysts are described as PtϕBr/C in the text. Thus, 20.0 mg of metal salt was first dissolved in 100.0 mL water followed by the addition of experimental ratio ϕ of potassium bromide under vigorous stirring for 1 h. Carbon Vulcan was then added to the solution and sonicated during 45 min for complete homogenization. Afterwards, sodium borohydride (15-fold excess in cold water solution) was added dropwise to the mixture and stirred for 2 h at 40 °C. The suspension was filtered and exhaustively washed with water. The final powder was dried for 24 h at 40 ºC before use. Vulcan XC 72R carbon support is used in all catalysts and was subjected to thermal treatment at 900 °C in argon atmosphere for 5 h in a tubular oven 12 . Therefore, the PtxRhy/C catalysts were prepared with different molar compositions (x:y = 100:0; 80:20; 70:30; 60:40; 50:50). All the catalysts were prepared keeping a 20 wt.% metal loading. The characterization and determination of the best ratio ϕ composition were undertaken from UVvisible spectroscopy (UV-vis), X-ray diffraction (XRD), CO stripping and cyclic voltammetric (CV) measurements.

Physicochemical characterization

Ultraviolet-visible spectroscopy (UV-vis) measurements were performed with a spectrophotometer Agilent model Carry-500. X-ray diffraction patterns of the catalysts were obtained with an X-ray diffractometer (Bruker -D2 Phaser) operating with Cu Kα radiation (λ = 0.15406 nm) generated at 30 kV and 10 mA. The parameters were kept constant during the analysis: 2θ range = 20 -90º, and step = 0.025º s -1 . The composition phase of the materials was achieved by fitting the experimental angular range of interest to the pseudo-Voigt function per crystalline peak with the Profile Plus Executable refinement program (Siemens AG). Debye-Scherrer equation was used to estimate the crystallite size, and the unit cell parameters were determined using the least-squares method by a UFit. exe v1.3-1992 software. The metal-loading of each as-prepared sample was estimated by thermogravimetric analysis (TGA) performed on a Q600 TA Instruments SDT2960 under synthetic air using a 10 °C min -1 heating rate from 20 to 900 °C. Energy-dispersive X-ray spectroscopy (EDX) was performed in a Leica Zeiss LEO 440 to check the homogeneity of the local elemental composition in each prepared material. Additionally, surface morphology was investigated with a High-Resolution Transmission Electron Microscopy (HRTEM) using a TECNAI G2F20 electron microscope in bright and dark field modes coupled with EDX analysis. X-ray photoelectron spectroscopy (XPS) was used to probe and characterize the surface and oxidation states of the prepared material samples. Analyses were performed on a Kratos Axis Ultra DLD spectrometer equipped with a monochromatic Al Kα X-ray source (1486.6 eV) operating at 15 kV and 10 mA (150 W). The base pressure of the instrument was 9 x 10 -8 Pa.

The sample powder was pressed in a copper holder of 3 mm diameter and introduced into the preparation chamber after being outgassed overnight. The analysis spot size is approximately 300 µm x 700 µm and the pass energy is 20 eV for recording high-resolution spectra. The C1s spectra used as internal reference is centered at 284.6 eV. Spectra were fitted with CasaXPS software (version 2.3.17). Shirley background has been chosen and asymmetric Gaussian-Lorentzian profile functions were used to fit the spectra.

Electrochemical characterization of the electrode materials

All the glassware was first thoroughly cleaned in an acidic potassium permanganate solution and then an acidic/hydrogen peroxide solution to remove any organic/inorganic impurities that may result from the previous experiments. After washing, the glassware was rinsed with hot water to remove any remaining species. Otherwise, a catalytic ink was prepared with 2.0 mg of the catalyst powder which was dispersed in a solution composed of water (100 µL), isopropanol (95 µL) and a Nafion® suspension (5 µL) (5 wt.% in aliphatic alcohol Aldrich). This ink was homogenized in an ultrasound bath for 30 min. Finally, 3 µL of the ink was deposited uniformly onto a glassy carbon (GC) disk (3 mm diameter) previously polished with alumina and dried at room temperature. The experiments were carried out using an Autolab Potentiostat (PGSTAT302N, Metrohm); all the solutions were prepared by using ultra-pure water (Milli-Q) and then purged with N2 gas for nearly 15 min before starting the electrochemical measurements. Cyclic voltammetry (CV) and chronoamperometry (CA) were performed in a conventional three-electrode cell. Hg/HgO/OH - (1.0 mol L -1 NaOH) and a platinized platinum wire were used as the reference and counter electrodes, respectively. For comparing easily, all potentials are associated with the reversible hydrogen electrode (RHE) from the Hg/HgO reference electrode (-0.965 V vs RHE). The CVs were recorded by potential cycling from 0.05 to 1.15 V vs. RHE in solution containing 0.20 mol L -1 ethanol (Merck) and without ethanol at a 10 mVs -1 scan rate. The chronoamperometry tests were conducted for 30 min and at 0.60 V vs. RHE in alkaline solution containing 0.20 mol L -1 ethanol.

The potential was recorded between 0.05 to 1.15 V vs. RHE at a 10 mV s -1 scan rate. The currents obtained during the electrochemical experiments were normalized with the mass of metals (Pt + Rh) contained in each deposited catalyst.

Analysis of reaction products by high-performance liquid chromatography

The performance of PtxRhy/C catalysts for ethanol conversion was investigated by electrolysis experiments realized in potentiostatic conditions. The potential was fixed in 0.60 V vs. RHE for 4 hours. Aliquots were collected every 30 min and injected in high-performance liquid chromatography (HPLC, from Shimadzu, model LC-10AT) equipped with a double on-line detection system i.e a UV-vis (λ = 210 nm) detector followed by a refractive index (RID-10A). The apparatus was also composed of an automatic injector with a 20 μL sample loop, and an ion exclusion column (Aminex HPX-87H, from BioRad). The mobile phase was a solution of sulfuric acid (3.33 mmol L -1 H2SO4 at a 0.6 mL min -1 flow rate. The reaction products were quantitatively determined by comparing their retention times with those pure commercial standards injected under the same isocratic analysis conditions (external calibration).

Cell voltage performance

The driving force of a direct ethanol fuel cell was evaluated in a home-made single Teflon twocompartment cell. The current-potential testing was implemented with the Pt50Rh50/C catalyst as anode with a 0.13 mg cm -2 metal loading. The catalytic ink was prepared by mixing the required material sample amount with 375 µL Milli-Q ® water and 50 µL Nafion ® 5 wt.%. The mixture was homogenized ultrasonically before its deposition onto the both sides of a carbon Toray substrate.

The cathode was composed of a palladium-selenium (PdSe/C) catalyst, which was selected for its more ethanol tolerance in case of fuel crossover to the cathodic compartment. Anion exchange membrane (AEM, Fumasep FAA, from Fumatech) pre-treated in a 0.1 mol L -1 NaOH solution, was used to separate physically the two compartments) and to insure the current relay between the electrodes. The DEFC operated with 1.0 mol L -1 NaOH supporting electrolyte at 25 °C in each compartment; while the anodic side contained a 1.0 mol L -1 ethanol solution, oxygen was supplied in the cathodic one.

Conclusions

In this work a revisited surfactant-free BAE method was used to synthesize PtxRhy/C catalysts that turned out to be noticeably active towards ethanol oxidation reaction. The Pt50Rh50/C catalyst was used as anode for undertaking a DEFC in which the ORR was catalyzed on a PdSe/C cathode, which is ethanol tolerant. The DEFC performed with a remarkable open circuit voltage, indicating how promising is the catalyst prepared with a synthetic method without any poisoning of the active site by heavy organics from the surfactant. Actually, the obtained PtRh nanoparticles were well dispersed on the carbon substrate, with a small distribution size (3.0-3.8 nm), which is associated with a high specific electrochemical active surface area. The physicochemical properties of the anode such as the high alloying degree may explain the beneficial ensemble (electronic and geometric) effects on the EOR. As a consequence, the presence of the Rh content matches well with the Pt atoms, which induces a dissociative ethanol adsorption to produce almost 4 times, more carbonate on Pt50Rh50/C than on Pt/C. Nevertheless, advanced techniques more sensitive than liquid chromatography are needed to improve the mass balance. In situ infrared spectroscopy measurements are ongoing to contribute to identifying some intermediates in low concentrationsconclusions section should come in this section at the end of the article, before the acknowledgements.

  also shows a shift of the diffraction peaks of PtxRhy/C catalysts towards higher 2θ values as the Rh content increases in the Pt-based catalyst composition.

Figure 1 :

 1 Figure 1: XRD patterns of the carbon supported PtxRhy materials prepared from the revisited BAE method.Table1summarizes the data related to the structural properties and the morphology (Figure SI-1) of the PtxRhy/C catalysts obtained by the BAE surfactant-free route. In comparison with recent literature, the proposed synthetic approach displays a good correlation of crystallite size values and permitted to recover lower particle sizes, which is synonymous to a gain of surface area and thus, an increase of the catalytic activity of the resulting electrode materials35 . Figure2aillustrates a TEM micrograph and a particle EDX analysis (Figure2b) for the Pt50Rh50/c catalyst. The TEM images show that the catalyst particles are well dispersed. The formation of Pt and Rh alloy is evidenced by EDX spectra which results were summarized in Table1. The other PtxRhy/C compositions are depicted in Figure SI-4 for comparison. As an example, the impregnation route led to PtxRhy/C materials with crystallite sizes comprised between 5 and 12 nm diameter28,49 . It can be also noticed in Table1an increase in the alloying degree[50][51][52] in the PtxRhy/C catalysts as a function of the Rh content, which may be deduced from the lattice contraction with an incorporation of smaller Rh atoms into the Pt fcc-structure during the synthesis process53,54 .

Figure 2 :

 2 Figure 2: (a) TEM images for Pt50Rh50/C material. (b) EDX spectra of Pt50Rh50/C particle.

Figure 3 :

 3 Figure 3: Voltammograms (CVs) of Pt and Rh based electrode materials prepared from the revisited BAE route. These CVs were recorded at room temperature and 10 mV s -1 and in 1 mol L - 1 NaOH, in the absence (a, b and c) and the presence of 0.2 mol L -1 ethanol (d, e and f).

Figure 4 :

 4 Figure 4: E-j polarizations curves obtained at the electrodes of a DEFC operating at room temperature and in alkaline medium. a) (-) Pt50Rh50/C / 1.0 mol L -1 ethanol // 1.0 mol L -1 NaOH, O2 / Pt/C (+); b) (-) Pt50Rh50/C / 1.0 mol L -1 ethanol // 1.0 mol L -1 NaOH, O2 / PdSe/C (+)

Table 2 :

 2 Experimental data from XPS spectra obtained from the analysis of the Pt50Rh50/C catalyst with binding energies collected every 0.1 eV.

	Catalyst	Experimental	Crystallite	Particle size	2θ	Lattice	Alloying
		composition	size (XRD)	(TEM)	(degree)	parameter	degree
		(EDX)		(nm)	(nm)		(nm)	(%)
	Pt/C	---		2.8		3.0	39.58	0.3920	-
	Rh/C	---		2.9		3.1	40.04	0.3790	-
	Pt50Rh50/C	Pt49Rh51/C		2.6		2.8	39.87	0.3861	51
	Pt60Rh40/C	Pt65Rh35/C		2.4		3.0	39.98	0.3873	42
	Pt70Rh30/C	Pt74Rh26/C		3.0		3.1	39.76	0.3892	20
	Pt80Rh20/C	Pt78Rh22/C		3.4		3.6	39.99	0.3891	20
								Relative
		Binding Energy / (eV)	Correspondi ng Band	Species	atomic percentage (%)
								Pt50Rh50/C
		71.4-75		Pt 4f	Pt metallic	0.9
		72.4-75.7				Pt 2+ (PtO)	0.3
		74.1-77.5				Pt oxide	0.3
						(PtO2)
		496.8		Rh 3p 3/2	Rh metallic	0.6
		499.8				Rh2O3	0.5
		284.4		C1s		C-C, C-H	67.3
		285.6				C-O		4.2
		286.7				C=O		8.9
		289				O=C-O	13.8
		531		O1s				4.3
								Ratio Pt/Rh
								1.25

. Electrochemical characterization of the PtxRhy/C catalysts Figure 3 depicts

  the cyclic voltammograms (CVs) of the targeted Pt50Rh50/C electrode, which is compared with those of Pt/C and Rh/C alone; the CVs of the other PtxRhy/C compositions are depicted in Figure SI-6 for comparison. All the current values were normalized with respect to the metal loading deposited onto the conducting support for evaluating similarly the mass activity of the prepared electrodes. One observes clearly the two following beneficial features in Figure

Table 3 : Distribution of the reaction products issued from the EOR in alkaline electrolyte and on PtxRhy/C anode materials.

 3

	Catalyst	Ethanol consumed (mol L -1 )	Reaction products Acetaldehyde Acetate (%) (%)	CO3 2-(%)	Mass balance (%)
	Pt/C	0.03	--	92.5	4.5	95.0
	Pt50Rh50/C	0.13	--	33.6	15.3	49.1
	Pt60Rh40/C	0.09	--	40	10.5	47.5
	Pt70Rh30/C	0.05	--	55	4.5	59.5
	Pt80Rh20/C	0.03	--	66	5.5	71.5

Acknowledgements

The authors thank CAPES-COFECUB (project n° 914/18) and CNPq for their financial support. "This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior -Brasil (CAPES) -Finance Code 001". The authors from IC2MP thank the European Union (ERDF) and "Région Nouvelle-Aquitaine for their support. The authors were grateful to the Prof. Dr. N. Alonso-Vante for providing the PdSe/C cathode material.

Conflicts of interest

In accordance with our policy on Conflicts of interest please ensure that a conflicts of interest statement is included in your manuscript here. Please note that this statement is required for all submitted manuscripts. If no conflicts exist, please state that "There are no conflicts to declare".


Lachouette Damien
email: damien.lachouette@cemagref.fr

Bonelli Stéphane

Brivois Olivier

Dense piping flows with erosion

Keywords: piping erosion, dense flow, turbulent flow

A phenomenon called « piping » often occurs in hydraulics works (earthdams, dykes), involving the formation and the progression of a continuous tunnel between the upstream and the downstream side. It is one of the main cause of failure. Starting from the bulk equations for diphasic flow with diffusion and from the jump equations with erosion, we propose a simplified model for dense piping flows with erosion. Numerical simulation with constant input and output pressure shows that the influence of the particles concentration can be signifiant in the beginning of the process, resulting in the enlargment of the hole at the exit.

Résumé :

Un phénomène appelé renard hydraulique survient souvent sur les ouvrages hydrauliques (barrages, digues), conduisant à la formation et au développement d'un tunnel continu entre l'amont et l'aval. C'est l'une des causes principales de rupture. A partir des équations d'écoulement diphasique avec diffusion, et des équations de saut avec érosion, nous proposons un modèle simplifié pour les écoulement denses de conduit avec érosion. Les résultats numériques avec pression constante en entrée et en sortie montrent que l'influence de la concentration en particles solides peut être significative au début de l'évolution, conduisant à un élargissement du trou en sortie.

Introduction

Erosion of soil resulting from piping, seepage or overtopping is the main cause of serious hydraulic work (dykes, dams) failure, in terms of the risk of flooding areas located downstream. The present study concerns the first process: the enlargement of a crack, which leads to an erosion process known as "piping" in soil mechanics. Piping erosion often occurs in hydraulics works, involving the formation and the progression of a continuous tunnel between the upstream and the downstream side.

A large literature on soil erosion exists in the field of hydraulics and river engineering [START_REF] Chanson | The Hydraulics of Open Channel Flows: An Introduction[END_REF], and in the field of poromechanics and petroleum engineering [START_REF] Vardoulakis | Hydromechanical aspects of sand production problem[END_REF]. In the field of geomechanics, [START_REF] Bonelli | On modelling of piping erosion[END_REF] have proposed a model for dilute piping flows with erosion. We focus here on the dense flow case.

Two-phase flow equations with interface erosion

The soil is eroded by the flow, which then carries away the eroded particles. As long as the particles are small enough in comparison with the characteristic length scale of the flow, this two-phase flow can be said to be a continuum. We take to denote the volume of the two-2 phase mixture and the fluid/soil interface. For the sake of simplification, sedimentation and deposition processes are neglected, and the soil is taken to be saturated. The mass conservation equations for the water/particles mixture and for the mass of the particles as well as the balance equation of momentum of the mixture within can be written as follows in a Eulerian framework [START_REF] Nigmatulin | Dynamics of multiphase media[END_REF]:

t + ( u) = 0 , Y t + ( Y u) = J , u t + ( u u) = .
In these equations, is the density of the mixture, depending on the particles mass fraction Y , u is the mass-weighted average velocity, J is the mass diffusion of the flux of particles, and is the Cauchy stress tensor in the mixture. As there is a process of erosion, a mass flux crosses the interface . Let us take n to denote the normal unit vector of oriented outwards from the soil, and v to denote the normal velocity of . The jump equations over are

( v u) n = 0 , Y ( v u) n = J n , u( v u) n = n ,
where a = a s a w is the jump of any physical variable a across the interface, and a s and a w stands for the limiting value of a on the solid and fluid sides of the interface, respectively. The soil is assumed to be homogeneous, rigid and devoid of seepage. The co-ordinate system depends on the soil in question. The total flux of eroded material (both particles and water) crossing the interface is therefore m = s v n , where s is the density of the saturated soil. Erosion laws dealing with soil surface erosion by a tangential flow are often written in the form of threshold laws such as [START_REF] Chanson | The Hydraulics of Open Channel Flows: An Introduction[END_REF]:

m = k er ( w c ) if b > c , 0 otherwise ,
where c is the critical shear stress involved in the erosion, k er is the coefficient of soil erosion, and w is the tangential shear stress at the interface defined as follows:

w = ( n) 2 ( n 2 w .

Application to dense piping flows with erosion

The use of above equations is extended here to the study of two-phase piping flow with erosion, by introducing a spatial integration over a cylinder with radius R (initial value R 0 ) and length L (Fig. 1). The dilute flow case has been adressed by [START_REF] Bonelli | On modelling of piping erosion[END_REF]: this assumption is relevant only when the pipe is not "too long" (i.e when Luk er R 0 where u is the average longitudinal velocity). This hypothesis is not necessary here.

We simplify above equations in a boundary layer theory spirit in order to obtain the Reduced Navier Stokes/Prandtl equations (Lagree & Lorthois, 2005). We therefore integrate the obtained system on a cross section. For simplification, some assumptions are made: the tangential velocities are supposed continuous across (no-slip condition on the interface), and the concentration is uniform in a section. Of course, the concentration is not uniform, and it influences most probably the velocity profil. However, to our knowledge, radial profil of velocity and concentration in turbulent pipe flow with erosion remains to be investigated.

3

We take p and w to denote the solid and water density, respectively, and to denote the volume fraction of the solid phase. Volume fraction and mass fraction are linked as follows: p = Y . The mixture density is therefore = ( p w ) + w . In particular, the saturated soil density is s = ( p w ) s + w where is s = 1 n is the compacity of the soil, while n is the porosity.

The following system is obtained:

R t = m s , u x + 2 u R R x = 0 , (1) t + u x = m R s ( s ) , u t + u u x = 2 R ( w u m) p x . ( 2
)
where a denotes the mean value of a across any section, and

= u 2 u 2 , = 1 + ( 1) 1 s .
Although turbulence models of considerable sophistication are now commonly used in single-phase fluid flows, the same cannot be said for the two-phase flow involving heavy particles of varying concentration. We use a strong assumption for the behaviour law:

w = f w (R e )f m ( )u 2 .
The influence of the concentration is taken from the quadratic rheological law for hyperconcentration of [START_REF] Julien | Erosion and Sedimentation[END_REF], while that of the Reynolds number is taken from [START_REF] Barenblatt | Scaling laws for fully developed turbulent flow in pipes[END_REF]:

f m ( ) = 1 + c B d d d l m 2 ( ) , ( ) = s 1/3 1 1 , f w (R e ) = 2 e (1 + e )(2 + e ) e 3/2 ( 3 + 5 e ) 2/(1+ e )
, e = 3 2 ln R e , where c B is the Bagnold coefficient, d p is the (eroded) soil particles diameter, and l m is the mixing length taken to be l m = c l R . The coefficient is evaluated with the radial velocity profil proposed by [START_REF] Barenblatt | Scaling laws for fully developed turbulent flow in pipes[END_REF] for turbulent pipe flows:

= (1 + e )(2 + e ) 2 4(1 + 2 e )
.

4

FIG. 1 -Axisymmetrical flow with soil erosion and transport of the particles.

Numerical results

The system Eqs. ( 1), ( 2) is solved numerically with unknowns ( , R, p,u ) . Initial conditions and boundary conditions are

R(0, x) = R 0 , (0, x) = 0, u(0, x) = 0, p(0, x) = 0 , (t, 0) = 0, p(t, 0) = p in (t), p(t, L) = 0 .
These boundary conditions require a specific numerical procedure, of which the formulation is beyond the scope of the present paper. We consider a unit step of input pressure p in (t) = 0 if t < 0, p in * if t > 0 . Erosion occurs if P 0 > c where P 0 = R 0 p in * / (2L) is the initial driving pressure. Numerical values of parameters are given in table I. These values correspond to a pipe in a highly erosive soil (see e.g. [START_REF] Wan | Investigation of rate of erosion of soils in embankment dams[END_REF], of a large earthdam.

Fig. 2 shows the temporal evolutions of ( , R, p) . The concentration reaches high values (close to s ), and then decreases. The radius has an exponential-like evolution with time. The pressure is somewhat influenced by the concentration: the average value of p increases a bit, then decreases a bit, and then stays at a constant mean value. The velocity is given by the total mass conservation equation, which can be re-written as u = u 0 (R / R 0 ) 1/2 where u 0 is the initial velocity. Fig. 3 gives ( , R, p) in relation to x for successive times until t =20 mn. The concentration profiles shows the accumulation of particles until the maximum value (close to s ), then the slow decrease to a dilute flow. High values of output concentration lead to enlargment of the output hole. This effect is progressively erased when dilute flow occurs. The pressure profile is affected during the dense flow period, and then shows a classical linear-like decrease.

Fig. 4 shows the three-dimensionnal plot of the hole at time t =9 mn. Taking into account the many simplifying assumptions, namely those concerning the radial profiles of concentration and velocity, this nice picture shows that this simple model is able to capture some of the main features of the piping erosion. We propose a simplified model for piping dense flows with erosion, able to capture some of the main features of the piping erosion. Numerical simulation under constant input and output pressure condition shows that the influence of the particles concentration can be signifiant in the beginning of the process, resulting in the enlargment of the hole at the exit. However, such a modelling needs informations concerning radial profiles of velocity and concentration in turbulent pipe flow with erosion. To our knowledge, this issue has not been addressed experimentaly, nor numerically.

5FIG. 2 -

 2 FIG.2-Temporal evolutions of ( , R, p) , minimum, mean and maximum values.

Acknowledgement

This research project is sponsored by the French National Research Agency under grant 0594C0115 (ERINOH), and by the Région Provence Alpes Côte d'Azur.