Charles Bouillaguet
email: charles.bouillaguet@ens.fr

Pierre-Alain Fouque
email: pierre-alain.fouque@ens.fr

Gaëtan Leurent
email: gaetan.leurent@ens.fr

Security Analysis of SIMD

Keywords: SIMD, SHA-3, hash function, distinguisher, security proof with distinguishers

In this paper we study the security of the SHA-3 candidate SIMD. We first show a new free-start distinguisher based on symmetry relations. It allows to distinguish the compression function of SIMD from a random function with a single evaluation. However, we also show that this property is very hard to exploit to mount any attack on the hash function because of the mode of operation of the compression function. Essentially, if one can build a pair of symmetric states, the symmetry property can only be triggered once. In the second part, we show that a class of free-start distinguishers is not a threat to the wide-pipe hash functions. In particular, this means that our distinguisher has a minimal impact on the security of the hash function, and we still have a security proof for the SIMD hash function. Intuitively, the reason why this distinguisher does not weaken the function is that getting into a symmetric state is about as hard as finding a preimage. Finally, in the third part we study differential path in SIMD, and give an upper bound on the probability of related key differential paths. Our bound is in the order of 2 -n/2 using very weak assumptions. Resistance to related key attacks is often overlooked, but it is very important for hash function designs.

Introduction

SIMD is a SHA-3 candidate designed by Leurent, Fouque and Bouillaguet [START_REF] Leurent | SIMD Is a Message Digest[END_REF]. Its main feature is a strong message expansion whose aim is to thwart differential attacks. This paper provides three important contributions to the security analysis of SIMD. In Section 2 we study its resistance against self-similarity attacks [START_REF] Bouillaguet | Another Look at the Complementation Property[END_REF]. This class of attack is inspired by the complementation property of DES and includes symmetry based attacks. In the case of SIMD, we show that it is possible to exploit the symmetry of the design using special messages. This shows that the constants included in the message expansion of SIMD are not sufficient to prevent symmetry relations, and non-symmetric constants should be added in the last steps of the message expansion. The study of this symmetry property shows that it is much weaker than symmetry properties in CubeHash [START_REF] Aumasson | Inside the Hypercube[END_REF][START_REF] Ferguson | Symmetric States and their Structure: Improved Analysis of CubeHash[END_REF] or Lesamnta [START_REF] Bouillaguet | Another Look at the Complementation Property[END_REF]. More precisely, most symmetry properties can be used to generate many symmetric states out of a single state, but this is not the case for SIMD.

In Section 3, we show a proof of security for the mode of operation used in SIMD, the truncated prefix-free Merkle-Damgård, in the presence of some efficient distinguishers on the compression function. The class of distinguisher we consider includes the symmetry based distinguisher, and also includes differential paths with a non-zero chaining value difference. This shows that the properties of the compression function of SIMD found so far do not affect the security of the iterated hash function. This part is also of independent interest and applies to other wide-pipe hash functions.

In Section 4, we study differential attacks, and bound the probability of paths with a non-zero message difference, i.e., related key attacks on the block cipher. We show an upper bound on such paths on the order of 2 -n/2 , and we argue that the best paths are probably much worse than this bound. We note that there are very few results known regarding resistance to related key attack for block ciphers. In particular, the differential properties of the AES have been extensively studied [START_REF] Park | Improving the Upper Bound on the Maximum Differential and the Maximum Linear Hull Probability for SPN Structures and AES[END_REF] but related key differential attacks have been shown recently [START_REF] Biryukov | Related-Key Cryptanalysis of the Full AES-192 and[END_REF]. In many hash function designs (in particular those based on the Davies-Meyer construction), related key attacks are a real concern and should be studied accordingly.

By combining the results of Section 3 and 4, we show that SIMD is resistant to differential cryptanalysis: a path with a non-zero difference in the chaining value input cannot be used to attack the hash function because it is wide-pipe, while a path a non-zero difference in the message can only have a low success probability.

Finally, in Section 5 we express our views on the security of SIMD.

Brief Description of SIMD

SIMD is built using a modified Davies-Meyer mode with a strong message expansion, as shown in Figure 1.

The compression part is built from 4 parallel Feistel ladders (8 for SIMD-512) with 32-bit registers, and is shown in Figure 2. We can describe the step update function as:

D j ← D j ⊞ W (i) j ⊞ φ (i) (A j , B j , C j ) ≪s (i) ⊞ A p (i) (j)
≪r (i) (A j , B j , C j , D j ) ← (D j , A ≪r (i) j , B j , C j )

where j denotes the Feistel number, and i denotes the round number. A, B, C, and D are the four registers of the Feistel ladders, while φ (i) is the Boolean function used at round i (which can be either IF or MAJ) and W is the expanded message. The parallel Feistels interact through the permutations p (i) , which are built as p (i) (j) = j ⊕ α i , for some α i . There are no explicit constants in the round function, but there are implicit constants in the message expansion.

The Message Expansion. The message expansion of SIMD is defined with the following operations:

1. Use a NTT transform (which is the same as a FFT over F 257 ) to double the size of the message. The NTT is actually used as a Reed-Solomon code. 2. Make two copies of the NTT output. 3. The first copy is multiplied by 185, while the second copy is multiplied by 233. This step also doubles the size of the message, as the output are 16-bit words. 4. Permute the 16-bit words and pack them into 32-bit words.

Constants are added in the NTT layer, and make it an affine code instead of a linear one. They avoid special expanded messages such as the all-zero message. For more details, see the specification of SIMD [START_REF] Leurent | SIMD Is a Message Digest[END_REF].

Previous Cryptanalysis Results

As far as we know, the following results have been found on SIMD:

-In [START_REF] Gauravaram | Private communication[END_REF], Gauravaram and Bagheri showed that the modified Davies-Meyer construction used in SIMD allows to find partial fixed-points (this is a weaker version of Davies-Meyer's fixed-points). There is no easy way to find full fixed-points as in the original Davies-Meyer construction, but those partial fixedpoints give an easy distinguisher of the compression function. Just like the fixed-points of Davies-Meyer, this property does not affect the security of a wide-pipe hash function, and the mode can be proven secure under the assumption that the block cipher is ideal [START_REF] Coron | Merkle-Damgård Revisited: How to Construct a Hash Function[END_REF].

-In [START_REF] Mendel | A Distinguisher for the Compression Function of SIMD-512[END_REF], Mendel and Nad showed a differential path with probability 2 -507 for the compression function of the round-1 version of SIMD-512. They used it to make a distinguishing attack on the compression function with complexity 2 427 , using IV/message modifications. In this path, no difference is introduced in the message, but a specific difference ∆ in in the chaining value can go to a difference ∆ out . Because of the need to control the chaining value difference, this path cannot be used to attack the iterated hash function. In Section 3, we show that even if there of a path with probability one, we only loose a factor 2 in the indifferentiability proof. However, this path was using some unwanted properties of the permutations used in the compression function, and it was decided to remove those properties by tweaking the design for the second round of the SHA-3 competition [START_REF] Leurent | Tweaking SIMD. Submission to the second round of SHA-3 competition[END_REF]. -More recently, in [START_REF] Yu | Cryptanalysis of the compression function of simd[END_REF] Yu and Wang studied differential paths for the round-2 version of SIMD. They describe near-collisions in reduced versions of the compression function (20 steps for SIMD-256 and 24 steps for SIMD-512) and build a differential path with probability 2 -897 for the full compression function of SIMD-512. This path can be used to build a distinguisher with complexity 2 398 , yielding pair of inputs and outputs with a fixed difference. Like the previous result, this work uses a difference in the chaining value and no difference in the message. For this reason it does not threaten the iterated hash function.

It should be noted that for this distinguisher, the attacker needs to choose both input chaining values, and not only the difference between the chaining values (it is a free-start attack, while the attack on the round-1 version could be mounted as a semi-free-start attack ). That makes it even less threatening to a wide-pipe design. Moreover we found several mistakes in the path described in the preprint of their work, which cast a doubt on the validity of the path. -In [START_REF] Nikolić | Rotational Cryptanalysis of (Modified) Versions of BMW and SIMD[END_REF], Nikolić et al. applied rotational cryptanalysis to the compression function of SIMD-512. They showed that 24 rounds can be distinguished from a random function with complexity 2 497 if the constants are removed from the design. In the real design, they can only distinguish 12 rounds (out of 36) because of the non-linear message expansion. This is clearly not a threat for SIMD-512.

A Distinguisher for the Compression Function of SIMD

Our distinguisher is based on symmetries in the design, and follows the ideas of [START_REF] Bouillaguet | Another Look at the Complementation Property[END_REF]. Symmetry based properties have already been found in several hash function designs, such as CubeHash [START_REF] Aumasson | Inside the Hypercube[END_REF][START_REF] Ferguson | Symmetric States and their Structure: Improved Analysis of CubeHash[END_REF] or Lesamnta [START_REF] Bouillaguet | Another Look at the Complementation Property[END_REF]. We describe the distinguisher in the case of SIMD-256, but it applies similarly to SIMD-512.

Building the Symmetric Messages

The basic idea is to build a message so that the expanded message is symmetric. Then, if the internal state is also symmetric, the compression rounds preserve the symmetry. This can also be used with a pair of symmetric messages, and a pair of symmetric states.

The NTT layer of the message expansion is an affine transformation, therefore it is easy to find inputs that satisfy some affine conditions on the output. Since it only doubles the size of the input, we have enough degrees of freedom to force equalities between pairs of output. The next expansion step is a multiplication by a constant, and it will preserve equality relations.

Then if we look at the permutations used in the message expansion, they have the following property1 : the NTT words used to build the message words

W (i) 0 , W (i) 1 , W (i) 2 , W (i) 3
are always of the form (y k1 , y k2 ), (y k1+2 , y k2+2 ), (y k1+4 , y k2+4 ), (y k1+6 , y k2+6 ) for some k 1 and k 2 (with k i = 0 mod 8 or k i = 1 mod 8). The full permutations are given in [START_REF] Leurent | SIMD Is a Message Digest[END_REF]Table 1.1]. Because of this property, if we have y i = y i⊕2 after the NTT, then we have

W (i) 0 = W (i) 1 and W (i) 2 = W (i)
3 . This allows us to build a symmetric message. An example of such a symmetric message is given in Appendix A.

More precisely, let us use the notation ← → • to denote this symmetry relation, and • ← → and ← → • ← → to denote the other two possible symmetries:

← -----→ (a, b, c, d) = (b, a, d, c) (a, b, c, d) ← -----→ = (c, d, a, b) ← -----→ (a, b, c, d) ← -----→ = (d, c, b, a)
We now consider two messages M and M ′ . We use y to denote the NTT output for M , and y ′ to denote the NTT output for M ′ . The equality constraints on the NTT output that are necessary to build a pair of symmetric expanded messages are (we use E to denote the message expansion):

