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

Ferdinand Sibleyras
email: ferdinand.sibleyras@inria.fr

Low-Memory Attacks against Two-Round Even-Mansour using the 3-XOR Problem

Keywords: Even-Mansour, Cryptanalysis, 3-XOR

The iterated Even-Mansour construction is an elegant construction that idealizes block cipher designs such as the AES. In this work we focus on the simplest variant, the 2-round Even-Mansour construction with a single key. This is the most minimal construction that offers security beyond the birthday bound: there is a security proof up to 2 2n/3 evaluations of the underlying permutations and encryption, and the best known attacks have a complexity of roughly 2 n /n operations. We show that attacking this scheme with block size n is related to the 3-XOR problem with element size = 2n, an important algorithmic problem that has been studied since the nineties. In particular the 3-XOR problem is known to require at least 2 /3 queries, and the best known algorithms require around 2 /2 / operations: this roughly matches the known bounds for the 2-round Even-Mansour scheme. Using this link we describe new attacks against the 2-round Even-Mansour scheme. In particular, we obtain the first algorithms where both the data and the memory complexity are significantly lower than 2 n . From a practical standpoint, previous works with a data and/or memory complexity close to 2 n are unlikely to be more efficient than a simple brute-force search over the key. Our best algorithm requires just λn known plaintext/ciphertext pairs, for some constant 0 < λ < 1, 2 n /λn time, and 2 λn memory. For instance, with n = 64 and λ = 1/2, the memory requirement is practical, and we gain a factor 32 over brute-force search. We also describe an algorithm with asymptotic complexity O(2 n ln 2 n/n 2 ), improving the previous asymptotic complexity of O(2 n /n), using a variant of the 3-SUM algorithm of Baran, Demaine, and Pǎtraşcu.

Introduction

The Even-Mansour construction [START_REF] Even | A construction of a cipher from a single pseudorandom permutation[END_REF] is a very simple and elegant way to design a block cipher E from a public permutation P , defined as E k (x) = P (x ⊕ k 1 ) ⊕ k 2 .

In the random permutation model, this construction has been proven secure as long as D • Q ≤ 2 n , with n the block size, D the data complexity (online queries to the encryption function) and Q the number of evaluation of the permutation (offline queries). In particular, the time T needed by an attacker is lower bounded by Q, therefore attacks must satisfy D • T ≥ 2 n . We also have a number of attacks matching this bound, such as [START_REF] Daemen | Limitations of the Even-Mansour construction (rump session)[END_REF] with chosen plaintext or [START_REF] Dunkelman | Slidex attacks on the Even-Mansour encryption scheme[END_REF] using just known plaintext: when balancing online and offline queries, these attacks require only 2 n/2 queries and 2 n/2 computations (including all the computations required by the attack, in addition to permutation queries). A single-key version of the Even-Mansour construction has also been proposed with the same security [START_REF] Dunkelman | Minimalism in cryptography: The Even-Mansour scheme revisited[END_REF], defined as E k (x) = P (x ⊕ k) ⊕ k.

More recently, this construction was generalized to the iterated Even-Mansour scheme, also called key-alternating cipher [START_REF] Bogdanov | Key-alternating ciphers in a provable setting: Encryption using a small number of public permutations -(extended abstract)[END_REF]. The r-round construction uses r independent permutations and r +1 keys, and can be considered as an idealization of concrete SPN ciphers:

E k (x) = P r • • • P 2 P 1 (x ⊕ k 0 ) ⊕ k 1 • • • ⊕ k r
This construction was first proven to be secure up to 2 2n/3 queries for r ≥ 2 [START_REF] Bogdanov | Key-alternating ciphers in a provable setting: Encryption using a small number of public permutations -(extended abstract)[END_REF], and later improved to 2 nr/(r+1) queries [START_REF] Lampe | An asymptotically tight security analysis of the iterated Even-Mansour cipher[END_REF][START_REF] Chen | Tight security bounds for key-alternating ciphers[END_REF].

As in the single-round case, the requirement to have independent keys and independent permutations can be relaxed without reducing the security. In particular, two single-key variants of the 2-round Even-Mansour have been proposed [START_REF] Chen | Minimizing the tworound Even-Mansour cipher[END_REF]:

EMIP : E k (x) = P 2 P 1 (x ⊕ k) ⊕ k ⊕ k EMSP : E k (x) = P P (x ⊕ k) ⊕ π(k) ⊕ k, with π a linear orthomorphism.
The EMIP construction uses two independent permutations, while the EMSP construction uses a single permutation, and a fixed linear orthomorphism (a linear operation such that both x → π(x) and x → x ⊕ π(x) are invertible, such as multiplication by a constant in a field).

There are simple key-recovery attacks matching the 2 nr/(r+1) bound on the number of queries given in [START_REF] Bogdanov | Key-alternating ciphers in a provable setting: Encryption using a small number of public permutations -(extended abstract)[END_REF], but even with r = 2 the best known attacks require about 2 n /n operations (in addition to the queries). Attacks against the 3-round Even-Mansour construction have also been given in [START_REF] Dinur | Key recovery attacks on 3-round Even-Mansour, 8-step LED-128, and full AES2[END_REF], with complexity close to 2 n /n, and no attack better than 2 n is known for r > 3.

In this paper we focus on the most simple instances, the 2-round variants of EMIP and EMSP, collectively denoted as 2EM, and we look for better attacks than what is currently known, with a focus on low memory and low data. Previous works. The first non-trivial attack against an iterated Even-Mansour construction was described by Nikolic, Wang, and Wu in [START_REF] Nikolic | Cryptanalysis of round-reduced LED[END_REF] against the tworound EMIP construction P 2 P 1 (x ⊕ k) ⊕ k ⊕ k, using multi-collisions. The main idea is to consider the function φ : u → P 1 (u) ⊕ u, and to evaluate it on a large number of points, so as to identify a particular value v that occurs more frequently than others (at least t times). Then, for each known plaintext pair x, E(x) , the attacker assumes that φ(x ⊕ k) = v, i.e. P 1 (x ⊕ k) ⊕ k = x ⊕ v; this gives a key candidate P 2 (x ⊕ v) ⊕ E(x). Since the assumption holds for at least t values of x, the expected complexity is 2 n /t.

According to the asymptotic analysis performed in [START_REF] Nikolic | Refinements of the k-tree algorithm for the generalized birthday problem[END_REF], the optimal choice is to set t = Θ(n/ ln n). A value with this number of repetitions is expected after evaluating φ roughly 2 n /n times, so that the total complexity of this attack is 2 n ln n/n, asymptotically smaller than 2 n . This attack was later improved by Dinur, Dunkelman, Keller and Shamir [START_REF] Dinur | Key recovery attacks on 3-round Even-Mansour, 8-step LED-128, and full AES2[END_REF]. In particular, they describe a variant with lower online complexity using N v different values v i that appear t times each, with a smaller value of t. Each online pair

x, E(x) is then used to make a key guess with every v i , which reduces the data complexity to 2 n /N v t. They didn't evaluate this strategy asymptotically, but they computed that N v = 2 n µ t e -t /t! multi-collisions should be found, when evaluating a fraction µ of the domain. In particular, with µ = 1/n and t = o(n/ ln n), we have an upper bound on the data complexity: 2 n /N v ≤ n 2t = exp(2t ln n), which is asymptotically smaller than 2 λn for any λ > 0. The time complexity is still 2 n /t. Variants of the attack that can applied to Even-Mansour schemes with a linear key-schedule, such as EMSP are also given in [START_REF] Dinur | Key recovery attacks on iterated Even-Mansour encryption schemes[END_REF].

Dinur et al. also proposed attacks against a more general construction with 3 independent keys, using multi-collisions to find differential properties of the random permutation. However this attack only reaches time complexity O(2 n / n/ ln n).

All those attacks require a large pre-processing step to discover multi-collisions: a t-collision is only expected after 2 n(t-1)/t evaluations of φ. Moreover, the best known algorithm to locate multi-collisions requires a memory of size 2 n(t-2)/t [START_REF] Joux | Improved generic algorithms for 3-collisions[END_REF]. Therefore, multi-collision based techniques intrinsically require time and memory close to 2 n (asymptotically, we need to have t approaching infinity in order to gain a non-constant advantage over brute-force attacks).

In the journal version of their paper, Dinur et al. show an interesting sideresult on EMIP. They describe an alternative attack with low memory using linear algebra [START_REF] Dinur | Key recovery attacks on iterated Even-Mansour encryption schemes[END_REF]Section 4.2]. In this attack, they evaluate φ : u → P 1 (u) ⊕ u on a small set of λn values (0 < λ < 1/3), and they look for linear relations that are satisfied by all φ(u) in the set: L(φ(u)) = 0 with n -λn equations. Then, for a given plaintext pair x, E(x) , if x ⊕ k is in the set, this implies linear relations on z = k ⊕ P 1 (x ⊕ k), the input of P 2 : L(z) = L(x). Finally, using structures for x and z, a match can be identified using linear relations on the key (following from the assumption that x ⊕ k is in the set), using k = P 2 (z) ⊕ E(x). The full details of the attack are given in [START_REF] Dinur | Key recovery attacks on iterated Even-Mansour encryption schemes[END_REF]. This attack only requires a memory of size 2 λn to store the structures, but it requires 2 n /λn chosen plaintext pairs. However, this approach is not applicable to 3EM or 2EM with independent keys, which are the main focus of their work.

More recently, Isobe and Shibutani [START_REF] Isobe | New key recovery attacks on minimal two-round Even-Mansour ciphers[END_REF] introduced Meet-in-the-Middle techniques to attack the 2-round Even-Mansour construction. The basic variant of their attack uses a function f depending on a bits of the key k f (with a in the order of ln n), and a function g depending on the remaining n -a bits k g . Furthermore, they use a starting point such that a output bits of f are actually independent of the key k f . This allows them to do the matching over P 2 using just k g . The attack requires time and data 2 n-a , with chosen plaintexts.

The function f is such that it is equivalent to looking for partial multicollisions in φ while imposing a structure on the inputs: they fix n -a bits of u and hope that a outputs bits of φ(u) will be independent of the remaining a bits of u. For this to work the parameter a must satisfy a • (2 a -1) ≤ n -a, and Isobe and Shibutani only give concrete parameters for some values of n. Asymptotically, the maximal value of a can be found by solving a • (2 a -1) = n -a; since a ≪ n and 1 ≪ 2 a , we have a ≈ W (n ln 2)/ ln 2 ≈ log n -log log n, using the Lambert W function.

They also describe a low-data complexity variant of the attack, where the starting point is dynamically chosen so that a + d bits of the plaintext are fixed. This reduces the data complexity to 2 n-d-a , while the time complexity is still 2 n-a . The parameters are more constrained and must satisfy a

