{'fraction_non_alphanumeric': 0.05165916466031613, 'fraction_numerical': 0.021511567047000944, 'mean_word_length': 3.688834355828221, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A note on APN permutations in even dimension

APN permutations in even dimension are vectorial Boolean functions that play a special role in the design of block ciphers. We study their properties, providing some general results and some applications to the low-dimension cases. In particular, we prove that none of their components can be quadratic. For an APN vectorial Boolean function (in even dimension) with all cubic components we prove the existence of a component having a large number of balanced derivatives. Using these restrictions, we obtain the first theoretical proof of the non-existence of APN permutations in dimension 4. Moreover, we derive some contraints on APN permutations in dimension 6.


Introduction
A block cipher is a cryptographic primitive that allows the encryption/decryption of fixedlength messages once a secret key has been shared (called the session key). Given a fixed key, a block cipher can be viewed as a permutation on the message space. For its performance, a block cipher is designed as the composition of many efficient transformations, called rounds. In any round, a round key is derived from the session key and acts on the message space, sometimes on the whole space (as in translation-based ciphers [10], such as the AES [14] or the SERPENT [4]), sometimes on portions thereof (as in Feistel ciphers [17]). The action of a round key is traditionally a translation, that is, any (portion of the) message is viewed as a binary vector and is summed with the round key (or XORed, in computer science language). These traditional ciphers are the most common and include some notable Feistel ciphers, such as DES [18], Camellia [1] and Kasumi [16], and all translation-based ciphers, but some alternative actions of the round keys can be found even in block ciphers which have been used in practice, such as IDEA [21], SAFER [25] and GOST [15]. Efficiency reasons explain why in traditional ciphers all-but-one round components are affine maps, being the so-called S-box the only exception, and the latter is then called the non-linear component of the cipher.
If also the S-boxes would be affine maps, the block cipher would be trivial to break. Unsurprisingly, the most effective attacks to traditional block ciphers start from the study of their S-boxes and their non-linear behavior, as explained below. In particular, the so-called differential cryptanalysis [5] has proved especially effective. The most basic version of this attack successfully applies when two plaintexts with a (known) fixed difference lead after the last-but-one round to outputs whose difference takes a (known) value with a probability significantly higher than the average. To minimize the success probability of this attack, the theory of vectorial Boolean functions ( [12]) has identified an ideal property for the involved S-box, that is, to be an Almost Perfect Nonlinear function (or APN for short). Relevant definitions and properties of APN functions can be found in Section 2. It is important to note that the APN functions used in translation-based ciphers have to be bijective, that is, they must be permutations. In the case of the ciphers AES and SERPENT the S-boxes used are not APN. As regards AES, there is no known example of an 8-bit APN permutation, while for SERPENT there does not exist a 4-bit APN permutation. However, in Feistel ciphers is not necessary that the S-boxes are invertible (not even in DES), although they are in some, like in Kasumi. In Kasumi the S-boxes are APN permutation, as they are defined over an odd dimensional space.
Although much is known for APN permutations in odd dimension, implementative reasons make a case for the use of APN functions in even dimension, especially when the dimension is a power of 2. Unfortunately, little is known at present for these cases and what is known relies heavily on computer checking: • It is known that there is no APN permutation in dimension 4 (the first non-trivial case), but the proof relies on extensive computations providing no theoretical insight on the reasons behind their non-existence.
• It is known that there is at least one APN permutation with dimension 6, called the Dillon's permutation ( [7]). Interestingly, prior to [7] it was conjectured that no APN permutations in even dimension could exist, since nobody could find any example [20].
• It is known that any cubic APN permutation in dimension 6 must be CCZ-equivalent to the Dillon's permutation, which is itself CCZ-equivalent to a quadratic function, but again this proof is of a purely computational nature [22].
• All computationally-found APN permutations in dimension 6 lack a quadratic component, again with no hint to as why [22].
• Very little is known on a putative APN permutation in dimension 8 or higher.
In this paper we present some advances in the theoretical understanding of properties for APN permutations of even dimension. After having provided some notation and preliminaries in Section 2, we claim the following main results: • in Section 3, any APN permutation must lack a partially-bent component; this implies that it must also lack a quadratic component; • in Section 4, any cubic APN function (not necessarily a permutation) must have a component with a large number of balanced derivatives; moreover, we classify cubic Boolean functions in dimension 4 according to their number of balanced derivatives; • in Section 5, we derive two immediate consequences of our previous results; the first relates to dimension 4 and is the first-ever theoretical proof of the non-existence of an APN permutation; the second relates to dimension 6 and is the theoretical explanation of the component degrees for all known APN permutations.

Preliminaries
We will denote by F 2 the finite field with two elements. Let m ≥ 1, in the sequel we consider Boolean function f from (F 2 ) m to F 2 and only vectorial Boolean function F from (F 2 ) m to (F 2 ) m . Without loss of generality we will assume f (0) = 0 (F(0) = 0).
If all non-zero components of F are quadratic then we say that F is a pure quadratic. If all non-zero components of F are cubic then we say that F is a pure cubic. Definition 2.1. Let F be a vectorial Boolean function, for any a, b ∈ (F 2 ) m we define The differential uniformity of F is Those functions with δ (F) = 2 are said Almost Perfect Nonlinear (APN).
We denote by F ( f ) the following value related to the Fourier transform of a Boolean function f : where w H ( f ) is the Hamming weight of f , i.e. the number of x such that f (x) = 1. The function is said to be balanced if and only if F ( f ) = 0.
A necessary condition for a vectorial Boolean function F to be APN was provided by Nyberg in [26]. This condition involves the derivatives of the components of F. It was proved by Berger et al. [3] that this condition is also sufficient.

Moreover, F is APN if and only if for all non-zero a
We recall the following non-linearity measures for vectorial Boolean functions, as introduced in [10,19]: For a vectorial Boolean function we report the following result.

Theorem 2.3 ([10, 19]). Let F be a vectorial Boolean function, then
The following theorem is well-known.
Theorem 2.4 cannot be extended to weakly-APN functions, since from the classification of bijective vectorial Boolean functions for m =4 there is one affine equivalent class of weakly-APN functions with n 1 = 1.
Finally we recall some results on quadratic and partially bent Boolean functions. The following two results can be found in [24] Chapter 15.

Remark 2.7. The proposition above implies that for any non-balanced quadratic Boolean function
We report now the definition of partially bent function, which was introduced in [11].

Remark 2.9. If f is partially bent, then f can be represented as a direct sum of the restricted
, for all z ∈V ( f ) and y ∈ U . Moreover we can deduce from Proposition 2.5 that any quadratic function is partially bent.

Properties of APN permutations
Our first result holds for any dimension and comes directly from the facts in previous section. •n(F) = 0, which implies that for any λ = 0 F λ is not partially bent and so n 1 (F) = n 2 (F) = 0; •n(F) = 1, for which it is possible that there is a λ = 0 such that F λ is partially bent, and so n 1 (F) = 0 and n 2 (F) ≥ 0.
Proof. From Theorem 2.3 and Theorem 2.4 we have thatn(F) ≤ 1 and n 1 (F) = 0. Ifn(F) = 0 then any non-zero component F λ has V (F λ ) = {0}. This implies that if F λ is partially bent, then F λ is bent, see Remark 2.10, but it is not possible as F is a permutation.
, and it could be partially bent (in particular it could be quadratic).
The condition on bijection for F is essential, otherwise the casen = 0 may have bent components. As there are examples of quadratic APN permutations for any odd dimension, the previous theorem cannot be improved.
The case of an APN permutation F with m even is quite different and we will restrict to it from now on. As shown in [27] there is no APN quadratic permutation over (F 2 ) m for m even, that is n 2 (F) ≤ 2 m−1 − 1. This result was extended by Nyberg [26] showing that an APN permutation F cannot have all components partially bent (for m even). Moreover, in [2] the authors give some properties on the the components of a weakly-APN permutation in even dimension. In particular they study partially-bent and quadratic components, obtaining that the number of the quadratic components of a weakly-APN permutation can be at most 2 m−2 − 1 ([2] Proposition 4). As an APN function is weakly-APN, we have n 2 (F) ≤ 2 m−2 − 1.
In the remainder of this section we will prove that no component of F is partially bent (quadratic).
We start with the following proposition. Proof. Suppose that there exist non-zero a, λ ∈ (F 2 ) m such that D a F λ = 0. Without loss of generality we can suppose that F λ = f 1 , thus we have Im(D a F) = {(0, y 2 , . . . , y m ) | y i ∈ F 2 }.
Being F APN we have |Im(D a F)| = 2 m−1 , so 0 has to lie in Im(D a F), contradicting the fact that F is a permutation. Proof. Suppose that F λ is partially bent, for some λ ∈ (F 2 ) m \ {0}. From Remark 2.10 and being F a permutation, we have that the space of the linear structure of F λ has at least dimension 2. Let a 1 and a 2 be two distinct non-zero vectors of V (F λ ). Let x ∈ (F 2 ) m , from Proposition 3.2 and Remark 2.10 we have D a 1 F λ (x) = F λ (a 1 ) = 1 and D a 2 F λ (x) = F λ (a 2 ) = 1. This implies a 1 + a 2 ∈ V (F λ ), a 1 + a 2 = 0 and But D a 1 +a 2 F λ = 0 contradicts Proposition 3.2.

As D a f is balanced, then D a ( f + ℓ) is balanced. This implies that f + ℓ is bent. Moreover, we immediately have that if f is partially bent and ℓ is a linear Boolean function, then f + ℓ is partially bent.
We recall that two functions F and F ′ are called EA-equivalent if there are an affine mapping L and function G affinely equivalent to F, such that F ′ = G + L. From Remark 3.6 we obtain the following.

Proposition 3.7. Let F be a vectorial Boolean function with partially bent components. If F ′ is EA-equivalent to F, then F ′ has partially bent components.
Proof. F ′ = G + L for some G affine equivalent to F and L affine map of (F 2 ) m . Thus the component λ of F ′ is F ′ λ = G λ + L λ for all λ ∈ (F 2 ) m . As F has a partially bent component, then also G has a partially bent component (it is affine equivalent to F). Let G λ be partially bent, then from Remark 3.6 we have that G λ + L λ is partially bent.
For m even and gcd(m, i) = 1 the following two families of APN functions were constructed in [9], [8] x 2 i +1 + (x 2 i + x + 1)Tr(x 2 i +1 ), where Tr(x) denotes the trace function from F 2 m into F 2 . It was proven in [23] that the first one is not EA-equivalent to permutations and, at the best of our knowledge, a similar result is missing for the second one. However, both functions have quadratic components which implies, according to Corollary 3.4 and Proposition 3.7, that both of them are not EA-equivalent to permutations. More generally, since EA-equivalence preserves partially bent components, then the following holds:

On cubics in even dimension
In this section we are interested in cubic Boolean functions and cubic vectorial Boolean functions.
Given a Boolean function f , we are interested in counting the number of its derivatives that are balanced, that is the cardinality of Γ( f ) = {a ∈ (F 2 ) m | D a f is balanced}. Observe that if f is quadratic, then its derivatives can be either linear functions (which are balanced) or constant functions, which are non-balanced. For a cubic function, the situation is less obvious. The following theorem presents an estimate of Γ for a component of a pure-cubic APN function.
Proof. Consider any a ∈ F m , a = 0. For any component F λ we are interested in the following integers: deg(D a F λ ), where clearly 0 ≤ deg(D a F λ ) ≤ 2, F (D a F λ ), and k λ = dim(V (D a F λ )). We note that k λ ≥ 2, because D a (D a F λ ) = 0 and so D a F λ cannot be bent (see Remark 2.10). We can have the following cases: 2) deg(D a F λ ) = 1, then D a F λ is balanced and so F (D a F λ ) = 0.
3) deg(D a F λ ) = 2 and D a F λ is balanced, so F (D a F λ ) = 0. Let s λ = m+k λ 2 , noting that k λ ≥ 2, then m 2 + 1 ≤ s λ ≤ m. Observe that in case 1 and 4 we have F 2 (D a F λ ) = 2 2s λ , while in case 2 and 3 we have F 2 (D a F λ ) = 0. Since a = 0 and F 2 (D a F 0 ) = 2 2m , from Proposition 2.2, we have We will now consider functions D a F λ , with λ and a varying freely in We have thus proved that and this is impossible. Thus there exists Observe that the previous theorem holds, when m is even, for any cubic APN function F such that F : (F 2 ) m → (F 2 ) m , even if F is not a permutation (and even if F is a pure-cubic).
It turns out that Γ( f ) suffers a strong constraint when we specialize to the case m = 4, as next theorem shows.

