Page 152 - 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. 152
4.5 Vectorial bent functions
Example 4.4.6 Let F (x ) = x 3 over 23 defined by a primitive polynomial p (x ) = x 3 + x + 1
over 2. Let α be primitive element of 23 , i.e., α3 = α + 1 and let {1, α, α2} be a polynomial
basis of 23 . Then the component functions of F (x ) = 1 · f 1(x1, x2, x3) + α f 2(x1, x2, x3) +
α2 f 3(x1, x2, x3) are derived as,
F (x ) = x 3 = (x0 + αx1 + α2x2)3 =
= (x0 + αx1 + α2x2)(x0 + αx1 + α2x2)2 =
= (x0 + αx1 + α2x2)(x0 + α2x1 + α4x2) α3==α+1 . . .
= (x0 + x1 + x2 + x1x2) + α(x1 + x0x1 + x0x2) + α2(x2 + x0x1)
Notice that the algebraic degree of F above is 2 since the binary (Hamming) weight of 3
is w t (3) = 2. Concludingly, even though x 3 is an APN permutation and an AB function as
well (thus achieving the maximum nonlinearity) its algebraic degree is low and therefore
its use in block ciphers is not recommended. We conclude this section with one of the
most elegant problem in the theory of finite fields (related to cryptography) which is the
existence of APN permutations for even n.
Open Problem 4.4.7 For even n > 6, find a class (or single function) which is an APN
permutation or disprove their existence !! Only recently, Dillon [2] exceptionally confirmed
the existence of such mappings for n = 6 using very sophisticated connections with coding
theory.
4.5 Vectorial bent functions
While the construction of Boolean bent functions (at least those in class was easy
and generic, the construction of F : n → k is not that obvious. Now we have to ensure
2 2
that for F (x ) = ( f 1(x ), . . . , f k (x )) all nonzero linear combinations of the form a 1 f 1(x ) +
. . . + a k f k (x ) are bent, where f i are Boolean functions. The bound on k for which it is
possible to find such a collection was given by Nyberg [8], that is, k ≤ n/2. The design of
such functions achieving the upper bound on k , that is k = n/2, was only given in terms
of sequences and the representation of these functions in [14] is not univariate (meaning
that their representation as polynomials over finite fields is unclear). In a recent work [7],
the structure of the cyclic group of the 2k + 1 roots of the unity was used to derive one
complete class of vectorial bent functions F : n → n /2 in a univariate representation.
2 2
Let us define the trace function Trmn : 2n → 2m , a mapping to a subfield 2m when
m | n, is defined as
T rmn (x ) = x + x 2m + x 22m + . . . + x 2(n/m−1)m , for all x ∈ 2n . (4.15)
The absolute trace Tr1n : 2n → 2, also denoted by Tr , then maps to the prime field.
Let also n = 2k , and denote by L the field 2n and its subfield 2k by K . Let =
Example 4.4.6 Let F (x ) = x 3 over 23 defined by a primitive polynomial p (x ) = x 3 + x + 1
over 2. Let α be primitive element of 23 , i.e., α3 = α + 1 and let {1, α, α2} be a polynomial
basis of 23 . Then the component functions of F (x ) = 1 · f 1(x1, x2, x3) + α f 2(x1, x2, x3) +
α2 f 3(x1, x2, x3) are derived as,
F (x ) = x 3 = (x0 + αx1 + α2x2)3 =
= (x0 + αx1 + α2x2)(x0 + αx1 + α2x2)2 =
= (x0 + αx1 + α2x2)(x0 + α2x1 + α4x2) α3==α+1 . . .
= (x0 + x1 + x2 + x1x2) + α(x1 + x0x1 + x0x2) + α2(x2 + x0x1)
Notice that the algebraic degree of F above is 2 since the binary (Hamming) weight of 3
is w t (3) = 2. Concludingly, even though x 3 is an APN permutation and an AB function as
well (thus achieving the maximum nonlinearity) its algebraic degree is low and therefore
its use in block ciphers is not recommended. We conclude this section with one of the
most elegant problem in the theory of finite fields (related to cryptography) which is the
existence of APN permutations for even n.
Open Problem 4.4.7 For even n > 6, find a class (or single function) which is an APN
permutation or disprove their existence !! Only recently, Dillon [2] exceptionally confirmed
the existence of such mappings for n = 6 using very sophisticated connections with coding
theory.
4.5 Vectorial bent functions
While the construction of Boolean bent functions (at least those in class was easy
and generic, the construction of F : n → k is not that obvious. Now we have to ensure
2 2
that for F (x ) = ( f 1(x ), . . . , f k (x )) all nonzero linear combinations of the form a 1 f 1(x ) +
. . . + a k f k (x ) are bent, where f i are Boolean functions. The bound on k for which it is
possible to find such a collection was given by Nyberg [8], that is, k ≤ n/2. The design of
such functions achieving the upper bound on k , that is k = n/2, was only given in terms
of sequences and the representation of these functions in [14] is not univariate (meaning
that their representation as polynomials over finite fields is unclear). In a recent work [7],
the structure of the cyclic group of the 2k + 1 roots of the unity was used to derive one
complete class of vectorial bent functions F : n → n /2 in a univariate representation.
2 2
Let us define the trace function Trmn : 2n → 2m , a mapping to a subfield 2m when
m | n, is defined as
T rmn (x ) = x + x 2m + x 22m + . . . + x 2(n/m−1)m , for all x ∈ 2n . (4.15)
The absolute trace Tr1n : 2n → 2, also denoted by Tr , then maps to the prime field.
Let also n = 2k , and denote by L the field 2n and its subfield 2k by K . Let =
