Information Technology Reference
In-Depth Information
term which reduces the lower bound. We show now some straightforward upper
bounds:
Proposition 6.
For every positive integers
m
,
n
,
s
≤
m
and
r
≤
n
and every
(
n, m
)
-function
F
, we have:
NL
s
(
F
)
2
n−s
.Thesein-
equalities are strict if
F
is not balanced (that is, if its output is not uniformly
distributed over
F
2
).
Proof.
There necessarily exists an (
m − s
)-dimensional ane subspace
A
of
F
2
such that the size of
F
−
1
(
A
)isatmost2
n−s
(more precisely, for every (
m
≤
2
n−s
and
nl
s,r
(
F
)
≤
−
s
)-
dimensional vector subspace
E
of
F
2
F
2
such that the size of
F
−
1
(
a
+
E
)isatmost2
n−s
, since the sets
F
−
1
(
a
+
E
) constitute a partition of
F
2
when
a
ranges over a subspace of
F
2
supplementary to
E
, and the number
of the elements of this partition equals 2
s
). Taking for
f
the indicator of
A
,
for
g
the null function and defining
h
(
x, y
)=
f
(
y
), we have
w
H
(
h
(
x, F
(
x
)) =
w
H
(
f
,thereexists
a
∈
2
n−s
,andthedegreeof
f
equals
s
. This proves that
NL
s
(
F
)
2
n−s
◦
F
)
≤
≤
2
n−s
. Moreover, according to the observations above, equality
is possible only if, for every (
m
and
nl
s,r
(
F
)
≤
s
)-dimensional ane subspace
A
of
F
2
,the
size of
F
−
1
(
A
)equals2
n−s
. This implies that for every ane hyperplane
H
,
the size of
F
−
1
(
H
)equals2
n−
1
. And this is equivalent to saying that for every
nonzero
v
−
F
2
, the Boolean function
v
∈
·
F
is balanced, which is equivalent to
F
balanced (see e.g. [6]).
2
n−s
is asymptotically
We shall see in Proposition 8 that the bound
nl
s,r
(
F
)
≤
approximately tight for permutations when
r
≤
s
≤
.
227
n
.
2
n−s
probably implies that we have
nl
s,r
(
F
)
Remark
. The inequality
nl
s,r
(
F
)
≤
=
nl
r,s
(
F
), in general and for many cases such that
r
=
s
-atleastfor
s
=1and
r>
1and
m
=
o
(
n
2
). We do not have a rigorous proof of this, except for a few
functions and cases (the inverse function for
s
=1and
r>
1, the Welch function
for
s
=1and
r
= 2, ...). We give a very informal argument: applying (1) to each
component function
v
F
2
∗
(assuming that the component functions of
a random S-box behave as random functions, which is not true), we have that a
function
F
:
F
2
→
·
F
;
v
∈
i
=0
i
2
n−
1
F
2
has
nl
1
,r
smaller than 2
n−
1
−
with a
2
1)2
(1
−
log
2
e
)
i
=0
(
i
)
) which tends to 0 also, when
r>
1,
if
m
=
o
(
n
2
). Hence, it seems that almost all functions
F
have an
nl
1
,r
greater
than 2
n−
1
probability in
O
((2
m
−
i
=0
i
2
n−
2
. This kind of “argument” still works when
s
is
greater than 1 (and is reasonably small with regard to
r
)and
m
is small enough
with regard to
n
. It would be nice to have a formal proof of all this.
−
3.1 The Inverse S-Box
For
F
inv
(
x
)=
x
2
n
−
2
and
f
inv
(
x
)=
tr
(
F
inv
(
x
)),
NL
1
(
F
inv
)=
nl
(
f
inv
)equals
2
n−
1
2
n/
2
when
n
is even and is close to this number when
n
is odd. We
have
NL
t
(
F
inv
) = 0 for all
t
−
2,sincewehave
w
H
(
h
(
x, F
inv
(
x
))) = 0 for the
bilinear function
h
(
x, y
)=
tr
(
axy
)where
a
is any nonzero element of null trace
≥
