Page 151 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 151
s Pasalic: Symmetric Key Cryptography and its Relation to Graph Theory 139
Referring back to our finite filed representation we now assume that n = m and consider
the derivative of F (x ) ∈ 2n [x ] (the ring of polynomials with coefficients in n ). That
2
is, for F (x ) ∈ 2n [x ] we consider the number of solutions to F (x + a ) + F (x ) = b , where
a∈ ∗ and b ∈ 2n . Notice that if x0 is a solution to this equation for some fixed a
2n
and b then x0 + a is a solution as well. Also, if a is fixed then clearly b∈ 2n δF (a ,b ) = 2n .
Therefore, the functions for which δ(F ) = 2 attains the lowest possible differential spectra
and are called almost perfect nonlinear (APN) functions.
Remark 4.4.4 The term perfect nonlinear functions is reserved for polynomials over q
where the prime characteristic of the filed p = 2. In this case, there exists mappings F (x ) ∈
q [x ] such that F (x + a ) − F (x ) is a permutation over Fq for any a ∈ ∗ , thus F (x + a ) −
q
F (x ) = b has exactly one solution for any a ∈ ∗ and b ∈ q . Such mappings are called
q
planar mappings and the known classes mainly come from linearized polynomials. For
instance, the mapping F (x ) = x 2 is planar over pn , for p = 2, since F (x + a ) − F (x ) =
x 2 + 2a x + a 2 −x 2 = 2a x + a 2 due to the fact that αx + β is a permutation over pn for any
nonzero α and any β .
Example 4.4.5 Let F (x ) = x 3 over 2n , where n is odd. Then, F is an APN permutation.
The permutation property being clear, we need to show that F (x + a ) + F (x ) = b admits at
most two solutions for any a ∈ ∗ and b ∈ 2n . Indeed, F (x + a ) + F (x ) = (x + a )3 + x 3 =
2n
a x 2 +a 2x +a 3 so that a x 2 +a 2x +a 3 = b is of degree 2 and can have at most two solutions
in the field.
Since for any α ∈ 2n we have α2n −1 = 1 it is sufficient to consider polynomials of de-
gree up to 2n − 1, that is the polynomials of the form F (x ) = 2n −1 a i x i , where ai ∈ 2n .
i =0
Notice that this global degree of a polynomial in 2n [x ] does not correspond to the al-
gebraic degree of F defined previously. More precisely, the algebraic degree of F corre-
sponds to the largest Hamming weight of i for which a i = 0, see Carlet [1] which is an
excellent reference for all topics treated here. To realize this consider F (x ) = x 4 over 2n
whose algebraic degree is only 1 since it belongs to the class of linearized polynomials
over the finite filed of the form L(x ) = n −1 a i x 2i . If α1, . . . , αn is a basis of 2n (through
i =0
the isomorphism of n and 2n ) so that any element x ∈ 2n can be uniquely represented
2
as x = x1α1 + . . . + xn αn , where xi ∈ 2, then,
x4 = (x 1 α1 + . . . + xn αn )4 = x 4 α14 + ... + x 4 α4n = x 1 α41 + . . . + xn α4n ,
1 n
since in the Boolean ring x 2 = xi . In this representation we actually consider F : n → n ,
i 2 2
where x = (x1, . . . , xn ) → ( f 1(x1, . . . , xn ), . . . , f n (x1, . . . , xn )), and each f i is a linear Boolean
function. Notice that α14, . . . , α4n is just a linear transformation of the basis (Forbenius
automormhism).
Referring back to our finite filed representation we now assume that n = m and consider
the derivative of F (x ) ∈ 2n [x ] (the ring of polynomials with coefficients in n ). That
2
is, for F (x ) ∈ 2n [x ] we consider the number of solutions to F (x + a ) + F (x ) = b , where
a∈ ∗ and b ∈ 2n . Notice that if x0 is a solution to this equation for some fixed a
2n
and b then x0 + a is a solution as well. Also, if a is fixed then clearly b∈ 2n δF (a ,b ) = 2n .
Therefore, the functions for which δ(F ) = 2 attains the lowest possible differential spectra
and are called almost perfect nonlinear (APN) functions.
Remark 4.4.4 The term perfect nonlinear functions is reserved for polynomials over q
where the prime characteristic of the filed p = 2. In this case, there exists mappings F (x ) ∈
q [x ] such that F (x + a ) − F (x ) is a permutation over Fq for any a ∈ ∗ , thus F (x + a ) −
q
F (x ) = b has exactly one solution for any a ∈ ∗ and b ∈ q . Such mappings are called
q
planar mappings and the known classes mainly come from linearized polynomials. For
instance, the mapping F (x ) = x 2 is planar over pn , for p = 2, since F (x + a ) − F (x ) =
x 2 + 2a x + a 2 −x 2 = 2a x + a 2 due to the fact that αx + β is a permutation over pn for any
nonzero α and any β .
Example 4.4.5 Let F (x ) = x 3 over 2n , where n is odd. Then, F is an APN permutation.
The permutation property being clear, we need to show that F (x + a ) + F (x ) = b admits at
most two solutions for any a ∈ ∗ and b ∈ 2n . Indeed, F (x + a ) + F (x ) = (x + a )3 + x 3 =
2n
a x 2 +a 2x +a 3 so that a x 2 +a 2x +a 3 = b is of degree 2 and can have at most two solutions
in the field.
Since for any α ∈ 2n we have α2n −1 = 1 it is sufficient to consider polynomials of de-
gree up to 2n − 1, that is the polynomials of the form F (x ) = 2n −1 a i x i , where ai ∈ 2n .
i =0
Notice that this global degree of a polynomial in 2n [x ] does not correspond to the al-
gebraic degree of F defined previously. More precisely, the algebraic degree of F corre-
sponds to the largest Hamming weight of i for which a i = 0, see Carlet [1] which is an
excellent reference for all topics treated here. To realize this consider F (x ) = x 4 over 2n
whose algebraic degree is only 1 since it belongs to the class of linearized polynomials
over the finite filed of the form L(x ) = n −1 a i x 2i . If α1, . . . , αn is a basis of 2n (through
i =0
the isomorphism of n and 2n ) so that any element x ∈ 2n can be uniquely represented
2
as x = x1α1 + . . . + xn αn , where xi ∈ 2, then,
x4 = (x 1 α1 + . . . + xn αn )4 = x 4 α14 + ... + x 4 α4n = x 1 α41 + . . . + xn α4n ,
1 n
since in the Boolean ring x 2 = xi . In this representation we actually consider F : n → n ,
i 2 2
where x = (x1, . . . , xn ) → ( f 1(x1, . . . , xn ), . . . , f n (x1, . . . , xn )), and each f i is a linear Boolean
function. Notice that α14, . . . , α4n is just a linear transformation of the basis (Forbenius
automormhism).
