Nonlinarity of Boolean functions and hyperelliptic curves

Eric Férard * , François Rodier †

Boolean functions is an important tool in computer sciences. It is especially useful in private key cryptography for designing stream ciphers. For security reasons, and also because Boolean functions need also to have other properties than nonlinearity such as balancedness or high algebraic degree, it is important to have the possibility of choosing among many Boolean functions, not only bent functions, that is functions with the highest possible non linearity, but also functions which are close to be bent in the sense that their nonlinearity is close to the nonlinearity of bent functions. For m odd, it would be particularly interesting to find functions with nonlinearity larger than the one of quadratic Boolean functions (called almost optimal in [START_REF] Canteaut | Fontaine Propagation characteristics and correlation-immunity of highly nonlinear Boolean functions[END_REF]). This has been done for instance in the work of Patterson and Wiedemann [START_REF] Patterson | The covering radius of the (2 15 , 16) Reed-Muller code is at least 16 276[END_REF] and also of Langevin-Zanotti [START_REF] Langevin | A note on the counter-example of Patterson-Wiedemann, Finite fields with applications to coding theory, cryptography and related areas[END_REF].

Let q = 2 m and F 2 m assimilated as a vector space to F m 2 . In this talk, we want to study functions of the form Tr G(x), where G is a polynomial on F 2 m and Tr the trace of F 2 m over F 2 .

For m even, many people got interested in finding bent functions of this form. To only mention the case of monomials, one can get the known cases (Gold , Dillon/Dobbertin, Niho exponents) in the paper of Leander [START_REF] Leander | Monomial Bent Functions[END_REF].

For m odd, one might have expected that among the functions f : x -→ Tr G(x) where G is a polynomial of degree 7, there are some functions which are close to being bent in the previous sense. This happens not to be the case, but we will show that for m odd such functions have rather good nonlinearity or autocorrelation properties. We use for that recent results of Maisner and Nart [START_REF] Maisner | Zeta functions of supersingular curves of genus 2[END_REF] about zeta functions of supersingular curves of genus 2.

On the other hand, vectorial Boolean functions are used in cryptography to construct block ciphers. An important criterion on these functions is a high resistance to the differential cryptanalysis. Nyberg [START_REF] Nyberg | Kaisa Differentially uniform mappings for cryptography[END_REF] has introduced the notion of almost perfect nonlinearity (APN) to study differential attacks. We relate this notion to the notion above, and we will give some criterion for a function not to be almost perfect nonlinear.

Preliminaries 1.Boolean functions

Let m be a positive integer and q = 2 m .

Definition 1.1 A Boolean function with m variables is a map from the space V m = F m 2 into F 2 .
A Boolean function is linear if it is a linear form on the vector space V m . It is affine if it is equal to a linear function up to addition of a constant.

Nonlinearity

Definition 1.2 We call nonlinearity of a Boolean function f : V m -→ F 2 the distance from f to the set of affine functions with m variables:

nl(f ) = min h affine d(f, h)
where d is the Hamming distance.

One can show that the nonlinearity is equal to

nl(f ) = 2 m-1 - 1 2 f ∞ where f ∞ = sup v∈Vm x∈Vm χ (f (x) + v • x) ,
where v • x denote the usual scalar product in V m and χ(f ) = (-1) f . It is the maximum of the Fourier transform of χ(f ) (the Walsh transform of f ):

f (v) = x∈Vm χ (f (x) + v • x) .
Parseval identity can be written

f 2 2 = 1 q v∈Vm f (v) 2 = q
and we get, for f a Boolean function on V m :

√ q ≤ f ∞ ≤ q.

The sum-of-square indicator

Let f be a Boolean function on V m . Zhang and Zheng introduced the sumof-square indicator [START_REF] Zhang | GAC -the Criterion for Global Avalanche Characteristics of Cryptographic Functions[END_REF], as a measure of the global avalanche criterion:

σ f = 1 q x∈Vm f (x) 4 = f 4 4 .
We remark that

f 2 ≤ f 4 ≤ f ∞ . (1)
Hence the values of f 4 may be considered as a first approximation of f ∞ and in some cases they may be easier to compute. The relationship of this function with non-linearity was studied by A. Canteaut et al. [START_REF] Canteaut | Fontaine Propagation characteristics and correlation-immunity of highly nonlinear Boolean functions[END_REF].

