Information Technology Reference
In-Depth Information
bent-negabent function in 2 n variables is also equal to n . For example, the cubic
function f : V 6 F 2
f ( x 1 ,x 2 ,x 3 ,y 1 ,y 2 ,y 3 )=
y 1 ( x 1 x 2 + x 2 x 3 + x 1 + x 2 )+ y 2 ( x 1 x 2 + x 2 x 3 + x 3 )+ y 3 ( x 1 + x 3 )
is bent-negabent. Note that f belongs to the Maiorana-McFarland class. In this
section we prove that the degree of a Maiorana-McFarland-type bent-negabent
function in 2 n variables is at most n
1for n> 3.
Theorem 10. Let σ be a permutation on V n and let g : V n F 2 be an arbitrary
Boolean function. Suppose that the function f : V n ⊕ V n F 2 given by
f ( x, y )= σ ( x )
·
y + g ( x )
is negabent. Then, if n> 3 , the degree of f is at most n
1 .
The proof of the theorem requires a lemma.
Lemma 11. The nega-Hadamard transform of a negabent function on V n con-
tainsonlyvaluesoftheform ω n i k ,where ω =(1+ i ) / 2 and k
Z 4 .
Proof. Let 2 2 S denote an arbitrary value of the nega-Hadamard transform of
a negabent function on V n .Then
2 =2 n
must be a sum of two squares (one of them may be zero). From Jacobi's two-
square theorem we know that 2 n has a unique representation as a sum of two
squares, namely 2 n =(2 n/ 2 ) 2 +0 2 if n is even, and 2 n =(2 ( n− 1) / 2 ) 2 +(2 ( n− 1) / 2 ) 2
if n is odd. Hence, if n is even, either
( S )or
( S )mustbeintegersand
|
S
|
( S )or
( S ) must be zero. If n is odd,
we must have
|
( S )
|
=
|
( S )
|
, which proves the lemma.
Proof (of Theorem 10). Using Lemma 1, we obtain
( f )( u, v )=2 −n
1) σ ( x ) ·y + g ( x )+ u·x + v·y i wt( x )+wt( y )
N
(
x,y∈V n
=2 −n
1) g ( x )+ u·x i wt( x )
1) ( σ ( x )+ v ) ·y i wt( y )
(
(
x∈V n
y∈V n
=2 2 ω n
1) g ( x )+ u·x i wt( x ) wt( σ ( x )+ v )
(
x∈V n
=2 2 ω n i wt( v )
1) g ( x )+ u·x + v·σ ( x ) i wt( x ) wt( σ ( x ))
(
x∈V n
2 ω n i wt( v )
=2
1) g ( x )+ u·x + v·σ ( x ) i w ( x ) ,
(
x
V n
where
n
w ( x )=
( x j +3 σ j ( x ))
(mod 4)
j =1
Search WWH ::




Custom Search