Pascale Charpin

Jie Peng

New links between nonlinearity and differential uniformity

This paper establishes some new links between the nonlinearity and differential uniformity of some large classes of functions, such as power functions, differentially two-valued functions and quadratic functions. We obtain a lower bound for the nonlinearity of general differential uniform power permutations, an upper bound for general differentially two-valued functions, together with some important results for quadratic functions. In particular, we show that the quadratic differentially 4-uniform permutations should be two-valued and possess the best known nonlinearity.

Introduction

The first statistical attack proposed for breaking iterated block ciphers, namely the differential cryptanalysis, was proposed by Biham and Shamir in [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF]. The security is quantified by the so-called differential uniformity of the substitution box (S-box), which can be represented by a function, say F , over the finite field of order 2 n denoted F 2 n . The Boolean functions used in block ciphers must have a high distance to the set of all affine functions to resist to the linear cryptanalysis [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF]. This criteria is called the nonlinearity. In this context, the knowledge of nonlinearity and differential uniformity of large families of functions is useful. On the other hand, such a study allows to exhibit specific objects or can be replaced in a theoretical research in algebraic coding theory or combinatorics.

It seems difficult to establish precise relations between the differential uniformity and the nonlinearity of any function. The aim of this work is to exhibit such property. We mainly focus on power functions, differentially two-valued functions and quadratic functions, which were widely studied but are not yet classified. Many problems on these functions remain open.

For any APN function, a lower bound for the sum of all the sum-ofsquare indicators of its components has been obtained, and the number of its bent components has been characterized in [START_REF] Berger | On almost perfect nonlinear functions[END_REF]. Besides, a lower bound for the nonlinearity of APN power functions has been derived in [START_REF] Carlet | Characterizations of the differential uniformity of vectorial functions by the walsh transform[END_REF]. In this paper, we derive similar results for such functions with general differential uniformity. For any function we obtain an upper bound for the sum of all the sum-of-square indicators of its components, which are achieved by differentially two-valued ones. Based on that, we show that any differentially 4-uniform plateaued function must have bent components, unless it is differentially two-valued. Moreover, we derive a lower bound for the nonlinearity of power permutations, and an upper bound for the nonlinearity of general differentially two-valued functions. We later focus on quadratic functions. We put forward a new approach to establish links between the nonlinearity and differential uniformity by studying some relations between the subspaces related to these functions. Some important results are then deduced. In particular, we show that the quadratic differentially 4-uniform permutations should be differentially two-valued and possess the best known nonlinearity.

The rest of the paper is organized as follows. The next section gives some necessary definitions on the cryptographic properties of functions over F 2 n and their components. In Section 3, we establishes some new links between the nonlinearity and differential uniformity of power functions and differentially two-valued functions. In Section 4 we mainly concentrated on quadratic functions. Finally an interesting application of the results for quadratic functions is given in Section 5. This paper is an extended abstract and some proofs are omitted.

Preliminaries

A mapping F : F 2 n → F 2 m is usually called an (n, m)-function or a vectorial Boolean function. When m = 1, we say that F is an n-variable Boolean function and usually use small letter f instead; we denote by B n the set of all n-variable Boolean functions. When m = n, we say that F is a function over F 2 n . In this paper we are mainly concentrated on the latter case, but will use the representation of F by its components functions.

For any function F over F 2 n , the components of F are those n-variable Boolean functions represented as

f λ = T r(λF (x)), λ ∈ F * 2 n
, where T r is the absolute trace function from F 2 n to F 2 . For any a ∈ F * 2 n , the function

D a F : F 2 n → F 2 n , x → F (x+a)+F (x)
is called the derivative of F in direction a. For any a ∈ F * 2 n and b ∈ F 2 n , we are interested by the cardinality of any set (

D a F ) -1 (b): set δ(a, b) = #{x ∈ F 2 n | D a F (x) = b}, (1)
where #{E} denotes the cardinal of the set E. The differential uniformity δ of F is defined as δ = max