• 2 a + d ≤ n -a.
If we want to achieve a data complexity of 2 λn for a constant 0 < λ < 1, we can set d = n -λn, and a = log λ + log n -log log n. This gives a time complexity of 2 n log n/λn. Finally, they give a time-optimized attack where b = a + c output bits of f are independent of k f (instead of just a). This reduces the number of queries and memory needed for the matching to 2 n-b , but the attack still requires 2 n-a memory accesses and chosen plaintext. The parameters must satisfy b • 2 a + b -a ≤ n -b, but the authors only give concrete values for some choices of n, and no asymptotic analysis. However, we can observe that we must have b • 2 a ≤ n; in particular, if we want an attack with an advantage that is not asymptotically bounded, we need to have a approaching infinity and therefore b/n approaching zero (this attack cannot reduce the memory to 2 λn with λ < 1). In particular, the optimal parameters satisfy b

• 2 a + b -a = n -b, with b ≪ n and a ≪ 2 a , hence b • 2 a ≈ n.
Therefore we have a complexity of roughly 2 n-b in queries and memory, and b2 n /n in time and data, with log n ≤ b ≪ n.

All those attacks are summarized in Tables 1 and2. We point out that the complexity reported in [START_REF] Isobe | New key recovery attacks on minimal two-round Even-Mansour ciphers[END_REF] is lower than listed here, because the authors assume that a memory access to a large table is significantly cheaper than the evaluation of the public permutations P i . Given that a public permutation can obviously be implemented with a table lookup if memory is fast and cheap, we assume that a memory access to a table of size roughly 2 n cannot be faster than the evaluation of the P i permutations. Our results. The main results of the paper are the three key-recovery attacks on EMIP given in Section 4 whose complexities are summarized in Tables 1 and2.

To the best of our knowledge these are the first attacks on EMIP to significantly reduce simultaneously the data and the memory complexities below 2 n . The first attack, Section 4.1, shows that we can achieve the best computational time complexity known so far, that is O(2 n /n), while using just as much data and queries as the best known distinguisher which is optimal in the balanced case (2 2n/3 calls to E, P 1 and P 2 ) with a memory usage not exceeding the number of queries. The next attack in Section 4.3 works exactly the same way only it is using another generic 3-XOR algorithm which improves the asymptotic time complexity to O(2 n ln 2 n/n 2 ) that beats the best one known so far. However this 3-XOR algorithm is believed to be impractical for realistic block sizes, notably for n = 64. And the third attack in Section 4.4 uses very low data, λn, and possibly low memory, 2 λn , for some λ < 1 while keeping a competitive asymptotic time complexity of O(2 n /λn).

We also present some security reduction notably showing that adding a linear key schedule does not protect against generic attacks on EMIP. This effectively extends the scope of our attacks in particular showing they can also be applied to the EMSP variant. We also explain the link between the 3-XOR problem and the key-recovery attacks on EMIP showing how one can help us solve the other which justifies our approach. Then we exhibit a symmetry in the Even-Mansour construction that shows how, in the chosen ciphertext attack (CPA) model, an attacker can always swap the number of queries he is making to E, P 1 and P 2 to optimize on the most available resources. This implicitly extends these and previous attacks to adapt to many different data and query complexity profiles. Lastly we generalize our approach to show that a single key r rounds Even-Mansour scheme can be rewritten as a structured (r + 1)-XOR problem with words of size rn. Interestingly both the single key r rounds Even-Mansour and the (r + 1)-XOR problem with words of size rn have a simple information theoretic solver using 2 r•n r+1 queries though solving these uses more computations than a brute-force solution for r ≥ 4.

Practical considerations.

In a practical setting, the data complexity and the memory complexity are important considerations. In particular, an attack with complexity 2 n /n is unlikely to be more efficient than a brute-force attack if it requires almost 2 n data, or almost 2 n memory. As mentioned above, some of the previous attacks can reduce the data complexity to 2 λn for an arbitrary λ > 0, and the attack from [9, Section 4.2] can reduce the memory to 2 λn , but so far none of them can simultaneously reduce the data and memory complexity below 2 λn for λ < 1.

Besides, multi-collision based attacks can use a sequential memory (such as a hard drive) and sort values to locate collisions while the Meet-in-the-Middle attacks require random access memory, with Θ(2 n ln n/n) accesses to a table of size Θ(2 n ln n/n).

On the other hand the linear algebra techniques we use in our attacks will require algorithmic tricks very close to what was done by Bouillaguet, Delaplace and Fouque [START_REF] Bouillaguet | Revisiting and improving algorithms for the 3xor problem[END_REF] for the 3-XOR problem. In particular the values we deal with are sufficiently random to be sorted linearly and the right matrix multiplication in GF(2) LM for an exponentially large matrix L can be computed with a number of operations linear in the size of L. Many constant time optimizations are therefore omitted in this work which justify that right multiplications, sorting and merging two big lists L 1 and L 2 take time and space O(|L 1 | + |L 2 |). This is consistent with previous cryptanalysis on EMIP.

For the cost of queries to the oracles E, P 1 and P 2 we mainly follow the convention established by Dinur et al. [START_REF] Dinur | Key recovery attacks on iterated Even-Mansour encryption schemes[END_REF] which states that an online query to E costs 1 unit of computation implying that P 1 and P 2 cost 1/2. The main advantage is that it makes it easy to compare with the brute-force solution that would use 2 n computations. The disadvantage is that it makes it hard to combine with the computations used for simple operations: an evaluation of a cryptographically secure permutation should cost more than a XOR operation.

We give concrete complexity values for n = 64 in Table 2 with the assumption that a combination of some linear time operations does not exceed the cost of computing a permutation that is 1/2 time unit. Concretely, iteratively right multiplying, sorting and merging two lists

L 1 , L 2 costs |L 1 |/2+|L 2 |/2.
We believe this makes an honest comparison with previous works though they may use other assumptions.

Organization of the paper. First, in Section 2, we show some reductions that extend our results and justify our approach. Then in Section 3 we take a close look on previous works done on the 3-XOR Problem to show how it can help the cryptanalysis of EMIP. Lastly, in Section 4, we devise three dedicated algorithms for EMIP each having their own particular complexity trade-off. Also we extend our approach in Appendix 5 to the r rounds iterated Even-Mansour construction.

Notations. We denote the block size of the Even-Mansour scheme (i.e. the width of the public permutations) as n, and the concatenation of n-bit blocks x and y as x y. When x and y fit together in one block, we use x|y to denote their concatenation. We use L[i] to denote element i of list L, x [i] to denote bit i of x, x [i:j] to denote bits i to j -1, 0 to denote a zero GF(2) matrix and I to denote an identity GF(2) matrix. When L is a list of n-bit values, we identify it with a × n matrix where the elements of L are the rows of the matrix. Finally, we use a curly brace for systems of equations.

Security Reductions

We start with some general observations about the security of iterated Even-Mansour schemes. In particular, we show that we can focus on the EMIP construction without loss of generality, how to reduce the security of this construction to an instance of the 3-XOR problem, and how to reorder the oracles to achieve many different trade-offs. Some previous works already implicitly took advantage of such reductions. For example Isobe and Shibutani [START_REF] Isobe | New key recovery attacks on minimal two-round Even-Mansour ciphers[END_REF] realised that their recent attack on EMIP is also applicable to EMSP and Dinur et al. [START_REF] Dinur | Key recovery attacks on iterated Even-Mansour encryption schemes[END_REF] realised that they could reorder the oracles for their cryptanalysis of reduced round LED. We formally show here that these tricks are in fact real security reductions and do not depend on the approach used.

Removing the Key Schedule

There are several variants of single-key multiple-round Even-Mansour studied in the literature. The most general form uses two independent permutations, and an arbitrary key schedule (see Figure 2):

E k (x) = P 2 P 1 (x ⊕ γ 0 (k)) ⊕ γ 1 (k) ⊕ γ 2 (k).
According to the analysis of [START_REF] Chen | Minimizing the tworound Even-Mansour cipher[END_REF], there is a class of good key schedules where the γ i 's are public linear bijective functions. In the following, we focus on this class of key schedules, i.e. we assume that the γ i ∈ GL(F n 2 ). In order to simplify the analysis, we reduce the security of this construction to the security of the EMIP variant without a key schedule.

x P1 P2 E(x) γ0(k) γ1(k) γ2(k) Fig. 2.
Linear key-schedule 2-round Even-Mansour.

The main trick is to rewrite the addition of the subkey γ i (k) as the application of the inverse γ -1 i , the addition of k and the application of the forward γ i :

x ⊕ γ i (k) = γ i γ -1 i (x ⊕ γ i (k)) = γ i γ -1 i (x) ⊕ k
which works thanks to γ i being linear. Then we define E , P 1 , P 2 as follows:

P 1 (x) = γ -1 1 P 1 (γ 0 (x)) P 2 (x) = γ -1 2 P 2 (γ 1 (x)) E (x) = γ -1 2 E(γ 0 (x))
Thanks to the previous relation, E , P 1 , P 2 is actually an instance of EMIP with the same key k (see Figure 3):

E (x) = P 2 P 1 (x ⊕ k) ⊕ k ⊕ k.
Therefore, any attack against EMIP can be used on E , P 1 , P 2 , and break the initial construction with a key schedule. In particular, a key-recovery attack against EMIP will recover the key of the more general scheme of 2EM.

In the following we only consider the EMIP variant without a key schedule, but thanks to this reduction our attacks can be applied to many other 2EM variants, including the EMSP construction of [START_REF] Chen | Minimizing the tworound Even-Mansour cipher[END_REF].

Definition 1 (EMIP key recovery).

Given oracle access to three permutations E, P 1 , P 2 and their inverses, with the promise that there exist k such that

E(x) = P 2 P 1 (x ⊕ k) ⊕ k ⊕ k, recover k. x γ -1 0 γ0 P1 γ -1 1 γ1 P2 γ -1 2 γ2 E(x) k k k P 1 P 2 γ -1 0 (x) γ -1 2 E(x) = E γ -1 0 (x) k k k Fig. 3.
Reduction of linear key schedule 2EM to EMIP.

Reduction to 3-XOR

Instead of directly focusing on a key-recovery attack, we focus on locating a triplet of values x, y, z such that the encryption of x is evaluated with permutation call P 1 (y) and P 2 (z). Formally, we say that x, y, z is a right triplet when y = x⊕k and z = P 1 (y) ⊕ k. A right triplet corresponds to a sequence of intermediate values in the Even-Mansour encryption, as shown in Figure 4:

x, y = x ⊕ k, P 1 (y), z = P 1 (y) ⊕ k, P 2 (z), E(x) = P 2 (z) ⊕ k ;
we call this sequence a path. Since the permutations P 1 and P 2 are public, it is easy to compute a path given the key. Recovering the key from a path is also easy (we have k = x ⊕ y), but it is hard to identify a right triplet corresponding to a path without the key. By definition a triplet is right when it follows the relation R defined as:

R(x, y, z) :=      x ⊕ y = k P 1 (y) ⊕ z = k P 2 (z) ⊕ E(x) = k (1) ⇒ x ⊕ y = P 1 (y) ⊕ z x ⊕ y = P 2 (z) ⊕ E(x) (2)
Notice that we can't directly observe (1) since we don't know k but we can easily verify the implied relation [START_REF] Bernstein | Better price-performance ratios for generalized birthday attacks[END_REF].

