Information Technology Reference
In-Depth Information
2
6
−
1
3
size of
W
will be at most 10, but we need of a set of size
= 21. Therefore,
the theorem is true for
m
=6.
Nowwesupposeitistruefor
m
=
t
and we will prove for
m
=
t
+2. We prove
it by contradiction. Consider that such a set
U
of size
2
t
+2
−
1
3
exists for
n
=
t
+2.
Now divide
U
into 4 parts
U
00
,U
01
,U
10
and
U
11
such that
U
ij
⊂
U
contains the
vectors having (
t
+ 1)th and (
t
+ 2)th co-ordinates
i
and
j
respectively. Hence
from pigeonhole principle, there must be a
U
ij
such that
2
t
+2
1
4
×
−
1
|
U
ij
|≥
=
3
2
t
−
1
4
2
t
−
1
3
. Now one can use this
U
ij
(excluding
t
+1 and
t
+ 2 th coordinates)
for
m
=
t
, which contradicts our supposition.
≥
3
Using Lemma 1, we have the following result for when a S3-to-1 function will be
APN.
Theorem 2.
Let
F
be a S3-to-1 function.
F
is APN iff for all
x, y
∈
V
m
such
that
P
(
x
)
=
P
(
y
)
,
F
(
x
)+
F
(
y
)+
F
(
z
)+
F
(
x
+
y
+
z
)
=0
for all
z
∈
V
m
,
z/
∈
P
(
x
)
∪
P
(
y
)
∪
P
(
x
+
y
)
.
Proof.
For the proof, we use Lemma 1. For this class of S-boxes the search
domains of
y
and
z
are decreased by putting some extra conditions. Now we will
show that the discarded
y
's and
z
's will not satisfy the condition
F
(
x
)+
F
(
y
)+
F
(
z
)+
F
(
x
+
y
+
z
)=0.
Let
y
P
(
x
).
F
(
x
)+
F
(
y
)+
F
(
z
)+
F
(
x
+
y
+
z
) = 0 i.e.,
F
(
z
)+
F
(
x
+
y
+
z
) = 0 implies
x
+
y
+
z
∈
P
(
x
). Then from the construction of
P
i
's, we have
x
+
y
∈
∈
P
(
z
) i.e,
x
+
y
P
(
x
), a contradiction that
x, y, z
and
x
+
y
+
z
are all distinct. Hence,
F
(
x
)+
F
(
y
)+
F
(
z
)+
F
(
x
+
y
+
z
)
∈
P
(
z
). This implies
x, y, z, x
+
y
+
z
∈
=0.
The exclusion of
z
's can be proved in similar way.
Note 1.
In Construction 1, each set
P
i
∪{
k
, forms a subspace of
dimension 2. If we wanted to use subspaces with dimension greater than 2 then
for the following reason
F
can not be APN. Consider
P
i
such that
P
i
∪{
0
}
,0
<i
≤
}
0
is of
dimension greater than 2. Then
P
i
will contain a subset
{
x, y, x
+
y, z, x
+
z, y
+
z, x
+
y
+
z
}
. Here the last 4 elements add to zero. This implies that we can not
consider the partitions
P
i
,
0
<i
≤
k
, such that
P
i
∪{
0
}
is 3 dimensional.
Definition 4.
A S3-to-1 function
F
:
V
m
→
V
m
is called identity S3-to-1 (in
short, IDS3-to-1) function if
F
(
P
i
)
k
.
IDS3-to-1 functions are similar to identity function. There are 3
k
IDS3-to-1
functions. Like identity function, in the following theorem we show that IDS3-
to-1 functions are not APN.
Theorem 3.
IDS3-to-1 functions are not APN when
m
∈
P
i
for
0
≤
i
≤
≥
6
.
u
i
,u
i
,u
i
}
Proof.
Let
P
i
=
{
where
F
(
P
i
)=
u
i
for 1
≤
i
≤
k
.Let
s
ij
=
u
i
+
u
j
for 1
k
.Ifall
s
ij
's are not distinct then there is
s
i
1
i
2
=
s
i
3
i
4
i.e.,
u
i
1
+
u
i
2
+
u
i
3
+
u
i
4
= 0, which implies that
F
is not APN. Hence, consider all
≤
i<j
≤
s
ij
s are distinct. There are
2
=
k
(
k
−
1)
many
s
ij
sand2
k
many
u
i
sand
u
i
s. For
2
6, we have
k
(
k−
1)
2
m
≥
>
2
k
. Hence there is a
s
i
1
i
2
=
u
i
3
i.e.,
u
i
1
+
u
i
2
+
u
i
3
=0.
Hence
F
is not APN.
