Information Technology Reference
In-Depth Information
If
AI
(
h
)
<r
, then there exists
g
= 0 such that either
g
∈
An
r
−
1
(
h
+1),
and therefore
supp
(
g
)
⊆
supp
(
h
), or
g
∈
An
r
−
1
(
h
), and therefore
supp
(
g
)
⊆
supp
(
h
+1). If
supp
(
g
)
supp
(
h
), then we apply Proposition 2 (last sentence
of) to the set
F
−
1
(
z
)(where
z
ranges over
F
2
) and to the function
g
(resp.
h
+1) and we get
⊆
|≥
AI
(
F
)
−r
i
=0
n−r
+1
i
F
−
1
(
z
)
F
−
1
(
z
)
|
∩
supp
(
h
)
|≥|
∩
supp
(
g
)
n−
i
. The case where
supp
(
g
)
|≥
AI
(
F
)
−r−
1
i
=0
F
−
1
(
z
)
and
|
∩
supp
(
h
+1)
⊆
supp
(
h
+ 1) is similar.
Remark
. In [8], the possibility that
h
could be constant was not taken into
account. The statement of Proposition 5 and the proof of Theorem 1 in this
reference are therefore incomplete. However, the result of [8, Theorem 1] is valid
(it is implied by Theorem 1 of the present paper, reduced to the case
m
=1).
2.4 Recent Recursive Lower Bounds
Lower bounds on the nonlinearity profile of a Boolean function by
means of the nonlinearity profiles of its derivatives.
We denote by
D
a
f
the so-called derivative of any Boolean function
f
in the direction of
a
F
2
:
∈
D
a
f
(
x
)=
f
(
x
)+
f
(
x
+
a
)
.
The addition is performed mod 2 (i.e.
D
a
f
is a Boolean function too). Applying
such discrete derivation several times to a function
f
leads to the so-called higher
order derivatives
D
a
1
···
D
a
k
f
(
x
)=
u∈F
2
f
(
x
+
i
=1
u
i
a
i
).
A simple tight lower bound on the
r
-th order nonlinearity of any function
f
,
knowing a lower bound on the (
r
1)-th order nonlinearity of at least one of its
derivatives (in a nonzero direction) is (see [9]):
−
1
2
max
nl
r
(
f
)
≥
nl
r−
1
(
D
a
f
)
.
a∈F
2
When applied repeatedly, the resulting bound
1
2
i
nl
r
(
f
)
≥
max
a
1
,...,a
i
∈F
2
nl
r−i
(
D
a
1
···
D
a
i
f
)
is also tight, but can not lead to bounds equivalent to 2
n−
1
and so is weak with
respect to (1). A potentially stronger lower bound, is valid when a lower bound
on the (
r
1)-th order nonlinearity is known for all the derivatives (in nonzero
directions) of the function.
−
Proposition 3.
[9] Let
f
be any
n
-variable function and
r
a positive integer
smaller than
n
. We have:
2
2
n
2
a∈F
2
1
2
2
n−
1
nl
r
(
f
)
≥
−
−
nl
r−
1
(
D
a
f
)
.
This bound also is tight.