linearly independent vectors.
Without loss of generality we can assume e 1 , e 2 , e 3 , e 4 (the standard basis) belong to Γ( f ). We will implicitly use in the remainder of this proof that D e 1 ( f ),..., D e 4 ( f ) are balanced for our f .
The Boolean function f can be written as where supp i ( f ) contains only terms of degree i for i = 1, 2, 3. Note that supp 0 ( f ) + supp 1 ( f ), that is, the linear part does not influence the balancedness of any derivative of f , and so we can consider f = supp 2 ( f )+ supp 3 ( f ). We will find a contradiction depending on the following cases, which are characterized by the weight of supp 3 ( f ), i.e. |supp 3 ( f )|, which can only vary in 1 ≤ |supp 3 ( f )| ≤ 4 since m = 4 and deg( f ) = 3. In the following cases we will write Boolean functions as polynomials that may contain squares, using the standard notation of viewing them implicitly in the quotient ring 4 . Also, since we will apply affine transformations we will sometimes obtain a Boolean function g such that g(0) = 1. However, we will write that g is equivalent to g ′ if g is affine equivalent to either g ′ or g ′ + 1. This equivalence notion preserves balancedness and it is appropriate for our goals.
We have already assumed that the standard basis belongs to Γ( f ), so Γ( f ) contains all vectors of weight 1. There are other 7 vectors in Γ( f ) and in (F 2 ) 4 there are five vectors of weight 3 or 4. Thus in Γ( f ) there is at least a vector of weight 2. A permutation of the coordinates will not change our situation, that is, Γ will still contain the vectors with the prescribed weights, and so without loss of generality we can assume that (1100) ∈ Γ. If we derive f in the direction of e 1 we obtain that is equivalent to x 1 x 2 + (1 + β 12 + β 13 + β 14 )x 3 . From Proposition 2.5 we have that D e 1 f is balanced if and only if β 12 + β 13 + β 14 = 0.
Without loss of generality we can consider Considering the derivative in the direction of e 2 we have As before, from Proposition 2.5 we have β 23 + β 24 = 1. Similarly, we have β 23 + β 34 = 1 from D e 3 f , and β 24 +β 34 = 1 from D e 4 f . The three conditions on β i j 's cannot simultaneously hold.
In this last case we can assume From the derivative in e 1 we have We can obtain similarly β 24 = 1 and β 34 = 1 from the derivatives D e 2 f and D e 3 f respectively. As in the previous case we want to find more than four (not-null) elements that give unbalanced derivatives. Let us consider a = 0, a = (a 1 , a 2 , a 3 , a 4 ), with a 1 + a 2 + a 3 = 0 and (a 1 , a 2 , a 3 ) = (0, 0, 0). Since in f the first three variables take the same role, we can assume without loss of generality that a 3 = 0, so a 1 = a 2 = 1. Now let us consider the derivative of f with respect to a = (1 1 0 a 4 ).
The obtained function is equivalent to x 1 x 2 , so it is not balanced. Therefore there are at least 6 elements for which D a f is not balanced and so Γ( f )<10.
The analysis of the previous cases has shown the following: We can conclude that for any f we certainly have Γ < 11.

