Page 149 - 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. 149
s Pasalic: Symmetric Key Cryptography and its Relation to Graph Theory 137
Given any two Boolean functions f , g ∈ n deciding whether they are EA-equivalent
or not is an important open problem. A direct verification requires a search over all the
elements of AG L( n ) and therefore its computational complexity is O(2n2 ). Since an ex-
haustive search over all the elements of AG L( n ) is not feasible for n ≥ 7, the decision
problem involving equivalence of Boolean functions is attempted by using carefully cho-
sen invariants. Algebraic degree of a non-affine Boolean function is an invariant with re-
spect to affine transformations and addition of affine functions. Therefore, two Boolean
functions with algebraic degree greater than or equal to 2 are EA-inequivalent if their al-
gebraic degrees are different. It is well known [3] that the absolute Walsh spectra of any
Boolean function f are invariants with respect to the action of AG L( n ) and the addi-
tion by an affine function. Unfortunately these invariants are not useful to determine
affine inequivalence of Boolean functions having the same algebraic degree and abso-
lute Walsh spectra. The problem of classifying Boolean functions and bent functions in
particular seems to be elusive.
Open Problem 4.3.3 Find new classes of bent functions by proving their affine non-equi-
valence to already known classes. The problem may also be viewed in terms of suitable
subgroups of permutations of the Walsh spectra. Indeed, since the dual bent function is
also bent it implies that either {α : Wf (α) = 2n/2} = 2n−1 −2n/2−1 and {α : Wf (α) = −2n/2} =
2n−1 + 2n/2−1 or vice versa. This is also related to a group action on the (multi)set of the
Walsh spectra.
Open Problem 4.3.4 A related concept to the above is so-called algebraic thickness which
refers to the most compact representation of a function by its ANF. For instance, the func-
tion f (x1, . . . , xn ) = x1x2 · · · xn (which is cryptographically disastrous, why ?) is obviously
affine equivalent to the function f (x1, . . . , xn ) = (x1 +1)(x2 +2) · · · (xn +1). While the former
contains a single term in its ANF, the latter contains all possible 2n terms in its ANF. Of
course, if we would implement such a function we would prefer the former one. Given any
function f ∈ n find efficiently its affine equivalent containing the least number of ANF
terms !
4.4 Vectorial Boolean functions - substitution boxes
The nonlinearity of F = ( f 1, f 2, . . . , f m ), denoted by NF , is defined as the minimum among
the nonlinearities of all nonzero linear combinations of the component functions of F ,
i.e.,
m
n l (F ) = min n l ( τ j f j (x )), where τ = (τ1, . . . , τm ) ∈ m ∗ . (4.11)
2
τ∈ m∗
2 j =1
Given any two Boolean functions f , g ∈ n deciding whether they are EA-equivalent
or not is an important open problem. A direct verification requires a search over all the
elements of AG L( n ) and therefore its computational complexity is O(2n2 ). Since an ex-
haustive search over all the elements of AG L( n ) is not feasible for n ≥ 7, the decision
problem involving equivalence of Boolean functions is attempted by using carefully cho-
sen invariants. Algebraic degree of a non-affine Boolean function is an invariant with re-
spect to affine transformations and addition of affine functions. Therefore, two Boolean
functions with algebraic degree greater than or equal to 2 are EA-inequivalent if their al-
gebraic degrees are different. It is well known [3] that the absolute Walsh spectra of any
Boolean function f are invariants with respect to the action of AG L( n ) and the addi-
tion by an affine function. Unfortunately these invariants are not useful to determine
affine inequivalence of Boolean functions having the same algebraic degree and abso-
lute Walsh spectra. The problem of classifying Boolean functions and bent functions in
particular seems to be elusive.
Open Problem 4.3.3 Find new classes of bent functions by proving their affine non-equi-
valence to already known classes. The problem may also be viewed in terms of suitable
subgroups of permutations of the Walsh spectra. Indeed, since the dual bent function is
also bent it implies that either {α : Wf (α) = 2n/2} = 2n−1 −2n/2−1 and {α : Wf (α) = −2n/2} =
2n−1 + 2n/2−1 or vice versa. This is also related to a group action on the (multi)set of the
Walsh spectra.
Open Problem 4.3.4 A related concept to the above is so-called algebraic thickness which
refers to the most compact representation of a function by its ANF. For instance, the func-
tion f (x1, . . . , xn ) = x1x2 · · · xn (which is cryptographically disastrous, why ?) is obviously
affine equivalent to the function f (x1, . . . , xn ) = (x1 +1)(x2 +2) · · · (xn +1). While the former
contains a single term in its ANF, the latter contains all possible 2n terms in its ANF. Of
course, if we would implement such a function we would prefer the former one. Given any
function f ∈ n find efficiently its affine equivalent containing the least number of ANF
terms !
4.4 Vectorial Boolean functions - substitution boxes
The nonlinearity of F = ( f 1, f 2, . . . , f m ), denoted by NF , is defined as the minimum among
the nonlinearities of all nonzero linear combinations of the component functions of F ,
i.e.,
m
n l (F ) = min n l ( τ j f j (x )), where τ = (τ1, . . . , τm ) ∈ m ∗ . (4.11)
2
τ∈ m∗
2 j =1
