Information Technology Reference
In-Depth Information
x
i
g
(
x
)=
(since
n
−
s
=
r
+1). Hence (
f
◦
F
inv
)(0) +
g
(0) = 1,
0
≤i<
2
n
−
1
F
inv
)(
x
)+
g
(
x
)=
1+
x
2
n
−
1
(
f
◦
F
inv
)(1) +
g
(1) = 1 and, if
x
∈
F
2
,(
f
◦
=0.
1+
x
Hencewehave
nl
s,r
(
F
inv
)
2 and since we know that
nl
s,r
(
F
inv
) is strictly
positive and that it is even, we deduce that
nl
s,r
(
F
inv
)=2.
≤
3.2 Existence of Permutations with Lower Bounded Higher Order
Nonlinearities
We investigate now, with a simple counting argument, the existence of permu-
tations
F
such that
nl
s,r
(
F
)
>D
for some values of
n
,
s
,
r
and
D
.
Lemma 1.
Let
n
and
s
be positive integers and let
r
be a non-negative integer.
If
2
i
=0
(
i
)
+
i
=0
(
i
)
2
n−s
then there exist permutations
F
from
F
2
to itself
whose higher order nonlinearity
nl
s,r
(
F
)
is strictly greater than
D
for every
D
such that
t
=0
2
n
≤
2
n
t
≤
(
2
n
2
n−s
)
2
i
=0
(
i
)
+
i
=0
(
i
)
.
Proof.
For every integers
i
[0
,
2
n
]and
r
, let us denote by
A
r,i
the number
of codewords of Hamming weight
i
in the Reed-Muller code of order
r
.Given
anumber
D
,apermutation
F
and two Boolean functions
f
and
g
,ifwehave
d
H
(
f
∈
D
then
F
−
1
maps the support
supp
(
f
)of
f
to the symmetric
difference
supp
(
g
)
ΔE
between
supp
(
g
)andaset
E
of size at most
D
(equal to
the symmetric difference between
F
−
1
(
supp
(
f
)) and
supp
(
g
)). And
F
−
1
◦
F, g
)
≤
maps
F
2
\
supp
(
g
)and
E
.Given
f
,
g
and
E
and denoting by
i
the size of
supp
(
f
)(with0
<i<
2
n
,since
f
supp
(
f
) to the symmetric difference between
F
2
\
=
cst
),
the number of permutations, whose restriction to
supp
(
g
)
ΔE
is a one-to-one
function onto
supp
(
f
) and whose restriction to (
F
2
\
supp
(
g
))
ΔE
is a one-to-
one function onto
F
2
supp
(
f
), equals
i
!(2
n
\
−
i
)!. Denoting by
j
thesizeof
supp
(
g
), then
d
H
(
g, f
◦
F
)
≤
D
implies
|
i
−
j
|≤
D
. We deduce that the number
of permutations
F
such that
nl
s,r
(
F
)
≤
D
is upper bounded by
2
n
t
D
A
s,i
A
r,j
i
!(2
n
−
i
)!
t
=0
0
<i<
2
n
j/|i−j|≤D
Since the nonconstant codewords of the Reed-Muller code of order
s
have weights
between 2
n−s
and 2
n
2
n−s
, we deduce that the probability
P
s,r,D
that a per-
mutation
F
chosen at random (with uniform probability) satisfies
nl
s,r
(
F
)
−
≤
D
is upper bounded by
2
n
t
2
n
D
A
s,i
i
!(2
n
−
i
)!
A
r,j
=
2
n
!
t
=0
j
=0
2
n−s
≤i≤
2
n
−
2
n−s
2
n
t
2
n
D
A
s,i
2
n
A
r,j
i
t
=0
j
=0
2
n−s
≤
i
≤
2
n
−
2
n−s