2 The functions f : x -→ Tr (G(x)) where G is a polynomial 2.1 Divisibility of f ∞ Let G(x) be the polynomial s i=0 a i x i with coefficients in F q and f the Boolean function Tr •G. Definition 2.1 The binary degree of G is the maximum value of σ(i) for 0 ≤ i ≤ s, where σ(i) is the sum of the binary digits of i.

One has the following proposition, due to C. Moreno and O. Moreno [START_REF] Moreno | The MacWilliams-Sloane conjecture on the tightness of the Carlitz-Uchiyama bound and the weights of duals of BCH codes[END_REF].

Proposition 2.1 Let G be a polynomial with coefficients in F q and binary degree d.

Then f ∞ is divisible by 2 ⌈ m d ⌉ .
2.2 Case where G is a polynomial of binary degree 2

The f ∞ are multiple of 2 ⌈ m 2 ⌉ . Therefore, if m is even f ∞ is a multiple of q 1/2 , and if m is odd, of √ 2q. In particular, if m is odd, the spectral amplitude is higher or equal to √ 2q which is equal to that of the quadratic Boolean functions, of the maximum rank.

3 The functions f :

x -→ Tr (G(x))
where G is a binary polynomial of degree 3

One simply will study the case where G is a binary polynomial of degree 2 to which one adds a monomial of degree 7:

G = a 7 x 7 + s b i x 2 i +1
where a 7 = 0 a polynomial of degree 7 with coefficients in k. We would like to evaluate f 4 on F 2 m , for f (x) = Tr (G(x)) where Tr indicates the function trace of F q on F 2 :

Tr(x) = m-1 i=0 x 2 i .
One obtains the simple expression of f 4 (cf [START_REF] Rodier | Sur la non-linéarité des fonctions booléennes[END_REF][START_REF] Rodier | On the nonlinearity of Boolean functions[END_REF]):

f 4 4 = x 1 +x 2 +x 3 +x 4 =0 χ (f (x 1 ) + f (x 2 ) + f (x 3 ) + f (x 4 )) = q 2 + α∈k * X α with X α = x∈k χ • Tr (G(x) + G(x + α)) 2 .
To compute X α , one can remark that the curve of equation y 2 + y = G(x + α) + G(x) is isomorphic to

y 2 + y = G(α)+ +(a 7 α 6 + a 1/4 7 α 3/4 + a 1/2 7 α 5/2 + (b i α) 2 -i + b i α 2 i )x+ +(a 7 α 4 + a 1/2 7 α 1/2 )x 3 + a 7 α 2 x 5
which is an equation of a curve C 1 of genus 2 for α = 0. One has

