Figure 2.7: Computation of the BCT at point(a,b)for an S-boxS
bility studied in (2.2) whenEmis an S-box. There is a strong relation between boomerang and differential uniformity. The former is always bigger than or equal to the latter and functions with optimal differential uniformity also have optimal boomerang uniformity.
Another rather powerful attack on symmetric cryptosystems is the linear attack, see [88]. This attack is effective when it is possible to find good linear approximations to the cipher up to a certain number of rounds. The nonlinear-ity property evaluates the resistance of the S-box to such attack.
As already mentioned, optimal cryptographic functions, are often optimal for other mathematical fields as well. Hence studying and getting a better un-derstanding of such functions can lead to important results in other research areas. The work of this thesis is focused on the differential uniformity prop-erty and on the boomerang uniformity propprop-erty. In particular it focuses on the study of optimal vectorial Boolean functions with respect to these properties.
2.2 Functions over finite fields
We present here necessary mathematical notions for understanding the con-tent of the next chapters. Even though most of the results presented in this work concern finite fields of even characteristic, we prefer to introduce many mathematical objects in their general definition. This is done in particular for definitions that will be used also for the case of finite fields of odd
characteris-tic in Chapter7.
Forpa prime number andna positive integer, we defineFpnthe finite field with pn elements, and Fnp the n-dimensional vector space over Fp, where an elementλ∈Fnp is of the formλ= (λ1, . . . ,λn). The p-weight of λ∈Fnpis the integerwp(λ) =∑ni=1λi. Instead, thep-weight of a positive integerk≤pn−1 is thep-weight of thep-ary expansion∑ni=−01pikiofk, that iswp(k0, . . . ,kn−1). With F⋆pn=hζiwe denote the multiplicative subgroup ofFpn, whereζis a primitive element. In general, for any setE,E⋆denotes its subsetE\ {0}.
Definition 2.1. An(n,m,p)-function, or avectorial function, is a map F from the vector spaceFnpto the vector spaceFmp. When p=2, such function is simply called an (n,m)-functionor avectorial Boolean function.
Remark 2.1. We assume here and in the next chapters that, when referring to an (n,m,p)-function, we have m≤n.
When m =1, the function is usually denoted by a lower case f and it is called aBoolean functionwhenp=2. In this last case we call f also ann-variable Boolean function.
An(n,m,p)-functionFcan be seen as a vector of(n, 1,p)-functions:
F= (f1, . . . ,fm),
where f1, . . . ,fm are (n, 1,p)-functions called the coordinates of F. Given an elementλ∈Fmp,λ6=0, theλ-component ofFis the(n, 1,p)-function
fλ=λ·F=
∑
m i=1λifi.
A vectorial function admits different representations. Thealgebraic normal form, shortly ANF, of an(n,m,p)-functionFis its representation as a polynomial with coefficients inFmp. Hence the ANF representation ofF∈Fmp[x1, . . . ,xn]is of the form
F(x1, . . . ,xn) =
∑
u∈Fnp
au
∏
n i=1xuii, withau∈Fmp.
Thealgebraic degreeof F, denoted as deg(F), is the maximum value in the set {wp(u):u∈Fnp s.t.au6= (0, . . . , 0)}and it corresponds to the maximum alge-braic degree of the coordinate functions ofF.
2.2 Functions over finite fields 19 The value set or image set ofFis denoted by Im(F), i.e. Im(F) ={F(c):c∈ Fnp}, and the set of roots ofFoverFnpis denoted by Ker(F). Whenm=nthe polynomialFis apermutation polynomial(PP) overFnpif Im(F) =Fnp, and it is a complete mappingoverFnpif bothFandF+Idare PPs. WithIdwe indicate the identity map, i.e. Id(u) =ufor everyu∈Fnp.
An(n,m,p)-function is calledbalancedif it takes every value ofFmp the same number pn−m of times. It is equivalent to have all the non-zero components balanced. Obviously, form=n, balanced functions are the permutations ofFnp. Whenm=ntheunivariate polynomial representationis often used. Indeed, the vector spaceFnp is identified with the finite fieldFpn, and a functionF:Fpn → Fpn admits a unique representation as a polynomial overFpnof degree at most pn−1,
F(x) =
pn−1 i
∑
=0aixi, with ai∈Fpn.
In this case the algebraic degree can be expressed using the p-weight of the exponents. It corresponds to the maximal p-weight ofi such that ai 6=0, see [42, p. 404] for the case p=2.
Given an(n,n,p)-functionF, we callF
• pm-linearor apm-polynomial, forma positive divisor ofn, if it is of the form F(x) =∑n/mi=0−1aixpmi, withai∈Fpn;
• linearif it is of the formF(x) =∑ni=−01aixpi, withai∈Fpn;
• affineif it is the sum of a linear function and a constant;
• DO polynomial(Dembowski-Ostrom polynomial) if it is of the formF(x) =
∑ni,j−=10aijxpi+pj, withaij∈Fpn (ifp=2 theni<j);
• quadraticif it is the sum of a DO polynomial and an affine function.2 A well-known example of linear function is the tracefunction that maps Fpn
intoFp:
Trn(x) =Tr(x) =x+xp+xp2+. . .+xpn−1=
n−1 k
∑
=0xpk.
Forma positive divisor ofn, the map Trmn denotes the trace function fromFpn
intoFpm:
Trmn(x) =Trm(x) =x+xpm+xp2m+. . .+xp(n/m−1)m.
2Affine functions and quadratic functions have algebraic degree at most one and two respectively.
For the univariate representation, theλ-component ofFis the mapfλ=Tr(λF). Remark 2.2. If m is a positive divisor of n, then a map F:Fpn →Fpm admits a univariate polynomial representation since it can be viewed as a function fromFpn to itself.
2.2.1 The differential uniformity
Definition 2.2.For an(n,m,p)-function F and(a,b)∈Fnp×Fmp, letδF(a,b)be the number of solutions of the equation F(x+a)−F(x) =b. Then the value
δF= max
a∈Fnp\{0},b∈Fmp
δF(a,b) (2.3)
is called the differential uniformity of F and F is said to be differentially δF -uniform. The function
∆F(x,y) =F(x+y)−F(x)−F(y)∈Fmp[x,y] is called thedifference operator ofF and the map
DaF(x) =F(x+a)−F(x) =∆F(x,a) +F(a) is thederivative ofFin the direction ofa.
When the mapF, considered in its univariate polynomial representation, is a power function, then the differential uniformity can be computed by fixing a=1. Indeed, forF(x) =xd,DaF(x) = (x+a)d−xd=ad x
a+1d
− xad. The number of solutions ofDaF(x) =bequals the number of solutions ofD1F(x) =
b ad.
Differential uniformity measures the resistance ofF, used as an S-box inside a cryptosystem, to the differential attack. To achieve a good resistance, the value ofδF has to be small. Hence the best resistance is achieved whenδF= pn−mand in this case the functionFis calledperfect nonlinear(PN). A function F is perfect nonlinear if and only if all its derivatives, except the one in the zero direction, are balanced, see Proposition 9.3 in [42] for the casep=2. For m=nsuch functions, withδF=1, that is, with all non-zero derivatives being permutations, are also calledplanar.
Clearly, forp=2, the smallest value achievable for(n,n)-functions is 2. In-deed ifx0 is a solution ofDaF(x) =b, alsox0+asatisfies the equation. In even characteristic, functions that achieve the best resistance are calledalmost perfect nonlinear(APN).
2.2 Functions over finite fields 21
2.2.2 Equivalence relations
In order to study vectorial functions, it is important to use equivalence rela-tions. This is especially true since the number of functions is so huge that it is not feasible to analyse each function. In this situation, it is easier to divide the set of all functions into equivalence classes and, for each class, study the prop-erties of one representative function. For example, the total number of (n, n)-functions is(2n)2n but, when considering an equivalence relation, the number of classes may be considerably smaller. Even for small dimensions the equiv-alence relations give us a big advantage. Indeed for n=4 there are in total 264 (4,4)-functions but, for the case of EA-equivalence, it has been computed that there are only 4713 different classes, see [20]. Since we are mainly inter-ested in studying the differential property of vectorial functions, we introduce equivalence relations that preserve the differential uniformity.
GivenF,F0two functions fromFnptoFmp, they are called
• linear equivalentif F0=A1◦F◦A2, for A1,A2 linear permutations ofFmp andFnprespectively;
• affine equivalent ifF0 =A1◦F◦A2, for A1,A2 affine permutations ofFmp andFnprespectively;
• extended affine equivalent(EA-equivalent) if F0 =F00+A, for A (n,m,p) -affine map andF00(n,m,p)-function affine equivalent toF;
• Carlet-Charpin-Zinoviev equivalent(CCZ-equivalent [44]) if there exists an affine permutationLofFnp×Fmp that maps the graph ofFinto the graph ofF0(L(ΓF) =ΓF0), whereΓF={(x,F(x)):x∈Fnp}andΓF0={(x,F0(x)): x∈Fnp}.
These relations are connected to each other: linear equivalence is a particular case of affine equivalence, affine equivalence is contained in EA-equivalence and EA-equivalence is contained in CCZ-equivalence. Moreover, every per-mutation is CCZ-equivalent to its inverse, while, in general, a perper-mutation and its inverse are not EA-equivalent. When a function is not affine, its algebraic degree is preserved via EA-equivalence but not via equivalence. CCZ-equivalence is so far the most general notion of CCZ-equivalence for which the dif-ferential uniformity is an invariant. Indeed, it has been proved to be more gen-eral than EA-equivalence together with taking the inverse of a permutation, see
[32]. However there are some specific cases for which these two equivalences coincide:
• for planar functions, in the case of DO planar functions they coincide also with linear equivalence, [33];
• for Boolean functions, [27];
• two quadratic APN functions are CCZ-equivalent if and only if they are EA-equivalent, as conjectured by Edel and proved by Yoshiara in [105].
Another notion of equivalence is known for planar quadratic functions which preserve differential uniformity and which is more general than CCZ-equivalence. This equivalence is called isotopic equivalence and it will be ex-plained in Section2.4.