Xavier Bonnetain
email: xavier.bonnetain@inria.fr

Léo Perrin
email: leo.perrin@inria.fr

Shizhu Tian
email: tianshizhu@iie.ac.cn

Anomalies and Vector Space Search: Tools for S-Box Analysis

Keywords: S-Box, Vector space search, BCT, Shannon effect, Anomaly, Boolean Functions

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

S-boxes are small functions with an input small enough that they can be specified by their lookup tables. If 𝐹 is an S-box with an 𝑛-bit input then it is feasible to describe it using only the sequence 𝐹 (0), 𝐹 (1), ..., 𝐹 (2 𝑛 -1) since, in the vast majority of the cases, 3 ≤ 𝑛 ≤ 8. S-boxes can therefore correspond to arbitrarily complex functions. In practice, such components are the only source of nonlinearity of many symmetric primitives. Most prominently, the AES [START_REF]Advanced Encryption Standard (AES)[END_REF] uses an 8-bit bijective S-box.

The aim of a block cipher is to simulate a pseudo-random permutation (PRP), meaning that it should not be possible for an attacker given a black box access to a block cipher with a secret key and to a permutation picked uniformly at random to figure out which is which. In this context, it might a priori make intuitive sense for block cipher designers to use (pseudo-)random components to design their algorithm. However, this approach would have substantial shortcomings in practice. For example, a random S-box is a priori hard to implement in hardware, random components are unlikely to yield an easy to analyze cipher, their mediocre properties may imply a higher number of rounds (which would slow the cipher down), and the seeds used to generate its random components would have to be published.

Instead, in practice, S-boxes are constructed taking multiple design requirements into account. For example, the mathematical properties of this component can be leveraged to prove that an algorithm is safe from differential [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF] or linear [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF] cryptanalysis. At the same time, the S-box may be intended to be implemented in hardware or in a bit-sliced fashion, in which case it is necessary to give it a specific structure that will ease such implementations.

While it is easy to compare the properties of two given S-boxes (we can simply compute them and then rank them), it is not trivial to quantify how different they are from an S-box picked uniformly at random with regard to each of their properties. Informally, the comparison with such an "ideal" object will quantify the distance between an S-box and random ones: if the property of the studied S-box is unlikely to occur by chance, then it means that the S-box is much better (or much worse) than average. In this paper, we build upon a framework introduced in [START_REF] Biryukov | On reverse-engineering S-boxes with hidden design criteria or structure[END_REF] to provide both definitions and practical means to compute such probabilities.

Let S 2 𝑛 be the set of all 𝑛-bit permutations and let 𝐹 ∈ S 2 𝑛 . As mentioned above, there are two sets of properties that are relevant when investigating Sboxes: how good their cryptographic properties are and whether or not they have some structure. Hence, in order to compare 𝐹 with a random S-box, we need to be able to answer the following two questions.

1. What is the probability that an S-box picked uniformly in S 2 𝑛 has differential/linear properties at least as good as those of 𝐹 ? 2. How can we recover the structure of 𝐹 (if it has any)?

Answering the first question can also help us better understand the properties of random permutations and thus to better estimate the advantage of an adversary trying to distinguish a (round-reduced) block cipher from a random permutation.

On the other hand, the second one is related to so-called white-box cryptography, i.e. to implementation techniques that will hide a secret from an attacker with a total access to the implementation of the algorithm. In practice, in order to try and hide for instance an AES key, the attacker will only be given access to an implementation relying on big lookup tables that hide the details of the computations. Recovering the original structure of these tables can also be seen as a particular case of S-box reverse-engineering in the sense of [START_REF] Biryukov | On reverse-engineering S-boxes with hidden design criteria or structure[END_REF].

Our Contributions

A Key Concept: Anomalies. We answer the two questions asked above using different variants of a unique approach based on what we call anomalies. Intuitively, an anomaly is a real number that quantifies how unlikely a property is. For example, there are very few differentially-6 uniform 8-bit permutations, 5meaning that the anomaly of this property should be high. However, we could argue that what matters in this case is not just the number of differentially-6 uniform permutations but the number of permutations with a differential uniformity at most equal to 6. In light of this, we define anomalies as follows.

Definition 1 (Anomaly). Let 𝐹 ∈ S 2 𝑛 and let 𝑃 be a function mapping S 2 𝑛 to a partially ordered set. The anomaly of 𝑃 (𝐹 ) is defined as A (𝑃 (𝐹 )) = -log 2 (Pr [𝑃 (𝐺) ≤ 𝑃 (𝐹 )]), where the probability is taken over 𝐺 ∈ S 2 𝑛 . We can equivalently write

A (𝑃 (𝐹 )) = -log 2 ( ⃒ ⃒ { 𝐺 ∈ S 2 𝑛 , 𝑃 (𝐺) ≤ 𝑃 (𝐹 ) }⃒ ⃒ |S 2 𝑛 | )
.

The negative anomaly of 𝑃 (𝐹 ) is A (𝑃 (𝐹 )) = -log 2 (Pr [𝑃 (𝐺) ≥ 𝑃 (𝐹 )]).

Regardless of 𝑃 , we always have 2 -A(𝑃 (𝐹 )) + 2 -A(𝑃 (𝐹 )) = 1 + Pr [𝑃 (𝐺) = 𝑃 (𝐹 )].

In the example given above, 𝑃 is simply the function returning the differential uniformity of a permutation. The anomaly of the differential uniformity then gets higher as the differential uniformity of 𝐹 decreases under the median differential uniformity as there are fewer permutations with a low differential uniformity. At the same time, the negative anomaly of the differential uniformity increases as the differential uniformity increases above its median value. To put it differently, the anomaly of 𝑃 (𝐹 ) quantifies how many S-boxes are at least as good 6 as 𝐹 in terms of 𝑃 , and the negative one how many are at least as bad as 𝐹 . In this paper, we study different anomalies and design new tools that allow their estimation for any S-box.

A property with a high anomaly can be seen as distinguisher in the usual sense, i.e. it is a property that differentiates the object studied from one picked uniformly at random. However, unlike usual distinguishers, we do not care about the amount of data needed to estimate the probabilities corresponding to the anomalies.

Statistical Anomalies. In [START_REF] Biryukov | On reverse-engineering S-boxes with hidden design criteria or structure[END_REF] and [START_REF] Perrin | Partitions in the S-box of Streebog and Kuznyechik[END_REF], the notions of "differential" and "linear" anomalies were introduced. Definition 1 is indeed a generalization of them. They are based on properties 𝑃 that correspond to how good the differential and linear properties are. In Section 2, we generalize this analysis to take into account the corresponding negative anomalies, and we introduce the use of the so-called Boomerang Connectivity Table (BCT) [START_REF] Cid | Boomerang connectivity table: A new cryptanalysis tool[END_REF] for this purpose. To this end, we establish the distribution of the coefficients of the BCT of a random permutation. As an added bonus, this new result allows a better estimation of the advantage of an adversary in a boomerang attack.

Structural Anomalies. Anomalies can also be related to the presence of a structure. For example, for 𝑛-bit Boolean functions, the existence of a simple circuit evaluating a function is unlikely:

"almost all functions" of 𝑛 arguments have "an almost identical" complexity which is asymptotically equal to the complexity of the most complex function of 𝑛 arguments. This statement of Lupanov [START_REF] Lupanov | On Networks Consisting of Functional Elements with Delays[END_REF] summarizes the so-called Shannon effect [START_REF] Shannon | The synthesis of two-terminal switching circuits[END_REF]. In other words, the existence of a short description is an unlikely event for a Boolean function. Here, we generalize this observation to permutations of F 𝑛 2 and construct anomalies that capture how "structured" an S-box is.

In Section 3, we present an estimation of the number of permutations that can be constructed using common S-box generation methods (multiplicative inverse, Feistel networks...) and derive the corresponding anomalies. In order to identify these anomalies, it is necessary to recover said structures when they are unknown. We present a simple approach applicable to inversion-based S-boxes that we successfully apply to the 8-bit S-box of the leaked German cipher Chiasmus. In other cases, we show that the detection of structures with a high anomaly can be performed using a vector space search.

Vector Space Search. We provide an efficient algorithm performing this search: given a set 𝒮 of elements of {0, 1} 𝑛 and an integer 𝑑, this algorithm returns all the vector spaces of dimension 𝑑 that are fully contained in 𝒮. We present it in Section 4. While such an algorithm is needed when looking for a structure in an S-box, we expect it to find applications beyond this area.

Mathematical Background

Boolean Functions. Let F 2 = {0, 1}. In what follows, we consider the following subsets of the set of all functions mapping F 𝑛 2 to itself.

-Recall that the set of all 𝑛-bit permutations is denoted

S 2 𝑛 . It contains 2 𝑛 ! elements. The compositional inverse of 𝐹 ∈ S 2 𝑛 is denoted 𝐹 -1 . -The set of all 𝑛-bit linear permutations is denoted ℒ 2 𝑛 . Its size is such that |ℒ 2 𝑛 | = ∏ 𝑛-1 𝑖=0 (2 𝑛 -2 𝑖 ).
For elements of F 𝑛 2 , "+" denotes the characteristic-2 addition, i.e. the XOR. In cases that might be ambiguous, we use "⊕" to denote this operation.

Let 𝐹 ∈ S 2 𝑛 be an S-box. Many of its cryptographic properties can be described using 2 𝑛 × 2 𝑛 tables: the LAT, DDT and BCT. They are defined below. ) where 𝑥•𝑦 = ⨁ 𝑛-1 𝑖=0 𝑥 𝑖 ×𝑦 𝑖 is the scalar product of two elements 𝑥 = (𝑥 0 , ..., 𝑥 𝑛-1 ), 𝑦 = (𝑦 0 , ..., 𝑦 𝑛-1 ) ∈ F 𝑛 2 . Its maximum for 𝑏 ̸ = 0 is the linearity of 𝐹 and is denoted ℓ(𝐹 ). The LAT is used to study linear cryptanalysis [START_REF] Tardy-Corfdir | A known plaintext attack of FEAL-4 and FEAL-6[END_REF][START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF]. The set of the coordinates of the coefficients equal to 0 plays a special role, as shown in [START_REF] Canteaut | On CCZ-equivalence, extended-affine equivalence, and function twisting[END_REF]. It is called the Walsh zeroes of 𝐹 and is denoted

The Linear Approximation Table (LAT) of 𝐹 is the table 𝒲

𝐹 with coefficients 𝒲 𝐹 (𝑎, 𝑏) = ∑ 𝑥∈F 𝑛 2 (-1) 𝑎•𝑥+𝑏•𝐹 (𝑥
𝒵 𝐹 = {(𝑎, 𝑏) ∈ (F 𝑛 2 ) 2 | 𝒲 𝐹 (𝑎, 𝑏) = 0} ∪ {(0, 0)}. The Difference Distribution Table (DDT) of 𝐹 is the table 𝛿 𝐹 with coeffi- cients 𝛿 𝐹 (𝑎, 𝑏) = # {𝑥 ∈ F 𝑛 2 , 𝐹 (𝑥 + 𝑎) + 𝐹 (𝑥) = 𝑏}.
Its maximum for 𝑎 ̸ = 0 is the differential uniformity of 𝐹 and is denoted 𝑢(𝐹 ). The DDT is needed to study differential cryptanalysis [START_REF] Biham | Differential cryptanalysis of Feal and N-hash[END_REF].

Recently

ℬ 𝐹 (𝑎, 𝑏) = # { 𝑥 ∈ F 𝑛 2 , 𝐹 -1 (𝐹 (𝑥) + 𝑏) + 𝐹 -1 (𝐹 (𝑥 + 𝑎) + 𝑏) = 𝑎 } .
Its maximum value for 𝑎, 𝑏 ̸ = 0 is the boomerang uniformity of 𝐹 and is denoted 𝛽 𝐹 . As hinted by its name, the BCT is relevant when studying boomerang attacks [START_REF] Wagner | The boomerang attack[END_REF]. Unlike the DDT and LAT, it is necessary that 𝐹 is a permutation for the BCT to be well defined.

Statistics. Some of our results rely on both the binomial and Poisson distribution. We denote with Binomial(𝑛, 𝑝) the binomial distribution with parameters 𝑝 and 𝑛 which correspond respectively to the probability of an event and to the number of trial. It is defined as follows:

Pr [𝑋 = 𝑖] = Binomial(𝑖; 𝑛, 𝑝) = 𝑝 𝑖 (1 -𝑝) 𝑛-𝑖 ( 𝑛 𝑖 ) .
It has a mean equal to 𝑛𝑝 and a variance of 𝑛𝑝(1 -𝑝). The Poisson distribution with parameter 𝜆 is defined by

Pr [𝑋 = 𝑖] = Poisson(𝑖; 𝜆) = 𝑒 -𝜆 𝜆 𝑖 𝑖! .
The mean value and variance of this distribution are both 𝜆. A binomial distribution with small 𝑝 can be closely approximated by a Poisson distribution with 𝜆 = 𝑛𝑝.

Statistical Properties

Let us consider a permutation 𝐹 that is picked uniformly at random from S 2 𝑛 and let us consider one of its tables, i.e. its DDT, LAT or BCT. The coefficients in this table may be connected to one another: for example the sum of the coefficients in a row of the DDT have to sum to 2 𝑛 . Yet, in practice, the coefficients act like independent and identically distributed random variables. In Section 2.1), we recall what the distributions of the DDT and LAT coefficients are and we establish the distribution of the BCT coefficients. Then, Section 2.2 presents how the knowledge of these distributions can be used to bound the probability that a random permutation has differential/linear/boomerang properties at least as good as those of the S-box investigated. Additionally, we explain in Section 2.3 how our newly gained knowledge of the distribution of the BCT coefficients allows a better estimation of the advantage of the attacker in a boomerang attack.