a∈F * 2 n , b∈F 2 n δ(a, b). ( 2
)
We also say that F is differentially δ-uniform. It is clear that δ is a positive even integer. When δ = 2, the possible smallest value, F is said to be almost perfect nonlinear (APN for short). The function F is said differentially twovalued if δ(a, b) takes two values only. These values are known to be {0, 2 s } for some positive integer s. Thus we will often say that F is differentially two-valued {0, 2 s }. A basic study of these functions can be found in [START_REF] Blondeau | Differential properties of power functions[END_REF]. For any f ∈ B n , its Walsh coefficients are defined as

W f (a) = ∑ x∈F 2 n (-1) f (x)+ax , a ∈ F 2 n .
The nonlinearity of f is denoted nl(f ) and computed as

nl(f ) = 2 n-1 - L(f ) 2 where L(f ) = max a∈F 2 n |W f (a)|.
The function f is said to be bent when n is even and W f takes two values ±2 n/2 only. It is said to be plateaued when either it is bent or W f takes three values {0, ±2 s/2 } for some even integer s. The value 2 s/2 is the amplitude of f . A plateaued vectorial function is a vectorial function whose components are plateaued Boolean functions. It is said plateaued with single amplitude when all components have the same amplitude.

The sum-of-square indicator of f ∈ B n is defined by

ν(f ) = ∑ a∈F 2 n W 2 Daf (0) = 2 -n ∑ b∈F 2 n W 4 f (b). (3)
Recall that ν(f ) ≤ 2 n L 2 (f ) with equality if and only if f is plateaued. We now consider any function F over F 2 n with components f λ . The Walsh transform of the function F is defined as

W F (λ, a) = W f λ (a) = ∑ x∈F 2 n (-1) T r(λF (x)+ax) , (λ, a) ∈ F * 2 n × F 2 n . ( 4
)
The Walsh spectrum of F is the multiset consisting of integers W F (λ, a) with their multiplicities. The function F is said almost bent (AB) when W F (λ, a) takes only the three values {0, ±2 (n+1)/2 }, so that n must be odd. The nonlinearity N L(F ) of F is defined as

N L(F ) = 2 n-1 - L(F ) 2 where L(F ) = max (λ,a)∈F * 2 n ×F 2 n |W F (λ, a)|.
For odd integers n, it has been proved that N L(F

) ≤ 2 n-1 -2 n-1 2 [8],
where the upper bound is achieved by the AB functions. But for even n, the known maximum nonlinearity is 2 n-1 -2 n 2 , which is conjectured to be an upper bound [START_REF] Dobbertin | One-to-one highly nonlinear power functions on GF (2 n )[END_REF].

A general relation and some consequences

The following lemma gives some link between the differential uniformity of a function over F 2 n and the sum-of-square indicators of its components.

Lemma 1 Let F be differentially δ-uniform over F 2 n , with components f λ , λ ∈ F * 2 n . Then (2 n -1)2 2n+1 ≤ ∑ λ∈F * 2 n ν(f λ ) ≤ (2 n -1)2 2n δ,
where the lower bound is achieved if and only if F is APN, and the upper bound is achieved if and only if F is differentially two-valued.

Proof. The result on the lower bound is obtained by [1, Corollary 1]. For the upper bound, one has

∑ µ∈F * 2 n ν(f µ ) = ∑ µ∈F * 2 n ∑ a∈F 2 n W 2 Dafµ (0) = ∑ a∈F * 2 n ∑ µ∈F 2 n W 2 Dafµ (0) = (2 n -1)2 2n+1 +2 n ∑ a∈F * 2 n ∑ b∈F 2 n δ(a, b)(δ(a, b)-2) ≤ (2 n -1)2 2n+1 +(δ-2)(2 n -1)2 2n = (2 n -1)2 2n δ,
with equality if and only if F is differentially two-valued. ⋄

Thus we have, since δ is even,

∑ µ∈F * 2 n ν(f µ ) = γ(2 n -1)2 2n+1 (5)
where γ is a rational number such that 1 ≤ γ ≤ δ/2.

In this paper we are interested by this problem: the number of bent components of vectorial functions over F 2 n , n even. A general approach is proposed by [START_REF] Pott | On the maximum number of bent component of vectorial functions[END_REF]Theorem 3]. For APN functions, this number has been characterized for plateaued such functions [1, Corollary 3]. For differentially 4-uniform functions, we give part of the answer in the following result.

