Information Technology Reference
In-Depth Information
If
such that
fg
1
=0.Let
g
=
g
1
+1 then
h
=
fg
=
f
with
deg
(
h
)=
deg
(
f
) which contradicts
with the definition that
deg
(
h
)
|
D
d
|
<
|
S
d
|
, according to Case 2 in Section 4.1, there is
g
1
∈
S
d
≥
e>deg
(
f
).
From Theorem 3, we know that Algorithm 1 can be used in two ways. One
is to verify whether a given function is (
d, e
)-resistance against FAA. In other
words, for a given function of degree
r
, we may run Algorithm 1 for all pairs
of (
d, e
)where1
e<n
. If the outputs are zero for each pair
of (
d, e
), then
f
is (
d, e
)-resistance to FAA. Note that we only need to load
S
m
in Algorithm 1 once. The complexity for verifying whether a given function is
(
d, e
)-resistance is approximately equal to
n
(
r
≤
d<r
and 1
≤
−
1) times the complexity of the
Gauss reduction involved in Algorithm 1.
F
2
4
be defined by a primitive polynomial
t
(
x
)=
x
4
+
x
+1 and
α
arootof
t
(
x
). Let
f
(
x
)=
Tr
(
αx
3
)where
Tr
(
x
)=
x
+
x
2
+
x
4
+
x
8
Example 2.
Let
is the
trace function from
F
2
. (Note that
f
(
x
) is a bent function.) Then,
f
(
x
)
is 2-resistance against FAA.
F
2
4
to
Proof.
From the DFT, any function
g
(
x
)
∈F
n
with
g
(0) = 0 can be written as
g
(
x
)=
Tr
(
bx
)+
Tr
(
cx
3
)+
Tr
1
(
dx
5
)+
Tr
(
ex
7
)+
wx
15
,b,c,e∈
F
2
4
,d∈
F
2
2
,w∈
F
2
where
Tr
1
(
x
)=
x
+
x
2
is the trace function from
F
2
2
to
F
2
. Multiplying
f
by
each monomial trace term in
g
,wehave
Tr
(
bx
)
Tr
(
αx
3
)=
Tr
(
b
4
α
4
x
)+
Tr
1
((
b
2
α
+
b
8
α
4
)
x
5
)+
Tr
((
bα
2
+
b
4
α
)
x
7
)
Tr
(
cx
3
)
Tr
(
αx
3
)=
Tr
((
c
2
α
4
+
c
4
α
2
+
c
8
α
8
)
x
3
)+
Tr
(
cα
4
)
Tr
1
(
dx
5
)
Tr
(
αx
3
)=
Tr
(
d
2
α
2
x
+
d
2
α
4
x
7
)
Tr
(
ex
7
)
Tr
(
αx
3
)=
Tr
((
e
4
α
4
+
eα
8
)
x
)+
Tr
1
((
e
2
α
2
+
e
8
α
8
)
x
5
)+
Tr
(
e
4
α
8
x
7
)
.
In the following, we consider
w
=0.Thecase
w
= 1 is similar. From the above
identities, we have the expansion of
f
(
x
)
g
(
x
) as follows
f
(
x
)
g
(
x
)=
Tr
(
Ax
+
Bx
3
+
Dx
7
)+
Tr
1
(
Cx
5
)+
E
where
A
=
b
4
α
4
+
d
2
α
2
+
e
4
α
+
eα
8
B
=
c
2
α
4
+
c
4
α
2
+
c
8
α
8
D
=
bα
2
+
b
4
α
+
d
2
α
4
+
e
4
α
8
C
=
b
2
α
+
b
8
α
4
+
e
2
α
2
+
e
8
α
8
E
=
Tr
(
cα
4
)
.
Considering that
fg
=0,then
deg
(
fg
) = 1 if and only if
B
=
C
=
D
=0
.