We claim that if one takes a random triplet combination and observes that it respects (2), then it is a right triplet with good probability. Indeed there are 2 n possible paths (one for every possible input x) implying as many right triplets and 2 3n possible triplet combinations; thus a random triplet will be right with probability 2 -2n . Since ( 2) is a 2n-bit relation, a random but false triplet respects (2) also with probability 2 -2n . Therefore we can expect roughly as many right triplets than false triplets that respect [START_REF] Bernstein | Better price-performance ratios for generalized birthday attacks[END_REF], thus the first one we find is right with probability Ω(1). So from now on and for simplicity we will focus on filtering and recovering a triplet that simply respects [START_REF] Bernstein | Better price-performance ratios for generalized birthday attacks[END_REF]. This means that our algorithms fails to recover the key on some instances, but they have a constant (non-zero) probability of success. In order to improve the success probability arbitrarily close to one, it is easy to test the triplets, and continue the attack until we find a right triplet (alternatively, the whole attack can just be repeated).

In order to simplify the analysis, the condition (2) can be rewritten as:

x ⊕ y ⊕ P 1 (y) ⊕ z = 0 x ⊕ E(x) ⊕ y ⊕ P 2 (z) = 0
Therefore, finding a triplet satisfying ( 2) is equivalent to solving an instance of the 3-XOR problem, defined as:

f 0 (x) := x x ⊕ E(x) (3) f 1 (y) := y ⊕ P 1 (y) y f 2 (z) := z P 2 (z)
The 3-XOR Problem is a well known algorithmic problem; it is a special case of k-XOR problem analyzed by Wagner as the generalized birhtday problem [START_REF] Wagner | A generalized birthday problem[END_REF].

Definition 2 (3-XOR problem). Given three functions f

0 , f 1 , f 2 , find three inputs (x 0 , x 1 , x 2 ) such that f 0 (x 0 ) ⊕ f 1 (x 1 ) ⊕ f 2 (x 2 ) = 0.
We usually focus on functions f 0 , f 1 , f 2 that are chosen at random. Equivalently, we can be given lists L 0 , L 1 , L 2 (of random elements) instead of functions. The presentation with functions makes it more clear that the adversary can choose how many queries he makes to each of the functions.

EMIP Key Recovery from the 3-XOR Problem. From the previous discussion, solving the 3-XOR instance defined by (3) gives a triplet satisfying R, which has a high probability of being a right triplet and revealing the key. Evaluating each of the f i functions requires a single computation of a permutation. However evaluating f 0 must be done online (using an oracle call to E) because it depends on the key, while evaluating f 1 and f 2 can be done offline as the permutations are public and computable at will by the attacker. As per our adopted convention, an evaluation of f 0 -that is a call to E -costs 1 unit of computation and an evaluation of f 1 or f 2 costs 1/2.

We denote the list of values of f i evaluated by an attacker as L i . Therefore, the data complexity of an attack is equal to D = |L 0 |. The time complexity is the amount of computation required to break the scheme. In the computational model, it will depend on the algorithm used and be denoted as T . In the information theoretic model we only look at the number of calls to the permutations and denote it Q, with Q = (|L 1 | + |L 2 |)/2. We will discuss both models.

As seen from the description in (3), we can choose some parts of the values in L i . However, if we only use random values of x, y, z to build the lists, we obtain a random 3-XOR instance with words of size w = 2n. It is known that to find a solution of a 3-XOR problem with good probability, the lists size should respect

|L 0 | × |L 1 | × |L 2 | ≥ 2 w .
In the information theoretic setting this gives a key recovery attack with D × Q 2 = 2 2n . This is the exact same complexity trade-off as the information theoretic distinguisher described by Gaži [START_REF] Gaži | Plain versus randomized cascading-based key-length extension for block ciphers[END_REF]. In particular it is known that this trade-off is proven optimal in the balanced case

D = Q = 2 2n/3 [5].

Symmetry between E, P 1 and P 2

In the 3-XOR problem the 3 functions behave essentially in the same way; if one has a solver using a few evaluations f 0 and lots of evaluations of f 1 and f 2 , then the same solver could decide to use lots of queries to f 0 and f 1 and use fewer f 2 queries (just by permuting the functions). In our case, a natural choice is to minimize the number of evaluations of f 0 , because they correspond to online queries. This ensures that we have D ≤ Q. While this is easy to do with a 3-XOR approach, it is not obvious whether this can be done in general for an Iterated Even-Mansour key recovery. We now show that in the chosen ciphertext setting an attacker can actually permute the functions E, P 1 and P 2 , and minimize the amount of online queries.

We assume that we are given an instance E, P 1 , P 2 of EMIP, i.e. we have oracle access to E, P 1 , P 2 denoting forward computations of the permutations, and E -1 , P -1 1 , P -1 2 denoting backward computations. We use a black-box solver S(E, E -1 , P 1 , P -1 1 , P 2 , P -1 2 ) that uses α calls to E/E -1 (online queries), β calls to P 1 /P -1 1 and γ calls to P 2 /P -1 2 and outputs the key k. The trick is that we can rewrite the EMIP instance E, P 1 , P 2 , by permuting the oracles. For instance we have

P 1 (x) = k ⊕ P -1 2 (k ⊕ E(k ⊕ x))
(directly from the definition of E), which gives the following EMIP instance with the same secret key k:

E = P 1 P 1 = E P 2 = P -1 2 .
Therefore, we can use the solver as S(P 1 , P -1 1 , E, E -1 , P -1 2 , P 2 ) to recover k using β online queries. Similarly, we can write

P 2 (x) = k ⊕ E(k ⊕ P -1 1 (k ⊕ x))
; therefore, we can use the solver as S(P 2 , P -1 2 , P -1 1 , P 1 , E, E -1 ) to recover k using γ online queries.

We could further use E -1 to rewrite P -1

1
and P -1 2 in the same fashion and obtain all the possible trade-off between α, β and γ. The point is that, given any solver S, it is always up to the attacker to choose what is the most accessible data.

From here onward all of our discussed trade-off will have

|L 0 | ≤ min(|L 1 |, |L 2 |)
to lower the query complexity but one can remember it is an arbitrary choice.

In particular, this trick can be applied to the attack of [9, Section 4.2]. Indeed, this attack uses λn queries to P 1 , with 0 < λ < 1/3 and 2 n /λn queries to E and P 2 . Using this trick we can reduce the data complexity from 2 n /λn to λn, without affecting the other parameters. Actually, the attack presented in Section 4.4 can be seen as an improved variant of this modified attack (using known plaintext rather than chosen plaintext).

2EM Attacks from 3-XOR Algorithms

In this section we explore the link between 2EM key recovery and the 3-XOR problem. First, we review existing approaches to solve the 3-XOR problem, and we show that previous 2EM attacks can be reinterpreted in a 3-XOR framework. Then we describe new attacks against 2EM based on the reduction of the previous Section. In this section, we focus on a generic 3-XOR instance given by three w-bit function f 0 , f 1 and f 2 , or three lists L 0 , L 1 , L 2 .

3-XOR Algorithms

The Birthday Problem, that is the problem of finding collisions among two lists, has been well studied and proven useful in a number of cryptanalysis. In 2002, Wagner proposed a natural extension of this problem, the Generalized Birthday Problem [START_REF] Wagner | A generalized birthday problem[END_REF], that is the problem of finding collisions among k lists. Here we refer to this problem as the k-XOR problem. In particular Wagner left the hard case of k = 3 as an open problem. His best algorithm would just take one value of the first function and solve the classical Birthday Problem among the two others, with complexity 2 w/2 . Subsequent works tried to address this open problem. Two main approaches managed to improve the time complexity of the 3-XOR: an approach based on partial multi-collisions by Nikolic and Sasaki [START_REF] Nikolic | Refinements of the k-tree algorithm for the generalized birthday problem[END_REF] and an approach using linear algebra by Joux [START_REF] Joux | Algorithmic Cryptanalysis[END_REF]. Unfortunately, those two solutions seem hard to combine.

Multi-collisions Algorithms. Nikolic and Sasaki [START_REF] Nikolic | Refinements of the k-tree algorithm for the generalized birthday problem[END_REF] introduced a multicollision algorithm for the 3-XOR problem as follows. First, compute many outputs of f 0 and look for the most frequent w/2-bit prefix α appearing. Store all the values with this fixed prefix in a list L 0 (a partial multi-collision for f 0 ). Then evaluate f 1 and f 2 , 2 w/2 / |L 0 | times each, and store the results in lists L 1 and L 2 . Sort the lists, and look for pairs with a difference α in the first w/2 bits. An average, there should be 2 w/2 /|L 0 | such pairs, and there is a high probability that one of them sums to a value in L 0 . According to their analysis, the optimal attack uses around 2 w/2 /w evaluations of f 0 , resulting in a multi-collision of size Θ(w/ ln(w)); therefore this algorithm solves the 3-XOR problem with complexity O 2 w/2 / w/ ln(w) .

Linear algebra. The second approach, introduced by Joux [START_REF] Joux | Algorithmic Cryptanalysis[END_REF], uses linear algebra and reaches a slightly better complexity of O(2 w/2 / √ w). This attack uses just w/2 evaluations of f 0 stored in a list L 0 , and 2 w/2 / w/2 evaluations of f 1 (resp. f 2 ) stored in a list L 1 (resp. L 2 ). Instead of collecting values in L 0 with a common prefix, we use Gaussian reduction to find a non-singular matrix M such that the elements of L 0 • M start with w/2 zeroes. 1 Then we focus on a modified 3-XOR instance:

L 0 = L 0 • M L 1 = L 1 • M L 2 = L 2 • M.
The new instance has the same solutions

(L 0 [h] ⊕ L 1 [i] ⊕ L 2 [j] = 0 ⇔ L 0 [h] ⊕ L 1 [i] ⊕ L 2 [j] = 0
), but the elements of L 0 start with w/2 zeroes. Therefore, as in the previous attack, we can efficiently find the solution after sorting the lists L 1 and L 2 . This approach was later generalized by Bouillaguet, Delaplace and Fouque [START_REF] Bouillaguet | Revisiting and improving algorithms for the 3xor problem[END_REF], in order to deal with instances of the 3-XOR problem where the size of the lists is limited: given three lists with

|L 0 | • |L 1 | • |L 2 | = 2 w , they solve the 3-XOR problem with complexity O(|L 0 | • (|L 1 | + |L 2 |)/w).
In particular, with three lists of size 2 w/3 this gives a time complexity of O(2 2w/3 /w).

In addition, this algorithm can be combined with the clamping trick of Bernstein to reduce the memory: the attacker first filters the lists L i to keep only values that start with w/4 zero bits, and solves a shorter 3-XOR instance on 3w/4 bits. If the initial lists have 2 w/2 elements, the filtered lists still have 2 w/4 elements, which is sufficient to expect a solution. This gives an algorithm with time O(2 w/2 ) and memory only O(2 w/3 ). Arguably, this is more practical that algorithms using O(2 w/2 /w) memory.

BDP Algorithm.