Coefficient Distributions

In [START_REF] Daemen | Probability distributions of correlation and differentials in block ciphers[END_REF], the authors established and experimentally verified the distribution followed by the DDT and LAT coefficients. The distribution of the LAT coefficients was first established in [START_REF] O'connor | Properties of linear approximation tables[END_REF] and then provided a different expression in [START_REF] Daemen | Probability distributions of correlation and differentials in block ciphers[END_REF]. A more thorough study of the DDT coefficient can be found in [START_REF] O'connor | On the distribution of characteristics in bijective mappings[END_REF]. We recall these results in the following two theorems.

Proposition 1 (DDT coefficient distribution [START_REF] Daemen | Probability distributions of correlation and differentials in block ciphers[END_REF]). The coefficients in the DDT of a random S-Box of S 2 𝑛 with 𝑛 ≥ 5 are independent and identically distributed random variables following a Poisson distribution Poisson(2 -1 ).

Proposition 2 (LAT coefficient distribution [START_REF] O'connor | Properties of linear approximation tables[END_REF][START_REF] Daemen | Probability distributions of correlation and differentials in block ciphers[END_REF]). The coefficients in the LAT of a random permutation7 of S 2 𝑛 are independent and identically distributed random variables with the following probability distribution:

Pr [𝒲 𝐹 (𝑖, 𝑗) = 4𝑧] = ( 2 𝑛-1 2 𝑛-2 +𝑧 )2 ( 2 𝑛 2 𝑛-1 ) .
The situation is the same for the BCT. In order to establish the distribution of the non-trivial coefficients of the BCT of a random permutation, we first recall an alternative definition of the BCT that was introduced in [START_REF] Li | New results about the boomerang uniformity of permutation polynomials[END_REF].

Proposition 3 (Alternative BCT definition [START_REF] Li | New results about the boomerang uniformity of permutation polynomials[END_REF]). Let 𝐹 ∈ S 2 𝑛 be a permutation. For any 𝑎, 𝑏 ∈ F 𝑛 2 , the entry ℬ 𝐹 (𝑎, 𝑏) of the BCT of 𝐹 is given by the number of solutions in F 𝑛 2 × F 𝑛 2 of the following system of equations

{ 𝐹 -1 (𝑥 + 𝑏) + 𝐹 -1 (𝑦 + 𝑏) = 𝑎 𝐹 -1 (𝑥) + 𝐹 -1 (𝑦) = 𝑎 . (1)
We use this theorem to obtain the distribution of the coefficients in the BCT.

Theorem 1 (BCT coefficient distribution). If 𝐹 is picked uniformly at random in S 2 𝑛 , then its coefficients with 𝑎, 𝑏 ̸ = 0 can be modeled like independent and identically distributed random variables with the following distribution:

Pr [ℬ 𝐹 (𝑎, 𝑏) = 𝑐] = ∑ 2𝑖1+4𝑖2=𝑐 𝑃 1 (𝑖 1 )𝑃 2 (𝑖 2 ) ,
where 𝑃 1 and 𝑃 2 are stochastic variable following binomial distributions:

𝑃 1 (𝑖) = Binomial ( 𝑖; 2 𝑛-1 , 1 2 𝑛 -1 ) and 𝑃 2 (𝑖) = Binomial ( 𝑖; 2 2𝑛-2 -2 𝑛-1 , 1 (2 𝑛 -1) 2 ) .
Proof. For any 𝑥, 𝑦 ∈ F 𝑛 2 such that 𝑥 ̸ = 𝑦, we define 𝑆 𝑥,𝑦 = {(𝑥, 𝑦), (𝑦, 𝑥), (𝑥 + 𝑏, 𝑦 + 𝑏), (𝑦 + 𝑏, 𝑥 + 𝑏)} , which is of cardinality 4 unless 𝑥 + 𝑦 = 𝑏, in which case it only contains 2 elements. These sets are such that a pair (𝑥, 𝑦) is a solution of System (1) if and only if all the elements in 𝑆 𝑥,𝑦 are as well. In order to prove this theorem, we will partition the set of all pairs of elements of F 𝑛 2 into such sets 𝑆 𝑥,𝑦 . To this end, we consider the following equivalence relation: (𝑥, 𝑦) ∼ (𝑥 ′ , 𝑦 ′ ) if and only if the multisets 𝑆 𝑥,𝑦 and 𝑆 𝑥 ′ ,𝑦 ′ are identical. The corresponding equivalence classes are of size 4 except when 𝑥+𝑦 = 𝑏, in which case they contain only 2 elements. There are in total 2 𝑛-1 classes of size 2. As there are 2 𝑛 (2 𝑛 -1) ordered pairs of elements in F 𝑛 2 , we deduce that there are

( 2 𝑛 (2 𝑛 -1) -2 × 2 𝑛-1 ) /4 classes of cardinality 4, i.e. 2 2𝑛-2 -2 𝑛-1 .
Then, in order for System (1) to have exactly 𝑐 solutions, we need that there exists 𝑖 1 solutions in classes of size 4 and 𝑖 2 in classes of size 2, where 2𝑖 1 +4𝑖 2 = 𝑐. We deduce that

Pr [ℬ 𝐹 (𝑎, 𝑏) = 𝑐] = ∑ 2𝑖1+4𝑖2=𝑐 𝑃 1 (𝑖 1 )𝑃 2 (𝑖 2 ) ,
where 𝑃 1 (𝑖 1 ) (respectively 𝑃 2 (𝑖 2 )) is the probability that there exists 𝑖 1 classes of size 4 (resp. 2) that are solutions of System (1). Let us now prove that the distributions of 𝑃 1 (𝑖 1 ) and 𝑃 2 (𝑖 2 ) are as stated in the theorem.

Size 2. In this case, it holds that 𝑦 = 𝑥 + 𝑏 so that the lines of System (1) are identical. We assume that 𝐹 -1 (𝑥) + 𝐹 -1 (𝑥 + 𝑏) = 𝑎 holds with probability 1/(2 𝑛 -1) as 𝐹 -1 (𝑥) + 𝐹 -1 (𝑥 + 𝑏) can take any value in F 𝑛 2 ∖{0}. Since there are 2 𝑛-1 such pairs, 𝑃 1 (𝑖 1 ) corresponds to a binomial distribution with 2 𝑛-1 repetitions of a Bernoulli trial that succeeds with probability (2 𝑛 -1) -1 . Size 4. The two equations of System (1) are now independent. Using the same reasoning as above, we assume that each line holds with probability 1/(2 𝑛 -1). Since there are 2 2𝑛-2 -2 𝑛-1 such pairs, 𝑃 2 (𝑖 2 ) corresponds to a binomial distribution with parameters 2 2𝑛-2 -2 𝑛-1 and (2 𝑛 -1) -2 . ⊓ ⊔

Anomalies in Table Coefficients Distributions

Building upon the general approach presented in [START_REF] Biryukov | On reverse-engineering S-boxes with hidden design criteria or structure[END_REF], we can define several anomalies using the distribution of the coefficients in the tables of a permutation 𝐹 ∈ S 2 𝑛 . We will then be able to estimate the values of the corresponding anomalies using the distributions derived in the previous section.

Maximum Value. For any table, the maximum absolute value of all coefficients is a natural property to use to construct an anomaly as the integers are ordered. Let max 𝑇 : S 2 𝑛 → N be the function mapping a permutation 𝐹 ∈ S 2 𝑛 to the maximum absolute value of the non-trivial coefficients in a table 𝑇 . Then we can use the distributions in Propositions 1 and 2 as well as Theorem 1 to estimate the associated anomalies:

A (max 𝑇 (𝐹 )) = -(2 𝑛 -1) 2 log 2 ⎛ ⎝ max 𝑇 (𝐹 ) ∑ 𝑖=0 𝑝 𝑖 ⎞ ⎠ ,
where 𝑝 𝑖 is the probability that 𝑇 (𝑎, 𝑏) = 𝑖. Indeed, there are only (2 𝑛 -1) 2 non-trivial coefficients in the DDT, LAT and BCT as the first row and column are fixed in each case. The (negative) anomalies corresponding to the differential uniformity, linearity and boomerang uniformity for 𝑛 = 8 are given in the appendix of the full version of this paper [START_REF] Bonnetain | Anomalies and vector space search: Tools for S-box analysis (full version)[END_REF].

Maximum Value and Number of Occurrences. In S 2 8 , the anomaly of a differential uniformity of 8 is equal to 16.2 but, for a differential uniformity of 6, it is 164.5. In order to have a finer grained estimate of how unlikely the properties of an S-box are, we combine the maximum coefficient in one of its tables with its number of occurrences as was first done in [START_REF] Biryukov | On reverse-engineering S-boxes with hidden design criteria or structure[END_REF]. For a 2 𝑛 × 2 𝑛 table of integers 𝑇 , let MO be the function such that MO(𝑇 ) = (𝑐, 𝑚) where 𝑐 is the maximum absolute value in 𝑇 and 𝑚 is its number of occurrences (where the first row and column are ignored). The set N × N in which the output of MO lives can be ordered using the lexicographic ordering, i.e. (𝑥, 𝑦) ≤ (𝑥 ′ , 𝑦 ′ ) if and only if 𝑥 < 𝑥 ′ or 𝑥 = 𝑥 ′ and 𝑦 ≤ 𝑦 ′ . We then define the differential, linear and boomerang anomalies of 𝐹 as respectively

A d (𝐹 ) = A (MO(𝛿 𝐹 ))) , A ℓ (𝐹 ) = A (MO(𝒲 𝐹 )) , and A b (𝐹 ) = A (MO(ℬ 𝐹 )) .
This definition of the differential and linear anomalies matches with the one given in [START_REF] Perrin | Partitions in the S-box of Streebog and Kuznyechik[END_REF]. The boomerang anomaly was not used before. We also introduce the negative differential, linear and boomerang anomalies as the corresponding negative anomalies. We estimate these anomalies for a table 𝑇 using the following expression:

A ( MO(𝑇 ) ≤ (𝑐, 𝑚) ) = -log 2 ⎛ ⎝ 𝑚 ∑ 𝑘=0 ( (2 𝑛 -1) 2 𝑘 ) × 𝑝 𝑘 𝑐 × ( 𝑐-1 ∑ 𝑗=0 𝑝 𝑗 ) (2 𝑛 -1) 2 -𝑘 ⎞ ⎠ ,
where 𝑝 𝑖 is the probability that 𝑇 (𝑎, 𝑏) = |𝑖|. For the corresponding negative anomaly, we use the following relation:

2 A(MO(𝑇 )≤(𝑐,𝑚)) + 2 A(MO(𝑇 )≤(𝑐,𝑚)) = 1 + ( (2 𝑛 -1) 2 𝑚 ) 𝑝 𝑚 𝑐 ( 𝑐-1 ∑ 𝑗=0 𝑝 𝑗 ) (2 𝑛 -1) 2 -𝑚 .

Tighter Advantage Estimations for Boomerang Attacks

The coefficient distribution we established in Theorem 1 can also be used to compute the expected value of a BCT coefficient. This in turn implies a better understanding of the advantage an adversary has in a boomerang attack.

Theorem 2. The expected value for each BCT coefficient of a random permutation of S 2 𝑛 converges towards 2 as 𝑛 increases.

Proof. Let 𝐹 ∈ S 2 𝑛 be picked uniformly at random. The expected value 𝐸 of

ℬ 𝐹 (𝑎, 𝑏) is ∑ 2 𝑛 𝑐=0 Pr [ℬ 𝐹 (𝑎, 𝑏) = 𝑐] 𝑐.
Using Theorem 1, we express Pr [ℬ 𝐹 (𝑎, 𝑏) = 𝑐] using two binomial distributions 𝑃 1 and 𝑃 2 so that

𝐸 = 2 𝑛 ∑ 𝑐=0 𝑐 × ( ∑ 2𝑖1+4𝑖2=𝑐 𝑃 1 (𝑖 1 )𝑃 2 (𝑖 2 ) ) = 2 𝑛 ∑ 𝑐=0 2 𝑛-1 ∑ 𝑖1=0 2 𝑛-2 ∑ 𝑖2=0 (2𝑖 1 + 4𝑖 2 )𝑃 1 (𝑖 1 )𝑃 2 (𝑖 2 ) × [2𝑖 1 + 4𝑖 2 = 𝑐] ,
where the expression between the brackets is equal to 1 if 2𝑖 1 + 4𝑖 2 = 𝑐, and 0 otherwise. Reordering the sums, we obtain the following expected value:

𝐸 = 2 𝑛-1 ∑ 𝑖1=0 2 𝑛-2 ∑ 𝑖2=0 (2𝑖 1 + 4𝑖 2 )𝑃 1 (𝑖 1 )𝑃 2 (𝑖 2 ) ⏟ ⏞ 𝐸(𝑛) 2 𝑛 ∑ 𝑐=0 [2𝑖 1 + 4𝑖 2 = 𝑐] ⏟ ⏞ ≤1 . (2)
We then approximate the binomial distributions 𝑃 1 and 𝑃 2 by Poisson distributions, namely 𝑃 1 (𝑖) ≈ Poisson(𝑖; 2 -1 ) = 𝑒 -1 2 2 -𝑖 /(𝑖!) and 𝑃 1 (𝑖) ≈ Poisson(𝑖; 4 -1 ) = 𝑒 -1 4 4 -𝑖 /(𝑖!). We get

𝐸(𝑛) = 2 𝑛-1 ∑ 𝑖1=0 2 𝑛-2 ∑ 𝑖2=0 (2𝑖 1 + 4𝑖 2 ) 𝑒 -1 2 2 -𝑖1 𝑖 1 ! 𝑒 -1 4 4 -𝑖2 𝑖 2 ! = 2 𝑛-1 ∑ 𝑖1=1 𝑒 -1 2 ( 1 2 ) 𝑖1-1 (𝑖 1 -1)! 2 𝑛-2 ∑ 𝑖2=0 𝑒 -1 4 ( 1 4 ) 𝑖2 𝑖 2 ! + 2 𝑛-1 ∑ 𝑖1=0 𝑒 -1 2 ( 1 2 ) 𝑖1 𝑖 1 ! 2 𝑛-2 ∑ 𝑖2=1 𝑒 -1 4 ( 1 4 ) 𝑖2-1 (𝑖 2 -1)! .
As all sums converge towards 1 as 𝑛 increases, the limit of 𝐸(𝑛) is 2. On the other hand, we remark that 𝐸 ≤ 𝐸(𝑛) because of Equation ( 2), and that

𝐸 ≥ 2 𝑛-2 ∑ 𝑖1=0 2 𝑛-3 ∑ 𝑖2=0 (2𝑖 1 + 4𝑖 2 )𝑃 1 (𝑖 1 )𝑃 2 (𝑖 2 ) 2 𝑛 ∑ 𝑐=0 [2𝑖 1 + 4𝑖 2 = 𝑐] ⏟ ⏞ =1 = 𝐸(𝑛 -1) , so 𝐸(𝑛 -1) ≤ 𝐸 ≤ 𝐸(𝑛).
As 𝐸(𝑛) converges to 2 as 𝑛 increases, so does 𝐸. ⊓ ⊔

The expected probability of a boomerang characteristic

𝐸 -1 𝑘 (𝐸 𝑘 (𝑥) ⊕ 𝑏) ⊕ 𝐸 -1 𝑘 (𝐸 𝑘 (𝑥 ⊕ 𝑎) ⊕ 𝑏) = 𝑎 is thus 2 1-𝑛
and not 2 -𝑛 as we might expect.

Experimental Results

Verification. To check the validity of our approach to estimate the statistical anomalies, we picked 2 21 permutations from S 2 8 uniformly at random. We then counted the number 𝑁 𝑡 of permutations 𝐹 such that ⌊A(𝐹 )⌋ = 𝑡, and we obtained the following results (only anomalies above 19 are listed):

A ℓ (𝐹 ) : 𝑁 19 = 1, 𝑁 21 = 1 A ℓ (𝐹 ) : 𝑁 19 = 1 A d (𝐹 ) : See below A d (𝐹 ) : 𝑁 20 = 1 A b (𝐹 ) : 𝑁 19 = 3 A b (𝐹 ) : 𝑁 20 = 2 .
We deduce that the anomalies other than A d (𝐹 ) behave as we expect: in a set of size 2 𝑡 , we can expect to see about 1 permutation with an anomaly of 𝑡. However, for A d (𝐹 ), our results do not quite match the theory. Indeed, we have found too many permutations with a high differential anomaly for it to be a coincidence:

A d (𝐹 ) : 𝑁 19 = 7, 𝑁 20 = 8, 𝑁 21 = 2, 𝑁 22 = 1, 𝑁 23 = 2, 𝑁 24 = 1, 𝑁 25 = 1, 𝑁 26 = 1, 𝑁 28 = 1 .
Recall that our estimates of the table-based anomalies rely on the assumption that the coefficients behave like independent random variables. While we experimentally found this assumption to yield accurate models in practice for all tables, it fails to accurately predict the behavior of the maximum value and its number of occurrences in the case of the DDT. S-boxes from the Literature. We computed the statistical anomalies we defined above for several 8-bit S-boxes from the literature that we obtained from [START_REF] Perrin | S-Boxes used in cryptographic schemes[END_REF]. The results are given in Table 1. We also list the number 𝑁 𝑉 of vector spaces of dimension 𝑛 contained in 𝒵 𝑠 ; its importance will appear later in Section 3.

The statistical anomalies of the AES S-box, i.e. of the multiplicative inverse, are unsurprisingly very large. But they are too large: an anomaly cannot be higher than log 2 (|S 2 𝑛 |). Our estimates do not hold for objects with properties as extreme as those of the inverse.

We can derive other results from this table. For example, 2-round SPNs have a high negative boomerang anomaly but 3-round ones loose this property. Classical 3-round Feistel networks, as used in ZUC S0, have a boomerang uniformity which is maximum [START_REF] Boura | Boomerang uniformity of popular S-box constructions[END_REF] so it is not surprising to see that they have a boomerang anomaly so high that we could not compute it. Even though the S-box of Zorro has a modified Feistel structure (it uses a sophisticated bit permutation rather than a branch swap), it still has a high negative boomerang anomaly.

As expected, the S-boxes that were generated using a random procedure have low positive and negative statistical anomalies. The S-box of MD2 was obtained using the digits of 𝜋, that of the newDES from the American declaration of independence, and that of Turing from the string "Alan Turing".

The correlation between the different statistical anomalies seems complex. On the one hand, there are S-boxes with very different linear and differential anomalies despite the fact that the square of the LAT coefficients corresponds to the Fourier transform of the DDT (see e.g. Skipjack). As evidenced by the anomalies of the S-boxes of Kalyna, which were obtained using a hill climbing method optimizing the differential and linear properties [START_REF] Kazymyrov | A method for generation of highnonlinear s-boxes based on gradient descent[END_REF], these improvements lead to an observable increase of the boomerang anomaly but it can be marginal.

Type Cipher A d (𝑠) A d (𝑠) A ℓ (𝑠) A ℓ (𝑠) A b (𝑠) A b (

Identifying Structures

In this section, we go through the most common S-box structures, and present for each of them the density of the set of such S-boxes (up to affine-equivalence) and the methods that can be used to identify them. In practice, S-boxes operating on at least 6 bits usually fall into two categories: those that are based on the inverse in the finite field F 2 𝑛 , and those using block cipher structures.

In both cases, the permutations are usually composed with affine permutations. In the context of white-box cryptography, it is common to compose functions with secret affine permutations so as to obfuscate the logic of the operations used. Hence, for both decomposing S-boxes and attacking white-box implementation, it is necessary to be able to remove these affine layers.

While recovering a monomial structure is simple even when it is masked by affine permutations (see Section 3.1 and our results on the S-box of Chiasmus), it is not the case with block cipher structures. In this section, we show how the the recovery of the pattern used in [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF] to remove the affine layers of the Russian S-box can be efficiently automatized (Section 3.2), and applied to both SPNs (Section 3.3) and Feistel network (Section 3.4). The core algorithm needed for these attacks is one returning all the vector spaces contained in a set of elements of F 𝑛 2 . We will present such an algorithm in Section 4. These techniques allow us to identify the structural anomalies in S-boxes. In order to estimate the anomaly associated with each structure, we upper bound the number of permutation that can be built using each of those that we consider. The corresponding anomalies are summarized in Section 3.5.

Multiplicative Inverse

Such permutations have a very simple structure: there exists two affine permutations 𝐴 : F 𝑛 2 → F 2 𝑛 and 𝐵 : F 2 𝑛 → F 𝑛 2 such that the permutations 𝐹 can be written 𝐹 = 𝐵 ∘ 𝐺 ∘ 𝐴, where 𝐺 is the permutation of F 2 𝑛 defined by 𝐺(𝑥) = 𝑥 2 𝑛 -2 . Their use was introduced in [START_REF] Nyberg | Differentially uniform mappings for cryptography[END_REF]; the AES [START_REF]Advanced Encryption Standard (AES)[END_REF] uses such an S-box.

In practice, the implementation of 𝐺 requires the use of an encoding of the elements of F 2 𝑛 as elements of F 𝑛 2 . Usually, it is achieved by mapping 𝑥 = (𝑥 0 , ..., 𝑥 𝑛-1 ) ∈ F 𝑛 2 to ∑ 𝑛-1 𝑖=0 𝑥 𝑖 𝛼 𝑖 , where 𝛼 ∈ F 2 𝑛 is the root of an irreducible polynomial with coefficients in F 2 of degree 𝑛. However, this encoding can be seen as being part of 𝐴 and 𝐵.

Density of the set.

There is only one function 𝑥 ↦ → 𝑥 2 𝑛 -2 . However, there are fewer than (|ℒ 2 𝑛 |2 𝑛 )

2 distinct permutations affine-equivalent to it. Indeed, (𝑥 × 𝑚) 2 𝑛 -2 = 𝑥 2 𝑛 -2 ×𝑚 2 𝑛 -2 , meaning that for a given pair (𝐴, 𝐵) of permutations of ℒ 2 𝑛 we can define 2 𝑛 -1 pairs (𝐴 𝑖 , 𝐵 𝑖 ) ∈ (ℒ 2 𝑛 ) 2 such that 𝐵 𝑖 ∘𝐺∘𝐴 𝑖 = 𝐵 𝑗 ∘𝐺∘𝐴 𝑗 for all 𝑖, 𝑗. The same reasoning applies to the Frobenius automorphisms because (𝑥 2 𝑖 ) 2 𝑛 -2 = (𝑥 2 𝑛 -2 ) 2 𝑖 . In the end, there are at most

|ℒ 2 𝑛 | 2 ⏟ ⏞ 𝐿 𝐴 and 𝐿 𝐵 × 2 2𝑛 ⏟ ⏞ 𝑐 𝐴 and 𝑐 𝐵 × 1 (2 𝑛 -1) ⏟ ⏞ multiplication × 𝑛 ⏟ ⏞ Frobenius = 2 𝑛 𝑛 × (|ℒ 2 𝑛 |) 2
distinct permutations affine-equivalent to the multiplicative inverse.

How to recognize them? The Chinese cipher SMS4 [START_REF] Diffie | SMS4 encryption algorithm for wireless networks[END_REF] uses an 8-bit S-box whose structure was not explained. This prompted Liu et al. to try and recover said structure [START_REF] Liu | Analysis of the SMS4 block cipher[END_REF]. They successfully identified it as being affine equivalent to the multiplicative inverse using an ad hoc method.

There is a simple test that can be applied to check if a permutation is affineequivalent to the multiplicative inverse when the input/output size is even. Lemma 1. Let 𝑠 : 𝑥 ↦ → 𝑥 2 𝑛 -2 be a permutation of F 2 𝑛 and 𝐹 ∈ S 2 𝑛 with 𝑛 even be such that 𝐹 = 𝐵 ∘ 𝑠 ∘ 𝐴 where 𝐴 : 𝑥 ↦ → 𝐿 𝐴 (𝑥) + 𝑐 𝐴 and 𝐵 : 𝑥 ↦ → 𝐿 𝐵 (𝑥) + 𝑐 𝐵 are affine permutations. Let {(𝑎 𝑖 , 𝑏 𝑖 )} be the set of all coordinates such that 𝛿 𝐹 (𝑎 𝑖 , 𝑏 𝑖 ) = 4. Then it holds that 𝑏 𝑖 = 𝐿 𝐵 ( 𝐿 𝐴 (𝑎 𝑖 ) 2 𝑛 -2 ) for all 𝑖, meaning that 𝑎 𝑖 ↦ → 𝑏 𝑖 and 𝑠 are identical up to translations.

Proof. We have that (𝑥 + 𝑎) 𝑒 + 𝑥 𝑒 = 𝑏 has as many solutions as (𝑦 + 1) 𝑒 + 𝑦 𝑒 = 𝑏/𝑎 𝑒 , meaning that all rows of its DDT contain the same coefficients: 𝛿 𝑠 (𝑎, 𝑏) = 𝛿 𝑠 (1, 𝑏/𝑎 𝑒 ). In the case of the inverse for 𝑛 even, 𝛿 𝑠 (1, 𝑐) ∈ {0, 2} for all 𝑐 ̸ = 1 and 𝛿 𝑠 (1, 1) = 4. Such a function was called locally-APN in [START_REF] Blondeau | Differential properties of 𝑥 ↦ → 𝑥 2 𝑡 -1[END_REF].

In our case, we have that 𝛿 𝐹 (𝑎, 𝑏) = 𝛿 𝑠 ( 𝐿 𝐴 (𝑎), 𝐿 -1 𝐵 (𝑏)

)

. Using the property we just established with 𝑒 = 2 𝑛 -2, we get 𝛿 𝐹 (𝑎, 𝑏) = 𝛿 𝑠 ( 1, 𝐿 -1 𝐵 (𝑏)/(𝐿 𝐴 (𝑎)) 2 𝑛 -2 ) , where the second coordinate simplifies into 𝐿 -1 𝐵 (𝑏) × 𝐿 𝐴 (𝑎). As a consequence, 𝛿 𝐹 (𝑎, 𝑏) = 4 if and only if 𝐿 -1 𝐵 (𝑏) = (𝐿 𝐴 (𝑎))

2 𝑛 -2 , which is equivalent to 𝑏 = 𝐿 𝐵 ( 𝐿 𝐴 (𝑎) 2 𝑛 -2 ) .
In [START_REF] Schuster | Reverse engineering of chiasmus from gstool[END_REF] and [START_REF] Schejbal | Reverse engineering of chiasmus from gstool[END_REF], two separate teams independently recovered the secret block cipher Chiasmus from an encryption tool called GSTOOL. Chiasmus is a German designed 64-bit block cipher which uses two S-boxes 𝑆 and 𝑆 -1 . Schuster had the intuition that it was built similarly to the AES S-box. He was right. Using Lemma 1 and the linear equivalence algorithm of [START_REF] Biryukov | A toolbox for cryptanalysis: Linear and affine equivalence algorithms[END_REF], we found that the S-box of Chiasmus is also based on a finite field inversion. However, unlike in the AES, it uses two affine mappings with non-zero constants. A script generating the S-box of Chiasmus is provided in the appendix of the full version of this paper [START_REF] Bonnetain | Anomalies and vector space search: Tools for S-box analysis (full version)[END_REF]. The S-box itself can be found in a SAGE [START_REF] Developers | SageMath, the Sage Mathematics Software System[END_REF] module [START_REF] Perrin | S-Boxes used in cryptographic schemes[END_REF].

We could also have recovered this structure using directly the algorithm of Biryukov et al. [START_REF] Biryukov | A toolbox for cryptanalysis: Linear and affine equivalence algorithms[END_REF] or the more recent one of Dinur [START_REF] Dinur | An improved affine equivalence algorithm for random permutations[END_REF]. However, the above approach and these algorithms share the same shortcoming when it comes to identifying the structure in an unknown S-box 𝐹 ∈ S 2 𝑛 : if we do not know the exact S-box to which 𝐹 might be affine-equivalent then they cannot be applied. Even if we know that it might be affine-equivalent to an SPN or a Feistel network, we cannot find the corresponding affine masks.

To solve this problem, we identify patterns in the LAT of the permutations with specific structures that are present regardless of the subfunctions they contain. As a consequence, they can always be detected.

TU-Decomposition

The TU-decomposition is a general structure that was first introduced in [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF] where it was shown that the S-box of the latest Russian standards has such a structure. Later, it was encountered again in the context of the Big APN problem, a long standing open question in discrete mathematics. Indeed, the only known solution to this problem is a sporadic 6-bit APN permutation that was found by Dillon et al. [START_REF] Browning | An APN permutation in dimension six[END_REF] and which was proved in [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF] to yield a TUdecomposition. This structure was then further decomposed to obtain the socalled open butterfly. As we will show below, some Feistel and SPN structures also share this decomposition. Thus, the tools that can find TU-decomposition can also be used to identify these structures even in the presence of affine masks.

Definition 2 (TU 𝑡 -decomposition). Let 𝑛 and 𝑡 be integers such that 0 < 𝑡 < 𝑛. We say that 𝐹 ∈ S 2 𝑛 has a TU 𝑡 -decomposition8 if there exists:

a family of 2 𝑛-𝑡 permutations 𝑇 𝑦 ∈ S 2 𝑡 indexed by 𝑦 ∈ F 𝑛-𝑡 2 , a family of 2 𝑡 permutations 𝑈 𝑥 ∈ S 2 𝑛-𝑡 indexed by 𝑥 ∈ F 𝑡 2 , and two linear permutations 𝜇 :

F 𝑛 2 → (F 𝑡 2 × F 𝑛-𝑡

2

) and 𝜂 : (

F 𝑡 2 × F 𝑛-𝑡 2 ) → F 𝑛 2 such that 𝐹 = 𝜂 ∘ 𝐺 ∘ 𝜇, where 𝐺 is the permutation of F 𝑡 2 × F 𝑛-𝑡 2 such that 𝐺(𝑥, 𝑦) = ( 𝑇 𝑦 (𝑥), 𝑈 𝑇𝑦(𝑥) (𝑦) )
. This structure is presented in Figure 1a.

In other words, 𝐹 ∈ S 2 𝑛 has a TU 𝑡 -decomposition if and only if it is affineequivalent to 𝐺 ∈ S 2 𝑛 with the following property: if 𝐺 𝑡 is the restriction of 𝐺 to its 𝑡 bits of highest weight then 𝑥 ↦ → 𝐺 𝑡 (𝑥||𝑎) is a permutation for all 𝑎 ∈ F 𝑛-𝑡 Density of the set. In order to define a permutation with a TU 𝑡 -decomposition, we need to choose 2 𝑛-𝑡 permutations of S 2 𝑡 , 2 𝑡 permutations of S 2 𝑛-𝑡 and two linear permutations operating on 𝑛 bits. However, several of the permutations generated in this way will be identical. Indeed, we can compose each 𝑇 𝑦 with a 𝑡-bit linear permutation 𝛼 ∈ ℒ 2 𝑡 to obtain a permutation 𝑇 ′ 𝑦 = 𝑇 𝑦 ∘ 𝛼. If we use 𝑇 ′ 𝑦 and compose 𝜇 with 𝛼 -1 , then we obtain the same overall permutation as when 𝑇 𝑦 and 𝜇 are used. More equivalent modifications can be made using linear permutations 𝛽 ∈ ℒ 2 𝑛-𝑡 , 𝛾 ∈ ℒ 2 𝑡 and 𝛿 ∈ ℒ 2 𝑛-𝑡 , as summarized in Figure 1b. Hence, the total number of 𝑛-bit permutations with TU 𝑡 -decompositions is at most

#TU 𝑡 ≤ |S 2 𝑡 | 2 𝑛-𝑡 ⏟ ⏞ 𝑇𝑦 × |S 2 𝑛-𝑡 | 2 𝑡 ⏟ ⏞ 𝑈𝑥 ( |ℒ 2 𝑛 | |ℒ 2 𝑡 | × |ℒ 2 𝑛-𝑡 | ) 2 ⏟ ⏞ 𝜇 and 𝜂 .
This quantity is only a bound as permutations that are self affine-equivalent lead to identical permutations with different 𝜇 and 𝜂. We used this bound to compute the anomaly associated to the presence of a TU 𝑡 -decomposition in a permutation. It is given in Section 2.

How to recognize them? Let 𝐹 ∈ S 2 𝑛 be a permutation. As was established in Proposition 6 of [START_REF] Canteaut | On CCZ-equivalence, extended-affine equivalence, and function twisting[END_REF], the presence of a TU 𝑡 -decomposition is equivalent to the presence of a specific vector space of zeroes of dimension 𝑛 in 𝒵 𝐹 . Let us first recall the corresponding proposition in the particular case of permutations.

Proposition 4 ( [START_REF] Canteaut | On CCZ-equivalence, extended-affine equivalence, and function twisting[END_REF]). Let 𝐹 ∈ S 2 𝑛 and let 𝒵 𝐹 be its Walsh zeroes. Then 𝐹 has a TU 𝑡 -decomposition without any affine layers if and only if 𝒵 𝐹 contains the vector space

{ (0||𝑎, 𝑏||0), 𝑎 ∈ F 𝑡 2 , 𝑏 ∈ F 𝑛-𝑡 2 } .
The advantage of Proposition 4 is that the pattern described depends only on the presence of a TU 𝑡 -decomposition and not on the specifics of the components 𝑇 and 𝑈 . Furthermore, recall that if 𝐺 = 𝐿 2 ∘𝐹 ∘𝐿 1 for some linear permutations

𝐿 1 and 𝐿 2 then 𝒲 𝐺 (𝑎, 𝑏) = 𝒲 𝐹 ( (𝐿 -1 1 ) 𝑇 (𝑎), 𝐿 𝑇 2 (𝑏) ) .
Corollary 1. Let 𝐹 ∈ S 2 𝑛 and let 𝒵 𝐹 be its Walsh zeroes. Then 𝐹 has a TU 𝑡decomposition with linear permutations 𝜇 and 𝜂 if and only if

{( (𝜇 -1 ) 𝑇 (0, 𝑎), 𝜂 𝑇 (𝑏, 0) ) , 𝑎 ∈ F 𝑡 2 , 𝑏 ∈ F 𝑛-𝑡 2 } ⊂ 𝒵 𝐹 .
It is therefore sufficient to look for all the vector spaces of dimension 𝑛 contained in 𝒵 𝐹 to see if 𝐹 has TU 𝑡 -decomposition. If we find a vector space that is not the Cartesian product of a subspace of {(𝑥, 0), 𝑥 ∈ F 𝑛 2 } with a subspace of {(0, 𝑦), 𝑦 ∈ F 𝑛 2 } then 𝐹 does not have a TU 𝑡 -decomposition but there exists a linear function 𝐿 of F 𝑛 2 such that 𝐹 + 𝐿 does [START_REF] Canteaut | On CCZ-equivalence, extended-affine equivalence, and function twisting[END_REF]. Regardless, the key tool that allows the search for TU-decomposition is an efficient algorithm returning all the vector spaces of a given dimension that are contained in a set of elements of F 𝑛 2 . Indeed, finding such vector spaces will allow us to recover all the values of (𝜇 -1 ) 𝑇 (0, 𝑎) and 𝜂 𝑇 (𝑏, 0) for (𝑎, 𝑏) ∈ F 𝑡 2 × F 𝑛-𝑡

2

, from which we will deduce information about 𝜇 and 𝜂. We present such an algorithm in Section 4 and we used it as a subroutine of program finding a TU 𝑡 -decomposition automatically (see the appendix of the full version [START_REF] Bonnetain | Anomalies and vector space search: Tools for S-box analysis (full version)[END_REF]).

As observed in [START_REF] Canteaut | On CCZ-equivalence, extended-affine equivalence, and function twisting[END_REF], the number of vector spaces of dimension 𝑛 in 𝒵 𝐹 is the same as the number of vector spaces of dimension 𝑛 in the set of the coordinates of the zeroes in the DDT. Thus, we could equivalently present our results in terms of DDT.

Substitution-Permutation Networks

An 𝑛-bit SPN interleaves the parallel application of 𝑘 possibly distinct 𝑚-bit Sboxes with 𝑛-bit linear permutations, where 𝑘 × 𝑚 = 𝑛. We use the common [START_REF] Biryukov | Structural cryptanalysis of SASAS[END_REF] notation 𝐴𝑆 to denote a linear layer followed by an S-box layer. A 𝑆𝐴𝑆 structure is depicted in Figure 2a.

Let us estimate the number of 𝑟-round SPNs. As the S-box layers are interleaved with linear layers, we need to consider not the size of S 2 𝑚 but instead the number of linear equivalence classes, which is at most number of permutations with a 𝐴(𝑆𝐴) 𝑟 structure is then at most

|S 2 𝑚 |/|ℒ 2 𝑚 | 2 . The
#𝐴(𝑆𝐴) 𝑟 ≤ ( |S 2 𝑚 | |ℒ 2 𝑚 | 2 ) 𝑟𝑛/𝑚 × |ℒ 2 𝑛 | 𝑟+1 .
The corresponding anomalies for some values of 𝑛 are given in Section 3.5.

How to recognize them? First of all, the algebraic degree of a 2-round SPN is at most equal to 𝑛 -2 [START_REF] Boura | On the influence of the algebraic degree of 𝑓 -1 on the algebraic degree of 𝑔 ∘ 𝑓[END_REF]. Hence, if a permutation is of degree 𝑛 -1, it cannot have such a structure. In Theorem 3, we will establish the existence of specific vector space of zeroes in the LAT of a 2-round SPN. However, in order to properly state this theorem, we first need to introduce the following notion.

Definition 3 (𝑚-Valid minors).

Let 𝑘, 𝑚 and 𝑛 be integers such that 𝑛 = 𝑘 × 𝑚. Let 𝐿 ∈ ℒ 2 𝑛 be a linear permutation. We define it using a 𝑘 2 block matrices 𝐿 𝑖,𝑗 of dimension 𝑚 × 𝑚:

𝐿 = ⎡ ⎣ 𝐿 0,0 ... 𝐿 0,𝑘-1 ... ... 𝐿 𝑘-1,0 ... 𝐿 𝑘-1,𝑘-1 ⎤ ⎦ .
We call a minor of the matrix 𝐿 𝑚-valid if there exists a pair 𝐼, 𝐽 of subsets of {0, ..., 𝑘 -1} which are of the same size 0 < |𝐼| = |𝐽| < 𝑘 and such that the rank of 𝐿 𝐼,𝐽 = [𝐿 𝑖,𝑗 ] 𝑖∈𝐼,𝑗∈𝐽 is equal to 𝑚.

In other words, an 𝑚-valid minor of 𝐿 is a non-trivial minor of 𝐿 that is obtained by taking complete 𝑚-bit chunks of this matrix, and which has maximum rank. Theorem 3. Let 𝐹 ∈ S 2 𝑛 be an ASASA structure built using 𝐿 as its central linear layer and two layers of 𝑚-bit S-boxes. For each 𝐼, 𝐽 {0, ..., 𝑘-1} defining an 𝑚-valid minor of 𝐿, there exists a vector space of zeroes of dimension 𝑛 in 𝒵 𝐹 .

Proof. Because of Corollary 1, we restrict ourselves to the 𝑆𝐴𝑆 structure. If we let the input blocks corresponding to the indices in 𝐼 take all 2 𝑚 |𝐼| possible values, then the output blocks with indices in 𝐽 will also take all 2 𝑚|𝐽| = 2 𝑚|𝐼| possible values. There is thus a corresponding TU 𝑚|𝐼| -decomposition and hence a corresponding vector space in 𝒵 𝐹 . This verification is less efficient than the dedicated cryptanalysis methods presented in [START_REF] Minaud | Key-recovery attacks on ASASA[END_REF]. However, the aim here is not so much to recover the ASASA structure used, it is rather to identify the S-box as having such a structure in the first place. Using the following corollary, we can immediately understand why

𝑁 𝑉 = ( 2×2
2

) = 6 for several S-boxes in Table 1: it is a direct consequence of their 2-round SPN structure and of the strong diffusion of their inner linear layer.

Corollary 2. Let 𝐹 ∈ S 2 𝑛 be the SAS structure built using 𝐿 as its linear layer and two layers of 𝑚-bit S-boxes, where 𝑛 = 𝑘 × 𝑚. If 𝐿 is MDS over the alphabet of S-box words, then 𝒵 𝐹 contains at least ( 2𝑘

𝑘

) vector spaces of dimension 𝑛.

Proof. As 𝐿 is MDS, all its minors and in particular those corresponding to the definition of 𝑚-minors have a maximum rank. There are

∑ 𝑘 𝑖=1 ( 𝑘 𝑖 ) × ( 𝑘 𝑖
) such 𝑚-minors, to which we add the "free" vector space {(𝑥, 0), 𝑥 ∈ F 𝑛 2 } which is always present: there are at least

∑ 𝑘 𝑖=0 ( 𝑘 𝑖 ) 2 = ( 2𝑘 𝑘 )
vector spaces in 𝒵 𝐹 .

Feistel Networks

The Feistel structure is a classical block cipher construction which is summarized in Figure 2b. The number of permutations that are affine-equivalent to 𝑟-round Feistel networks that use permutations as the round functions is at most equal to

|S 2 𝑛/2 | 𝑟 ⏟ ⏞ round funcs. × 1 (2 𝑛 ) ⌈ 𝑛 2 ⌉ ⏟ ⏞ constants × |ℒ 2 𝑛 | 2 ⏟ ⏞ outer layers × 1 |ℒ 2 𝑛/2 | 2 ⏟ ⏞ branch transforms
. Indeed, we can apply 𝑛/2-bit linear permutations 𝐿 and 𝐿 ′ to each branch and, provided that the round functions are modified, we can cancel them out by applying 𝐿 -1 and (𝐿 ′ ) -1 on the output branches. We can also add constants freely to the output of the first ⌈𝑟/2⌉ round functions, as explained in [START_REF] Biryukov | Cryptanalysis of Feistel networks with secret round functions[END_REF].

How to recognize them? There are efficient function-recovery techniques for up to 5-round Feistel networks [START_REF] Biryukov | Cryptanalysis of Feistel networks with secret round functions[END_REF]. However, as soon as affine masks are added, the corresponding techniques can no longer be applied. Still, as with the SPN structure, Feistel networks with few rounds exhibit specific vector spaces in their Walsh zeroes as was already observed for 4-round Feistel network in [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF]. This means that it is possible to detect such structures using the vector spaces in their Walsh zeroes.

Theorem 4 ([7]

). Let 𝐹 be a 4-round Feistel network such that round functions 2 and 3 are permutations. Then 𝒲 𝐹 (𝑥||𝑦, 0||𝑦) = 0 for all 𝑥, 𝑦 in

F 𝑛/2 2 .
This observation also holds for a 3-round Feistel. In fact, there are more vector spaces in such a structure. Theorem 5. Let 𝐹 0 , 𝐹 1 and 𝐹 2 be functions of

F 𝑛/2 2 such that 𝐹 1 ∈ S 2 𝑛/2 . Let 𝐹 ∈ F 𝑛
2 be the 3-round Feistel network using 𝐹 0 , 𝐹 1 and 𝐹 2 as its round functions. Then the set 𝒵 𝐹 contains the following vector spaces of dimension 𝑛:

1. {(𝑥, 0), 𝑥 ∈ F 𝑛 2 }, {(0, 𝑦), 𝑦 ∈ F 𝑛 2 }, 2. { (𝑥||0, 𝑦||0), (𝑥, 𝑦) ∈ F 𝑛/2 2 × F 𝑛/2 2 } , 3. { (𝑥||𝑦, 𝑥||0), (𝑥, 𝑦) ∈ F 𝑛/2 2 × F 𝑛/2 2 } , { (𝑥||0, 𝑥||𝑦), (𝑥, 𝑦) ∈ F 𝑛/2 2 × F 𝑛/2 2 } , 4. { (𝑥||𝑦, 0||𝑦), (𝑥, 𝑦) ∈ F 𝑛/2 2 × F 𝑛/2 2 } , { (0||𝑦, 𝑥||𝑦), (𝑥, 𝑦) ∈ F 𝑛/2 2 × F 𝑛/2 2 } , the fourth category being present if 𝐹 0 and 𝐹 2 are in ∈ S 2 𝑛/2 .
The proof of this theorem follows from direct applications of results in [START_REF] Canteaut | On CCZ-equivalence, extended-affine equivalence, and function twisting[END_REF] and of these observations:

if the 3-round Feistel network implies a specific vector space, it also implies the one with the coordinates swapped because its inverse is also a 3-round Feistel network,

-(𝑥, 𝑦) ↦ → 𝐹 (𝑥, 𝑦) ⊕ (𝑥, 0) is a permutation if 𝐹 1 ∈ S 2 𝑛/2 , and -(𝑥, 𝑦) ↦ → 𝐹 (𝑥, 𝑦) ⊕ (0, 𝑦) has a TU 𝑛/2 -decomposition if 𝐹 2 ∈ S 2 𝑛/2 .
The details are provided in the appendix of the full version [START_REF] Bonnetain | Anomalies and vector space search: Tools for S-box analysis (full version)[END_REF].

Structural Anomalies

In light of our results, we can quantify the anomaly associated to the presence of various structures. In this case, the mapping 𝑃 considered maps S 2 𝑛 to {0, 1}: a permutation has a specific structure or it does not. The anomaly associated to a given structure is then

A structure = -log 2 ( ⃒ ⃒ {𝐺 ∈ S 2 𝑛 , 𝐺 has the structure} ⃒ ⃒ |S 2 𝑛 | ) ,
meaning that the set sizes we extracted above allow us to quantify the anomalies associated to the TU 𝑡 -decomposition, the SPN structure, the Feistel network and the TKlog (see below for the latter). The corresponding anomalies are summarized in Table 2 for different values of 𝑛.

The existence of a TU-decomposition with 𝑡 = 1 for 𝐹 ∈ S 2 𝑛 is equivalent to the presence of a component with a linear structure [START_REF] Canteaut | On CCZ-equivalence, extended-affine equivalence, and function twisting[END_REF], i.e. to the existence of 𝑎 ∈ F 𝑛 2 such that the Boolean function 𝑥 ↦ → 𝑎 • 𝐹 (𝑥) has a probability 1 differential. Thus, the corresponding row of Table 2 gives the anomaly corresponding to linear structures.

We can also compute the anomaly associated to the TKlog structure [START_REF] Perrin | Partitions in the S-box of Streebog and Kuznyechik[END_REF] used in the S-box of Streebog and Kuznyechik [START_REF]Information technology -data security: Hash function[END_REF][START_REF]Information technology -data security: Block ciphers[END_REF] called 𝜋 ∈ S 2 8 . A TKlog is a 2𝑚-bit permutation parametrized by an affine function 𝜅 : F 𝑚 2 → F 2 2𝑚 such that 𝜅(𝑥) = 𝛬(𝑥) ⊕ 𝜅(0) for some linear function 𝛬. This function must be such that Im(𝛬) ∪ F 2 𝑚 spans F 2 2𝑚 . The TKlog also depends on a permutation 𝑠 of S 2 𝑚 -1 . It is defined as follows

⎧ ⎪ ⎨ ⎪ ⎩ 𝜋(0) = 𝜅(0), 𝜋 ( 𝛼 (2 𝑚 +1)𝑗 ) = 𝜅(2 𝑚 -𝑗), for 1 ≤ 𝑗 < 2 𝑚 -1, 𝜋 ( 𝛼 𝑖+(2 𝑚 +1)𝑗 ) = 𝜅(2 𝑚 -𝑖) + 𝛼 (2 𝑚 +1)𝑠(𝑗) , for 𝑖 < 2 𝑚 + 1, 𝑗 < 2 𝑚 -1 , (3)
where 𝛼 is a root of a primitive polynomial 𝑝 of degree 2𝑚, so that 𝛼 2 𝑚 +1 is a multiplicative generator of F * 2 𝑚 . The number of TKlog, is then given by

2𝑚-1 ∏ 𝑖=𝑚 (2 2𝑚 -2 𝑖 ) ⏟ ⏞ 𝛬 × |S 2 𝑚 -1 | ⏟ ⏞ 𝑠 × ( 𝜑(2 2𝑚 -1)/(2𝑚) ) ⏟ ⏞ #primitive polynomials × 2 2𝑚 ⏟ ⏞ 𝜅(0)
where 𝜑 is Euler's totient function. As for the inverse function, the encoding of the elements of F 2 2𝑚 as binary strings can be considered to be part of the outer affine layers. Table 2: Upper bounds on the anomalies of the affine-equivalence to some structures. For the TKlog, "AE" corresponds to permutations affine-equivalent to some TKlog and "pure" to TKLog themselves. 𝑆/𝑟 is the number of S-boxes used in each round, i.e. the number that are applied in parallel.

Vector Spaces Extraction Algorithms

Let 𝒮 be a set of elements of F 𝑛 2 . In this section, we describe an algorithm which extracts all the vector spaces of dimension at least 𝑑 that are completely contained in 𝒮. As established in the previous section, the ability to solve this problem will allow us to identify TU-decompositions, some SPNs, and 3,4-round Feistel networks even in the presence of affine encodings. It can also test the CCZ-equivalence [START_REF] Carlet | Codes, bent functions and permutations suitable for DES-like cryptosystems[END_REF] of a function to a permutation, as was done by Dillon et al. [START_REF] Browning | An APN permutation in dimension six[END_REF] to find the first APN permutation operating on an even number of bits.

Our results can be interpreted using both the ordering relation over the integers and by reasoning over the respective position of the zeroes of the elements in F 𝑛 2 . The following lemma links these two views. Definition 4 (Most Significant Bit). Let 𝑥 ∈ F 𝑛 2 and let us write 𝑥 = (𝑥[0], ..., 𝑥[𝑛 -1]) where 𝑥[0] is the least significant bit. We denote MSB(𝑥) the greatest index 𝑖 such that 𝑥[𝑖] = 1.

Lemma 2. For any 𝑥 ∈ F 𝑛 2 , it holds that

𝑥 < 𝑥 ⊕ 𝑎 ⇔ 𝑥[MSB(𝑎)] = 0 ,
where the order relation is obtained by interpreting 𝑥 and 𝑥 ⊕ 𝑎 as the binary representations of integers.

A Simple Approach and How Ours Improves It

Let us first present a naive approach to solving this problem. At its core, this approach is a tree search that builds the complete vector spaces iteratively.

Starting from a specific element 𝑥 ∈ 𝒮 and vector space 𝑉 𝑥 = {0, 𝑥}, we loop over all the elements 𝑦 such that 𝑦 > 𝑥 and check whether (𝑥 ⊕ 𝑦) ∈ 𝒮, in which case we build 𝑉 𝑥,𝑦 = 𝑉 𝑥 ∪ {𝑦 ⊕ 𝑣, 𝑣 ∈ 𝑉 𝑥 }. We then repeat this process by looking for 𝑧 > 𝑦 such that (𝑧 ⊕ 𝑣) ∈ 𝒮 for all 𝑣 ∈ 𝑉 𝑥,𝑦 . This process can then be iterated until complete bases (𝑥, 𝑦, 𝑧, ...) of vector spaces are found. Our approach is based on the same principles but it significantly outperforms this naive algorithm by solving its two main shortcomings.

First, the basis of a vector space is not unique. The condition that it be ordered, which is implied by the algorithm sketched above, is not sufficient to ensure uniqueness. This implies that the algorithm will be slowed down by the exploration of the branches that actually correspond to identical spaces, and that a post processing checking for duplicated spaces will be needed. Our algorithm will solve this problem and return exactly one basis for each vector space contained in 𝒮. These bases are called Gauss-Jordan Bases (GJB) and are introduced in Section 4.2.

Second, at each iteration, we need to consider all 𝑧 ∈ 𝒮 such that 𝑧 is strictly larger than the largest vector already in the basis being built. In our approach, we update at each iteration a set that contains all the elements 𝑧 that could be used to construct a larger basis using a process which we call vector extraction (see Section 4.3). Like in the algorithm above, this set only contains elements that are strictly greater than the previous bases elements. However, it is also strictly larger than all the elements in the vector space spanned by this basis and its size is reduced by at least a factor 2 at each iteration. Using vector extractions, we can also skip the test that (𝑧 ⊕ 𝑣) ∈ 𝒮 for all 𝑣 in the current vector space which will increase the speed of our algorithm.

Besides, in each iteration, we use a heuristic method to consider only a subset of this set of 𝑧 which is based on the number and positions of its zeroes, the Bigger MSB Condition.

In summary, we improve upon the algorithm above in the following ways:

we construct exactly one basis per vector space contained in 𝒮 (using GJB, see Section 4.2), we significantly reduce the number of vectors that can be considered in the next iterations (using vector extractions, see Section 4.3), and we further decrease the number of vectors that need to be explored at a given iteration using a specific filter (using the Bigger MSB condition, see Section 4.4).

Finally, the vector space extraction algorithm itself is presented in Section 4.5. An algorithm extracting affine spaces which uses the former as a subroutine is presented along with an actual implementation of the vector space algorithm in the appendix of the full version [START_REF] Bonnetain | Anomalies and vector space search: Tools for S-box analysis (full version)[END_REF].

In [START_REF] Canteaut | Finding nonnormal bent functions[END_REF], Canteaut et al. introduced an algorithm which, given an 𝑛-bit Boolean function 𝑓 , lists all the affine spaces of dimension 𝑚 such that 𝑓 is constant (or affine) on them. Our algorithm can easily perform the same task. Indeed, 𝑓 is affine on a subspace 𝑈 if and only if {𝑥||𝑓 (𝑥), 𝑥 ∈ 𝑈 } is an affine subspace, meaning that our affine space search algorithms can list all such spaces.

Using our implementation (see [START_REF] Bonnetain | Anomalies and vector space search: Tools for S-box analysis (full version)[END_REF]), we only need about 12 min to reprove their Fact 22 which deals with a 14-bit Boolean function while they claim a runtime of 50 h in this case. Our machine is more recent and thus likely faster than theirs but not by a factor 250: our algorithm is inherently more efficient. It is also far more versatile, as we have established above.

Gauss-Jordan Bases

These objects are those which our vector space search will actually target. They were described in the context of Boolean functions in [START_REF] Canteaut | Finding nonnormal bent functions[END_REF].

Definition 5 (GJB [START_REF] Canteaut | Finding nonnormal bent functions[END_REF]). For any vector space 𝑉 of dimension 𝑑, the Gauss-Jordan Basis (GJB) of 𝑉 is the set {𝑣 0 , ..., 𝑣 𝑑-1 } such that ⟨𝑣 0 , ..., 𝑣 𝑑-1 ⟩ = 𝑉 which is the smallest such set when sorted in lexicographic order.

For any space 𝑉 there is exactly one GJB. Indeed, we can write down all of its bases, sort the elements in each of them in increasing order and then sort the reordered bases in lexicographic order. This implies that 𝑣 𝑖 < 𝑣 𝑖+1 for all 𝑖. Some key properties of GJBs are given by the following lemma. Lemma 3. GJBs have the following properties.

1. If {𝑣 0 , ..., 𝑣 𝑖 } is the GJB of ⟨𝑣 0 , ..., 𝑣 𝑖 ⟩ then {𝑣 0 , ..., 𝑣 𝑖-1 } is a GJB.

3. If {𝑣 0 , ..., 𝑣 𝑑-1 } is a GJB then, for all 𝑗 ∈ {0, ..., 𝑑-1}, ⟨𝑣 0 , ..., 𝑣 𝑑-1 ⟩ contains exactly 2 𝑗 elements 𝑥 such that MSB(𝑥) = MSB(𝑣 𝑗 ).

Proof. We prove each point separately.

Point 1. A basis of ⟨𝑣 0 , ..., 𝑣 𝑖-1 ⟩ lexicographically smaller than {𝑣 0 , ..., 𝑣 𝑖 } could be used to build a basis of ⟨𝑣 0 , ..., 𝑣 𝑖 ⟩, lexicographically smaller than its GJB, which is impossible.

Point 2. We prove each direction of the equivalence separately.

⇒ Suppose that {𝑣 0 , ..., 𝑣 𝑑-1 } is indeed a GJB. Then MSB(𝑣 𝑗 ) = MSB(𝑣 𝑗+1 ) would imply that MSB(𝑣 𝑗 ⊕ 𝑣 𝑗+1 ) < MSB(𝑣 𝑗 ) which, in particular, would imply that 𝑣 𝑗 ⊕𝑣 𝑗+1 < 𝑣 𝑗 . This would contradict that {𝑣 0 , ..., 𝑣 𝑑-1 } is a GJB. Similarly, MSB(𝑣 𝑗 ) > MSB(𝑣 𝑗+1 ) would imply 𝑣 𝑗 > 𝑣 𝑗+1 which is also a contradiction. We deduce that MSB(𝑣 𝑗 ) < MSB(𝑣 𝑗+1 ) for any 0 ≤ 𝑗 < 𝑑 -1. Suppose now that 𝑣 𝑖 [MSB(𝑣 𝑗 )] = 1 for some 𝑗 < 𝑖. We deduce from Lemma 2 that 𝑣 𝑖 ≥ 𝑣 𝑖 ⊕ 𝑣 𝑗 , which is again a contradiction because {𝑣 0 , ..., 𝑣 𝑑-1 } is minimal. We have thus established that if {𝑣 0 , ..., 𝑣 𝑑-1 } is a GJB then it must satisfy the conditions in Equation ( 4). ⇐ Let us now assume that these conditions hold. In this case, we have that 𝑣 𝑖 < 𝑣 𝑖 ⊕ ⨁ 𝑗∈𝐼 𝑣 𝑗 for any subset 𝐼 of {0, ..., 𝑖 -1} because the MSB of ⨁ 𝑗∈𝐼 𝑣 𝑗 is always strictly smaller than MSB(𝑣 𝑖 ) and because of Lemma 2. Thus, adding 𝑣 𝑖 at the end of {𝑣 0 , ..., 𝑣 𝑖-1 } yields a GJB of ⟨𝑣 0 , ..., 𝑣 𝑖 ⟩. A simple induction then gives us the result.

Point 3. Using the first point of this lemma allows us to proceed via a simple induction over the size of the basis. If the basis is simply {𝑣 0 } then the lemma obviously holds. Then, adding an element 𝑣 𝑑 to the end of a GJB of size 𝑑 will add 2 𝑑 elements 𝑥 such that MSB(𝑥) = MSB(𝑣 𝑑 ).

⊓ ⊔

The last point of Lemma 3 allows a significant speed up of the search for such GJBs. To describe it, we introduce the following concept. The following lemma provides a necessary condition for some 𝑒 0 ∈ 𝒮 to be the first element of a GJB of size 𝑑. This lemma provides an efficient filter to know whether 𝑥 can be the start of a GJB of size 𝑑 which depends only on the MSB of 𝑥, so that it does not need to be evaluated for all 𝑥 ∈ 𝒮 but only once for each subset of 𝒮 with a given MSB.

Vector Space Extraction Algorithm

Algorithm 1 GJBExtraction algorithm. for all 𝑎 ∈ 𝜑 𝑑 (𝒮) do 4:

𝑠𝑎 ← 𝒳𝑎(𝒮) 5:

if |𝑠𝑎| ≥ 2 𝑑-1 -1 then 6:

ℒ ′ ← GJBExtraction (𝑠𝑎, max(𝑑 -1, 0)) 7:

for all 𝐵 ∈ ℒ ′ do 8:

Add the GJB ({𝑎} ∪ 𝐵) to ℒ 9:

end for 10:

end if 11:

end for 12:

return ℒ 13: end function If we let 𝜑 𝑑 be the identity then we can directly deduce from Theorem 6 and Corollary 4 that GJBExtraction (as described in Algorithm 1) returns the unique GJBs of each and every vector space of dimension at least equal to 𝑑 that is included in 𝒮.

This algorithm can be seen as a tree search. The role of 𝜑 𝑑 is then to cut branches as early as possible by allowing us to ignore elements that cannot possibly be the first element of a base of size 𝑑 by implementing the Bigger MSB Condition of Lemma 5: Note that we only need to try and build such a sequence of increasing 𝑚 𝑗 once for each value of MSB(𝑥) for 𝑥 ∈ 𝒮. It is possible to check for the existence of such a sequence in a time proportional to |𝒮|.

Conclusion

We have presented a comprehensive list of anomalies quantifying how unlikely the properties of a given S-box are. These can be of a statistical nature and we have pioneered the use of the BCT for this purpose. They can also correspond to the presence of a specific structure, many of which are particular cases of the TU-decomposition. To find TU-decompositions, we presented an efficient vector space algorithm which can be of independent interest. We have also showed how finding TU-decompositions can help bypass affine masks for several S-box structures.

We can apply our results to 𝜋, the 8-bit S-box used by both Streebog [START_REF]Information technology -data security: Hash function[END_REF] and Kuznyechik [START_REF]Information technology -data security: Block ciphers[END_REF]. It has very high anomalies (see Table 3) which means that the set of S-boxes with as strong a structure as the TKlog found in 𝜋 is very small. This observation is coherent with the claim of [START_REF] Perrin | Partitions in the S-box of Streebog and Kuznyechik[END_REF] that the structure of 𝜋 was deliberately inserted by its designers. Table 3: Some of the anomalies of 𝜋.

We finally list some open problems that we have identified while working on this paper.

Open Problem 1. How can we better estimate the differential anomaly? Open Problem 2. Why are there so many vector spaces in 𝒵 𝐹 when 𝐹 is a 3-round Feistel network of S 2 8 ?

6 Acknowledgement

  Composing its components with linear permutations.

Fig. 1 :

 1 Fig. 1: Two functionally equivalent permutations.

Fig. 2 :

 2 Fig. 2: Two block-cipher-like S-box structures.

Definition 6 (

 6 MSB spectrum). Let 𝒮 be a set of elements inF 𝑛 2 . The MSB spectrum of 𝒮 is the sequence {N 𝑖 (𝒮)} 0≤𝑖<𝑛 such that N 𝑖 (𝒮) = # {𝑥 ∈ 𝒮, MSB(𝑥) = 𝑖} .Corollary 3 (MSB conditions). If a set 𝒮 of elements from F 𝑛 2 contains a vector space of dimension 𝑑, then there must exist a strictly increasing sequence{𝑚 𝑗 } 0≤𝑗≤𝑑-1 of length 𝑑 such that N 𝑚𝑗 (𝑆) ≥ 2 𝑗 .Lemma 4. Let 𝒮 be a set of elements in F 𝑛 2 and let 𝑎 ∈ 𝒮. Then we have 𝒳 𝑎 (𝒮) = 𝑛 ⋃ 𝑖=MSB(𝑎)+1 𝒳 𝑎 ({𝑥 ∈ 𝒮, MSB(𝑥) = 𝑖}) 4.4 Bigger MSB Condition

Lemma 5 (

 5 Bigger MSB condition). If 𝑒 0 is the first element in a GJB of size 𝑑 of elements of a set 𝒮 of elements in F 𝑛 2 , then 𝒮 ′ defined as 𝒮 ′ = {𝑥 ∈ 𝒮, MSB(𝑥) > MSB(𝑒 0 )} must satisfy the MSB condition of Corollary 3 for dimension 𝑑 -1, i.e. there is a strictly increasing sequence {𝑚 𝑗 } of length 𝑑 -1 such that # {𝑥 ∈ 𝒮, MSB(𝑥) = 𝑚 𝑗 } > 2 𝑗 .

1 :

 1 function GJBExtraction(𝒮, 𝑑)

  𝑎 ∈ 𝜑 𝑑 (𝒮) if and only if ∃{𝑚 𝑗 } 0≤𝑗<𝑑 , { 𝑚 𝑗+1 > 𝑚 𝑗 > MSB(𝑎) , # {𝑥 ∈ 𝒮, MSB(𝑥) = 𝑚 𝑗 } > 2 𝑗 .

5 †

 5 This anomaly might be overestimated (Sect. 2.4).

  , Cid et al. introduced a new tool which they called Boomerang Connectivity Table (BCT) [17]. It is again a 2 𝑛 × 2 𝑛 table ℬ 𝐹 defined by

Table 1 :

 1 The statistical anomalies and number of vector spaces for some S-boxes from the literature.

	𝑠)	𝑁𝑉 (𝑠)

  2. The basis {𝑣 0 , ..., 𝑣 𝑑-1 } is a GJB if and only if { ∀𝑗 ∈ {0, ..., 𝑑 -2}, MSB(𝑣 𝑗 ) < MSB(𝑣 𝑗+1 ) ∀𝑖 ∈ {1, ..., 𝑑 -1}, ∀𝑗 ∈ {0, ..., 𝑖 -1}, 𝑣 𝑖 [MSB(𝑣 𝑗 )] = 0 .

We formally define differential uniformity later. All that is needed in this discussion is that the differential uniformity is an integer which is better when lower.

In this paper, the properties 𝑃 considered are better when lower.

The distribution of the coefficients in the LAT of random functions (not permutations) is also provided in[START_REF] Daemen | Probability distributions of correlation and differentials in block ciphers[END_REF].

This is a simplified version of the TU𝑡-decomposition compared to[START_REF] Canteaut | On CCZ-equivalence, extended-affine equivalence, and function twisting[END_REF]. Indeed, in that paper, the authors only impose that 𝑇𝑦 ∈ S 2 𝑛-𝑡 ; 𝑈𝑥 may have collisions. Since we are only considering bijective S-boxes here, we consider that 𝑈𝑥 ∈ S 2 𝑡 .

We thank Jérémy Jean for shepherding this paper. We also thank Florian Wartelle for fruitful discussions about vector space search, and Anne Canteaut for proofreading a first draft of this paper. The work of Xavier Bonnetain receives funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 714294acronym QUASYModo). The work of Shizhu Tian is supported by the National Science Foundation of China (No. 61772517, 61772516).

Vector Extractions

We now present a class of functions called extractions which will play a crucial role in our algorithms. We also prove their most crucial properties.

Definition 7 (Extraction). Let 𝑎 ̸ = 0 be some element of F 𝑛 2 . The extraction of 𝑎, denoted 𝒳 𝑎 , is a function mapping a subset 𝒮 of F 𝑛 2 to 𝒳 𝑎 (𝒮), where 𝑥 ∈ 𝒳 𝑎 (𝒮) if and only if all of the following conditions are satisfied:

In particular, 𝒳 𝑎 (𝒮) ⊆ 𝒮. Our algorithm will iterate such extractions to construct smaller and smaller sets without loosing any GJBs. This process is motivated by the following theorem. Theorem 6. Let {𝑣 0 , ..., 𝑣 𝑖-1 } be elements of some subset 𝒮 of F 𝑛 2 such that 0 ∈ 𝒮 and such that 𝑣 𝑗+1 ∈ (𝒳 𝑣𝑗 ∘ ... ∘ 𝒳 𝑣0 )(𝒮) for all 𝑗 < 𝑖. Then it holds that 𝑣 𝑖 ∈ (𝒳 𝑣𝑖-1 ∘ ... ∘ 𝒳 𝑣0 )(𝒮) if and only if ⟨𝑣 0 , ..., 𝑣 𝑖 ⟩ ⊆ 𝒮 and {𝑣 0 , ..., 𝑣 𝑖 } is the GJB of this vector space.

Proof. In order to prove the theorem, we proceed by induction over 𝑖 using the validity of the theorem over bases of size 𝑖 as our induction hypothesis. At step 𝑖, we assume that 𝑣 0 , ..., 𝑣 𝑖 are elements of 𝒮 and that 𝑣 𝑗+1 ∈ (𝒳 𝑣𝑗 ∘ ... ∘ 𝒳 𝑣0 )(𝒮) for all 𝑗 < 𝑖.

Evaluating 𝒳 𝑎 imposes a priori to look whether 𝑥 ⊕ 𝑎 belongs in 𝒮 for all 𝑥 ∈ 𝒮 such that 𝑥 < 𝑥 ⊕ 𝑎. This verification can be implemented efficiently using a binary search when 𝒮 is sorted. We can make it even more efficient using the following lemma.


domain: spi phys

text:
David Delhaye
email: david.delhaye@onera.fr

Ismael K Ortega

Fabrice Graude

Pascal Gabas

Stéphane Pascaud

Helicopter engine particulate matter emissions characterization

Keywords: Soot, biofuel, engine emissions, aviation

Introduction

Aircraft engines undergo a certification process to assure that their emissions full fit the actual regulations. In this process both gases (CO 2 , CO, NO x and unburned hydrocarbons) and nonvolatile particulate matter (nvPM) are measured. nvPM emissions were traditionally addressed by smoke number measurements. However, this method has become obsolete and is currently being revised by the Committee for Aviation Environmental Protection (CAEP). Small engines like auxiliary power units (APU) or helicopter engines are not included in the actual regulation. Therefore, there is only scarce information on emission repertories about them. In the present work we have done a measurement campaign on a helicopter engine working at different engine regime to characterize its emissions. In this campaign the standard gas and smoke number measurements have been combined with Particle number and mass measurements included in the new certification process. In addition we have measured SO 2 and particle size distribution, which are not yet included in the certification protocol.

Methods

Fig. 1 depicts the measurement line used for the measurements. This measurement line was complemented by a gas and a smoke number lines measuring in parallel. In first place we set an exhaust with a valve to reduce the pressure in the line to the atmospheric pressure if needed. After this exhaust, SO 2 and pressure were measured and then we used a splitter to divide the sample flow in three lines. The first one was used to measure the CO 2 , the second one was used to measure particle size distribution (Scanning Mobility Particle Spectrometer) and the third one was treated with a catalytic stripper set at 350 °C to remove the volatile fraction of the sample. After the catalytic stripper the flow was divided again in three. Two lines where used to measure the soot mass (Laser Induced Incandescence) and particle number (Pegasor Particle Sensor at 160°C ) and the third one was again split in to two to measure particle number with two different instruments (Pegasor Particle Sensor at room temperature and a Condensational Particle Counter).

During the test we studied different engine regimes (Fig. 2) Figure 2. Engine regimes studied during the test We will present the impact of engine regime in its emissions, in terms of particle number, mass and size distribution. We will compare the obtained results with smoke number results, searching for a link between both measurements. Finally we will discuss the results concerning the SO 2 measurements and its link with engine regime.

Figure 1 .

 1 Figure 1. Schematic of the instrumental set up

This work was supported by ANTARES project, funded by the European Union's Horizon 2020 program for the Clean Sky Joint Technology Initiative under grant agreement CSJU-CS2-GAM-ENG-2014-15


Philippe Le Corre

P Le

Chinese Investments in European Countries: Experiences and Lessons for the "Belt and Road" Initiative

by the European Commission, with the goal of raising 315 billion euros for stimulating growth and employment. China is expected to contribute 5-10 billion euros to the EFSI. A working group including experts from China's Silk Road Fund, the European Commission, and the European Investment Bank has been set up to explore opportunities for co-financing.

COOPERATION BETWEEN CHINESE INVESTORS AND LOCAL PUBLIC AND PRIVATE ACTORS IN THE INFRASTRUCTURE SECTOR

It has taken some time before Europeans and Chinese started working together. In its three decades of "open door policy" (1978-2008), China was initially a manufacturing country that attracted European companies and others to invest in its industries and market. In China itself, foreign firms were required to engage in joint-venture companies with Chinese partners. China then started hunting for natural resources in places as diverse as Australia, Africa, and Latin America. It only started investing equity outside its borders about 15 years ago. Europe became part of the "going out policy" (Zou Chu Qu 走出去) in 2008 and has since seen a growing number of state-owned enterprises as well as some private companies investing in the EU. [START_REF] Le | China's Offensive in Europe[END_REF] There have been a number of cases in the industrial sector such as the Geely-Volvo partnership in Sweden, Zoomlion-Cifa in Italy, Sany-Putzmeister in Germany, and Dongfang-PSA Peugeot-Citroën in France. A few public-private partnerships have timidly emerged, especially in the UK. In Finland, Tencent acquired Supercell for $7 billion, and in Ireland HNA group bought aircraft leaser Avolon. The year 2016 saw much debate in Germany about Chinese takeovers of technology brands in fields where national security is at risk. For example, in 2016, a Chinese company was barred from acquiring the semi-conductor company Aixtron.

Other challenges have arisen from this new Chinese wave, especially in the field of acculturation. Most Chinese companies have been facing difficulties in adjusting not only to a different business model but also a very different political, social, and economic environment. This may have prevented China from expanding more quickly than it would have liked.

Although transactions between Chinese and European firms have evolved over the years, they are still characterized by snags that are capable of making the negotiations fail at any moment. The list of these obstacles is long: a negotiation that lasted much longer than the standard length in the profession; ignorance of Western business norms and customs on the part of the Chinese participants; constant personnel changes on the teams in place; the drafting of changes, ranging from inserting due diligence clauses to the writing of the final agreements; "resolved" clauses that were regularly put back on the table; unreliable valuations; and financing that was once in place, but is now lost.

The diversity of cultures and languages in Europe has often disarmed Chinese entrepreneurs. Poorly understood by some investors, European law is often perceived as overly favorable to the employees. A Chinese lawyer who has settled in Europe cites as obstacles to investors the authorizations required for overtime work or work outside an employee's gradelevel duties, the tax system, and the role of trade unions. Meanwhile, there is one Chinese characteristic that is proving difficult when dealing with Europeans: All Chinese SOEs and some private companies are tied to entities of the Chinese government or the Communist Party.

Many intended Chinese investments remain unsuccessful for reasons that are often cultural. "Chinese enterprises do not want to admit that they must produce in Europe if they want to be accepted in the long term," stressed a well-known Chinese academic who prefers to remain anonymous. 3 He deplored the "absence of vision" among his compatriots. Different notions of timeliness are indeed among the principal challenges: While Europeans want results right away (or by a fixed date), the Chinese work over the long term, with economies of energy. The contrast is often that between a sprinter and a marathon runner.

The differences are slowly eroding, however. Little by little, Chinese entrepreneurs are using accountants, lawyers, auditing services, bankers, and other professional services. This is particularly true of groups that have international ambitions, those that interest us here. For example, Lenovo, which inherited a mixed corporate culture since the 2005 IBM acquisition, has been practicing intercultural management at the highest level: Its executive committee now includes four mainland Chinese, a Chinese person from Hong Kong, a Dutch national, an American, an Italian, and a Canadian. All its European subsidiaries are run by European managers.

It will take time before Chinese entrepreneurs adjust to the Western business world. Business school training will not be enough as cultural habits and practices dominate, but if the company of the twenty-first century is to be "Sino-Western," both sides will have to engage in a process of mutual understanding. In the past few years, Chinese firms have stepped foot in Europe, but it is especially the case in two singled-out countries which have allowed Chinese equity into some of their key-utilities: Greece, which started welcoming Chinese investors for its port facilities in 2008; and Portugal, which since 2010 has become a key destination for energy-related Chinese companies.

CASE N°1: GREECE'S PIRAEUS HARBOR COSCO-RUN CONTAINER PORT TARGETING EUROPE AND THE BALKANS

As a principal victim of the financial crisis that struck Europe, Greece scarcely hesitated to call upon Chinese entities to invest. The country was encouraged to do so by institutional loaners such as the European Commission, the European Central Bank (ECB), and the International Monetary Fund (IMF). In 2008, the 30-year concession given to the Chinese state-owned shipping giant China Overseas Shipping Group Co. (COSCO) to manage two terminals of the commercial Port of Piraeus, near Athens, for the sum of €490 million (apparently five times more than the market value), constituted one of China's most visible commercial actions in Greece. [START_REF]The port's passenger terminal from which ferries to Greek islands depart is a separate entity from the commercial port[END_REF] COSCO was later given another five-year contract and the right to build a third terminal. In 2013, COSCO chose to increase its investment by renovating-for another €230 million-the existing terminals, thus making Piraeus its port of entry into southern Europe, with the aim of targeting opportunities in the Balkans and Mediterranean countries. [START_REF] Smoltczyk | One Port, Two Worlds: China Seeks Dominance in Athens Harbor[END_REF] When COSCO first arrived in Athens, it was met with a month-and-ahalf-long dockworkers' strike and a banner along the waterfront: "COSCO Go Home." At the time, Piraeus was a struggling harbor worn down by decades of industrial decline and the country's protracted debt crisis. Greece has experienced a punishing economic crisis since then. The unemployment rate at times reached 70% in the Athens suburbs due to a process of deindustrialization and a badly performing shipping industry, which used to be the nation's economic flagship. According to several reports-at least on its Chinese side-the Piraeus port has been transformed by COSCO, even though the company only ran two terminals out of six until April 2016. [START_REF] Meunier | A Tale of Two Ports: the Epic Story of Chinese Direct Investment in the Greek Port of Piraeus[END_REF] COSCO has quadrupled container traffic to just under 3 million units a year. That capacity was to be expanded to 6.2 million units in 2016. "Piraeus has become the story of two worlds-that of the 'turbo capitalism' of the successors to Mao Zedong on one side, and a market economy that can move as slowly as a Socialist one on the other. Some people see the port as an image of the country's future. It's an image that is "a horrific one for many, including a large portion of Syriza voters," a news report stated. 7 The investment ranks as one of the most successful Greek privatizations in recent decades. COSCO has successfully upgraded the infrastructure, introduced more efficient machineries and equipment, dealt with the issues of labor unions, improved the management system, and created more traffic. In 2008, Piraeus moved just 433,582 containers. In 2014, that number grew more than sevenfold to 3.16 million, 80% of which can be attributed to COSCO, which ran Piers II and III, while Greek stateowned OLP port authority ran Pier I. [START_REF] Granitsas | Chinese Transform Greek Port, Winning Over Critics[END_REF] Originally, the Greeks and the Chinese shared processing responsibilities for the containers of MSC, the shipping company. Due to the Greek economic crisis, traffic collapsed between 2011 and 2015. Since MSC and Maersk, the two market leaders, began their 2M Alliance in January 2016, all of the company's containers have been loaded by COSCO on Pier II. COSCO is simply twice as fast as its competitor. COSCO has installed 11 new loading cranes that will put its Piraeus operations roughly on equal footing with the capacity at Rotterdam, Antwerp, and Hamburg, Europe's three busiest container ports. By 2016, the new COSCO-built container terminals employed 1200 workers, "silencing" most union unrest. [START_REF] Smoltczyk | One Port, Two Worlds[END_REF] Chinese leaders have spent a great deal of time visiting Greece. In June 2014, Premier Li Keqiang spent three days in Greece-an exceptional duration for an official trip-which led to no less than 19 cooperation agreements and commercial contracts for a total amount of €3.4 billion.

In January 2015, plans to sell off further port assets, including repair docks as well as car, passenger, and cruise ship terminals, were halted by Alexis Tsipras' newly elected Syriza left-wing government, who decided to take into account the views from the dockworkers' union and the Greek Communist party. Both insisted that COSCO would use Piraeus for social dumping and would limit labor rights. Until his reelection in June 2015, Tsipras remained publicly elusive on the future of the COSCO-Greek cooperation. His former Finance Minister Yanis Varoufakis estimated that "this problem will be solved," but China did not appreciate this uncertainty and speculated about the "risks" the elections would bring to its investments. 10 Towards the end of 2015, the situation started to improve after Tsipras was reelected at the helm of a more moderate government. Although Greece wanted to be less dependent on its creditors, the internal debates reflected the changing political climate in Greece, or perhaps in Southern Europe, where a number of commentators started monitoring closely the management by Chinese companies of major infrastructure projects in Europe. Piraeus became representative of some concerns regarding Chinese FDI in Europe, including labor issues and national security.

Meanwhile, in June 2015, at the annual EU-China summit, Premier Li Keqiang made clear that China saw its relationship with the EU as vital to its long-term interests, though primarily in economic terms. When Li was asked during his press conference in Brussels (July 2015) if China was willing to provide loans or other financial aid to help Greece, the Premier responded by restating China's preference for "a united Europe, a prosperous EU, and a strong euro." He continued: "As for the issue of Greek debt, in principle it is an internal affair of Europe. Having said that, whether Greece would stay within Europe is not only a question that concerns Europe but also concerns China and Europe … that is why China has made its own efforts to help Greece overcome the debt crisis." [START_REF]Li Keqiang Expounds Chinese Government's Position on Greece's Debt Problems[END_REF] COSCO was given full management of Piraeus in April 2016. It paid $420 million (€368.5 million) for a 67% stake of the harbor authority, which is increasingly becoming China's maritime gateway to Europe, and has plans to further expand. The total value of the COSCO deal is estimated to be €1.5 billion, including additional investment. [START_REF] Stamouli | Greece Signs Deal to Sell Stake in Port of Piraeus to China's Cosco[END_REF] The announcement led to dockworkers' protests in the streets of Athens although the Syriza government had already sealed the deal. [START_REF] Koutantou | Workers Protest as Greece Sells Piraeus Port to China COSCO[END_REF] In June 2016, the Greek Parliament approved it, putting a closing line on a long-standing debate. This was followed by an official visit to China by Prime Minister Tsipras.

As a foreign investor, China had seemed all along ready to speak up for its interests. It has shown its commitment towards Greece but admits it has no control over the fast-evolving local situation. For months, it adopted a wait-and-see attitude in order not to become a scapegoat in the Greek context. Eventually, this strategy was successful, and China is now hopeful it can "create jobs and help the Greek economy prospering." [START_REF]COSCO's Acquisition of Greek Piraeus Port to Further Contribute to Local Economy[END_REF] There is little doubt that China will use Piraeus to enhance its presence in Greece and the Mediterranean region. Other Greek infrastructures are also on the Chinese radar. Led by the Shanghai-based group Fosun, a consortium has purchased the Elliniko airport south of Athens to make it a leisure complex in the mode of Dubai. [START_REF]acquisitions of France's Club Med, Greece's Folli Follies and Portugal's top insurance company[END_REF] China State Construction Group (a state-owned enterprise) has expressed interest in the airport of Kastelli. Lastly, the port of Tympaki on the island of Crete has been a target for COSCO for several years but the deal has not been finalized.

CASE N°2: THROUGH PORTUGAL, IS CHINA TARGETING THE LUSOPHONE MARKET?

In 2004, China signed strategic partnerships with four European countries: Germany, France, the UK and-perhaps more surprisingly-Portugal. With Germany, Beijing aimed at an increased economic partnership; with France, it aimed at a continuous multilateral dialogue via the United Nations (UN) and African issues; and with Britain, there was the financial weight of the City of London and the longstanding relations formed around the former British colony of Hong Kong, not to mention the Commonwealth, the English language, and multilateralism. But why Portugal, whose tottering economy had made life difficult for the European Union after the financial crisis of 2008? There are many reasons for this. First, China recognizes the political weight of the former Portuguese empire through language; there are more than 220 million Lusophones in the world. In 1996, seven countries created a new community of Portuguese-speaking countries (Comunidade dos Países de Língua Portuguesa). Apart from Brazil, Angola, and Mozambique (a country where China has many economic interests), one should not forget the special relationship between the former Portuguese enclave of Macau and the former Middle Kingdom, which retook possession of its territory in 1999 after more than four centuries of Portuguese colonization. Chinese and Portuguese elites have had close relationships for a long time, through the Sino-Portuguese Chamber of Commerce as well as a number of Macaurelated organizations. Each year, the Macau Forum celebrates-in the presence of senior Chinese officials-the relationship between Beijing and Lisbon via Macau, and it now also includes economic cooperation in Portugal and elsewhere.

Second, on the investment side, the Chinese in Hong Kong and Macau quickly swarmed to Lisbon. From the 1980s, thanks to a "Macau connection," overseas Chinese started investing in Portuguese real estate. According to a report published in late 2015, Portugal has in recent years received more Chinese investment than any EU member state except the UK, Germany, and France. [START_REF]Chinese Enterprises Pump Billions into Portuguese Companies[END_REF] "Chinese investors increasingly deployed capital in economies that were severely affected by the financial crisis [and] seized opportunities arising from the privatization of … utilities and transportation infrastructure," says the report. The Head of Portugal's investment and trade agency says the inflow proves "not only the quality of our P. LE CORRE assets but the closeness of the relationship." Portugal offers "a platform for the Portuguese-speaking world and its 250m consumers." 17 Third, there is the hot issue of immigration visas. Today, agencies specializing in obtaining "golden visas" are multiplying in Portugal. [START_REF]The Winners and the Losers of Portugal's Golden Visa Scheme[END_REF] The principle is simple: whoever invests a minimum of €500,000 in real estate property may obtain a long-stay visa, with the minimal obligation to spend seven days every year in the country. After six years, the investor can ask for Portuguese nationality and then get a EU passport. Of course this procedure still affects only a small number of persons (2788 in Portugal in 2015), but it is expressly aimed at (rich) Chinese nationals who want to emigrate. [START_REF]Buying Their Way In[END_REF] Up to now, the number of jobs created has remained very small and the results are mixed, and most of the beneficiaries have been individual Chinese property owners. A corruption scandal has made headlines after a probe into allegations of corruption, influence peddling, and money laundering linked to the program prompted 11 people to be detained in November 2014, according to the Portuguese Prosecutor General's Office. [START_REF] Almeida | Portugal Plans Tighter Golden Visa Controls[END_REF] Since then, the Portuguese authorities have tightened their visa policy, upsetting a number of applicants. The real question is whether this will benefit employees of Chinese groups, both private and public, that have made important investments.

As part of Beijing's "going out policy" (走出去), China's acquisition wave in Portugal began in 2011 when the state-owned Three Gorges Corporation paid €2.7 billion for 21% of Energias de Portugal (EdP), the country's highly indebted top power utility, which has a virtual monopoly on the residential retail energy market. The Chinese company won against Germany's E.ON, following what reports called "Berlin's high-handedness in demanding that Portugal undergo structural economic reforms." [START_REF] Roberts | Chinese Investment in Portuguese Power Grid Raises Eyebrows[END_REF] Three Gorges' offer to EdP seemed to have come at the right time. In June 2014, the head of EdP, Joao Marques Cruz, declared that, through this deal, his company was interested in working with CTG towards the Brazilian or African market. [START_REF]Portuguese and Chinese Companies Team Up for Energy Development[END_REF] Three months later, China's State Grid invested €1.4 billion to acquire 25% of Redes Energéticas Nacionais (REN), the National Grid operator.

On the private side, the Shanghai-based private conglomerate Fosun International spent €1 billion in 2014 to acquire 80% of Caixa Seguros Saúde, Portugal's largest insurance group, and has also acquired the distressed hospital business Espírito Santo Financial Group for €460.5 million. Huawei invested €10 million in a technology center and Beijing Enterprises Water Group bought Veolia Água. 23 "The important thing in a country in crisis is to shift capital from weak hands-of owners with solvency and debt problems-into stronger hands with the capacity to invest and open up markets," commented José Brandão de Brito, chief economist at Portuguese bank Millennium BCP in a report. "The Chinese are in a very good position to do this." [START_REF]Chinese Enterprises Pump Billions[END_REF] Many of these investors plan to expand to Angola, Brazil, Mozambique, or other former Portuguese colonies. The link was made particularly clear in 2011 when Sinopec, China's state oil company, paid $4.8 billion for a 30% stake in the Brazilian subsidiary of Galp Energia, Portugal's largest oil and gas utility, to jointly develop its Brazilian upstream portfolio. [START_REF]Galp Energia Announces a Partnership with Sinopec to Jointly Develop its Brazilian Upstream Portfolio, Valued at $12.5 billion[END_REF] Last June, they unveiled their latest, Hydroglobal, targeting South America and Africa. State Grid created similar ventures with REN in Angola and Mozambique, and in 2013 helped it secure a €1 billion finance line from China's Development Bank. Fidelidade continued its drive into Africa, setting up in Mozambique.

With their Chinese partners, Portuguese energy companies are expanding their hydropower and other new energy businesses to Brazil, Mozambique, and Angola, which all have large energy needs. So far, the process has taken place smoothly, and there has been limited social action in Portugal. The business community has also been extremely supportive of Chinese investors.

In October 2015, as in Greece, a left-wing government led by Prime Minister Antonio Costa was elected in Portugal, with an equal support of local trade unions. Costa vowed to end austerity through "persistence in investment" and "corporate modernization." [START_REF] Walker | Portugal's New Government Sworn In[END_REF] Chances were high that foreign investors would not be as welcomed as they were under the previous center-right government. There is a possibility that a democratic process in a European country may not be working in favor of foreign investors. China, as an investor, is particularly willing to avoid controversy, although in this case, Portuguese authorities have been very cautious not to address sensitive issues regarding Chinese investments publicly in order not to offend their new partners. There seems to be a left-right political disagreement on whether China might be the answer to some of Portugal's economic problems. A cabinet minister of the new Portuguese administration told the author in July 2016 that his party was originally opposed to the privatization program and expressed concerns about the national security aspects. "We were not happy with the privatization of major parts of Portugal's national power utility (Energias de Portugal) and national grid (Redes Energéticas Nacionais) P. LE CORRE orchestrated by the previous government, and we are concerned about long-term consequences for our national security," he said during a private meeting. 27

WHAT IS THE IMPACT OF CHINESE INVESTMENTS

ON TARGETED COUNTRIES?

One should here make a clear distinction between public and private investments. Although they often require approval from the Chinese authorities, private acquisitions are made on a case-by-case basis, per the board's decisions-hence they do not generally carry a strategic dimension. On the other hand, investments by public entities do represent a challenge as acquisitions are often made at the highest level in China, either at the state level (COSCO) or sometimes the provincial level. China's investment in European infrastructures will lead to more questions to European governments. A case such as Piraeus Harbor has started attracting attention, as COSCO has in fact been able to demonstrate its management skills as well as financial capabilities. Chinese investments in Portugal will soon also be closely studied, with Energias de Portugal as a prime example of China's ambition. Another critical example would be the UK's Hinkley Point nuclear power plant. 28 Hence the question that many experts have been asking: besides cash, what is the benefit for European countries to have some of their national infrastructures controlled by a future competitor like China? 29 China is looking at further investments in infrastructures, not just in Europe but also in Central Asia and South Asia, as part of the BR. [START_REF]Chinese investment: Is It Good for Britain?[END_REF] It is trying to sell high-speed trains and will soon try to export nuclear plants. Therefore, it is natural for European countries to engage in a debate about whether this particular nation should be allowed to take a stake in their utilities.

Secondly, there are questions asked about the long-term interest of China in European utilities: If it does finance a nuclear plant in the UK, for example, the British consumer will be paying for it through its monthly consumption. Hence a legitimate "value for money" question: While China is investing in European infrastructures, it is not always committed to the idea of public service. The bills ultimately land at the feet of the public, whether it is electricity, rail fares, or taxation. 31 The European general public and the media do not necessarily have a detailed grasp of the financial stakes and implications. Although Chinese investors have been better at communicating their positions recently, there seems to be a gap between European elites and grassroots on the matter of Chinese investments. [START_REF] Fu Chengqiu | has been giving numerous interviews and speeches. It is also true of the president of China Three Gorges Corporation, Cao Guangjing[END_REF]

LESSONS TO BE LEARNED

It is much too early to make a definitive assessment about Chinese investments in Western Europe in the field of infrastructures. The number of compelling cases is limited. Only the Greek case seems worthy of an indepth analysis because it encompasses several matters that we have alluded to in this paper. First, cooperation between Europe and China: is it short term, long-term, or strategic? Many agreements have been designed and signed, but both bureaucracies and multiplying EU crises have somewhat prevented a faster development. Second, the future of European infrastructures: There are technical aspects that involve the protection of local industries and environmental laws. Third, the impact of national elections on government decision-making: They can be quite radical, and more dramatic changes could take place in the years to come. Fourth, tensions between elites and grassroots views. There is a sense that decisions on allowing Chinese FDIs are sometimes "made by elites" against the will of the people, and not necessarily to the benefit of the latter. Sixth, human resources: Job creation remains the top priority of all the decision-makers in Europe. As explained in the COSCO/Piraeus case, Chinese investors have been better perceived when using local staff.

Most of these issues can be applied to future projects under the BR. If China is to lead through this new initiative, it is implied that it should develop a sense of universality, or at least an understanding of the political, social, cultural, and economic environments where it is intending to invest. 33 Central Asian countries, for example, have a relatively short history as independent nations, but they have the same sense of belonging and history as any other country. Therefore, the BR will have to encompass local aspects as much as global aspects, financial sustainability, transparency, and local political systems.

The internationalization of China, and of its companies in particular, is one of the most important phenomena of the beginning of the twenty-first century. After taking an interest in Africa, Oceania, and Latin America, China has started looking at developed countries, where it engaged in some increasingly important investments. Each of the European countries possesses a sophisticated legal apparatus inherited from its history. The legislation of the European Union adds still another layer of complexity. However, if they want to be engaged over the long term, potential Chinese investors will have no other choice but to understand and accept this system. Now that China is engaged in a major initiative that will give it responsibilities not just towards its own people, but also towards the foreign populations in countries where it is investing, it is hoped that Beijing's decisions will not be oriented exclusively towards its domestic public opinion, especially when acquiring European technological jewels, or even utilities. Moreover, promises of Chinese infrastructure projects directed at Central Asia, Pakistan, and even Europe must be followed by actual deeds. In too many cases, announcements of cooperation have been made without them becoming reality.

P. LE CORRE

European Fund for Strategic Investments (