y i = y ′ i⊕2 ⇒ E(M ) = ←--→ E(M ′ ) y i = y ′ i⊕4 ⇒ E(M ) = E(M ′ ) ←--→ y i = y ′ i⊕6 ⇒ E(M ) = ←--→ E(M ′ ) ←--→
By solving the corresponding linear systems, we can compute the sets of symmetric messages (the sets are described in the full version of this paper). We can count the symmetric messages M such that E(M ) = ← --→ E(M ), and the pairs of messages M, M ′ such that E(M ) = ←--→ E(M ′ ):

Symm. class (SIMD-256) # msg # pairs ← → • y i = y ′ i⊕2 W i = W ′ i⊕1 2 8 256 • 255 • ← → y i = y ′ i⊕4 W i = W ′ i⊕2 2 16 (256 • 255) 2 ← → • ← → y i = y ′ i⊕6 W i = W ′ i⊕3 2 8 256 • 255
Symm. class (SIMD-512) # msg # pairs

y i = y ′ i⊕2 W i = W ′ i⊕1 2 8 256 • 255 y i = y ′ i⊕4 W i = W ′ i⊕2 2 16 (256 • 255) 2 y i = y ′ i⊕6 W i = W ′ i⊕3 2 8 256 • 255 y i = y ′ i⊕8 W i = W ′ i⊕4 2 32 (256 • 255) 4 y i = y ′ i⊕10 W i = W ′ i⊕5 2 8 256 • 255 y i = y ′ i⊕12 W i = W ′ i⊕6 2 16 (256 • 255) 2 y i = y ′ i⊕14 W i = W ′ i⊕7 2 8 256 • 255
An important property of these message classes is that they are all disjoint: it is not possible to use the intersection of two symmetry classes.

Symmetry Property on the Compression Function