Even before these two approaches, Baran, Demaine and Pǎtraşcu [START_REF] Baran | Subquadratic algorithms for 3sum[END_REF] proposed an algorithm for the 3-SUM problem (using modular additions instead of XORs) with the asymptotical complexity of O(2 w/2 • ln 2 (w)/w 2 ). This algorithm has been adapted to the 3-XOR problem by Bouillaguet et al. [START_REF] Bouillaguet | Revisiting and improving algorithms for the 3xor problem[END_REF] with the same complexity. This is best known asymptotic complexity for the 3-XOR problem, even though the algorithm is highly impracticable for realistic values of w. We nevertheless use this algorithm to cryptanalyse 2EM in Section 4.3.

Revisiting Previous Cryptanalysis

Interestingly all attacks so far on 2EM use the same techniques as developed against the 3-XOR problem. Most of the attack are based on multicollisions [START_REF] Nikolic | Cryptanalysis of round-reduced LED[END_REF][START_REF] Dinur | Key recovery attacks on 3-round Even-Mansour, 8-step LED-128, and full AES2[END_REF][START_REF] Dinur | Key recovery attacks on iterated Even-Mansour encryption schemes[END_REF], and the MitM attack by Isobe and Shibutani [START_REF] Isobe | New key recovery attacks on minimal two-round Even-Mansour ciphers[END_REF] can also be interpreted as looking for a structured partial multi-collision, as seen in Section 1. On the other hand, the attack from [9, Section 4.2] uses linear algebra.

Using the Reduction to 3-XOR. As explained in Section 2.2, we can use an attack against 3-XOR to build a key-recovery against 2EM in a generic way. In particular, this reduction gives attacks similar to the known attacks on 2EM if we start from multi-collision algorithms to solve 3-XOR. More precisely, the reduction leads to a 3-XOR instance with w = 2n, defined as:

f 0 (x) := x x ⊕ E(x) (3) f 1 (y) := y ⊕ P 1 (y) y f 2 (z) := z P 2 (z)
If we directly apply the previous algorithm the time complexity will be O 2 n / n/ ln(n) . Concretely the most natural way would be to search for prefix multi-collisions offline in f 1 as it is computationally intensive. Because of the definition of f 1 , the second half y won't repeat but (y ⊕ P 1 (y)) should repeat roughly as often as a random function (assuming that P 1 is a random permutation). Indeed previous works [START_REF] Nikolic | Cryptanalysis of round-reduced LED[END_REF][START_REF] Dinur | Key recovery attacks on 3-round Even-Mansour, 8-step LED-128, and full AES2[END_REF] also use repetitions in the values of (y ⊕ P 1 (y)) in their attacks.

Improved Attack from Multi-collisions. We can actually improve this attack and obtain an attack equivalent to the previous works from [START_REF] Nikolic | Cryptanalysis of round-reduced LED[END_REF][START_REF] Dinur | Key recovery attacks on 3-round Even-Mansour, 8-step LED-128, and full AES2[END_REF], by using the special structure of the 3-XOR instance (3). After building a partial multicollision L 1 with Θ(n/ ln(n)) values of f 1 starting with α, we look for pairs with We see that because we can choose parts of the inputs our problem may be easier than the purely random 3-XOR case. However generic algorithms are a good start to find dedicated cryptanalysis of 2EM. Moreover, the best known attacks against 2EM [START_REF] Nikolic | Cryptanalysis of round-reduced LED[END_REF][START_REF] Dinur | Key recovery attacks on 3-round Even-Mansour, 8-step LED-128, and full AES2[END_REF] can actually be reinterpreted in this way.

f 0 (x) ⊕ f 2 (z) [0:n] = α.
In this paper, we will give new attacks against 2EM starting from this 3-XOR presentation, and using algorithms based on the linear algebra approach.

A Key Recovery Algorithm

Now we describe a key recovery algorithm simply using the linear algebra 3-XOR algorithm by Joux [START_REF] Joux | Algorithmic Cryptanalysis[END_REF] on the 3-XOR instance obtained by the reduction from 2EM. Using this algorithms as a black box, we have a time complexity of O(2 n / √ n) (since w = 2n). This is not as good as the best known 2EM key recovery, but this will lay the ground for the more efficient algorithms in Section 4.

The full attack can be written as Algorithm GA:

GA1. Compute f 1 (y) = (y ⊕ P 1 (y)) y for Q different values y and store them in L 1 .

GA2. Compute f 2 (z) = z P 2 (z) for Q different values z and store them in L 2 .

GA3.

Observe and find a set of n pairs of plaintext/ciphertext (x, E(x)) such that all {f 0 (x) = x (x ⊕ E(x))} are linearly independent and store x (x ⊕ E(x)) in L 0 .

GA4. See L 0 as a n × 2n matrix. Use column reduction to find a 2n × 2n transformation matrix M s.t.

L 0 M = [0 n×n I n ]. 2
GA5. Right-multiply the lists with the transformation matrix:

L 0 ← L 0 M ; L 1 ← L 1 M ; L 2 ← L 2 M .
GA6. Sort and find partial collisions in L 1 and L 2 on the first n-bit half. For each partial collisions L 1 [i] ⊕ L 2 [j] check whether the second n-bit half differs only on the h th bit for some h. If yes go to GA7. If no solution found, algorithm fails.

GA7. A solution to the 3-XOR problem (L

0 [h], L 1 [i], L 2 [j]) has been found. Output k = x ⊕ y with x the first half of L 0 [h] and y the second half of L 1 [i].
The main idea is that, since the transformation matrix M is linear, solving the 3-XOR problem for L 0 , L 1 , L 2 yields the same solutions as L 0 , L 1 , L 2 . Using the transformed lists is easier as we exploit the fact that L 0 = [0 n×n I n×n ] which is always possible to ensure after step GA3.

Step GA3 will cost only n queries as n random words of size 2n will be linearly independent with very high probability. Note that because we just need to observe these, this attack works in the KPA setting.

Analysis.

The query complexity Q is also the size of the lists L 1 and L 2 . There are Q2 pairs each XORing to one of the n elements of L 0 with probability n/2 2n as they are taken randomly. Thus the probability of step GA6 succeeding is

(n • Q 2 )/2 2n .
Therefore for a constant success probability we fix (n • Q 2 )/2 2n = Θ(1). This leads to the following complexities:

Q = O(2 n / √ n), T = O(2 n / √ n) and D = O(n).
We recall here that sorting random values and performing a right matrix multiplication L 1 M (resp. L 2 M ) on an exponentially large L i are both computed in time linear with the size of L i [START_REF] Bouillaguet | Revisiting and improving algorithms for the 3xor problem[END_REF]. As for the computation of M , it is of polynomial time in n and therefore negligible.

Q is the query complexity and we find the relation DQ 2 = 2 2n as expected. Memory-wise we need to store the full lists L 1 and L 2 so the memory complexity will also be

Q = O(2 n / √ n).
Steps GA1 and GA2 concentrate all the permutation's evaluations but can be done as a pre-processing step.

Improved Attacks from the 3-XOR Problem

In the previous section we saw how tools to solve the 3-XOR problem could prove very useful for the 2EM key recovery attacks. But the cryptanalysis allows us to do some tweaks and have better results than simply applying the generic solutions.

In this section we will first show how to add a simple filter to Algorithm GA to mount an attack following the trade-off curve DQ 2 = 2 2n while improving the time complexity of T = 2 n /n (matching the best known 2EM attacks) and memory not exceeding Q. We also show how using the same filter but with the BDP algorithm adapted for the 3-XOR can give the best asymptotic time complexity so far,

T = O( 2 n •ln 2 (n) n 2
), though that largely remains theoretical. Then we describe a very low-data and low-memory key recovery attack that essentially tweaks the previous Algorithm GA to a version that uses, for some parameter 0 < λ < 1, few queries, D = λn, time Q = T = 2 n /λn and memory 2 λn . This actually beats the best information theoretic distinguisher known so far in this range of very low data (DQ 2 < 2 2n ).

Clamping to a Smaller 3-XOR Instance

We first describe an efficient algorithm with a large trade-off space with parameter

D = |L 0 | = 2 d and Q = |L 1 | = |L 2 | = 2 n-d/2 and time complexity O(2 n /n) (independently of D and Q).
This algorithm is built from the 3-XOR algorithm of [START_REF] Bouillaguet | Revisiting and improving algorithms for the 3xor problem[END_REF], but we take advantage of the structure of the 3-XOR problem to reduce the time complexity below O(2 n / √ n) (reached by Algorithm GA). Indeed, our 3-XOR instance is given as:

f 0 (x) := x x ⊕ E(x) (3) f 1 (y) := y ⊕ P 1 (y) y f 2 (z) := z P 2 (z)
We can use a variant of the clamping trick of Bernstein [START_REF] Bernstein | Better price-performance ratios for generalized birthday attacks[END_REF] to simplify this instance. For a parameter d, we consider the 2 n-d/2 values y with y [0:d/2] = 0 and we evaluate f 1 on those values. This gives a list

L 1 with |L 1 | = 2 n-d/2
such that all values have d/2 zero bits (L 1 [i] [n:n+d/2] = 0). Similarly, we consider all values z with z [0:d/2] = 0, and we evaluate f 2 on z = P -1 2 (z ) to build a list L 2 with L 2 [j] [n:n+d/2] = 0. Finally, we consider 2 d known plaintexts x, and we keep the values with x ⊕ E(x) [0:d/2] = 0 in a list L 0 . We expect to have |L 0 | = 2 d/2 . We now have three lists with L i [u] [n:n+d/2] = 0, so we can consider this as a 3-XOR problem on w = 2n -d/2 bits. We have

|L 0 | • |L 1 | • |L 2 | = 2 2n-d/2 = 2 w ;
therefore there is on average one solution, and the algorithm of Bouillaguet et al. [START_REF] Bouillaguet | Revisiting and improving algorithms for the 3xor problem[END_REF] finds it with complexity

O |L 0 | • (|L 1 | + |L 2 |)/w = O(2 n /n).
When writing the full details, we have Algorithm CL: CL1. Compute f 1 (y) = (y ⊕ P 1 (y)) y for all y such that y Query Complexity. The offline query complexity is also the size of L 1 and L 2 , that is 2 n-d/2 = Q. In particular, we use as much data as the best known distinguisher with D • Q 2 = 2 n . Notice that for the balanced case D = Q = 2 2n/3 this attack is optimal in the information theoretic model as Chen et al. [START_REF] Chen | Minimizing the tworound Even-Mansour cipher[END_REF] proved that O(2 2n/3 ) is a lower bound.

Time Complexity. First we need to compute both lists L 1 and L 2 requiring to compute 2 n-d/2 permutations each (this can be a precomputation). We expect the algorithm to succeed after 2 d pairs (x, E(x)) with good probability. Thanks to the d/2-bit filter in step CL3.1 only 2 d/2 pairs are expected to be processed by batches of n values. Therefore we expect to do 2 d/2 /n loops CL3 before we finish. Each loop consists of computing a small transformation matrix, applying it to the big lists L 1 and L 2 , sorting them and looking for prefix collisions. All of these costs are linear in the lists size, 2 n-d/2 , or in the number of expected (n

-d/2)-bit prefix collisions in CL3.4 that is |L 1 | • |L 2 |/2 n-d/2 = 2 n-d/2 . Therefore each loop costs O(2 n-d/2
) and is expected to be performed 2 d/2 /n times for a total computational time complexity of T = O(2 n /n). This computational time is independent of d.

