Page 147 - 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. 147
s Pasalic: Symmetric Key Cryptography and its Relation to Graph Theory 135
For any bent function f one may define its dual f˜ as (−1)f˜(x) = 2−n/2Wf (x ) for all
x∈ n .
2
Proposition 4.2.15 The dual bent function f˜ of a bent function f is again bent.
PROOF. If f is bent the inverse Walsh transform gives, (−1)f (x) = 2−n α∈ n Wf (α)(−1)α·x ,
2n /2 (−1) f˜(α) f˜, 2
for all x ∈ n . Replacing Wf (α) = from the definition of we get
2
2n/2(−1)f (x ) = (−1)f˜(α)(−1)α·x = (−1)f˜+α·x = Wf˜(α),
α∈ n α∈ n
2 2
thus Wf˜(α) ∈ {−2n/2, 2n/2} and f˜ is bent.
One class of bent functions of particular importance, known as the Maiorana-McFar-
land class, is specified as follows. Let us, for n = 2k , identify n with k × k . Suppose
2 2 2
π: k → k is a permutation and g ∈ k . A function f : k × k → 2 defined by
2 2 2 2
f (x , y ) = x · π(y ) + g (y ), for all x , y ∈ k , (4.7)
2
is a bent function and this class is denoted as .
Proposition 4.2.16 The function f defined by (4.7) is a bent function.
PROOF. The Walsh transform at (a ,b ) ∈ k × k equals to:
2 2
Wf (a ,b ) = (−1)f (x ,y )+(a ,b )·(x ,y ) = (−1)g (y )+b ·y (−1)x ·π(y )+a ·x .
x∈ k y ∈ k y∈ k x∈ k
2 2 2 2
For any fixed y the sum x∈ k (−1)x ·π(y )+a ·x = x∈ k (−1)x ·(π(y )+a ) = 0, unless π(y ) = a
2 2
which happens exactly for one y = π−1(a ). In the case π(y ) = a the sum
(−1)x ·(π(y )+a ) = 2k ,
x∈ k
2
and therefore Wf (a ,b ) = 2k (−1)g (π−1(a ))+b·π−1(a ), thus f is bent.
Notice that the class contains as a subclass a class of bent functions, but it can
also generate resilient functions with high nonlinearity. To see this we modify the above
definition as follows,
Definition 4.2.17 For any positive integers p , q such that n = p + q , a function f ∈ n in
the Maiorana McFarland class is defined by
f (x , y ) = φ(y ) · x ⊕ g (y ), x ∈ p , y ∈ q , (4.8)
where φ is any mapping from q to p , g ∈ q is arbitrary.
For any bent function f one may define its dual f˜ as (−1)f˜(x) = 2−n/2Wf (x ) for all
x∈ n .
2
Proposition 4.2.15 The dual bent function f˜ of a bent function f is again bent.
PROOF. If f is bent the inverse Walsh transform gives, (−1)f (x) = 2−n α∈ n Wf (α)(−1)α·x ,
2n /2 (−1) f˜(α) f˜, 2
for all x ∈ n . Replacing Wf (α) = from the definition of we get
2
2n/2(−1)f (x ) = (−1)f˜(α)(−1)α·x = (−1)f˜+α·x = Wf˜(α),
α∈ n α∈ n
2 2
thus Wf˜(α) ∈ {−2n/2, 2n/2} and f˜ is bent.
One class of bent functions of particular importance, known as the Maiorana-McFar-
land class, is specified as follows. Let us, for n = 2k , identify n with k × k . Suppose
2 2 2
π: k → k is a permutation and g ∈ k . A function f : k × k → 2 defined by
2 2 2 2
f (x , y ) = x · π(y ) + g (y ), for all x , y ∈ k , (4.7)
2
is a bent function and this class is denoted as .
Proposition 4.2.16 The function f defined by (4.7) is a bent function.
PROOF. The Walsh transform at (a ,b ) ∈ k × k equals to:
2 2
Wf (a ,b ) = (−1)f (x ,y )+(a ,b )·(x ,y ) = (−1)g (y )+b ·y (−1)x ·π(y )+a ·x .
x∈ k y ∈ k y∈ k x∈ k
2 2 2 2
For any fixed y the sum x∈ k (−1)x ·π(y )+a ·x = x∈ k (−1)x ·(π(y )+a ) = 0, unless π(y ) = a
2 2
which happens exactly for one y = π−1(a ). In the case π(y ) = a the sum
(−1)x ·(π(y )+a ) = 2k ,
x∈ k
2
and therefore Wf (a ,b ) = 2k (−1)g (π−1(a ))+b·π−1(a ), thus f is bent.
Notice that the class contains as a subclass a class of bent functions, but it can
also generate resilient functions with high nonlinearity. To see this we modify the above
definition as follows,
Definition 4.2.17 For any positive integers p , q such that n = p + q , a function f ∈ n in
the Maiorana McFarland class is defined by
f (x , y ) = φ(y ) · x ⊕ g (y ), x ∈ p , y ∈ q , (4.8)
where φ is any mapping from q to p , g ∈ q is arbitrary.