Let us consider a pair of symmetric messages for one of the symmetry relations (without loss of generality, we assume it's the ← → • symmetry):

E(M ′ ) = ← --→ E(M ).
We can take advantage of the symmetry of the Feistel part using those messages. If we have a pair of states S (i) , S ′(i) with S ′(i) = ← → S (i) and we compute one Feistel step with messages W and W ′ such that W ′ = ← → W , we obtain a new pair of states with S ′(i+1) = ← --→ S (i+1) . The xor-based symmetry classes commute with the xor-based permutations p (i) used to mix the Feistels (and they are the only symmetry classes to do so).

Because the compression function is built using a modified Davies-Meyer mode (Figure 1), we need to start with H i-1 such that H i-1 ⊕ M is symmetric:

H ′ i-1 ⊕ M ′ = ←-----→ H i-1 ⊕ M .
Then, in the feed-forward, H i-1 is used as the key to a few Feistel rounds, and since H i-1 is not symmetric, those rounds will break the symmetry. However, it turns out the symmetric messages are very sparse, so H i will be almost symmetric, and the feed-forward will mostly preserve the symmetry of the outputs.

This gives a distinguisher on the compression function: an almost symmetric chaining value is transformed into a somewhat symmetric chaining value. See Appendix A for a concrete example.

The distinguisher can be used either with a pair of messages and chaining values with

E(M ′ ) = ← --→ E(M ) and H ′ i-1 ⊕ M ′ = ←-----→ H i-1 ⊕ M ,
or with a single chaining value and message, with

E(M ) = ← --→ E(M ) and H i-1 ⊕ M = ←-----→ H i-1 ⊕ M .

Non-Ideality of the Compression Function

Here we define the bias of the compression function with the notations that will be used in Section 3. For each symmetric message M under a symmetry relation (denoted by ← → • without loss of generality), we have a first order relation between the inputs and output of the compression function:

R M 1 (h, m, h ′ ) := m = M ∧ h ⊕ m = ← --→ h ⊕ m ⇒ P -1 (h ′ , h) = ←-----→ P -1 (h ′ , h)
We use the feed-forward permutation P to define the relation, because it is tricky to describe exactly the somewhat symmetry of h ′ after the feed-forward. We have about 2 16 such relations for SIMD-256 and about 2 32 relations for SIMD-512. Similarly, for each symmetric message pair M, M ′ , this gives a second order relation (there are about 2 32 such relations for SIMD-256 and 2 64 for SIMD-512):

R M,M ′ 2 (h 1 , m 1 , h 2 , m 2 , h ′ 1 , h ′ 2 ) := m 1 = M ∧ m 2 = M ′ ∧ h 1 ⊕ m 1 = ← ----→ h 2 ⊕ m 2 ⇒ P -1 (h ′ 1 , h 1 ) = ← -------→ P -1 (h ′ 2 , h 2 )
The corresponding weak states are:

W M 1 := {x ⊕ M | x = ← → x } W M,M ′ 2 := (h, ← → h ⊕ M ′ ⊕ ← → M )
The study of the symmetry classes of SIMD shows that:

|W 1 | = 2 256 • 256 2 + 2 • 256 ≈ 2 256 • 2 16
for SIMD-256

|W 1 | = 2 512 • 256 4 + 2 • 256 2 + 4 • 256 ≈ 2 512 • 2 32
for SIMD-512

|W 2 | = 2 512 • ((256 • 255) 2 + 2 • 256 • 255) < 2 512 • 2 32
for SIMD-256

|W 2 | = 2 1024 • ((256 • 255) 4 + 2 • (256 • 255) 2 + 4 • 256 • 255) < 2 1024 • 2 64 for SIMD-512
Each chaining value can be used with less than 2 32 related chaining values (less than 2 64 for SIMD-512) and each such pair can be used with a single message.

Impact of the Symmetry-based Distinguisher

There are two main classes of attacks based on symmetric properties of the compression function. To attack the compression function, one can use the symmetry property to force the output of the compression function into a small subspace. This allows to find collisions in the compression function more efficiently than brute force, with the efficiency of this attack depending on the size of the symmetry classes. On the other hand, to attack the hash function, one can first try to reach a symmetric state using random messages, and then use symmetric messages to build a large set of symmetric states. To expand the set, the attacker will build a tree, starting with the symmetric state that was reached randomly. The degree and the depth of the tree can be limited depending on the symmetry property. In the case of SIMD, none of these attacks are effective for the following reasons:

-First, the modified Davies-Meyer mode of operation means that the compression function does not transform a symmetric state into a symmetric state, but it transforms an almost symmetric state into a somewhat symmetric state. We show in the full version of the paper that a "somewhat symmetric" output pair can only be used as an "almost symmetric" input pair with a very small probability. This prevents attacks based on building long chains of symmetric messages, like the attacks on CubeHash [START_REF] Aumasson | Inside the Hypercube[END_REF][START_REF] Ferguson | Symmetric States and their Structure: Improved Analysis of CubeHash[END_REF]. -Second, if a pair of almost symmetric states is reached, there is only a single message pair that can be used to reach a symmetric state in the Feistel rounds. This prevents attacks like the herding attack on Lesamnta [START_REF] Bouillaguet | Another Look at the Complementation Property[END_REF], where one reaches a symmetric state and then uses a lot of different messages in order to explore the subset of symmetric outputs. -Third, the final transformation of SIMD uses the message length as input. Therefore, the symmetry property can only be seen in the output of the hash function with messages of unrealistic length (almost 2 512 bits for SIMD-256 and almost 2 1024 bits for SIMD-512). Note that computing the hash of such a message is vastly more expensive than finding a preimage. -Moreover the symmetry classes do not intersect. It is not possible to build a smaller symmetry classes in order to show collisions in the compression function, as was done for CubeHash [START_REF] Aumasson | Inside the Hypercube[END_REF][START_REF] Ferguson | Symmetric States and their Structure: Improved Analysis of CubeHash[END_REF]. Finding collisions in the compression function using the symmetry property costs 2 n/2 . It is more efficient than generic attacks on the compression function, but cannot be used to find collisions in the hash function faster than the birthday attack. We also note that the initial state of the SIMD hash function is not symmetric.

To summarize, reaching a symmetric state in SIMD is far less interesting than reaching a symmetric state in CubeHash or in Lesamnta. Table 1 gives a comparison of the symmetry properties found in these functions. Another very important factor is that SIMD is a wide-pipe design. Therefore reaching a symmetric state is about as hard a finding a preimage for the hash function. In the next section, we provide a formal proof that this distinguisher has only a small effect on the security of SIMD. We can prove that the hash function behaves as a random oracle under the assumption that the compression function is a weak perfect function having this symmetry property.

3 Free-start Distinguishers, Non-Ideal Compression Functions and Wide-Pipe Designs

In this section, we discuss the security of the prefix-free iteration of non-ideal compression functions. While our primary objective is to show that the distinguisher for the compression function of SIMD presented in Section 2 does not void the security proof of SIMD, the reasoning and the proof presented here are pretty general and could very well be adapted to other functions. Let H = {0, 1} p denote the set of chaining values, M = {0, 1} m denote the set of message blocks, and F be the set of all functions H × M → H. Let F ∈ F be a compression function taking as input an p-bit chaining value and an m-bit message block. A mode of operation for a hash function H • combined with a compression function F yields a full hash function H F .

Following [START_REF] Maurer | Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology[END_REF][START_REF] Coron | Merkle-Damgård Revisited: How to Construct a Hash Function[END_REF], we rely on the notion of indifferentiability of systems to reduce the security of SIMD to that of its compression function. The usual way of establishing the soundness of a mode of operation H • is to show that it is indifferentiable from a random oracle. This is done by constructing a simulator S such that any distinguisher D cannot tell apart (H F , F ) and (RO, S) without a considerable effort, where RO is a variable-input-length random oracle (VIL-RO, for short). When this is established, it is shown in [START_REF] Maurer | Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology[END_REF] that any cryptosystem making use of a VIL-RO is not less secure when the random oracle is replaced by the hash function H F , where F is an ideal compression function (i.e., a fixed-input-length random oracle, FIL-RO for short). Informally, if F is ideal (i.e., has no special property that a random function would not have), then H F is secure up to the level offered by the indifferentiability proof. More precisely, if H • is (t D , t S , q S , q 0 , ε)-indifferentiable from a VIL-RO when the compression function is assumed to be a FIL-RO, then this means that there exists a simulator running in time t S , such that any distinguisher running in time t D and issuing at most q S (resp. q 0 ) queries to the FIL-RO (resp. VIL-RO) has success probability at most ε.

A property of this methodology is that as soon as the compression function used in a hash function turns out to be non-ideal, then the security argument offered by the indifferentiability proof becomes vacuous. For instance, distinguishers exhibiting a "non-random" behavior of the compression function are usually advertised by their authors to nullify the security proof of the full hash function.

This problematic situation was first tackled by the designers of Shabal, who provided a security proof taking into account the existence of an efficient distinguisher on the internal permutation of their proposal [START_REF] Bresson | Indifferentiability with Distinguishers: Why Shabal Does Not Require Ideal Ciphers[END_REF]. We will follow their track and demonstrate that the security of SIMD can be proved despite the existence of an efficient distinguisher on its compression function.

The mode of operation of SIMD can be "concisely" described as being the wide-pipe prefix-free2 iteration of the compression function. Let H F therefore denote the prefix-free Merkle-Damgård iteration of F . Formally, g : {0, 1}

* → M * is a prefix-free encoding if for all x, x ′ , g(x) is not a prefix of g(x ′ ). The mode of operation H • simply applies the Merkle-Damgård iteration of F to the prefix-free encoding of the message.

The original security argument was that if the internal state and the hash are both p-bit wide, then prefix-free Merkle-Damgård is indifferentiable from a random oracle up to about 2 p/2 queries [START_REF] Coron | Merkle-Damgård Revisited: How to Construct a Hash Function[END_REF]. Theorem 1 below gives a formal statement of this result.

Theorem 1. Prefix-Free Merkle-Damgård is (t D , t S , q S , q O , ε)-indifferentiable from a VIL-RO when the compression function is modeled by a FIL-RO, for any running time t D of the distinguisher, and

t S = O (q O + κ • q S ) 2
where κ is an upper-bound on the size of the queries sent to the VIL-RO. If q = q S + κ • q O + 1, then the success probability of the distinguisher is upper-bounded by:

ε = 8 • q 2 2 p
In SIMD where the internal state is 2n bits, this ensures the indifferentiability of the whole function up to roughly 2 n queries (if H is indifferentiable up to q queries, then the composition of a truncation that truncates half of the output and of H is also secure up to q queries).

To restore the security argument damaged by the distinguisher, we will show that the prefix-free iteration of a non-ideal compression function is to some extent still indifferentiable from a VIL-RO.

Deterministic Distinguishers for the Compression Function

Let us consider a non-ideal compression function F .

-For instance, it may have weak states, that are such that querying F thereon with a well-chosen message block produces a "special" output allowing to distinguish F from random in one query. Known examples include for instance the symmetry on the compression function of Lesamnta [START_REF] Bouillaguet | Another Look at the Complementation Property[END_REF], CubeHash [START_REF] Aumasson | Inside the Hypercube[END_REF][START_REF] Ferguson | Symmetric States and their Structure: Improved Analysis of CubeHash[END_REF], and SIMD (described in Section 2). -But F can also have bad second-order properties, meaning that the output of F on correlated input states (with well-chosen message blocks) produces correlated outputs, allowing to distinguish F from random in two queries. A notable example of this property include the existence of differential paths with probability one in the compression function of Shabal [START_REF] Aumasson | More on Shabal's permutation[END_REF]. Symmetry properties also give second order relations, which means that Lesamnta, CubeHash and SIMD have bad second-order properties as well.

Following the methodology introduced in [START_REF] Bresson | Indifferentiability with Distinguishers: Why Shabal Does Not Require Ideal Ciphers[END_REF], we model this situation by saying that there are two relations R 1 and R 2 such that:

∀(h, m) ∈ H × M : R 1 (h, m, F (h, m)) = 1 ∀(h 1 , h 2 , m 1 , m 2 ) ∈ H 2 × M 2 : R 2 (h 1 , m 1 , h 2 , m 2 , F (h 1 , m 1 ), F (h 2 , m 2 )) = 1
We denote by R the relation formed by the union of R 1 and R 2 , and we will denote by F[R] the subset of F such that the above two equations hold. We require the relations to be efficiently checkable, i.e., that given h, m and h ′ , it is efficient to check whether R 1 (h, m, h ′ ) = 1. The relation can thus be used as an efficient distinguishing algorithm that tells F[R] apart from F.

A weak state is a state on which it is possible to falsify the relation R 1 . We formally define the set of weak states for R 1 in the following way:

W = {h ∈ H | ∃m, h ′ ∈ M × H such that R 1 (h, m, h ′ ) = 0}
W should be a relatively small subset of H because the loss of security will be related to the size of W. Moreover, we require that the IV is not in W.

In the same vein, a weak pair is a pair of states on which it is possible to falsify the relation R 2 . We therefore define the set of weak pairs for R 2 by an undirected graph G R2 = (H, WP), where WP is defined by:

WP = h 1 ↔ h 2 | ∃m 1 , m 2 , h ′ 1 , h ′ 2 ∈ M 2 × H 2 such that R 2 (h 1 , m 1 , h 2 , m 2 , h ′ 1 , h ′ 2 ) = 0
Similarly, WP should be a relatively small subset of H 2 because the security loss will be related to the size of WP. For the sake of expressing things conveniently, we define a variant of the same graph, G ′ R2 = (H × M, WP ′ ), where WP ′ is defined by:

WP ′ = (h 1 , m 1 ) ↔ (h 2 , m 2 ) | ∃h ′ 1 , h ′ 2 ∈ H 2 such that R 2 (h 1 , m 1 , h 2 , m 2 , h ′ 1 , h ′ 2 ) = 0
To simplify the proof we also require that the connected component of G ′ R2 have size at most two. This rules out some second-order relations, but it includes for instance the existence of a differential path with probability one with a non-zero difference in the input chaining value, as well as the symmetry in the compression function of SIMD or Lesamnta. We expect a similar result with larger connected components, but there will be a loss of security related to their size.

We also require the existence of sampling algorithms for R, namely of two efficient algorithms Sampler 1 and Sampler 2 such that:

Sampler 1 (h, m) : h ′ $ ← -{f (h, m) | f ∈ F[R]} ; return h ′ Sampler 2 (h 1 , m 1 , h 2 , m 2 , h ′ 1 ) : h ′ 2 $ ← -{f (h 2 , m 2 ) | f ∈ F[R] and F (h 1 , m 1 ) = h ′ 1 } ; return h ′ 2
Informally, the sampling algorithms should produce an output that looks as if it were produced by a random function constrained to conform to R.

Adapting the Indifferentiability Proof to Non-Ideal Compression Functions

We now assume that the compression function is a public function chosen uniformly at random in F[R], and for the sake of convenience we will call it a "biased FIL-RO". We show that the prefix-free iteration of biased FIL-RO is indifferentiable from a VIL-RO. In fact, we extend Theorem 1 to the case where the compression function is biased.

Theorem 2. Prefix-Free Merkle-Damgård is (t D , t S , q S , q O , ε)-indifferentiable from a VIL-RO, when the compression function is modeled by a biased FIL-RO conforming to the relation R, for any running time t D of the distinguisher, and t S = O (q O + κ • q S ) 2 where κ is an upper-bound on the size of the queries sent to the VIL-RO. If q = q S + κ • q o + 1, then the probability of success of the distinguisher is upper-bounded by:

ε = 16 • q 2 2 p + 4 • |W| • q 2 p + 4 • |WP| • q 2 (2 p -q) 2
The first term of the expression of ε is similar to the result given in Theorem 1, when the compression function is ideal (up to a factor two that could be avoided by making the argument slightly more involved). The two other terms reflect the fact that the compression function is biased. The relation induces a security loss if |W| is at least of order 2 p/2 , or if |WP| is at least of order 2 p . Informally, it seems possible to iterate compression functions having a relatively high bias in a secure way.

Application to Free-start Differential Attacks. Let us assume that the compression function is weak because of the existence of a good differential path with a non-zero difference in the input chaining value. Even if the probability of the differential path is 1, this has a very limited effect on the security of the hash function: this leads to W = ∅ and |WP| = 2 p-1 . The advantage of the distinguisher is at most twice as high, compared to the iteration of an ideal FIL-RO.

Application to SIMD. In SIMD-256 (resp. SIMD-512), the internal state has p = 512 bits (resp. p = 1024 bits), and the distinguisher of Section 2 yields |W| = 2 p/2+16 , |WP| = 2 p+32 (resp. |W| = 2 p/2+32 , |WP| = 2 p+64 ). Therefore the advantage of any distinguisher in telling apart SIMD-256 from a VIL-RO with q queries is upper-bounded by:

ε = 16 • q 2 2 p + 4 • 2 p/2+16 • q 2 p + 4 • 2 p+32 • q 2
(2 pq)

2 SIMD-256 is then secure up to roughly 2 256-16 queries (SIMD-512 is secure up to 2 512-32 queries).

Application to Lesamnta. Lesamnta follows the prefix-free Merkle-Damgård mode of operation due to its special finalization function. An efficient distinguisher based on symmetries was shown in [START_REF] Bouillaguet | Another Look at the Complementation Property[END_REF], with |W| = 2 p/2 and |WP| = 2 p-1 . According to Theorem 2, the advantage of any distinguisher in telling apart Lesamnta-256 from a random oracle with q queries is upper-bounded by:

ε = 16 • q 2 2 p + 4 • 2 p/2 • q 2 p + 4 • 2 p-1 • q 2 (2 p -q) 2 ≈ 22 • q 2 p/2
Note that since Lesamnta is a narrow-pipe design, we have p = n. Our result shows that Lesamnta remains secure against generic attacks up to the birthday bound. This is the best achievable proof for Lesamnta, since it does not behave as a good narrow-pipe hash function beyond that bound: a dedicated herding attack based on the symmetry property is shown in [START_REF] Bouillaguet | Another Look at the Complementation Property[END_REF], with complexity 2 n/2 .

The proof is heavily based on the proof in the extended version of [START_REF] Coron | Merkle-Damgård Revisited: How to Construct a Hash Function[END_REF]. Due to space constraints, the proof is not included in this paper, but can be found in the full version.

On Differential Attacks against SIMD

In this section we will present our results concerning differential paths in SIMD. Using Integer Linear Programming, we show that if there is a difference in the message, then the probability of the path will be at most of the order of 2 -n/2 . We stress that this result is not tight, but the computational power needed to improve the bound using this technique grows exponentially.

Related Work. The first attempt to avoid differential attack in a SHA/MD-like hash function was proposed in [START_REF] Jutla | Provably Good Codes for Hash Function Design[END_REF], where Jutla and Patthak described a linear code similar to the message expansion of SHA-1, and proved that it has a much better minimal distance than the original SHA-1 message expansion. They proposed to use SHA-1 with this new message expansion and called the new design SHA-1-IME.

Our Results. The design of SIMD follows the same idea, using a strong message expansion with a high minimal distance. In this paper we show that we can prove the security of SIMD more rigorously than the security of SHA-1-IME. While the security of SHA-1-IME is based on the heuristic assumption that the path is built out of local collisions, our proof gives an upper bound on the probability of any differential characteristic with a non-zero difference in the message.

Our results prove the following: for any message pair with a non-zero difference, the probability of going from an input difference ∆ in to an output difference ∆ out is bounded by 2 -132 for SIMD-256, and 2 -253 for SIMD-512.

Modeling Differential Paths

To study differential attacks against SIMD, we assume that the attacker builds a differential path. The differential path specifies the message difference and the state difference at each step. For each step i, we study the probability p(i) that the new step difference conforms to the differential path, assuming that the previous state difference and the message difference conforms to the path, but that the values themselves are random. Since SIMD heavily uses modular additions, our analysis is based on a signed differential, as used by Wang et al. [START_REF] Wang | Finding Collisions in the Full SHA-1[END_REF]. A signed difference gives better differential paths than an XOR difference if two active bits cancel each other out: with an XOR difference this gives a probability 1/2, but with a signed difference we have a probability 1 if the signs are opposed.

To study differential paths, we will consider the inner state of SIMD, and the Boolean functions φ (i) . A state bit A (i) j is called active if it takes two different values for a message pair following the differential path. Similarly, a Boolean function is called active if at least one of its inputs is active. A differential path consists of a set of active message bits, active state bits, active Boolean function, and the sign of each active element. We assume that the adversary first builds such a differential path, and then looks for a conforming pair of messages and chaining values. If we disregard the first and last rounds, each Boolean function has three inputs, and each state bit enters three Boolean functions. We use this simplification in Section 4.4.

The Message Expansion

The minimal distance of the message expansion of SIMD is at least 520. This distance counts the number of active bits, but we can also show that even if consecutive bits can collapse to give a single signed difference, we still have a minimal distance of 455 (respectively 903 for SIMD-512). The only case where adjacent differences can collapse to give a smaller signed difference is when the bits 15 and 16 are active in the two 16-bit words that are packed into a 32-bit word. In Section 4.4, we disregard this property and we just consider that the message introduces 520 differences through the message expansion, but the model used in Section 4.5 accounts precisely for that.

Structure of a Differential Path

The basic idea of our analysis is to use the lower bound on the number of active message bits to derive a lower bound on the number of active state bits. Each message difference must either introduce a new difference in the state, or cancel the propagation of a previous state difference. A single difference propagates to between 2 and 5 differences, depending on whether the Boolean functions absorb it or let it go through. This means that a collision corresponds to between 3 and 6 message differences.

For instance, if a difference is introduced in the state A

(5)

1 by W (5)
1 , it will appear in A

(5)

1 , B (6)
1 , C

1 , D

1 . Each of the Boolean function φ

(6) 1 , φ (7) 1 , φ (8)
1 can either absorb it or pass it. This difference will propagate to A if the corresponding Boolean functions are not absorbing. We consider two parts of the compression function: the computation of φ, and the modular sum. In order to study the probabilities associated with these computations, we will count the conditions needed for a message pair to follow the characteristic. φ-conditions. The Boolean functions MAJ and IF used in SIMD can either absorb or pass differences. When there is a single active input, the probability to absorb and to pass is 1/2. Each time a state difference enters a Boolean function, the differential characteristic specifies whether the difference should be passed or absorbed, and this gives one condition if the Boolean functions have a single active input. Thus, each isolated difference in the state will account for 3 φ-conditions: one for each Boolean function they enter. ⊞-conditions. When a difference is introduced in the state, it has to come from one of the inputs of the round function:

A (i) j = D (i-1) j ⊞ W (i) j ⊞ φ (i) (A (i-1) j , B (i-1) j , C (i-1) j ) ≪s (i) ⊞ A (i-1) p (i) (j) ≪r (i)
The round function is essentially a sum of 4 terms, and the differential characteristic will specify which input bits and which output bits are active. Thus, the differential characteristic specifies how the carry should propagate, and this gives at least one condition per state difference.

In the end, a state difference accounts for 4 conditions.

Heuristics

We first give some results based on heuristics. We assume that the adversary can find message pairs that give a minimal distance in the expanded message, and we allow him to add some more constraints to the expanded message. Note that finding a message pair with a low difference in the expanded message is already quite difficult with the message expansion of SIMD.

Heuristic I assumes that the adversary can find message pairs with minimal distance, but no other useful property. The adversary gets a message pair with minimal distance, and connects the dots to build a differential characteristic. Heuristic II assumes that the adversary can find message pairs with minimal distance and controls the relative positions of the message difference. He will use that ability to create local collisions. Heuristic III assumes that the adversary can find a message pair with any message difference, limited only by the minimal weight of the code. He will cluster local collisions to avoid many conditions.

Heuristic I. In this section, we assume that the adversary can find a message pair such that the expanded messages reach the minimal distance of the code, but we assume that the message pair has no further useful properties.

In this case, this adversary gets a message pair with a small difference and he has to connect the dots to build a differential path. This is somewhat similar to the attacks on MD4 [START_REF] Wang | Cryptanalysis of the Hash Functions MD4 and RIPEMD[END_REF]: the messages are chosen so as to make a local collision in the last round, and the attacker has to connect all the remaining differences into a path with a good probability.

It seems safe to assume that such a differential path will at least have as many active state bits as active message bits. Since an isolated difference in the state costs 4 conditions, we expect at least 2080 conditions (resp. 4128 for SIMD-512), which is very high.

Heuristic II. We now assume that the adversary can force some structure in the expanded message difference. Namely, he can choose the relative location of the differences in the expanded message. Since the probability of the path is essentially given by the number of active bits in the state, the path should minimize this. This is achieved with local collisions, and each local collision will use as many message differences as possible. Due to the structure of the round function of SIMD, a local collision can use between 3 and 6 message differences, depending on whether the Boolean functions absorb or pass the differences. In order to minimize the number of state differences, the path will make all the Boolean functions pass the differences, yielding six message differences per state difference. This is somewhat counter-intuitive because most attacks try to minimize the propagation of differences by absorbing them. However, in our case it is more efficient to let the differences go through the Boolean functions, and to use more message differences to cancel them, because we have a lower bound on the number of message differences.

Since the adversary only controls the relative position of the message differences, we assume that most local collisions will be isolated, so that each local collision gives 4 conditions. Thus, a differential is expected to have at least 520 × 4/6 ≈ 347 conditions (688 for SIMD-512). This leaves a significant security margin, and even if the adversary can use message modifications in the first 16 rounds, it can only avoid half of those conditions.

This can be compared to the attacks on SHA-1 [START_REF] Chabaud | Differential Collisions in SHA-0[END_REF][START_REF] Wang | Finding Collisions in the Full SHA-1[END_REF]. These attacks are based on local collisions, but we do not know how to find a message pair which would have both minimal distance and yield a series of local collisions in SHA-1. Instead, attacks on SHA-1 use the fact that the message expansion is linear and circulant: given a codeword, if we shift it by a few rounds we get another valid codeword and similarly if we rotate each word we get another valid codeword. Then we can combine a few rotated and/or shifted codewords so as to build local collisions. The attacks on SHA-1 start with a codeword of minimal distance, and combines 6 rotated versions. Thus the weight of the actual expanded message difference used in the attack is six times the minimal weight of the code.

Note that message expansion of SIMD is more complex than the one from SHA-1, and it seems very hard to find this kind of message pairs in SIMD. Moreover, the trick used in SHA-1 cannot be used here because the message expansion is neither linear nor circulant.

Heuristic III. We now remove all heuristic assumptions and we try to give a bound on any differential trail. However, to keep this analysis simple, we still disregard the specificities of the first round, and the fact that one can combine some of the message differences.

The adversary will still use local collisions to minimize the number of differences in the state, but he will also try to reduce the number of conditions for each local collision by clustering them. We have seen that an isolated state difference costs 4 conditions, but if two state differences are next to each other, the cost can be reduced when using a signed difference. For instance, if two inputs of the MAJ function are active, the adversary does not have to pay any probability: if both active inputs have the same sign, then the output is active with the same sign, but if the inputs have opposite signs then the output will be inactive. In this section we consider that a Boolean function with more than one active input does not cost any probability.

Thus, the best strategy for the adversary is to place the state differences so that each active Boolean function has two active inputs, in order to avoid any φ-conditions. Each state difference costs only one ⊞-condition, and gets 4.5 message differences (these message differences corresponding to the Boolean functions are shared between two Boolean functions). This gives a lower bound of 116 conditions.

Program 1 Linear Program

Minimize S + αβ with the constraints:

3S = α + β + γ (1) 520 ≤ 3S + α (2) γ ≤ β ≤ α (3)
α ≥ 0 is the number of Boolean functions with at least one active input β ≥ 0 is the number of Boolean functions with at least two active inputs γ ≥ 0 is the number of Boolean functions with at least three active inputs S ≥ 0 is the number of active state bits More rigorously, this can be described by a linear program, as shown in Linear Program 1. Equation ( 1) comes from counting the number of active inputs to the Boolean functions in two different ways, while Equation ( 2) counts the number of message differences that can be used. The objective value S + αβ counts the conditions: one for each state difference, plus one for each Boolean function with exactly one active input. The optimal solution to this program is 520/4.5 ≈ 115.55.

In the next section we will see how to improve this bound and get a bound on the probability of any differential path.

Comparison with SHA-1-IME. The security of SHA-1-IME is based on a heuristic that is quite similar to our Heuristic I. Jutla and Patthak assume that the adversary will use the same technique as the attacks on SHA-1, i.e. create local collisions using the fact that the code is linear and circulant. They deduce that the probability of a differential characteristic will be about 2 75×2.5 . They implicitly assume that the adversary cannot find minimal codewords that would already give local collisions. Our Heuristic II assumes that the attacker can find such codewords, and if we apply it to SHA-1-IME, it would only guarantee that we have at least 13 local collisions (each local collision accounts for 6 message differences). Since a local collision in SHA-1 has an average probability of 2 -2.5 , this would only prove that an attack has at least a complexity 2 13×2.5 = 2 32. 5 . This shows that our Heuristic II and III are much weaker than the heuristic used in SHA-1-IME.

Upper Bounding the Probability of a Differential Path

The bound given by Heuristic III is slightly lower than n/2 so we would like to improve it. To find a better bound, we will follow the approach of Linear Program 1. Note that in the optimal solution, all the Boolean functions have either zero or two active inputs, but it is unlikely that such a path actually exists because of the way the Boolean functions share inputs. In order to remove some impossible solutions, we use a more detailed modeling of differential paths where each individual state bit is treated separately. This also allows us to express some extra constraints that will help to improve the lower bound.

Constraints related to the message expansion. We know that the message expansion gives at least 520 differences in the expanded message, but there are some constraints on the positions of these differences. Namely, we have at least 65 active words in each copy of the message, and each active word has at least 4 active bits. For instance, a difference pattern with 3 active bits in each word would have 768 bit differences, but it is not a valid pattern. Moreover, the active words in both copies have to be the same up to the permutation P . To include these constraints in our model, we add a set of binary variables Y i which encode whether word i is active in the output of the NTT. This is modeled by Equations ( 4) and [START_REF] Bouillaguet | Security analysis of simd[END_REF]. Note that this still allows many difference patterns that cannot be the output of a real message pair.

Better cost estimation. In Program 1, we only count a condition for the Boolean functions with a single active input. In fact, if we look at the truth table of the Boolean functions we see that the IF function still needs a condition when inputs 1 and 2, or 1 and 3 are active. Since we are using distinct variables for each of these inputs, we can include this in our description.

Program 2 Integer Linear Program (simplified)

Minimize P S (j)[k] i + P α (j)[k] i - P β (j)[k] i
with the constraints:

S (j-1)[k] i + S (j-2)[k] i + S (j-3)[k] i = α (j)[k] i + β (j)[k] i + γ (j)[k] i (1') W (j)[k] i ≤ S (j)[k+s j ] i + S (j-4)[k-r j ] i + S (j-1)[k-r j +s j ] p j (i) + α (j)[k] i (2') γ (j)[k] i ≤ β (j)[k] i ≤ α (j)[k] i (3') 15 X k=0 W (j)[k] i ≥ 4Y P 1 (i,j) 31 X k=16 W (j)[k] i ≥ 4Y P 0 (i,j) (4)
X Yi ≥ 65 (5) α (j)[k] i ∈ B is true iff φ (j)[k] i
has at least one active input

β (j)[k] i ∈ B is true iff φ (j)[k] i has at least two active input γ (j)[k] i ∈ B is true iff φ (j)[k] i
has at least three active input

S (j)[k] i ∈ B is true iff the state bit A (j)[k] i is active W (j)[k] i ∈ B is true iff the expended message bit W (j)[k] i is active Yi ∈ B
is true iff the word i is active in the output of the NTT

We can write all these constraints as a huge optimisation problem with approximately 30,000 variables and 80,000 equations, but we need some tool to find the optimal solution of the system, or at least find a lower bound. We decided to write our problem as an Integer Linear Program.

Integer Linear Programming. Integer Linear Programming (ILP) is a generalisation of Linear Programming (LP) where some variables are restricted to integer values. While LP is solvable in polynomial time, ILP is NP-complete. ILP solvers usually use some variants of the branch-and-bound algorithm. In the case of minimization problem, the branch-and-bound algorithm computes a lower bound to the optimal solution and incrementally raises this lower bound. Meanwhile, non-optimal solutions give an upper bound, and when the two bounds meet, the search is over.

Results. A simplified version of the ILP is given by Program 2. The first equations and the objective value mirrors Program 1, but use many variables to allow for more precise extra constraints. The full program has 28,576 variables and 80,162 equations for SIMD-256. We used the solver SYMPHONY, an open-source solver for mixed-integer linear programs, available at http://www.coin-or.org/SYMPHONY/. The solver could not find an optimal solution to the program, but it reached an interesting lower bound after some time: a differential path for SIMD-256 has at least 132 conditions, while a differential path for SIMD-512 has at least 253. The computation for SIMD-512 took one month on a bi-quadcore machine.

Summary. The optimal strategy of the attacker is to use local collisions (avoiding any difference propagation) and to cluster the local collisions so as to avoid most conditions. Our modeling allows the adversary to do this because he can choose the message difference and the expanded message difference independently, and he can position the differences arbitrarily in the inner code. However, this is not possible in practice, and most solutions of the Integer Linear Program will require an expanded message difference that is not actually feasible. Therefore, we expect that the best differential path in SIMD is much worse that the optimal solution of our Integer Linear Program. Moreover, the program is too large to be solved to optimality, and we only have a lower bound on the number of conditions (this lower bound keep improving if we let the solver run).

On the Symmetry-based Distinguisher

The distinguisher of Section 2 shows that the compression function of SIMD is not ideal. It does not affect the security of the hash function, but it is nonetheless an unwanted property. Since this distinguisher is based on symmetry properties, it is easy to avoid this property by slightly changing the design. Therefore, we plan to tweak the SIMD design by adding non-symmetric constants, if given such an opportunity. We also note that other SHA-3 candidates are in a similar situation:

-CubeHash has strong symmetry properties in its round transformation [START_REF] Aumasson | Inside the Hypercube[END_REF][START_REF] Ferguson | Symmetric States and their Structure: Improved Analysis of CubeHash[END_REF]. It is thought that since the initial state in not symmetric, it is not possible to reach a symmetric state. -Shabal has strong distinguishers on its compression function: there are differential paths with probability 1 [START_REF] Aumasson | More on Shabal's permutation[END_REF], and the inverse permutation does not have full diffusion (some input bits do not depend on all output bits). The Shabal team has shown that these distinguishers do not affect the security [START_REF] Bresson | Indifferentiability with Distinguishers: Why Shabal Does Not Require Ideal Ciphers[END_REF].

Countermeasures. An interesting way to avoid the symmetry properties would be to add a counter to the expanded message after the multiplication by a constant (step 3 of the message expansion). This would ensure that each expanded message word has a different value modulo 185 (respectively modulo 223), and it prevents equality constraints between the expanded message words.

On Differential Attacks

Concerning differential attacks, our results are two-fold:

1. A differential path with a non-zero difference in the input chaining value does not affect the security of the hash function because it is wide-pipe 2. A differential path with a non-zero difference in the message cannot have a high success probability, because of the strong message expansion.

This shows that successful attacks on the hash function based on differential properties are very unlikely.

A Example of Weak Message

Here is an example of a weak message, and the output of the compression function when used with the same value for the message and chaining value (this ensures that the XOR is symmetric). Notice that the output is mostly symmetric.

Message = Chaining Value A0..3 00000000 00000000 00000000 00000000 B0..3 00000000 00000000 00000000 a2000000 C0..3 00000000 00000000 00000000 00000000 D0..3 00000000 00000000 00000000 f1000000

Fig. 1 .Fig. 2 .

 12 Fig. 1. SIMD modified Davies-Meyer mode

  Boolean functions do not absorb it. Up to five active message bits can be used to cancel this propagation: W

Output A0.. 3

 3 0e0618e6 0ee618e6 ec5a3cee fbdc48ae B0..3 17bde794 17bddbd4 5a0a59f2 5a2a59f2 C0..3 12a9c015 12a9c015 be7d3df1 be775df1 D0..3 15f9cb8d 15f9cb8d 2efef45c 2efef45c Expanded Message W

Table 1 .

 1 Comparison of symmetry properties in several hash functions.

		Reach	Max. Max.	Free-start
	Function symm. state length degree	Collisions
	Lesamnta-512	2 256	1	2 256 2 128 (semi-free-start)
	CubeHash (symm C1..C7)	2 384	∞	2 128 2 32 (semi-free-start)
	CubeHash (symm C8..C15)	2 256	∞	1	2 64 (semi-free-start)
	SIMD-512	2 480	1	1	2 256

This design choice was guided by implementation efficiency

this is not explicitly stated in the submission document, but SIMD has a different finalization function that effectively acts as a prefix-free encoding.

Acknowledgments

We would like to thank Praveen Gauravaram from Technical University of Denmark, Copenhagen for discussions on the proof of indifferentiability.

We would also like to thank Franck Landelle from CELLAR for insightful comments on the security of SIMD and limitations of our initial study of differential paths. Part of this work was supported by CELLAR.

Part of this work was supported by the European Commission through ECRYPT, and by the French government through the Saphir RNRT project.


Tristan Belzacq

Stéphane Avril
email: avril@emse.fr

Emmanuel Leriche

Alexandre Delache

Modelling of fluid structure interactions in stenosed arteries: effect of plaque deformability

Keywords: vascular, fluid structure interaction; stenosis, blood flow

Introduction

This paper deals with the study of fluid structure interactions in stenosed arteries. Stenoses in arteries are usually induced by the formation of an atheromatous plaque. This is a major issue of public health. Diagnoses based on simple image analysis (measurement of stenosis severity) are currently insufficient for reducing the impact of the cardio-vascular diseases, which may provoke a decrease of life expectancy for the 25-45 generation in the near future. Improved diagnoses should be devised for avoiding this issue. Therefore, there is a real medical and economical interest in developing tools and systems for determining and understanding the mechanical response of plaques in the arteries [START_REF] Li | Stress analysis of carotid plaque rupture based on in vivo high resolution MRI[END_REF]. This mechanical response is mainly induced by the combination of shear and pressure loads applied by the blood at each heart beat. Several authors developed numerical models based on fluid structure interactions (FSI) for taking into account these effects [START_REF] Li | Simulation of the interaction between blood flow and atherosclerotic plaque[END_REF][START_REF] Tang | Local critical stress correlates better than maximum stress with plaque morphological features linked to atherosclerotic plaque vulnerability: an in-vivo multi-patient study[END_REF]. Their main conclusion was that the vulnerability of atheromatous plaques may be explained by a concentration of stresses in the fibre cap that contains the lipid core of the plaque.

However, there is a large variability of plaque types among the patients and the models cited previously considered only very idealized geometry. No parametric study has ever been published about the effect of plaque type, plaque composition and plaque geometry on the mechanical response of the stenosed artery. The main objective of this paper is to address this issue.

Methods

A 2D axisymmetric model of a stenosed artery has been developed (Figure 1). It is composed of the healthy arterial wall outside (material 1), a lipid core (material 2), a fibre cap (material 3) containing the lipid core and a calcified inclusion (material 4). Each of this material is modelled as an elastic solid with a Poisson's ratio of 0.45 and a different Young's modulus (E1=500kPa, E2=20kPa, E3=600kPa, E4=10MPa). Different plaque parameters can be tuned (Figure 1) for covering different types of atheromatous plaques reported in [START_REF] Cai | Classification of human carotid atherosclerotic lesions with in vivo multicontrast magnetic resonance imaging[END_REF]: the elastic moduli of the constituents, the thickness of the fibre (e), the severity (S) of the stenosis (ratio between the radius of the healthy artery and the stenosed artery), the radius (Rem) of remodelling (externally bulging part of the artery), the length of the stenosis (L), location of the calcified inclusion. Blood is modelled as an incompressible Newtonian fluid. FSI computations are run using the finite element (FE) method in Comsol software. Mesh updating of the fluid problem is based on an Arbitrary Eulerial Lagrangian (ALE) scheme. Boundary conditions for the fluid are a physiological Womersley velocity profile at the inlet, and a physiological pressure prescribed at the outlet.

Results and conclusions

The advantage of using a 2D axisymmetric model is that a large number of FE models could be run in a reasonable time. The analysis focuses on the following aspects of the computed responses: -A1: maximum cyclic Von Mises equivalent strain in the fibre cap [START_REF] Ohayon | In-vivo prediction of human coronary plaque rupture location using intravascular ultrasound and the finite element method[END_REF] -A2: maximum cyclic shear stress -A3: maximum radial and axial motion of the plaque during a cardiac cycle -A4: length of the recirculation zone. Results show that A1, A2, A3 and A4 increase when increasing S and decreasing L. Indeed, for very slender plaques, a pinching occurs, resulting in increased deformations. This phenomenon is shown in Figure 2 on a severe short plaque where the deformed shape of the fibrous cap was plotted at the systolic time. The pinching phenomenon can also induce buckling in the fibrous cap for larger stenoses when e is smaller, as shown in Figure 3. Increase of E3 and e is shown to reduce A1 and A3. The presence of a calcified inclusion is shown to increase A1 and A3, and hence to amplify the pinching phenomenon. The interpretation of these results is under progress and it still has to be validated by an experimental study. However, the trends are that the effects of pressure and shear loads applied by the blood is amplified if plaques are very deformable. In other words, the most stable plaques are the least deformable ones. These trends are usually confirmed by the clinical practice. Future work will address the definition a criterion of plaque vulnerability, based on plaque deformability. 3D models of the stenosed carotid bifurcation are also under development.

Figure 1 .

 1 Figure 1. Geometrical model of the plaque: e=thickness of the fibre cap, S=severity of the stenosis, Rem=increase in external radius, L=length of the stenosis.

Figure 2 .

 2 Figure 2. The deformed shape of the fibrous cap at systole (colorbar figures the stress level, from minimum=black to maximum=white) and the plaque deform shape at diastole in uniform grey.

Figure 3 .

 3 Figure 3. The deformed shape of the fibrous cap with buckling at systole (colorbar figures the stress level, from minimum=black to maximum=white) and the plaque deform shape at diastole in uniform grey.


Fati Kirakoya-Samadoulougou

Marie-Christine Defer

Seydou Yaro

Paulin Fao

François Ilboudo

Youssouf Langani

Nicolas Meda

Annie Robert

Nicolas Nagot

LOW SEROPREVALENCE OF SYPHILIS IN BURKINA FASO

Keywords: Syphilis, urban, rural, prevalence, Burkina Faso

Background: Little information is available on the epidemiology of syphilis in West Africa, where this infection is routinely screened in antenatal clinics to prevent congenital infection.

In order to inform control programmes, we estimated the burden of active syphilis among pregnant women and adults in Burkina Faso.

Methods: This study enrolled 2136 pregnant women from 98 health care facilities and 1679 consenting women and men from the general population of Ouagadougou, the capital city.

After a face-to-face interview on demographic characteristics, blood samples were collected and tested for syphilis. Active syphilis was defined by a dually positive result on RPR and TPHA tests.

Results:

The overall seroprevalence of active syphilis was 1.7% (95% confidence interval (CI)=1.3-2.2), with similar rates between women (1.2%, CI=0.7-2.3) and men (1.8%, CI=1.0-3.0) in Ouagadougou, and a trend for higher prevalence among pregnant women from semiurban areas (2.2%, CI=1.0-4.5) compared with rural areas (1.7%, CI=1.2-2.4, p=0.06). The prevalence tended to be higher among women aged 20-24 (2.6%, CI=1.3-7.6) and men aged 30-34 (3.9%, CI=0.8-11.0) than at other ages. However, age, marital status, location and education were not associated with syphilis.

Conclusion:

The low prevalence of syphilis among pregnant women and the adult general population is very encouraging but should not challenge the amount of resources dedicated to STI and HIV prevention.

Specific tasks and major degree(s) of author and co-authors:

Seydou Yaro (MD, Msc), Paulin Fao (MD, Msc), and Nicolas Nagot (MD, PhD) designed the study, directed its implementation, coordinated the discussion of the results, and commented on the draft manuscript.

Fati Kirakoya-Samadoulougou (Msc) performed serological testing, retrieved the data, and participated in the statistical analysis and the data interpretation and manuscript preparation.

François Ilboudo(Msc) and Youssouf Langani (Msc) coordinated data collection in

Ouagadougou site, and commented on the draft manuscript.

Marie-Christine Defer (PhD) implemented, performed and supervised all laboratory activities including quality assurance and control, participated in the interpretation of results, and corrected the first draft.

Nicolas Meda (MD, PhD) helped supervise the field activities, designed the study's analytic strategy and manuscript preparation.

Annie Robert (PhD) provided guidance to all aspects of statistical analysis and revised manuscript for important intellectual content.

All authors read and approved final manuscript.

Introduction

Syphilis remains a major cause of reproductive morbidity and poor pregnancy outcomes in sub-Saharan Africa, which justified a routine serological screening during antenatal consultations. In addition, syphilis infection substantially increases the sexual transmission of HIV [START_REF] Fleming | From epidemiological synergy to public health policy and practice: the contribution of other sexually transmitted diseases to sexual transmission of HIV infection[END_REF].

The prevalence of syphilis amongst pregnant women varies widely throughout Africa, from 17.4% in Cameroon, 8.4% in South Africa to 6.7% in Central African Republic [START_REF]Global Prevalence and Incidence of Selected Curable Sexually Transmitted Infections: Overview and Estimates[END_REF]. In Burkina Faso (BF), the syphilis prevalence among pregnant women was 0.24% between 1995 and 1998 (3). In the general population, only 3 cases of syphilis have been detected among a random sample of 2364 adults in 2000(4). . In order to document syphilis prevalence in BF, we conducted a cross-sectional study among the general population in the capital city and among pregnant women in 4 geographically distant provinces of BF.

Methods

Study among pregnant women

A sero-survey was conducted between May and July 2003 among pregnant women attending all ANC clinics (n=98) from Boulgou, Poni, Seno and Yatenga provinces [START_REF] Kirakoya-Samadoulougou | Bacterial vaginosis among pregnant women in Burkina Faso[END_REF].

Study in the general population in Ouagadougou, capital city

We used a two-stage clustered sample design in the first stage, we randomly selected 59/713 administrative areas and in the second stage, we randomly selected 20 households in each area. All adults aged 15-49 years present in the selected households were invited to participate in the study. After informed consent, individuals were interviewed to collect data on demographic factors, medical backgrounds and behaviours related to the risk of HIV/STI.

Common procedures for the two studies

Active serological syphilis was diagnosed by a positive Rapid plasma regain (RPR) test (any titre), confirmed by the Treponema haemaglutination assay test (TPHA; at dilution below 1:80) (Newmarket Laboratories Ltd Germany). Prevalences are reported with 95% confidence intervals computed using Poisson distribution because of small proportions. All analyses (estimation, confidence intervals), adjusted for the Ouagadougou clustered design. Specially, we specified individual weight, secondary sampling units and primary sampling unit [START_REF] Levy | Sampling of Populations: Methods and Applications[END_REF]. A P value < 0.05 was considered as significant.

Ethical considerations

The Ministry of Health of BF approved the study. Participants with active syphilis and their partners were treated based on the National STD Treatment Guidelines. Because HIV test results unlinked, women and men who wished to know their HIV status were referred to a nearby facility for free voluntary counselling and testing.

Results

The seroprevalence of syphilis was 1.7% (95% confidence interval (CI)=1.3-2.2) among all participants (N=3815), with a good response rate (93.5% among pregnant women and 77.2% in Ouagadougou).

A total of 64 pregnant women (3.0%) were positive for RPR; 38 were positive for TPHA, giving a active syphilis seroprevalence of 1.8% (CI=1.3-2.5), ranging from 0.6% (CI= 0.2-1.9) in Boulgou province to 3.6% (CI= 2.2-5.9) in Poni province (table 1). Pregnant women living in rural areas tended to be less infected (1.7% versus 2.2%) than those living in semiurban areas (main cities of the province)( p=0.06). HIV prevalence in this population was 2.5% (CI=1.9, 3.3), ranging from 1.3% (CI= 0.5-2.9) in Seno province to 3.6% (CI= 2.2-5.7) in Boulgou province.

In Ouagadougou, active syphilis seroprevalence was 1.5% (CI= 1.1-2.3). There were 32 RPR positive and 25 TPHA positive. The prevalence of active syphilis tended to be higher among women aged 20-24 (2.6%, CI=1.5-3.7) and men aged 30-34 (3.9%, CI=0.4-8.2). However, age, marital status, location and education were not associated with syphilis in multivariable analysis (data not shown).

Discussion

The prevalence of syphilis among pregnant women in this study was lower than in a similar study from 1997 (2.5%, IC:1.7%-3.5%) [START_REF] Sangare | HIV infection among pregnant women in Burkina Faso: a nationwide serosurvey[END_REF], but with important regional variations.

The syndromic management of STI was implemented in BF in 1996. Widespread use of antibiotics and good access to health care may have contributed to the decline in syphilis and STD prevalence [START_REF] Nagot | Review of STI and HIV epidemiological data from 1990 to 2001 in urban Burkina Faso: implications for STI and HIV control[END_REF], along with a decline in risky sexual behaviours resulting from HIV prevention programmes.

The differences in syphilis prevalence between urban (Ouagadougou) and rural areas (pregnant women) may be explained by different sexual behaviours, the urban area being more exposed to HIV prevention programmes. The development of HIV prevention initiatives towards rural areas could be pivotal to further reduce syphilis. This low prevalence of syphilis infection should not challenge the systematic screening of this infection among pregnant women. Terris-Prestholt and colleagues (9) estimated the cost effectiveness of the intervention according to different levels of syphilis prevalence varying from 2% to 15%. The cost per DALY saved decreased substantially as prevalence increased.

However, even at prevalence as low as 2%, antenatal syphilis screening and treatment remains cost effective ($33 per DALY saved including stillbirth).

The low prevalence of syphilis in Burkina Faso is encouraging, but should not divert the resources dedicated to STI and HIV prevention in the country to other interventions.

Acknowledgements

These results were presented in part at the 5th International AIDS Society conference on HIV pathogenesis, treatment and prevention, Cape Town (South Africa), 19 -22 July, 2009.

We thank the staff from the 4 provinces of Burkina Faso, the staff of centre MURAZ, the Ministry of Health, and the National AIDS Control Programme.

This work was supported by the United Nations Development Programme (UNDP), World

Health Organisation (WHO), the United Nations Population Fund (UNFPA), Embassies of Holland, Switzerland, Denmark and Belgium.

Finally, we thank all the individuals who sacrificed their time to be interviewed as part of this study.

Key points

• Although the seroprevalence of active syphilis was as low as 2% among pregnant women in Burkina Faso, it still justifies the need for systematic screening during pregnancy.

• Age, marital status, urban or rural location and education were not associated with active syphilis. Pregnant women from semi-urban areas tended to be more infected with syphilis than pregnant women from rural areas

• this survey confirm the decrease of bacterial STIs in this African region over the past 15 years.

Conflict of interest : none

Word count : 774

Copyright licence statement I Fati KIRAKOYA-SAMADOULOUGOU The Corresponding Author has the right to grant on behalf of all authors and does grant on behalf of all authors, an exclusive licence on a worldwide basis to the BMJ Group and co-owners or contracting owning societies (where published by the BMJ Group on their behalf), and its Licensees to permit this article (if accepted) to be published in Sexually Transmitted Infections (STI) and any other BMJ Group products and to exploit all subsidiary rights, as set out in your licence set out at http://sti.bmj.com//ifora/licence.pdf).


Choukri Kazi

Thomas Le Bourgeois

François Munoz

Contribution à l'étude des communautés d'adventices des culture du secteur phytogéographique oranais (Nord-ouest algérien) : aspects botanique, agronomique et phyto-écologique

Keywords:

and research institutions in France or abroad, or from public or private research centers.

AFPP -VINGT ET UNIÈME CONFÉRENCE DU COLUMA JOURNÉES INTERNATIONALES SUR LA LUTTE CONTRE LES MAUVAISES

, LE BOURGEOIS T. (2) , MUNOZ F. (3) (1) Département des Sciences Agronomiques et des Forêts, Faculté des Sciences de la Nature et de la Vie et des Sciences de la Terre et de l'Univers, Université Abou Bekr Belkaïd, B.P. 119, 13 000 Tlemcen, Algérie -Mél : kazi_tc@yahoo.com (2) CIRAD, UMR AMAP, TA A51/PS2, 34398 Montpellier cedex 5, France Mél : thomas.le_bourgeois@cirad.fr (3) UM2, UMR AMAP, TA A51/PS2, 34398 Montpellier cedex 5, France Mél : francois.munoz@cirad.fr RÉSUMÉ L'étude de l'enherbement des agrosystèmes d'Oranie, dans le Nord-Ouest de l'Algérie, s'appuie sur 547 relevés floristiques réalisés dans les différentes cultures de cette région, pour décrire les caractères d'ensemble de la flore adventice ainsi que les attributs botaniques, phytogéographiques, biologiques et éthologiques des 425 espèces recensées. Nous analysons l'importance agronomique des espèces à partir de leur fréquence relative et de leur recouvrement moyen. La projection des espèces sur un diagramme d'infestation a permis de différencier 6 groupes d'espèces. L'étude phyto-écologique des relations entre espèces et variables de milieu par l'analyse non-symétrique des correspondances -NSC, sous contrainte environnementale indique que la principale source de variation floristique au niveau des différents terroirs d'Oranie est liée aux systèmes de cultures.

Mots-clés : Flore adventice -Agrosystèmes -Phyto-écologie -Nuisibilité -Analyse nonsymétrique des correspondances.

INTRODUCTION

L'Algérie possède une des flores les plus diversifiées et les plus originales du bassin méditerranéen. Cette flore compte 3 139 espèces répartis dans près de 150 familles parmi lesquelles 653 espèces sont endémiques, soit un taux d'endémisme d'environ 12,6 %. En ne considérant que le secteur phytogéographique oranais, celui-ci conserve environ 1 780 espèces végétales du total de la flore algérienne soit environ 57 % de la flore du pays, mais 95 % de la flore méditerranéenne maghrébine (cette dernière comptant 1 865 espèces selon [START_REF] Quézel | Réflexions sur l'évolution de la flore et de la végétation au Maghreb méditerranéen[END_REF]). Environ 14 % (250 espèces) de ces éléments floristiques sont répertoriés au niveau de la flore de Quézel et Santa (1962[START_REF] Quézel | -1963 -Nouvelle Flore de l'Algérie et des Régions Désertiques Méridionales[END_REF] comme strictement inféodés aux parcelles cultivées. La connaissance de la composition de la flore adventice et de son évolution avec les pratiques culturales est un préalable indispensable à toute mise au point de stratégies de lutte intégrée. C'est la raison pour laquelle, depuis plusieurs années déjà, des études floristico-écologiques ont été entreprises dans différentes régions d'Algérie [START_REF] Chevassut | Végétation spontanée hivernale des vignobles de la plaine littorale algéroise de la Mitidja (Algérie)[END_REF][START_REF] Fenni | Contribution à l'étude des groupements messicoles des Hautes Plaines sétifiennes[END_REF][START_REF] Abdelkrim | Contribution à la connaissance des groupements de mauvaises herbes des cultures du secteur algérois : Approche syntaxonomique et phénologique[END_REF]etc.). Ces études régionales ont permis une meilleure connaissance de la constitution et de la répartition de la flore adventice. Toutefois, les régions agricoles du pays qui ne sont pas encore explorées sont nombreuses. C'est particulièrement le cas de l'Oranie qui est pourtant une zone céréalière et viticole de première importance. Les terroirs de la région restent marqués par une agriculture traditionnelle extensive (polyculture, élevage, jachère…) où perdure encore la pratique de la vaine pâture sur les chaumes après les moissons, bien que les contraintes économiques actuelles poussent beaucoup d'agriculteurs de la région à se moderniser et à adopter des pratiques plus intensives facteur de la régression de la flore spontanée des champs. Dans le présent travail, nous étudierons les différents aspects botaniques, écologiques et agronomiques que présentent les adventices des cultures annuelles et pérennes ainsi que des jachères d'Oranie. Sachant que si une meilleure connaissance de la flore arvicole permet l'élaboration de plans de lutte intégrée, elle aide aussi à mieux la protéger.

MATERIEL ET MÉTHODE

LA

LA COLLECTE ET L'ANALYSE DES DONNEES

La flore arvicole oranaise a été recensés à partir de 547 relevés floristiques réalisés dans les différentes cultures annuelles et pérennes de l'ensemble du domaine phytogéographique oranais (figure 1), depuis 50 m d'altitude jusqu'à environ 1 250 m au-dessus du niveau de la mer, en deux campagnes: la première de Janvier à Juillet 2006, la seconde de Mars à Juin 2009 [START_REF] Kazi | Aspects floristiques des agrophytocenoses du domaine phytogéographic oranais (Nord-Ouest algérien) et persistence d'espèces rares et endémiques[END_REF]. Les relevés ont été réalisés selon la méthode des aires minimales évaluées préalablement en fonction de chaque type de culture (Tableau I). La nomenclature botanique suivie est celle de la "Nouvelle Flore de l'Algérie" de Quézel et Santa (1962[START_REF] Quézel | -1963 -Nouvelle Flore de l'Algérie et des Régions Désertiques Méridionales[END_REF]. Les noms latins ont été transcrit en code Bayer [START_REF] Bayer | Composite list of weeds[END_REF]. La projection des espèces sur un diagramme d'infestation où sont portées en abscisse leurs fréquences relatives et en ordonnée leur abondance moyenne (toutes deux représentent une notion primordiale en malherbologie), permet de différencier les espèces selon leur degré d'infestation, donc de leur importance agronomique [START_REF] Loudyi | Étude botanique et écologique de la végétation spontanée des terres cultivées du plateau de Meknès (Maroc)[END_REF][START_REF] Guillerm | Westerm Mediterranean countries of Europe[END_REF][START_REF] Bourgeois | Étendue de distribution et degré d'infestation des adventices dans la rotation cotonnière du Nord-Cameroun[END_REF]. L'abondance moyenne d'une espèce dans un ensemble de relevés est représentée par son indice d'abondance/dominance moyen, AD moy(e). Celui-ci correspond à la moyenne des indices d'abondance/dominance de l'espèce AD(e), calculé par rapport au nombre de relevés dans lesquels l'espèce est présente Nrel(e). L'indice d'abondance/dominance est un indice de 1 à 100 correspondant à l'échelle de recouvrement du sol. L'utilisation d'un indice moyen confère aux espèces un poids semblable au niveau du graphique et permet de délimiter aisément les secteurs correspondants aux différents groupes. AD moy(e) = Σ AD(e) / Nrel(e) Nous avons analysé les sources de variation floristique des communautés d'adventices à l'aide des analyses sur variables instrumentales (analyse non-symétrique des correspondances -NSC, sous contrainte environnementale) de façon à mettre en évidence le rôle de différentes variables du milieu :

• les systèmes d'exploitation ;

• les types présumés de sol ;

• la présence ou l'absence d'irrigation ;

• et les interactions 2 à 2. Pour chaque variable testée, le diagramme obtenu représente les deux premières composantes de l'analyse, avec la position des groupes, les coordonnées espèces et le lien avec l'analyse NSC non contrainte (cercle de corrélation). Par ailleurs, le positionnement des espèces dans le diagramme permet de préciser leur degré de relation avec les variables écologiques.

RESULTATS ASPECT SYSTEMATIQUE

Les 547 relevés éffectués dans les différents terroirs d'Oranie ont mis en évidence un patrimoine botanique riche de 425 espèces adventices. La totalité des espèces recensées sont des Angiospermes se rattachant à 51 familles botaniques et 217 genres différents dont :

- Bien que l'Oranie fasse partie de la microplaque bético-rifaine sa flore arvicole ne présente pourtant que 2,58 % des taxons ibéromaurétaniens. Les éléments endémiques et subendémiques dans les milieux cultivés ne sont pas négligeables (21 espèces), ce qui porte le taux d'endémisme de notre flore arvicole à près de 5 % (contre 12,6 % pour toute l'Algérie).

SPECTRE BIOLOGIQUE GLOBAL

Le spectre biologique brut global du recouvrement établi au niveau des parcelles cultivées du secteur phytogéographique oranais fait apparaître l'existence de 7 types biologiques (tableau II). Le tableau II montre un nombre très important de thérophytes soit près de 76 % de l'effectif total. Malgré l'importance des thérophytes, les hémicryptophytes gardent une place assez importante (près de 12 %). Les géophytes viennent au troisième rang et contribuent à 7,52 % de la flore.

Tableau II : Spectre biologique brut global établi au niveau des cultures du secteur phytogéographique oranais. Raw biological spectra of the crops of the oranian phytogeographical territory.

Type éthologique

DIAGRAMME D'INFESTATION

Par référence aux catégories de mauvaises herbes définies par Le [START_REF] Bourgeois | Les mauvaises herbes dans la rotation cotonnière du Nord-Cameroun (Afrique). Amplitude d'habitat et degré d'infestation[END_REF], l'analyse de nos 547 relevés a permis de distinguer 6 groupes d'espèces reflétant leur potentiel de nuisibilité donc leur importance agronomique (figure 2). Ces différents groupes (tableau III) sont :

• Groupe 1 : "Mauvaises herbes" majeures générales. Ce sont les espèces les plus nuisibles de la région pouvant coloniser pratiquement tous les milieux écologiques (espèces très fréquentes). Leur grande adaptation à l'environnement agricole leur confère un potentiel d'envahissement des parcelles très important (espèces très abondantes). Dans le cas présent il s'agit de Convolvulus arvensis et Sinapis alba. La première espèce est classée parmi les quinze premières "mauvaises herbes" des cultures printanières et estivales [START_REF] Maillet | Les liserons[END_REF]. La deuxième espèce, Sinapis alba, était autrefois plutôt rudérale et xérophile qu'arvicole.

Groupe 3 Groupe 2 Groupe 1 Groupe 4 Groupe 5 Groupe 6

Tableau III : Importance agronomique des principales espèces adventices d'Oranie.

Agronomic importance of the main weed species of Oranie. • Groupe 4 : "Mauvaises herbes" générales. Elles sont très ubiquistes mais ne posent pas de problème particulier dans le contexte phytotechnique actuel. Ce sont des espèces à surveiller, du fait de leur grande distribution, lors de modifications du contexte par une évolution du système de culture qui pourrait se traduire par un bouleversement dans les relations de compétition inter-spécifiques. C'est le cas par exemple d'Hordeum murinum, espèce xérophile et nitrophile, présente dans tous types de sols et tous types de cultures et qui est actuellement en extension dans les parcelles céréalières à faible densité de semis.

• Groupe 5 : "Mauvaises herbes" régionales. Elles ont une amplitude écologique moyenne mais ne constituent pas une contrainte agronomique du fait de leur abondance limitée. Par contre, elles peuvent servir d'indicatrices de conditions écologiques régionales. Par exemple Avena sterilis, Bromus rigidus, Fumaria parviflora, Malva parviflora, Medicago hispida, Vaccaria pyramidata et Galium tricorne relèvent essentiellement des céréales d'hiver ; Hedypnois cretica et Torilis nodosa sont des espèces relevant principalement des jachères.

• Groupe 6 : "Mauvaises herbes" mineures. Elles sont peu fréquentes et peu abondantes et ne constituent, en aucun cas, une gêne pour la culture. Ce sont des espèces rares, étrangères, pionnières ou résiduelles d'une situation antérieure, assez souvent patrimoniales entrant dans un objectif de maintien de la biodiversité. Elles peuvent être inféodées à des conditions écologiques très peu représentées ce qui leur donne un statut d'espèces indicatrices strictes ou bien elles sont tellement rares que leur présence ne peut apporter aucune information si ce n'est une indication à caractère historique.

LES GROUPES PHYTOECOLOGIQUES AU NIVEAU GLOBAL

Les résultats des analyses non-symétrique des correspondances, sous contrainte environnementale nous indiquent que la principale source de variation floristique au niveau des différents terroirs d'Oranie sont les systèmes de cultures alors que les types présumés du sol ainsi que la présence/absence d'irrigation ne sont pas pertinentes (figure 3). [START_REF] Loudyi | Étude botanique et écologique de la végétation spontanée des terres cultivées du plateau de Meknès (Maroc)[END_REF][START_REF] Boulet | Index synonymique des taxons présents dans les milieux cultivés ou artificialisés du Maroc occidental et central[END_REF]. Les adventices thérophytes prépondérantes (76 %) se manifestent chaque année grâce à la redistribution du stock semencier par le labour. En deuxième importance viennent les hémicryptophytes (12 %). Ce groupe charnière entre les thérophytes et les géophytes, peut passer d'un type à un autre suivant les conditions de leur développement. Le travail du sol est alors le meilleur révélateur de la biologie, car il n'épargne que les géophytes [START_REF] Jauzein | Flore des champs cultivés[END_REF]. [START_REF] Abdelkrim | Contribution à la connaissance des groupements de mauvaises herbes des cultures du secteur algérois : Approche syntaxonomique et phénologique[END_REF] ainsi que ceux du Maroc [START_REF] Gmira | La végétation du Sahel du Safi: étude physionomique, phytoécologique des milieux maraboutiques[END_REF]. En France, [START_REF] Maillet | Constitution et dynamique des communautés de mauvaises herbes des vignes de France et des rizières de Camargue[END_REF] préfère parler d'un "équilibre dynamique pluriannuel" au sein du pool des espèces possibles les plus adaptées et les plus abondantes à l'intérieur de la station ou de la région. On constate également que le cercle de corrélation des vignobles chevauche sur celui des céréales et non pas sur celui des vergers ce qui confirme le fait que la flore adventice des vignobles présente plus de similitude avec celle des céréales (Cs = 64 %) qu'avec celle des vergers (Cs = 57 %). Ceci a, d'ailleurs, suggéré à Montégut (1993) de considérer les vignobles comme des espaces refuges aux messicoles en régression.

CONCLUSION

L'importance de la biodiversité associée aux cultures ("crop-associated agrobiodiversity") du domaine phytogéographique oranais s'explique par la persistance des pratiques agricoles extensives, la polyculture, la pratique du resemis et le faible usage des produits herbicides. La flore adventice des cultures maraîchères pluviales présente une assez grande similitude (64,73 %) avec celle des céréales. Ceci se comprend facilement lorsqu'on sait que ce que l'on désigne par maraîchage pluvial n'est, dans la majorité des cas, que de la jachère cultivée pour la production des légumes secs. Les légumes secs, se trouvant en tête d'assolement avant le blé, reposent le sol et apportent de l'azote entre deux pailles. Ce système de rotation largement pratiqué en Oranie est très conservateur des espèces messicoles traditionnelles. L'introduction de nouvelles cultures dans la rotation pourrait par contre provoquer la régression de ces messicoles à grande valeure patrimoniale. Si le degré de similitude entre les communautés d'adventices des vergers et des vignobles d'une part, et celle des céréales d'autre part est faible, c'est parce qu'ils sont hors-assolement et occupent le sol pendant plusieurs années, contrairement aux cultures soumises à l'assolement.

Figure 1 :

 1 Figure 1 : Situation géographique de la zone d'étude avec délimitation des sous secteurs : O1, Sahels littoraux ; O2, Plaines littorales ; O3, Atlas tellien ; H1, Hauts-Plateaux algérois et oranais. Geographic location of the study area with delimitation of the phytogeographic territories.

•

  Groupe 2 : "Mauvaises herbes" majeures régionales. Ce sont des espèces à amplitude écologique large ou moyenne dont la présence est liée à des facteurs mésologiques d'ordre régional (culture, sol, climat). Leur abondance est régulièrement forte, leur conférant le statut d'espèces fréquemment codominantes des communautés auxquelles elles participent. Elles peuvent parfois aussi être ponctuellement très abondantes, prenant alors le statut de dominantes. Il s'agit d'une part de Rhagadiolus stellatus, Scandix pecten-veneris et Bromus madritensis espèces liées aux cultures annuelles d'hiver (blé d'hiver notamment) et d'autre part de Chenopodium album, Amaranthus angustifolius et Cynodon dactylon pour les cultures maraîchères irriguées d'été et le faciès estival des cultures pérennes.

Figure 2 :

 2 Figure 2 : Diagramme d'infestation des espèces (les espèces sont représentées par leur code OEPP). Species infestation diagram (species are represented by their EPPO code).

Figure 3 :

 3 Figure 3 : Projection des systèmes de culture sur le plan factoriel des axes 1 et 2.Crop systems projection on the factorial axes 1 and 2.

  6 familles, 38 genres et 59 espèces de Monocotylédones ; -45 familles, 179 genres et 366 espèces de Dicotylédones. Trois familles dominent nettement la flore adventice oranaise : Asteraceae, Fabaceae et Poaceae. Elles capitalisent à elles seules 166 espèces soit 39 % de l'effectif global. Ces familles occupent d'ailleurs les trois premiers rangs si on considère la flore algérienne dans son ensemble. À côté d'elles, Brassicaceae, Caryophyllaceae, Apiaceae et Boraginaceae sont également bien représentées conservant sensiblement le même ordre de classement que celui qu'elles ont dans la flore algérienne. Ces sept familles englobent à elles seules 60 % des espèces, les 40 % restants étant répartis entre 44 familles différentes. , méditerranéens/ouest asiatiques, méditérranéens/iranotouraniens, etc.) allouent 57,64 % des espèces arvicoles. Les éléments Westméditerranéens sont représentés par 20 espèces soit 4,70 % des effectifs totaux. Le caractère méditerranéen de la flore arvicole oranaise est nuancé par des influences européennes. Les espèces plus nordiques, Eurasiatiques (8,47 %) et Euroméditerranéennes (7,05 %) notamment, forment un assez important groupe floristique avec 15,52 %. Les espèces à large répartition tempérée (Paléotempérées, Cosmopolites, Subcosmopolites, Paléotropicales sensu lato, Circumboréales) représentent 15,75 % en Oranie.

	REPARTITION BIOGEOGRAPHIQUE
	Sur le plan phytogéographique, la flore adventice de l'Oranie se caractérise par un ensemble
	hétérogène d'éléments d'origines très diverses.
	Les	espèces	méditerranéennes	sensu	lato	(incluant	les	birégionales
	méditerranéens/macaronésiens

•

  Groupe 3 : "Mauvaises herbes" majeures locales. Elles ont une amplitude écologique très étroite. Elles ne se rencontrent que dans certaines conditions de milieu peu représentées et pour lesquelles elles constituent des indicatrices écologiques. Dans ces conditions de milieu, elles sont très abondantes et constituent une contrainte agronomique importante. C'est le cas par exemple de Cyperus rotundus, Oxalis cernua ou Portulaca oleracea. Toutes ces espèces à développement estival exubérant, sont hygrophiles, affectionnant les sols sableux, riches en éléments nutritifs et se rencontrant donc principalement au niveau des grandes cultures d'été et des agrumeraies soumises à une irrigation soutenue (irrigation à la raie ou par cuvette notamment). Rumex bucephalophorus est reconnu comme étant une espèce silicicole, calcifuge montrant une nette prédilection pour les sols acides.

  Les deux espèces agronomiquement les plus nuisibles se sont révèlées être Convolvulus arvensis qui est une géophyte à forte capacité d'infestation et de propagation et qui n'est pas détruite par les herbicides classiquement utilisés. La seconde est Sinapis alba qui est devenue plus infestante à cause, probablement, de la sécheresse prolongée de ces trente dernières années. Le système de cultures apparaît comme la variable de milieu la plus susceptible de discriminer au mieux les différents milieux étudiés en Oranie. Ce type de répartition a également été observée par[START_REF] Loudyi | Étude botanique et écologique de la végétation spontanée des terres cultivées du plateau de Meknès (Maroc)[END_REF] au niveau des cultures du Maroc septentrional. Au centre du diagramme se projettent les jachères, à cheval entre les cultures annuelles et les cultures pérennes. L'essentiel du groupement d'espèces définissant les jachères persiste dans les cultures se succédant dans l'assolement pendant plusieurs années. La mise en culture n'entame donc pas la nature essentielle du groupe écologique mais détermine simplement le remplacement de certaines espèces par d'autres qui sont l'expression de la phytotechnie. Ce même phénomène a été constaté au niveau des agrophytocénoses du secteur phytogéographique algérois