Discussion. Algorithm CL achieves a computational time complexity of T = 2 n /n while using as much information as the best known information theoretic attack with

D • Q 2 = 2 2n
. In particular this is information theoretically optimal in the balanced case D = Q = 2 2n/3 that is for d = 2n/3. This attack works with known plaintexts, and there is no obvious way to improve it using chosen plaintext.

For most of the choices of d, evaluations of the cipher and the permutations is not the dominant cost of the algorithm. In this analysis we assume that operations on n-bit words and memory access to lists L 1 and L 2 cost θ(1) evaluations of the cipher, but if we assume instead that they cost much less than one evaluation (as done in [START_REF] Isobe | New key recovery attacks on minimal two-round Even-Mansour ciphers[END_REF]) the attack is even more interesting.

To optimize the memory complexity that is 2 n-d/2 , we need to choose a fairly high value d. In that case the data complexity D = 2 d becomes problematic but we can swap the number of online call to E with the number of offline calls to P 1 , effectively swapping f 0 and f 1 , thanks to the symmetry highlighted in Section 2.3. This gives a data and memory complexity of 2 n-d/2 , a query complexity of Q = 2 n-d/2-1 + 2 d-1 and the time remains T = O(2 n /n). This becomes a Chosen Plaintext attack because step CL1 requires to choose part of inputs. Concrete values for n = 64 for such trade-off are given in Table 2 as "optim. memory & swap E ↔ P 1 ".

Using Baran-Demaine-Pǎtraşcu's 3-SUM Algorithm

Since the previous algorithm just uses a 3-XOR algorithm as a black box after clamping, we can also use it with the BDP algorithm adapted to 3-XOR [START_REF] Bouillaguet | Revisiting and improving algorithms for the 3xor problem[END_REF]. In fact, any 3-XOR algorithm could be used after clamping which implies that an improved random 3-XOR algorithm would lead to an improved 2EM cryptanalysis. This adapted BDP algorithm has a better asymptotic complexity, with a speed-up of w 2 ln 2 (w) compared to the quadratic algorithm. This results in a key-recovery attack against 2EM with asymptotic time complexity O(2 n • ln 2 (n)/n 2 ). This is asymptotically better than the best known 2EM key recoveries. However, as shown in [START_REF] Bouillaguet | Revisiting and improving algorithms for the 3xor problem[END_REF], it is not practical for realistic word sizes w. Indeed the dominant term in the complexity of the BDP algorithm is O(|L 0 |.|L 1 |/m 2 ) with m = Θ(n/ ln(n)). Following the analysis of Bouillaguet et al., we have more concretely m n/(112 ln(n)). Therefore, in order to have m 2 > n, we would need n > 2.75 × 10 6 .

Very Low Data Algorithm

The previous Algorithm CL can reach a low-data complexity (with a small parameter d) that would be a multiple of n, or a relatively low-memory complexity (close to 2 n/2 with a large d), and having both close to 2 n/2 requires chosen plaintexts. We now describe a new algorithm that combines a very low-data complexity and a low memory. This algorithm uses only D = λn known plaintexts for 0 < λ < 1, and has a time complexity T = O(2 n /λn) while using only a memory of size 2 λn . Moreover, we have

D • Q = 2 n and D • Q 2 = O(2 2n /λn),
that is the best information theoretical trade-off so far between online and offline queries.

This will be algorithm LD with parameter 0 < λ < 1 (typically, we have λ = 1/2): LD1. Observe and find a set of λn pairs of plaintext/ciphertext (x, E(x)) such that all {(x ⊕ E(x)) [n-λn:n] } are linearly independent and store f 0 (x) = x (x ⊕ E(x)) in L 0 . LD2. See L 0 as a three concatenated λn-line matrices:

L 0 = [ A n B n-λn C λn ]
Define the n × n small transformation matrix M s :

M s = I 0 C -1 B C -1 M -1 s = I 0 B C
and the 2n × 2n big transformation matrix M :

M =   I 0 M s 0 A M s   =   I 0 0 0 I 0 C -1 A C -1 B C -1   LD3.
Right-multiply the list L 0 with the big transformation matrix:

L 0 ← L 0 M = [ 0 n 0 n-λn I λn ]
LD4. Until a solution is found pick a new (n -λn)-bit value α and do: We again use the property that finding a solution for the 3-XOR in the modified lists yield the same solution in the original lists.

LD4.1. For all λn-bit value u compute f 1 [α|u]•M -1 s = [α|u]•M -1 s ⊕P 1 [α|u]• M -1 s [α|u] • M -1 s . Store them in L 1 . LD4.2. For all λn-bit value u compute f 2 P -1 2 ([α|u] • M -1 s ) = P -1 2 ([α|u] • M -1 s ) [α|u] • M -1 s .
With the way we defined the big transformation matrix M in LD2 and the fact that we applied M -1 s to the inputs in steps LD4.1 and LD4.2, when we perform step LD4. [START_REF] Bogdanov | Key-alternating ciphers in a provable setting: Encryption using a small number of public permutations -(extended abstract)[END_REF] we get the values

f 1 [α|u]•M -1 s •M = [α|u]•M -1 s ⊕P 1 [α|u]•M -1 s ⊕ (0|(u•A)) [α|u] and f 2 P -1 2 ([α|u]•M -1 s ) •M = P -1 2 ([α|u]•M -1 s )⊕(0|(u•A))
[α|u] stored in L 1 and L 2 respectively. Thus the right-hand side of both lists reverts to the form {α|u} with fixed α and for all u. Therefore we get an (n -λn)-bit collision for free on α matching with zeroes in L 0 .

Complexity Analysis

For this attack, in each loop we pick a value α and build L 1 , L 2 of size 2 λn . Then we have a solution among the 2 2λn pairs if one of them XORs to one of the λn values of L 0 . Since we have a collision on (n -λn)-bit value α for free, one couple gives a solution with probability λn • 2 -(n+λn) . Thus each loop gives a solution with probability 2 2λn • λn • 2 -(n+λn) = λn • 2 λn-n . For a constant probability of success we will need to perform around 2 n-λn λn iterations.

Data Complexity.

Step LD1 completely determines the data complexity of the algorithm. We capture λn plaintext/ciphertext pairs and we get a linearly independent set of values with good probability. Therefore D = λn is the data complexity.

Memory Complexity. The list L 0 and the matrices take a space polynomial in n and therefore negligible. The lists L 1 and L 2 are always of size 2 λn . Therefore the memory complexity is O(2 λn ).

Query Complexity. The computation of the public permutations are all done in steps LD4.1 and LD4.2 to build lists of size 2 λn . We pass through this step at each loop meaning that the total offline query complexity is:

Q = 2 λn • 2 n-λn λn = 2 n λn
Time Complexity. Again, computations of the matrices in step LD2 are essentially polynomial in n so negligible.

Step LD4.3 performs right-multiplications on large matrices and step LD4.4 is about sorting and merging which makes those steps linear given that the merged list is of reasonable size. Here we have a partial collision on n bits with probability 2 -n therefore there will be around 2 2λn • 2 -n = 2 2λn-n partial collisions that is less than the size of the lists (2 λn ) therefore step LD4.4 has also a linear cost. The computational time complexity is therefore also led by the query complexity that is T = 2 n λn . Acceptable Range. Notice that the previous reasoning to derive the time complexity is only applicable when we do need more than one loop to finish the algorithm as it makes no sense to multiply by half-a-round. So all those trade-off depending on λ are constraints by:

2 n-λn λn ≥ 1 ⇔ λ ≤ W (2 n ln 2) n ln 2 = 1 - ln(n ln 2) n ln 2 + o(1)
(using the Lambert W function)

Discussion. This attack works in the KPA setting as we only need to observe pairs of plaintext/ciphertext, and we need to observe surprisingly few of them, λn pairs are sufficient. The memory requirement, O(2 λn ), can also go quite low as we choose the parameter λ but this comes at the cost of no pre-computation possible as we need the transformation matrix to get the right inputs to the public permutations.

The computational time complexity T = 2 n /λn compares well with previous cryptanalysis done on this subject. So far there were no key recovery attack on 2EM with a better asymptotic complexity than O(2 n /n).

In the information theoretic model, trade-off between D and Q is important as a designer can always arbitrarily limit the maximum value of D by, for example, rekeying in order to achieve a certain security goal. In this regard, this algorithm has a better trade-off between the data and query complexity than the best known generic distinguisher by Gaži [START_REF] Gaži | Plain versus randomized cascading-based key-length extension for block ciphers[END_REF] that has the trade-off DQ 2 = 2 2n . Here DQ 2 = 2 2n /λn thus being the best known key recovery, and also the best distinguisher, for the acceptable range of λn.

In fact the proof by Chen et al. [START_REF] Chen | Minimizing the tworound Even-Mansour cipher[END_REF] says nothing for low-data range D ≤ 2 n/4 and the best proof is therefore inherited from the original one round Even-Mansour scheme that lower-bounds the trade-off with DQ ≥ 2 n . Gap between the best known distinguisher and the proof in this range is still an open problem but Algorithm LD, which has the trade-off DQ = 2 n -and also DT = 2 n -for any λ, proves for the first time the optimality of the original proof of the trade-off between D and Q for the acceptable range of λ that is for 1 ≤ D ≤ W (2 n ln 2) ln 2

. Previous Work. We can see this cryptanalysis as an advanced version of the attack by Dinur et al. using linear algebra [9, Section 4.2]. We can list three main differences that make this attack an improvement over the previous one. First, as already mentioned in Section 2.3, we use the symmetry between E, P 1 , P 2 to reduce the data complexity from 2 n /λn to λn. Then the use of the big transformation matrix M , that essentially performs a Gaussian elimination over the whole 2n-bit words, makes the attack works with known plaintexts while Dinur et al. required chosen plaintexts (even after applying the symmetry trick). Finally, the resulting n-bit filter of step LD4.4 allows for a larger acceptable range of λ than the previous attack that needed λ < 1/3 to limit the number of partial collisions.

Extension to r rounds.

The approach can be generalized to attack multiple rounds. In fact the cryptanalysis of a single key r-round EM scheme can be written as a (r + 1)-XOR problem with words of size rn. Even though for r ≥ 4 generic algorithms won't directly provide interesting attacks with competitive computational complexity, this elegantly rewrites the known generic distinguisher on rEM and may be a good start to look for dedicated cryptanalysis.

f 0 , f 1 , f 2 , ..., f k , find k inputs (x 0 , x 1 , x 2 , ..., x k ) such that f 0 (x 0 ) ⊕ f 1 (x 1 ) ⊕ f 2 (x 2 ) ⊕ ... ⊕ f k (x k ) = 0.
Extended Relation. To see that we follow the same reasoning as in Section 2.2 but for the r-round EM, Figure 5, and look for an (r + 1)-tuple (x 0 , x 1 , ..., x r ) satisfying the generalized relation R:

R(x 0 , x 1 , x 2 , ..., x r ) :=      x 0 ⊕ x 1 = k P i (x i ) ⊕ x i+1 = k, 1 ≤ i ≤ r -1 P r (x r ) ⊕ E(x 0 ) = k (4) ⇒      x 0 ⊕ x 1 = P 1 (x 1 ) ⊕ x 2 P i (x i ) ⊕ x i+1 = P i+1 (x i+1 ) ⊕ x i+2 , 1 ≤ i ≤ r -2 P r-1 (x r-1 ) ⊕ x r = P r (x r ) ⊕ E(x 0 ) (5)
Again we cannot directly observe R but we can observe the implied relation 5 which is an rn-bit filter and is enough so that a random (r + 1)-tuple satisfying Filter 5 is a right tuple with good probability.

Define Lists. Now we can define r + 1 lists of r n-bit entries such that solving the (r + 1)-XOR problem on those lists over all entries trivially gives a solution to 5:

L 0 [h] :=      x 0 , h = 1 0 , 2 ≤ h ≤ r -1 E(x 0 ) , h = r L 1 [h] :=      x 1 ⊕ P 1 (x 1 ) , h = 1 P 1 (x 1 )
, h = 2 0 , h ≥ 3

L i [h] 2≤i≤r-1 :=                0 , h ≤ i -2 x i , h = i -1 x i ⊕ P i (x i ) , h = i P i (x i ) , h = i + 1 0 , h ≥ i + 2 L r [h] :=      0 , h ≤ r -2 x r
, h = r -1 x r ⊕ P r (x r ) , h = r see example for r = 5 in Table 3. Thus this indeed defines an (r + 1)-XOR problem with rn-bit words even though it is more structured than the purely random k-XOR problem. Upon its resolution we have a successful key recovery with good probability when guessing k = x 0 ⊕ x 1 . ). Interestingly this exactly coincides with the lower bound queries for the single key r-round Even-Mansour scheme [START_REF] Bogdanov | Key-alternating ciphers in a provable setting: Encryption using a small number of public permutations -(extended abstract)[END_REF]. Using generic algorithms allows a cryptanalysis using D = Q = O(2 rn r+1 ) therefore being optimal in query complexity. In fact the approach can be thought as similar to the simple known distinguisher but instead of looking for contradictory paths we directly look for a correct path (that implies a right tuple) and guess the key.

Limitation. The computational time complexity of generic algorithms by Wagner for this problem is T = O r • 2 rn log(r+1) +1 [START_REF] Wagner | A generalized birthday problem[END_REF]. For r = 2 and 3 rounds this is just O(2 n ) and we could improve from there in the 2EM case. For the 3EM case Dinur et al. [START_REF] Dinur | Key recovery attacks on iterated Even-Mansour encryption schemes[END_REF] showed that we can have a complexity below O(2 n ) using multicollisions and while it is fairly straightforward to rewrite the same attack in the 4-XOR context it is also non-trivial to improve this.

On the other hand the complexity is way over 2 n for r ≥ 4 rounds. Therefore this is mainly an information theoretic attack. However the lists here have a strong structure, see Table 3, with many bits to 0 which opens the question of a dedicated algorithm with competitive computational time/memory trade-off.

Conclusion

In this paper we presented a 3-XOR approach to key-recovery attacks on singlekey two-round Even-Mansour. That allows us to gain a better understanding of previous works and devise competitive algorithms using linear algebra techniques that have been initially developed for the random 3-XOR problem.

These attacks have a particularly interesting data and memory complexities. In particular, we give the first attacks where both the data and memory complexity are below O(2 n-ε ) for ε > 0, while achieving the best known time complexity of O(2 n /n). Previous attacks with a similar time complexity required either a very large memory or very large data, making them unlikely to be useful in practice. We also give an attack that improves the asymptotic time complexity to O(2 n • ln 2 (n)/n 2 ), although it is not applicable for practical values of n. As another interesting result, we show a very low-data attack that beats the best known distinguisher, and actually matches the proven lower bound for single round Even-Mansour construction, with DT = 2 n .

All those attacks are shown on the 2EM construction with no key schedule and independent permutations, but we prove that an attack on this variant of 2EM leads to an attack on the more general 2EM with a linear key schedule. Additionally we show that the 2EM construction has an implicit symmetry that allows to blindly swap the number of calls one makes to each oracle during an attack; this automatically allows new trade-offs between the parameters. Iterated Even-Mansour schemes are idealized SPN networks and understanding their security is important because many block ciphers, including the AES, are based on this design. In this work we focused on the two-round construction linking it to the 3-XOR problem such that a future improvement of the random 3-XOR algorithms will improve our cryptanalysis. But we can also extend this approach to r-round constructions and the (r + 1)-XOR problem with a particular structure. We detail this link in Section 5 but additional work is required to build competitive key-recovery attacks from that.

Fig. 1 .

 1 Fig. 1. Single key two-round Even-Mansour scheme (2EM) EMIP variant

Fig. 4 .

 4 Fig. 4. A right triplet gives a path of EMIP

  Because of the structure of f 0 and f 2 , we can just use z = x⊕α for each known plaintext x. Therefore we have |L 0 | = |L 2 | pairs partially colliding to a predefined value. Each couple gives a full collision if the second n-bit part corresponds to one of the elements in L 1 ; this happens with probability n/ ln(n) • 2 -n . Thus this attack requires lists of size D = Q = O 2 n /(n/ ln(n)) in order to succeed with high probability in the KPA model.

  [0:d/2] = 0. Remove bits [n : n + d/2] (fixed to 0) and store the (2n -d/2)-bit values in L 1 .

Fig. 5 .

 5 Fig. 5. A right tuple gives a path of rEM

Table 1 .

 1 Comparison of attacks against 2EM. Asymptotic complexity, up to constants. "Data" denotes encryption queries, while "Queries" denotes calls to the public permutations Pi. 0 < λ < 1; log n ≤ β ≪ n; KP: Known plaintext; CP: Chosen plaintext.

	Ref	Data	Queries	Time		Memory	Comment
	[19]	2 n ln n/n KP 2 n ln n/n	2 n ln n/n	2 n ln n/n	Multi-collisions
	[8]	2 n ln n/n CP 2 n ln n/n 2 n ln n/n 2 n ln n/n Diff. m-c (indep. keys)
	[8]	2 λn	KP 2 n ln n/n	2 n ln n/n	2 n ln n/n	Multi-collisions
	[9]	2 n /λn	CP 2 n /λn	2 n /λn	2 λn		Linear algebra
	[14]	2 n ln n/n CP 2 n ln n/n	2 n ln n/n	2 n ln n/n	MitM
		2 λn	CP 2 n ln n/n	2 n ln n/n	2 n ln n/n	MitM
		2 n β/n	CP 2 n /2 β	2 n β/n	2 n /2 β	MitM
	S. 3.3 n	KP 2 n /	√ n	2 n / √	n	2 n /	√ n	3XOR [15]
	S. 4.1 2 d	KP 2 n-d/2	2 n /n		2 n-d/2	Clamping + 3XOR [4]
	S. 4.3 2 d	KP 2 n-d/2	2 n ln 2 n/n 2 2 n-d/2	Clamping + 3XOR [1]
	S. 4.4 λn	KP 2 n /λn	2 n /λn	2 λn		Low Data Filter

Table 2 .

 2 Comparison of attacks against 2EM with n = 64. The complexity unit is one evaluation of the cipher; we assume that computing P1 or P2 costs 1 /2, and that a memory access to a large table also costs 1 /2. The time complexity also includes the time necessary to generate the data.

	Ref	Data	Queries Time Memory Comment
	[19]	2 58.7 KP 2 60.5	2 60.9 2 60	Multi-collisions
	[8]	2 45 KP 2 60.7	2 60.7 2 60	Multi-collisions
	[9]	2 60 CP 2 59	2 60.6 2 16	Linear algebra
	[14]	2 60 CP 2 60	2 61.3 2 60	MitM
		2 8 CP 2 62	2 62.6 2 62	MitM
		2 61 CP 2 57	2 61.7 2 58	MitM
	Sec. 3.3 2 6 KP 2 61	2 62	2 61	3XOR
	Sec. 4.1 2 42 KP 2 43	2 58	2 42	Clamping + 3XOR [4], bal. case
		2 14 KP 2 57	2 58.6 2 57	optim. data
	Sec. 4.2 2 35 CP 2 57	2 58.6 2 35	optim. memory & swap E ↔ P1
	Sec. 4.3 2 42 KP 2 43	N.A. N.A.	Clamping + 3XOR [1], bal. case
	Sec. 4.4 2 5 KP 2 59	2 60	2 32	Low Data Filter λ = 1/2
		2 4 KP 2 60	2 61	2 16	λ = 1/4

  Store them in L 2 LD4.3. Modify the lists with the big transformation matrix:L 1 ← L 1 M ; L 2 ← L 2 M .Note that all elements of L 1 and L 2 have bits [n : n + λn] set to α. Sort and find partial collisions in L 1 and L 2 on the first n-bit half. For each partial collisions L 1 [i] ⊕ L 2 [j] check whether the second half differs on a single bit h with n -λn < h ≤ n. If yes go to LD5. If no solution found, continue to loop on LD4. LD5. A solution to the 3-XOR problem (L 0 [h -(n -λn)], L 1 [i], L 2 [j]) has been found. Output k = x ⊕ y with x the first half of L 0 [h -(n -λn)] and y the second half of L 1 [i].

	LD4.4.

Table 3 .

 3 Cryptanalysis of 5EM.Lists' construction for a cryptanalysis using the 6-XOR problem. Even though the problem is structured this allows us to use generic algorithms for the k-XOR problem to perform a cryptanalysis. With purely random functions it is known that the lower bounds of queries for the the rn-bit words (r + 1)-XOR problem is O(2

	L0 {	x0	.	.	.	E(x0)}
	L1 { x1 ⊕ P1(x1)	P1(x1)	.	.	. }
	L2 {	x2	x2 ⊕ P2(x2)	P2(x2)	.	. }
	L3 {	.	x3	x3 ⊕ P3(x3)	P3(x3)	. }
	L4 {	.	.	x4	x4 ⊕ P4(x4)	P4(x4)}
	L5 {	.	.	.	x5	x5 ⊕ P5(x5)}
	Generic Cryptanalysis. rn
				r+1

For instance, we write L0 as a block matrix A B with two w/2 × w/2 sub-matrices.If B is non-singular, we can use M = I 0 B -1 A B -1

We write L0 = A B . If B is non-singular, we can use M = I 0 B -1 A B -1

Acknowledgement

Part of this work was supported by the French DGA.

CL3.3. Right-multiply the lists with the transformation matrix:

In steps CL1 and CL2 we only fixed the d/2 first bits so that we have lists of size 2 n-d/2 . Step CL2 still constructs the usual L 2 as a collection of z P 2 (z) only we need to fix the values of P 2 (z) = z and compute the value z = P -1 2 (z ) using the inverse.