Theorem 1 Let n be even and let F be a differentially 4-uniform function over F 2 n such that all its components are plateaued. Let A be the number of bent components of F . Then there exists some rational number (the one in ( 5))

1 < γ ≤ 2 depending on F , such that A ≥ (4-2γ)(2 n -1) 3 ,
providing that if F is not two-valued, i.e., γ ̸ = 2, then F has bent components.

Consequently, if F is not two-valued, then F is not a permutation. Moreover, for any linear function L over F 2 n , F + L is not a permutation.

In particular, any differentially 4-uniform quadratic permutation is differentially two-valued.

In the following, we present some results which are derived from Lemma 1, concerning respectively the power functions and the two-valued functions.

First let F (x) = x d be a power function over F 2 n . When F is a permutation, all its components f λ have the same Walsh spectrum; moreover all ν(f λ ) are equal. It is well known that if F is APN, then gcd(d, 2 n -1) = 1 for odd n and gcd(d, 2 n -1) = 3 for even n. Consequently, F APN and n odd imply that ν( Proposition 5]. Then one can deduce an upper bound for power APN functions as

f λ ) = 2 2n+1 , λ ∈ F * 2 n [1,
N L(F ) ≤ 2 n-1 -2 n-1
2 , though it gives not any new information. While for even n, the situation is more complicated, the last result is due to Canteaut and is listed below.

Theorem 2 [START_REF] Canteaut | Analyse et conception de chiffrements clef secrte[END_REF]Theorem 8.14] Let n = 2m and let the power function