Consequences in low dimensions
In this section we discuss some consequences of our previous results.

m=4
There are two immediate non-existence results for the case m = 4. The first holds also for non-bijective functions. Proof. Suppose that F is APN. Then from Theorem 4.1 there exists a component F λ such that |Γ(F λ )| ≥ 11. But Theorem 4.2 shows Γ(F λ ) < 11, since F λ is cubic.
As consequence we obtain our second result, which is the non-existence of APN permutations for m = 4. Proof. Since F is invertible, then F is at most cubic. Since F is an APN, then n 1 (F) = 0 (Theorem 2.4). Since F is an invertible APN, then n 2 (F) = 0 (Corollary 3.4). Therefore, F is a pure cubic. But this contradicts Theorem 5.1.
Observe that Theorem 5.1 and our previous result do no prevent the existence of quadratic or cubic APN's, which are known to exist (but of course they are not bijective). Indeed, in [6] they show (computationally) that there are exactly two APN functions in dimension 4 (up to EAequivalence), one quadratic and one cubic. Theorem 5.1 shows that the latter, being a cubic APN, cannot be a pure cubic.

m=6
The first consequence of our previous result to dimension 6 is the following corollary. Proof. An invertible APN cannot have any quadratic component (Corollary 3.4), any linear component (Theorem 2.4) and any degree-6 component (because it's invertible). This is in accordance with experimental results by Langevin [22] and explains also because the degree of the components of Dillon's permutation are only 3 and 4 (although in principle there could be a component of degree 5).
Theorem 5.1 cannot be trivially extended to dimension 6, since pure cubic APN functions exist. Still, Theorem 4.1 applies and therefore any cubic APN must have a component with a large number of balanced derivatives, that is, with Γ(F λ ) ≥ 47. However, for m = 6 this arises no contradiction, since there are cubics with Γ( f ) ≥ 47 and a suitable extension of Theorem 4.2 to the case m = 6 is missing.
We conclude this paper with noting that from the exam of the computational results presented in [22], we can derive a weaker version of Theorem 5.1 for m = 6.