Then all of this works very much like Algorithm GA the main difference begin at step CL3.1 where we filter the observed pairs. Indeed we look for a triplet such that x ⊕ y = z ⊕ E(x) so fixing bits of y and z fixes bits of (x ⊕ E(x)).

Complexity Analysis

Data Complexity. The data complexity depends on the number of plaintext/ciphertext pairs we will expect to observe before we find a solution. One way to see it is to count the number of observable right triplets. Initially there are 2 n right triplets but we restrict ourselves to triplets such that y [0:d/2] = 0 and P 2 (z) [0:d/2] = 0, a d-bit filter, so on average will remain 2 n-d right triplets. Therefore the moment we observe an x belonging to one of these right triplets it will necessarily pass the filter, give a solution and finish the algorithm. This happens with probability 2 n-d /2 n = 2 -d therefore we expect solution after D = 2 d pairs (x, E(x)).

Memory Complexity. The largest lists in memory are L 1 and L 2 that require, in the balanced case, O(2 n-d/2 ) blocks of memory.


Hana Ayedi
email: hana.ayedi.4@gmail.com

Alaeddine Zouari
email: ala.zouari@isgis.usf.tn

Nadia Hamani
email: nadia.hamani@u-picardie.fr

An exploratory study of the bike rental system in Sfax -Tunisia

Keywords: Shared transportation, sustainable urban mobility, active transportation, bike rental system, LOGIT model

facing the growth of urban mobility in the city of Sfax and the problems of traffic, congestion and pollution, the development of active transportation has become an unavoidable solution. In this context, a study on the promotion of the bike use at Sfax City is launched for the first time. The study is based on a survey done with a sample of 500 citizens. The first part of this work is addressed to know the traveling habits of citizens in order to better understand the state of the current use of the bike at Sfax. The second part is dedicated for the identification of factors influencing the choice of bike's rental through LOGIT model.

I. INTRODUCTION

Nearly a million inhabitants, the city of Sfax is the second largest Tunisian governorate after the capital Tunis in terms of its demographic weight [START_REF] Anme | Stratégie Sfax 2030: Diagnostic stratégique de l'état du développement de la région[END_REF]. Sfax is known for its important economic dynamism and the diversity of its industrial sectors. However, the governorate of Sfax has suffered for decades from serious problems in the transportation and traffic system. These problems affect the three pillars of sustainable development (economic, environmental and social/societal). This transport system is a major generator of environmental nuisances and contributes significantly to the problems of congestion, pollution, and noise. At peak times (morning, afternoon and evening), and the eve of holidays, the problem of transportation is more and more accentuated, and always in city center [START_REF] Anme | Stratégie Sfax 2030: Diagnostic stratégique de l'état du développement de la région[END_REF]. Traffic congestion and problems are due to local concentration of economic activities and administrative services. It get worst by the increase in the use of private vehicles, the circulation of heavy trucks, the deterioration of public transport services, the uncontrolled parking due to the lack of parking spaces and the development of road infrastructure. Between 1984 and 2015, the modal split is marked by the dominance of privet cars and taxis compared to public transport and twowheeled vehicles usage. A share of only 1% proves the quasi-absence of the bike. [START_REF] Anme | Stratégie Sfax 2030: Diagnostic stratégique de l'état du développement de la région[END_REF]. Indeed, the transport sector is considered as one of the biggest sources of air pollution that degrades the viability of the city. The total emissions in Sfax territory amounted to 5.2 million tonnes of CO2, with a significant share attributed to the transport sector (persons and goods), which emits 54% of greenhouse gas emissions. (GES) [START_REF] Pdu | Plan de Déplacements Urbains du Grand Sfax à l'horizon 2030[END_REF].

In this context, it is necessary to find alternative solutions for a sustainable transportation system, tends to the energy independence, rather than a polluting and congestive transportation system by developing more environmental friendly transport such as public transport, bike and pedestrians [START_REF] Frade | Bicycle sharing systems demand[END_REF]. For this purpose, we are interested on the bike usage as an alternative solution for evolution without harmful consequence. So, a study of bikes rental system "bike sharing" in the city of Sfax was done, where the bikes could occupy a dominant place of citizen's transport.

The objective of this study is to reconsider bikes as an alternative transport solution. Firstly, it aim to know the transportation habits of the citizens of Sfax and to study their opinion regarding this system of bikes renting, Secondly, to identify the factors influencing the choice of renting bikes.

II. LITERATURE REVIEW

The bike is reappeared in the last years with a phenomenal development on almost all continents after a long disappearance. Nowadays, the shared bike, represent an alternative solution to motorized mobility [START_REF] Zhang | Sustainable bikesharing systems: characteristics and commonalities across cases in urban China[END_REF]. Since the launching of the first system in the 1960s in the Netherlands, four generations of bike sharing can be considered [START_REF] Demaio | Bike-sharing: History, impacts, models of provision, and future[END_REF], [START_REF] Shaheen | Bikesharing in Europe, the Americas, and Asia: past, present, and future[END_REF], [START_REF] Mátrai | Comparative assessment of public bike sharing systems[END_REF]. The first generation is known as Witte Fietsen "white bikes" This service is characterized by bikes randomly placed in a certain areas for free usage [START_REF] Shaheen | Bikesharing in Europe, the Americas, and Asia: past, present, and future[END_REF]. Unfortunately, this experience had failed, because bikes were simply harmed either thrown into channels or adapted for private use [START_REF] Demaio | Bike-sharing: History, impacts, models of provision, and future[END_REF]. A second generation appeared in the early 1990 years, in Farsø, Grenå, and Nakskov to face the problems encountered during the first generation by integrating a financial fee to encourage users to bring the borrowed bike into a station to recover their deposit [START_REF] Benarbia | Contribution à la modélisation et à l'analyse de performances des systèmes de vélos en libre-service en vue de leur régulation: Une Approche basée sur les réseaux de Pétri[END_REF]. The third generation start in the beginning of 1996, the bike sharing system became more popular. This generation is characterized by a variety of technological enhancements, including the electronic locking barriers, telecommunication systems, smart cards or magnetic stripe cards, mobile phone access and embedded computers [START_REF] Demaio | Will smart bikes succeed as public transportation in the United States?[END_REF]. In May 2009, BIXI is the first shared fourthgeneration bike system appeared in Canada with its solarpowered mobile stations [START_REF]City cycling[END_REF]. Other innovations emerged with the fourth generation including mobile stations, solar energy stations, electrical assistance bikes and the setting up of self-regulation policy using smartphones applications [START_REF] Jachelski | Worcester, MA Bike Share Feasibility Study[END_REF].

In 2014, approximately 855 bike sharing programs was counted in almost every region of the world with about 946,000 bikes [START_REF] Fishman | Bikeshare: A review of recent literature[END_REF]. However, in the African continent, only two shared bike programs have been set up. The first is located in Marrakech in 2016 with 350 bikes and a dozen stations. The second was set up in Egypt in 2017 with 100 bicycles and 5 stations. In Tunisia, preparations are in progress in Sfax, Kairouan, and Tunis 1 .

This system has multiple environmental, economic and social benefits. Bike share is a sustainable practice with minor negative impacts and even without any negative impacts compared to other transportation methods. The increased use of bikes can solve problems of congestion, fuel expenses, and greenhouse gas emissions [START_REF] Parkes | Understanding the diffusion of public bikesharing systems: evidence from Europe and North America[END_REF]. A 312 000 km/day course by the users of Vélib' represents a reduction of about 57 720 kg of CO2 per day compared with the same usage by car [START_REF] Shaheen | Bikesharing in Europe, the Americas, and Asia: past, present, and future[END_REF]. Shared bike systems contribute to reduce air and noise pollution, as well as preserve urban spaces. Moreover, requested space for bike facilities is smaller than the infrastructures required for cars [START_REF] Dhingra | Public bicycle schemes: Applying the concept in developing cities examples from India[END_REF]. Furthermore, using bikes helps to reduce stress and make users more healthy18]. Some literature reviews, highlight a lot of variety of researches done on shared bike systems [START_REF] Fishman | Bikeshare: A review of recent literature[END_REF] [20], some of them was done with deep analysis to check if it is possible to implant similar system. Others study done by focusing on the environmental, socio-economic, geographic and psychological factors that influence the probability to use the bike. However, few studies have explored the characteristic of bike sharing users and the factors that encourage and discourage them to use it [START_REF] Bachand-Marleau | Better understanding of factors influencing likelihood of using shared bicycle systems and frequency of use[END_REF]. In our study, we will particularly focus on this innovative system.

III. WORKING METHODOLOGY

In order to analyze the characteristics of citizens' movements and to study their behavior towards a bike sharing system in the city of Sfax, we conducted an investigation based on sequence of four steps, described in

A. Formulation of the questionnaire

After study of the literature and the consultation of university experts, a questionnaire has been proposed for citizens of the city of Sfax. The questionnaire consists of seventeen questions with different types, in which six of them are open-ended questions and the rest are closed. Closed questions have a unique choice and one of them is with a multiple choice. There is a semi-closed question that comprises a choice "other" in the event that respondents provide other proposals. It is made with different types of data like socioeconomic, traveling habit, and traveling by bike. The table below represents the detailed information gathered via the questionnaire.

1 http://www.codatu.org/actualites/le-velo-dans-les-villesmediterraneennes-du-sud-il-est-temps-de-passer-la-seconde Before launching the questionnaire, it was pre-tested and validated with the help of academic experts, in order to assess the comprehension and coherence of the questions, also, to determine the required time for the questionnaire. After some modifications and improvements proposed by these experts, the questionnaire was validated. The main objects of this survey are:  Know the characteristics and nature of the trips.

 Measure distance traveled and travel time per trip.

 Know the obstacles encountered when using the bike.

 Collect the opinion of the investigators about the bicycle rental system and the conditions of use

C. Data collection and analysis

The data were collected from a survey based on questionnaire for a sample of the governorate of Sfax on 2017. The sample consists of 500 citizens who represent 0. 1 % of the population of Grand Sfax [START_REF] Anme | Stratégie Sfax 2030: Diagnostic stratégique de l'état du développement de la région[END_REF]. The survey was done during three months: May, June, and July in several places and at different times. The questionnaire was completed by hand, where the answers were coded.

1) Statistical analysis

After collection, the data were analyzed using the statistical analysis software SPSS (Statistical Package for the Social Sciences). This software allowed us to do a descriptive and econometric analysis.

In order to better understand how the various responses are distributed and identify possible blockages, a descriptive analysis was carried out by analyzing the questionnaire question by question.

