Page 148 - 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. 148
4.3 Equivalence classes of Boolean functions
Proposition 4.2.18 Let f be defined as above and for p > q assume that π is injective.
Then, N f = 2n−1 − 2p−1. In addition, if w t (φ(y )) ≥ t + 1 for all y ∈ q then f is t -resilient.
2
PROOF. Let n = p × q . All we have to do is to show that max(a,b)∈ p × q | Wf (a ,b ) |= 2p .
2 2 2 2 2
We have,
Wf (a ,b ) = (−1) f (x , y ) + (a ,b ) · (x , y ) = (−1)g (y )+b·y (−1)φ(y ) · x + a · x .
y∈ q x∈ p y∈ q x∈ p
2 2 2 2
Then again, for any fixed y ∈ q the sum x∈ p (−1)φ(y ) · x + a · x = 0, unless π(y ) = a .
Since 2 1. In the case π(y ) = a we
q a} 2
π is injective then #{y ∈ 2 : π(y ) =
is either 0 or
have x∈ p (−1)φ(y ) · x +a ·x = 2p , and the first part follows. The second part is left as
2
an exercise.
Example 4.2.19 Let n = 6, p = 4, q = 2 and (x , y ) ∈ 4 × 2 . Define injective π : 2 → 4
2 2 2 2
as π(00) = (1100), π(10) = (0110), π(01) = (1010), π(1) = (10011). Then, for any fixed
y the function f (x , y ) is a linear function in x1, . . . , x4. More precisely, f (x , 00) = x1 + x2,
f (x , 10) = x2+x3, f (x , 01) = x1+x3, f (x , 11) = x1+x3+x4. Then f is 1-resilient, d e g ( f ) = 3
(check this !), and f = 24.
More advanced construction methods are not treated here due to their tedious repre-
sentation. The currently best known methods are given recently by Pasalic and Zhang
based on the use of disjoint linear codes (resilient S-boxes) and a subtle modification of
the Maiorana-McFarland construction for resilient Boolean functions.
4.3 Equivalence classes of Boolean functions
The group of all invertible 2-linear transformations on n is denoted by G L( n ).
Definition 4.3.1 Two Boolean functions f , g ∈ n are said to be affine equivalent if and
only if there exist A ∈ G L( n ) and b ∈ n such that
g (x ) = f (Ax + b ) for all x ∈ n . (4.9)
The affine general linear group AG L( n ) consists of all the element of the form (A,b ). It
can be verified that the transformation f (x ) → f (Ax +b ) is a group action of AG L( n ) on
n.
Definition 4.3.2 Two Boolean functions f , g ∈ n are said to be extended affine equiva-
lent (EA-equivalent, or, equivalent) if and only if apart from A and b as above there exist
µ ∈ n and ε ∈ 2 such that
g (x ) = f (Ax + b ) + µ · x + ε for all x ∈ n . (4.10)
2
Proposition 4.2.18 Let f be defined as above and for p > q assume that π is injective.
Then, N f = 2n−1 − 2p−1. In addition, if w t (φ(y )) ≥ t + 1 for all y ∈ q then f is t -resilient.
2
PROOF. Let n = p × q . All we have to do is to show that max(a,b)∈ p × q | Wf (a ,b ) |= 2p .
2 2 2 2 2
We have,
Wf (a ,b ) = (−1) f (x , y ) + (a ,b ) · (x , y ) = (−1)g (y )+b·y (−1)φ(y ) · x + a · x .
y∈ q x∈ p y∈ q x∈ p
2 2 2 2
Then again, for any fixed y ∈ q the sum x∈ p (−1)φ(y ) · x + a · x = 0, unless π(y ) = a .
Since 2 1. In the case π(y ) = a we
q a} 2
π is injective then #{y ∈ 2 : π(y ) =
is either 0 or
have x∈ p (−1)φ(y ) · x +a ·x = 2p , and the first part follows. The second part is left as
2
an exercise.
Example 4.2.19 Let n = 6, p = 4, q = 2 and (x , y ) ∈ 4 × 2 . Define injective π : 2 → 4
2 2 2 2
as π(00) = (1100), π(10) = (0110), π(01) = (1010), π(1) = (10011). Then, for any fixed
y the function f (x , y ) is a linear function in x1, . . . , x4. More precisely, f (x , 00) = x1 + x2,
f (x , 10) = x2+x3, f (x , 01) = x1+x3, f (x , 11) = x1+x3+x4. Then f is 1-resilient, d e g ( f ) = 3
(check this !), and f = 24.
More advanced construction methods are not treated here due to their tedious repre-
sentation. The currently best known methods are given recently by Pasalic and Zhang
based on the use of disjoint linear codes (resilient S-boxes) and a subtle modification of
the Maiorana-McFarland construction for resilient Boolean functions.
4.3 Equivalence classes of Boolean functions
The group of all invertible 2-linear transformations on n is denoted by G L( n ).
Definition 4.3.1 Two Boolean functions f , g ∈ n are said to be affine equivalent if and
only if there exist A ∈ G L( n ) and b ∈ n such that
g (x ) = f (Ax + b ) for all x ∈ n . (4.9)
The affine general linear group AG L( n ) consists of all the element of the form (A,b ). It
can be verified that the transformation f (x ) → f (Ax +b ) is a group action of AG L( n ) on
n.
Definition 4.3.2 Two Boolean functions f , g ∈ n are said to be extended affine equiva-
lent (EA-equivalent, or, equivalent) if and only if apart from A and b as above there exist
µ ∈ n and ε ∈ 2 such that
g (x ) = f (Ax + b ) + µ · x + ε for all x ∈ n . (4.10)
2