X α = (#C 1 -q -1) 2 .
To compute X α , we will need results of Van der Geer -van der Vlugt and of Maisner -Nart.

Van der Geer and van der Vlugt theory

Let C 1 the curve with affine equation:

C 1 : y 2 + y = ax 5 + bx 3 + cx + d
with a = 0. Let R be the linearized polynomial ax 4 + bx 2 + c 2 x. The map

Q : k → F 2 x → Tr(xR(x))
is the quadratic form associated to the symplectic form

k × k -→ F 2 (x, y) → < x, y > R = Tr(xR(y) + yR(x)).
The number of zeros of Q determines the number of points of C 1 :

#C 1 (k) = 1 + 2#Q -1 (0).
Let W be the radical of the symplectic form <, > R , and w be its dimension over F 2 . The codimension of the kernel V of Q in W is equal to 0 or 1. Theorem 3.1 (van der Geer -van der Vlugt [START_REF] Van Der Geer | Reed-Muller codes and supersingular curves. I[END_REF])

If V = W , then #C 1 (k) = 1 + q. If V = W , then #C 1 (k) = 1 + q ± √ 2 w q.

Values of X α

In [START_REF] Férard | Nonlinearity of some Boolean functions[END_REF], we study the factorization of P which determines V and W (see Maisner-Nart [START_REF] Maisner | Zeta functions of supersingular curves of genus 2[END_REF]). Thanks to the work of van der Geer -van der Vlugt, we can compute the number of points of the curves y 2 + y = G(x + α) + G(x).

Proposition 3.1 Suppose that m is odd. Then X α = 0 or 2q or 8q.

ßLet ℓ = a -1/3 7 α -7/3 . Then X α = 8q if and only if Tr ℓ = 0 , ℓ = v + v 4 with Tr v = 0 , Tr (a + c)α λ v 3 = 1 , Tr (a + c)α λ (v + v 2 ) = 1 ; X α =
| f 4 4 -3q 2 | ≤ 185.2 s-1 q 3/2 .

Proof

One can evaluate the number of α which gives each case of the preceding proposition. The proves of these evaluations are linked with the computations of exponential sums over the curve v + v 4 = γx 7 . We get

#{α | X α = 8q} - 1 8 ≤ 23.2 s-1 q 1/2 #{α | X α = 2q} - 1 2 ≤ 3q 1/2 + 1
One deduce easily the evaluation of f 4 4 . The details of the proof will appear in [START_REF] Férard | Nonlinearity of some Boolean functions[END_REF].

Remark 4.1 This result is to be compared with proposition 5.6 in [START_REF] Rodier | Sur la non-linéarité des fonctions booléennes[END_REF] where the distribution of f 4 4 for all Boolean function is shown to be concentrated around 3q 2 .

5 Bound for f ∞ From the theorem, we can deduce some lower bounds for f ∞ .

Proposition 5.1 For the functions f : x -→ Tr (G(x)) on F 2 m where G is the polynomial G = a 7 x 7 + s b i x 2 i +1 and m is odd one has, for m ≤ 11+2s: 2q ≤ f ∞ .

For m ≥ 15 + 2s, one has moreover:

2q < f ∞ .

Proof

The evaluation of the number of α such that Tr ℓ = 1 in proposition 3.1 gives: 2q

2 -6q 3/2 ≤ f 4 4 .
As it is easy to show that

f 4 4 ≤ q f 2 ∞
we get 2q -6q 1/2 ≤ f 2 ∞ whence the result, as f ∞ is divisible by 2 ⌈m/3⌉ . The second inequality is a consequence of theorem 4.1.

Remark 5.1 So f is not almost optimal (in the sense of [START_REF] Canteaut | Fontaine Propagation characteristics and correlation-immunity of highly nonlinear Boolean functions[END_REF]), for m ≥ 15 + 2s.

APN Functions

Let us consider a function G : F q -→ F q . Definition 6.1 The function G is said to be APN (almost perfect nonlinear) if for every a ∈ F * q and b ∈ F q , there exists at most 2 elements of F q such that G(z + a) + G(z) = b. Proposition 6.1 The function

G : F q -→ F q x → a 7 x 7 + s 0 b i x 2 i +1
is not APN for m ≥ 13 + 2s.

Proof

For γ ∈ F q , consider the function f γ (x) = Tr(G(γx)). The proposition follows from proposition 4.1 and the following result from Chabaud-Vaudenay [START_REF] Chabaud | Serge Links between differential and linear cryptanalysis[END_REF]. Proposition 6.2 One has γ∈k * σ(f γ ) ≥ 2q 2 (q -1).

The function G is APN if and only if the equality is true.

For s ≤ 2, one can even say more. The following theorem [START_REF] Rodier | Borne sur le degré des polynômes presque parfaitement non-linéaires[END_REF] proves that the function G is not APN for m ≥ 11. Theorem 6.1 Let G be a polynomial from F 2 m to F 2 m , d its degree. Let us suppose that the curve X ∞ of equation

x d 0 + x d 1 + x d 2 + (x 0 + x 1 + x 2 ) d (x 0 + x 1 )(x 2 + x 1 )(x 0 + x 2 )
= 0 is smooth. Then if m ≥ 6 and d < q 1/6 + 3.9, G is not APN.

4 Evaluation of f 4 4 4 . 1

 441 2q if and only if Tr ℓ = 1 ; X α = 0 in the remaining cases. Proposition The value of f 4 4 on F 2 m when m is odd and f (x) = Tr (G(x)) is such that