In this study, the proportion of the investigated men is more important than women and represent 60 % of the total surveyed peoples (Fig. 2). 60% 40% Man Women Fig. 2. Persons surveyed by gender As Figure 3 shows, the majority of people in this survey are students (36%) and executives (30%). ). As per the results, the majority of respondents make between one and two travel per day for both reasons. According to figures 7 and 8, we can notice that the car is the most used way of transport and the bike is the least used one. We can also notice a small share is attributed to bus users comparing to taxi users. This proves that very few citizens use active transport, such as walking and biking, to carry out their travels. Thus, the low percentage of public transportation usage is due to the poor quality of the offered service. The various problems mentioned for the rejection to use bikes are illustrated in Fig 10 . The main reason is the road insecurity with 43% followed by the problem of discomfort related to traffic of vehicles (noise, pollution) with 15%. Other problems are also mentioned by respondents such as the shameful image, the need for physical effort, high maintenance costs, etc. In the case of the implementation of a bike rental system, a short-term rental is more requested than a long-term rental. More than a quarter of respondents refuse to rent (Fig 12).

2) Econometric analysis

In our study, 28% of respondents refused to rent a bike. This justifies the choice to use a LOGIT model for a better understanding of the different factors influencing the choice of bikes rental and to model the probability of renting a bike. We used LOGIT to model the probability of renting a bike. The reason of this model is to be used for studies aim to check if the independent variables can predict a dichotomous dependent variable. The independent variables can be qualitative or quantitative variables [START_REF] Desjardins | L'analyse de régression logistique[END_REF]. Thus, the objective of the model is to explain the behavior yi observed through a series of independent variables. The variable yi follows Bernoulli's law:

     i i i p y probabilit with p y probabilit with y 1 0 1 
In our case, the people surveyed have two possible choices: «YES», they would agree to rent a bike for their trips or «NO» they would refuse to rent the bike. Therefore, in our case, "y" is the binary dependent variable identifying the choice of the person being surveyed ie (yi = 1) if the individual i chose to rent the bike and (yi = 0) if not. The use of such a model seems interesting to model the probability of renting bicycles taking into consideration certain independent variables that influence the variable to be explained.

Four explanatory variables were selected and included in the model: "csp", "mean-n", "n-use" and "ni-weather". These variables were selected via the chi-two statistical test. Significant variables accepted are those with a calculated pvalue below the significance level set at 0.05. The variables "csp" and "mean-a" are polytomic with respectively eight and five modalities, while the two others, "n-use" and "niweather", are dichotomous with two modalities.

Name of variables modalities Descriptions

CSP CSP1

The person surveyed is a high school student.

CSP2

The person surveyed is a student.

CSP3

The person surveyed is a worker.

CSP4

The person surveyed is an executive.

CSP5

The person surveyed is a craftsman.

CSP6

The person surveyed is a liberal profession The estimates obtained from the SPSS software from the LOGIT model are presented in Table 3. As previously mentioned, the LOGIT model allowed us to calculate the probability coefficients that a surveyed individual chose to rent a bike. As a result, we proceed by interpreting the exponential regression of coefficient β which corresponds to the odds ratio (exp β, also called the odds ratio). If β is negative and the odds ratio is less than 1, then the event is less likely to appear compared the reference category of the variable. On the other hand, if β is positive and the odds ratio is greater than 1, then the event is more likely to appear compared to the reference category of the variable [START_REF] Mel | L'étude des déterminants des opérations de fusions et acquisitions pour les entreprises innovantes: le cas de l'industrie pharmaceutique[END_REF].

For a qualitative variable, the exponential of the regression coefficient associated with a modality corresponds to the odds ratio between the reference category and the modality considered [START_REF] Gillaizeau | Modèles de régression multiple[END_REF]. As a result, a reference category is chosen for each type of variable. For example, the variable «mean-n» takes the modality «mean-a» as the reference modality with respect to the modalities «mean-v», «mean-b», «mean-t» and «mean-m».

R2 Nagelkerke allows judging the quality of a model. [START_REF] Desjardins | L'analyse de régression logistique[END_REF]. The resulting model explains 33.1% of the bike rental variability, which is considered satisfactory.

The Hosmer-Lemeshow test evaluate the quality of model adjustment according to the data. It corresponds to Khi-Deux statistic between observed and expected probabilities. If the degree of significance p is greater than 0.05, then the fit to the data is considered good [START_REF] Rakotomalala | Pratique de la régression logistique Régression Logistique Binaire et Polytomique[END_REF]. In our case p = 0.518> 0.05 so the model is acceptable. Thus, the main findings from odd ratios are:  Before interpreting the odds ratios, we excluded three categories (high school students, workers and those with a liberal profession) because they were not significant since the p-value value calculated for these methods was higher then the level of significance of 0.05. On the other hand, the other modalities were significant. Students, executives, craftsmen and those with no profession are more likely to rent a bike than retirees. In first and second position, we find the craftsmen (β = 1.962) and the unemployed (β = 1.950) whose odds ratios are respectively 7.113 and 7.026. Then, students (β = 1.887) and executives (β = 1.661) with odds ratios respectively 6.598 and 5.263.

 Those who agree to use bicycle are more likely accept to rent a bicycle (β = 2.182) compared to those who do not use the bike, the odds ratio being 8.860 times higher.

 Being a weather-sensitive person increases the possibility of renting a bike (β = 1.018), with the odds ratio being 2.767.

 Using a private car or public transport for other purposes (leisure, shopping, etc.) increases the probability of renting a bike compared to those who use active transportation (cycling, MAP ). Users of car (β = 0.421), bus (β = 1.331) and taxi (β = 2.001) have odds ratios of 2.057, 3.784 and 7.399 times respectively, to rent a bike. On the other hand, motorcycle users are less likely to rent a bike (β = -0.989) than those who use active transportation, with odds ratio 0.372

In conclusion, the use of such a model is an excellent technique to determine the factors that most influence the choice of bike rental for citizens of Sfax. This shows that craftsmen, unemployed, students and executives who accept the use of bicycles, have problems related to weather conditions and use public transport and private are key factors in renting a bike.

D. Results and recommendations

As a result of the analysis obtained from the survey, some actions are recommended:

 Greater awareness among citizens to encourage them to use the bicycle as a means of transportation. Indeed, we found a considerable lack of awareness regarding active mobility. The bike is almost absent in the traveling of citizens compared to other modes of motorized transport. Less than one percent of citizens travel by bike.

 A better motivation: it will overcome the main obstacles encountered by citizens when using the bike. First, it will improve the comfort and safety conditions of bike users by creating a favorable and safe environment for users (a majority of 43% suffer from unsafe roads and 15% others have problems related to discomfort due to vehicle traffic). In order to encourage citizens to massively use bicycles, it seems necessary to provide adequate infrastructure for cycling. On the one hand, it will be necessary to offer bike lanes by physically separating the bicycle traffic from the car traffic (65% of the respondents declare that they would ride by bicycle if they could make their journey on bicycle paths separated from the car traffic). On the other hand, it will be necessary to trace the bike lanes (18% of the respondents want to ride if the bands are present). In addition, it is recommended to develop zones 30 because 6% of respondents find that zones 30 can be as a solution to guarantee their security. Then, it seems interesting to put bike accessories to fight against cold, rain and heat because 11% of respondents have problems related to weather conditions.

 Promoting the use of bicycles by setting up an efficient bike rental system is justified since 72% of respondents agree to rent a bike.

Nevertheless, it is also clear there are some limitations. Firstly, one limitation of the study is related to a random sampling approach. The second limitation is that, the statistic explains nothing, but provides potential elements for the explanation. Also the term explanatory variable or variable to explain is probably not the most judicious [START_REF] Lebart | Statistique exploratoire multidimensionnelle[END_REF]. A different study and a different approach more complex and sophisticated are needed to model bike travel and rental choice by this special population.

IV. CONCLUSION

This study aims to guide the city of Sfax towards sustainable transport. Initially, we developed a survey to learn the travel habits of the Sfaxiens, check the state of use of the bike in Sfax, identify the constraints and know the requirements of citizens for a bike rental system in Sfax. In a second step, we used a LOGIT model to identify the factors influencing the choice of bicycle rental. As results, according to the socio-economic categories of surveyed peoples, artisans, unemployed, students and executives are the most favorable for bike rental. At the level bike rent system implementation, the rent for short duration is more requested than the long-term rental. Efforts to raise awareness and solve problems related to bicycle use are necessary to change the position of the 28% who refuse to rent a bike.

In future work, we will make a techno-economic feasibility study that will propose the best formula for the implementation of a bike rental system.

Fig. 1 .

 1 Fig. 1. Working methodology

Fig. 3 .

 3 Fig. 3. People surveyed by age and genderFigure4shows a high motorization rate, as nearly 80% of the respondents have at least one car, compared to 40% possessing bike.

Fig. 4 .

 4 Fig. 4. Motorization rate Figures 5 and 6 represent the daily frequency of travel for work or school/University and other stuff (leisure, shopping, etc.). As per the results, the majority of respondents make between one and two travel per day for both reasons.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Frequency of travel (A/R) to work or school/university by gender

Fig. 7 .Fig. 9 .

 79 Fig. 7. The method of transportation used to go to work or school/university by gender

Fig. 10 .

 10 Fig. 10. Reason to reject the usage of bike To guarantee their safety, 66% of respondents said they would cycle if there is separate bike path as shown in Fig 11.

Fig. 11 .

 11 Fig. 11. Bike traffic conditions by gender

Fig. 12 .

 12 Fig. 12. Requirement of bike rental by gender

  Respondent uses the motorcycle for the other reason. MEAN-A Respondent uses the bike / MAP for the other reason. N-USE 1-USE Respondent wants to use the bike. 0-USE Respondent refuse to use the bike.

TABLE I .

 I INFORMATION GATHERED VIA THE QUESTIONNAIRE

	Type of information	Detailed information
		Sex ;
		Age ;
	Socio-economic data	socio-professional category ;
		Number of vehicle possessed by family
		(Car, motorcycle, bike);
		Reason of trip ;
		Frequency (A / R) ;
	Traveling habit	Type of transport used ;
		Distance traveled per trip (A or R) in km ;
		Travel time per trip (A or R) in mn ;
		Obstacles encountered ;
	Traveling by bike	Traffic conditions ;
		Requirements for bike rental ;
	B. Questionnaire pre-test

Table 2

 2 below represents the number of explanatory variables used in the model with their modalities

TABLE II .

 II THE EXPLANATORY VARIABLES SELECTED FROM THE LOGIT MODEL

TABLE III .

 III RESULTS OBTAINED FROM THE LOGIT MODEL

	Constant	1587
	Khi-2 (13) = 131.044	R 2 from Nagelkerke	Khi-2 (8) = 7.176
	P = 0.000	= 0.331	P = 0.518
			Explanatory	β	Exp β	Sig
			variables
			CSP1	0.767	2.153	0.311
			CSP2	1.887	6.598	0.005
			CSP3	1.115	3.050	0.140
			CSP4	1.661	5.263	0.013
			CSP5	1.962	7.113	0.047
			CSP6	1.223	3.397	0.097
			CSP7	1.950	7.026	0.011
			CSP8	Ref
			1-USE	2.182	8.860	0.000
			0-USE	Ref
			0I-WEATHER	1.018	2.767	0.014
			1I-WEATHER	Ref
			MEAN-V	0.721	2.057	0.009
			MEAN-B	1.331	3.784	0.008
			MEAN-T	2.001	7.399	0.000
			MEAN-M	-0.989	0.372	0.040
			MEAN-A	Ref