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.
   142   143   144   145   146   147   148   149   150   151   152