F (x) = x d over F 2 n . Assume that gcd(d, 2 n -1) > 1. Then N L(F ) ≤ 2 n-1 -2 m+1 . If N L(F ) = 2 n-1 -2 m+1 then gcd(d, 2 n -1) = 3 and W F (λ, 0) = { (-1) m+1 2 m+1 , if λ ∈ {x 3 , x ∈ F * 2 n } (-1) m 2 m , if λ ̸ ∈ {x 3 , x ∈ F * 2 n } ,
Applying Lemma 1 to power permutations, we obtain a precise result.

Proposition 1 Let F (x) = x d be differentially δ-uniform with gcd(d, 2 n -1) = 1. Then ν(f λ ) ≤ 2 2n δ for any λ ∈ F * 2 n , with equality if and only if F is differentially two-valued {0, 2 s }. In this case, L(F ) ≥ 2 (n+s)/2 with equality if and only if F is plateaued.

Little is known on the lower bound of the nonlinearity of differential uniform functions, even for APN functions. It seems that the nonlinearity of all known APN functions is rather good. It is of interest and importance to find the reason. Recently, Carlet proposed a nonzero lower bound for the nonlinearity of APN power functions F in [7, Theorem 5.6], where he used the fourth moment of the Walsh transform to show that N L(F ) ≥ 2 n-1 -2 3n- 3 4 for n odd and N L(F ) ≥ 2 n-1 -2 3n-2 4

for n even. Using Lemma 1, we are able to generalize this result for bijective power functions of any differential uniformity with a simple proof.

Theorem 3 Let F be a power permutation over F 2 n with differential uniformity δ. Then we have

N L(F ) ≥ 2 n-1 -2 3n-4 4 4 √ δ.
Proof. By Lemma 1, according to Proposition 1 it holds for any λ:

L 4 (f λ ) ≤ ∑ c∈F 2 n W 4 F (λ, c) = 2 n ν(f λ ) ≤ 2 3n δ.
Consequently,

N L(F ) ≥ 2 n-1 -2 3n-4 4 4 √ δ.
⋄ Moreover, by applying Lemma 1 to differentially two-valued functions, we can obtain an upper bound for their nonlinearity.

Theorem 4 Let F be differentially two-valued {0, 2 s }. Then it holds N L(F ) ≤ 2 n-1 -2 n+s 2 -1 .
where s should be odd when n is odd.

Quadratic functions

We will now deal with quadratic functions and we begin by fixing notation and definitions. We assume that F :

F 2 n → F 2 n is of the form F (x) = ∑ i,j a i,j x 2 i +2 j , 0 ≤ i < j ≤ n-1, (6)
so that F (0) = 0. Then f λ (x) = T r(λF (x)) is a quadratic form for any λ ∈ F 2 n , and the function

(x, a) → T r(λQ(x, a)), where Q(x, a) = F (x+a)+F (x)+F (a). ( 7
)
is an alternative bilinear form. The corresponding radical of this quadratic form is

rad λ (F ) := {a ∈ F 2 n | T r(λQ(x, a)) = 0, ∀ x ∈ F 2 n }. ( 8
)
Note that rad λ (F ) is actually the linear space of f λ , i.e., the set of a such that the derivative of f λ in direction a is constant. Such a point a is called a linear structure of f λ . We will denote by ℓ(λ) the dimension of rad λ (F ). It is well known and easily checked that for any λ ∈ F * 2 n and for any b

∈ F 2 n W 2 F (λ, b) = ∑ a∈F 2 n (-1) T r(ba+λF (a)) ∑ x∈F 2 n
(-1) T r(λQ(x,a)) , [START_REF] Dobbertin | One-to-one highly nonlinear power functions on GF (2 n )[END_REF] which leads easily to

W 2 F (λ, b) = 2 n ∑ a∈rad λ (F ) (-1) T r(ba+λF (a)) = { 2 n+ℓ(λ) , if T r(ba+λF (a)) vanishes on rad λ (F ) 0, otherwise, (10)
since by definition a → T r(ba + λF (a)) is linear on rad λ (F ). Therefore, all quadratic functions are plateaued and their derivatives are either balanced or constant. Moreover, as W F (λ, b) is an integer, it follows from [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF] that

n ≡ ℓ(λ) (mod 2). ( 11
)
Note also that for any λ ∈ F * 2 n the Walsh transform b → W F (λ, b) of f λ takes the values {0, ±2 (n+ℓ(λ))/2 } if f λ is non-bent and the values {±2 n/2 } if f λ is bent. Therefore, the best nonlinearity of quadratic functions over

F 2 n is 2 n-1 -2 n-1 2
for odd n and 2 n-1 -2 n 2 for even n, which is also called the quadratic bound. Now we define

ker a (F ) := {λ ∈ F 2 n | T r(λQ(x, a)) = 0, ∀ x ∈ F 2 n }. ( 12
)
and denote by d(a) the dimension of the vector space ker a (F ) for convenience.

Our main results are based on the following observation.

Lemma 2 Let F be quadratic and differentially δ-uniform. For any a ∈ F * 2 n , the function D a F is 2 d(a) -to-1, where d(a) is the dimension of the vector space ker a (F ) defined by [START_REF] Yu | A Matrix Approach for Constructing Quadratic APN Functions[END_REF]. Hence δ = max a∈F * 2 n 2 d(a) . In this paper we put forward a different approach for the study of those ℓ(λ) by studying some relations between the subspaces related to the function F . Our method also applies to quadratic functions with higher differential uniformity.

A relation between nonlinearity and differential uniformity

It appears that the quadratic functions can be classified by their differential uniformity as well as by their nonlinearity. The link between these two concepts is really not clear, as proves the next example due to Dillon and indicated in [START_REF] Bracken | Fourier spectra of binomial APN functions[END_REF]. It is an example of APN quadratic function whose nonlinearity is not the quadratic bound for n = 6. More such examples for n = 8 can be found in the list of [START_REF] Yu | A Matrix Approach for Constructing Quadratic APN Functions[END_REF].

Example 1 Let n = 6 and let α be a primitive element of F 6 . The function

F (x) = x 3 +α 11 x 5 +α 13 x 9 +x 17 +α 11 x 33 +x 48
is APN with a five-valued Walsh spectrum. By the MAGMA package, we obtain that F has 46 bent components (ℓ(λ) = 0), 16 components such that

ℓ(λ) = 2 and one λ ∈ F * 2 n such that ℓ(λ) = 4. Therefore, N L(F ) = 2 n-1 - 2 n+4 2 -1 = 16.
Note that the number of bent components is greater than the lower bound which is 42 as we recall later in Remark 1.

Theorem 5 Let F be a quadratic function over F 2 n . Notation is as above, defined by [START_REF] Chabaud | Links between differential and linear cryptanalysis[END_REF] to [START_REF] Yu | A Matrix Approach for Constructing Quadratic APN Functions[END_REF]. Then we have ∑

λ∈F * 2 n 2 ℓ(λ) = ∑ a∈F * 2 n 2 d(a) . ( 13
)
Proof. It is simply obtained by computing: a) .

∑ λ∈F * 2 n 2 ℓ(λ) = ∑ λ∈F * 2 n |{a ∈ F 2 n | T r(λQ(x, a)) = 0, ∀ x ∈ F 2 n }| = 2 n -1+ ∑ a∈F * 2 n |{λ ∈ F * 2 n | T r(λQ(x, a)) = 0, ∀ x ∈ F 2 n }| = ∑ a∈F * 2 n |{λ ∈ F 2 n | T r(λQ(x, a)) = 0, ∀ x ∈ F 2 n }| = ∑ a∈F * 2 n 2 d(

⋄

Corollary 1 Let F be quadratic over F 2 n such that δ = 2 s and L(F ) = 2 (n+t)/2 . For any integers i and j such that 1 ≤ i ≤ s and j ∈ J := { j | 0 ≤ j ≤ t, n + j even }, set

N i = #{ a ∈ F * 2 n | D a F is 2 i -to-1 } and n j = #{ λ ∈ F * 2 n | ℓ(λ) = j }.
Then it holds

∑ j∈J 2 j n j = s ∑ i=1 2 i N i , ( 14
)
where

∑ i N i = ∑ j n j = 2 n -1. In particular, if F is differentially two-valued {0, 2 s }, then we have ∑ λ∈F * 2 n 2 ℓ(λ) = 2 s (2 n -1) where t ≥ s, t = max λ {ℓ(λ)}. ( 15
)
If F has single amplitude 2 (n+t)/2 then ∑ a∈F *

∑ i n i = (2 n -1). Then L(F ) = 2 (n+1)/2 , i.e., F is an AB function. -Assume that n is even. Then n 0 +2 2 A = 2(2 n -1), where A = n 2 +2 2 n 4 +• • •
and n i = 0 for i odd. Thus n 0 > 0, which means that F has an even number of bent components. Now, since (2 n -1) -

∑ i̸ =0 n i = n 0 we get 3 t ∑ i=2 n i ≤ t ∑ i=2 (2 i -1)n i = 2 n -
(F ) = 2 n-1 -2 n/2 .
When F is differentially 4-uniform, but not two-valued, there are surely a number of different Walsh spectrum. However, specific properties appear.

Corollary 2 Let F be quadratic over F 2 n such that δ = 4, which is not two-valued. With notations as in Corollary 1. We have:

∑ j∈J 2 j n j = ∑ λ∈F * 2 n 2 ℓ(λ) = 2N 1 +4N 2 .
In particular:

• If n is odd and L(F ) = 2 (n+3)/2 then n 1 ̸ = 0. Moreover N 2 = 3n 3 .
• If n is even and L(F ) = 2 (n+2)/2 then n 0 ̸ = 0. Moreover, the number n 0 of bent components satisfies n 0 = 2(2 n -1 -N 2 )/3. In particular, N 2 is divisible by 3.

An application

In this section we want to give an interesting application of our results. Notation is fixed in all this section. Throughout this section the quadratic function F is as follows defined.

F (x) = ∑ r∈Q ν r x r , where Q = {2 i +2 j | 0 ≤ i < j ≤ n-1}. ( 17
)
By using Theorem 6, we can prove the following property.

Theorem 8 Let F , given by ( 17), be any quadratic function over F 2 n which has no bent component (when n is even). Let t be a nonzero integer which divides n and the nonzeros i and j, for all r ∈ Q, r = 2 i + 2 j , such that ν r ̸ = 0. Then F is differentially two-valued {0, 2 t } if and only if the component functions of F have all the same amplitude which is ±2 (n+t)/2 with n+t even. The Walsh spectrum of F has values {0, ±2 (n+t)/2 }.

The following theorem is actually [START_REF] Bracken | Binomial differentially 4-uniform permutations with high nonlinearity[END_REF]Theorem 1.2] that we are able to complete. The properties (i) and (ii) are proved in [START_REF] Bracken | Binomial differentially 4-uniform permutations with high nonlinearity[END_REF]. The authors later proved that N L(F ) = 2 n-1 -2 (n+2)/2-1 , for t = 2 and n even, and that N L(F ) ≥ 2 n-1 -2 (n+t-e)/2-1 , e ≡ n + t (mod 2). The proof is specific and technical. In fact, we can directly prove (iii) by applying Theorem 8.

Theorem 9

Let n = 3k with gcd(3, k) = 1. Let t be a divisor of k such that k/t is odd. Let s be an integer such that gcd(n, s) = t and 3 divides k + s. Define the function over

F 2 n F (x) = αx 2 s +1 +α 2 k x 2 n-k +2 k+s ,
where α is a primitive element of F 2 n . Then (i) F is a permutation;

(ii) F is differentially two-valued {0, 2 t }.

(iii) Moreover N L(F ) = 2 n-1 -2 (n+t)/2-1 , all components of F have the same amplitude; the Walsh spectrum of F has values {0, ±2 (n+t)/2 } only.

Proof. We are going to prove (iii) by using our previous results. First, if t = 2 we apply Theorem 7. More generally, we can apply Theorem 8. Indeed, F is a permutation and then cannot have a bent component. Further, t divides n, s, k and then it divides n -k and k + s too. ⋄

2 n 2 dRemark 1

 221 (a) = 2 t (2 n -1) where 1 ≤ d(a), s ≥ t, s = max a {d(a)}. (16) Well-known properties of any APN quadratic function F are directly derived from the previous results: -If n is odd, then 2(n 1 +2 2 A) = 2(2 n -1) from (15), where A = n 3 +2 3 n 5 +• • • and n i = 0 for i even. But we must have n 1 + 2 2 A = (2 n -1) which forces A = 0 and n 1 = 2 n -1, since

  [START_REF] Berger | On almost perfect nonlinear functions[END_REF], where i is even. Let n be even. Then any quadratic differentially 4-uniform permutation is two-valued {0, 4} and has the best nonlinearity, i.e., N L

	Theorem 7
	Hence the number of non bent components is less than or equal to (2 n -1)/3.
	The number of bent components equals 2(2 n -1)/3 if and only if L(F ) =
	2 (n+2)/2 (t = 2).

Quadratic differentially two-valued functions

In this section we explore in some detail the link between the nonlinearity and the two-valued property. We will also focus on quadratic differentially 4uniform functions. First, we give a useful result for differentially two-valued functions.

Lemma 3

Let F be a differentially two-valued {0, 2 s } function over F 2 n . If s is even then n must be even too. In particular, F cannot be differentially 4-uniform when n is odd.

Then we can be more precise, regarding Theorem 4.

F is plateaued with single amplitude. For n even and s odd, equality cannot occur when F is plateaued with single amplitude.

An application of Theorem 6 is given by Theorem 8 in Section 5. Now we treat differentially two-valued {0, 4} functions.

Lemma 4

Let F be a quadratic function over F 2 n which is differentially twovalued {0, 4}. Then n is even and N L(F ) = 2 n-1 -2 n/2 if and only if F does not have bent components. Moreover, in this case ℓ(λ) = 2 for any λ ∈ F * 2 n . Proof. For δ = 2 s with s even, then n must be even by Lemma 3. If F does not have any bent components, say there is not any λ ∈ F * 2 n such that ℓ(λ) = 0, then ℓ(λ) ≥ 2 for all λ ∈ F * 2 n . But from Corollary 1, we have

which is possible if and only if ℓ(λ) = 2 for all λ. Now suppose that F has the best nonlinearity. Then F is plateaued with single amplitude, from Theorem 6. This amplitude is 2 (n+2)/2 providing that F has no bent component. ⋄ Assume that F is a quadratic permutation over F 2 n with δ = 4, where n is even. We know from Theorem 1 that F is two-valued. Moreover L(F ) = 2 (n+2)/2 from Lemma 4.