Information Technology Reference
In-Depth Information
δ
(
F
) needs to be as low as possible to resist differential attacks on block ci-
phers [7]. Since
D
a
F
(
x
)=
D
a
F
(
x
+
a
)for
a
2and
even. The S-boxes for which the equality holds are the best choices against the
differential attack.
Definition 2.
An S-box
F
:
V
m
=0
∈
V
m
,wehave
δ
(
F
)
≥
→
V
m
is called
Almost Perfect Nonlinear
(in
short, APN) if
δ
(
F
)=2
.
Lemma 1.
F
:
V
m
→
V
m
is APN iff there do not exist different
x, y, z
∈
V
m
such that
F
(
x
)+
F
(
y
)+
F
(
z
)+
F
(
x
+
y
+
z
)=0
.
Now we define a class of functions as following.
Definition 3.
Consider
m
is even. An S-box
F
:
V
m
→
V
m
is defined as 3-to-1
S-box if
F
−
1
(0) =
F
−
1
(
a
)
V
m
=
V
m
\{
.
Note that, the 3-to-1 S-box is defined for even variable S-boxes because 2
m
{
0
}
and
|
|
=3
or,
0
for
a
∈
0
}
−
1
is not divisible by 3 when
m
is odd.
The APN property is preserved by Extended Ane (EA) transformation [8]
and CCZ transformation [4]. Two S-boxes
F
and
F
are EA-equivalent if there
exist two ane permutations
A
1
,A
2
and an ane function
A
such that
F
=
A
1
◦
A
2
+
A
. CCZ-equivalence corresponds to the ane equivalence of the
graphs of two S-boxes [4]. EA-equivalence is a particular case of CCZ-equivalence.
In [3] one can find a list of classes of APN functions which are EA-inequivalent
and CCZ-inequivalent to power functions. In this paper we will show that an
important class of even variable S-boxes are 3-to-1 S-boxes.
We denote
e
F
◦
⊆
d
for two non-negative integers
e
and
d
if
e
∧
d
=
e
where
∧
is
the bitwise logical
AN D
operation i.e.,
e
i
≤
i<n
where
e
i
and
d
i
's are
i
th bit of the
n
-bit binary representation of
e
and
d
respectively. From Lucas'
d
i
,
0
≤
theorem [6, page 79], we have
e
=1mod2iff
e
⊆
d
for two non-negative
integers
d
and
e
.
3 S3-to-1 APN S-Box
In this section, we present a special class of 3-to-1 APN S-box and show that
some of the known constructions of S-boxes on even variables are of this type.
Note that, in this section we always consider
m
as even positive integer and
k
=
2
m
−
3
.
Construction 1 (S3-to-1 function).
Let
V
m
be partitioned into disjoint parts,
P
0
=
{
0
}
,P
1
,P
2
,...,P
k
, such that each set
P
i
,
1
≤
i
≤
k
contains
3
different
elements
a, b, c
where
a
+
b
=
c
(i.e.,
P
i
∪
P
0
,
1
≤
i
≤
k
are
2
-dimensional flats).
Further, let
U
⊂
V
m
be an ordered set and
|
U
|
=
k
+1
. Then the S-box
F
:
V
m
→
V
m
is constructed as
F
(
x
)=
u
i
where
x
P
i
and
u
i
is the
i
th element in
U
.
We name this special class of 3-to-1 functions as S3-to-1 functions.
∈
Notation 1.
Referring to the partitions
P
i
in Construction 1, we denote (1)
F
(
P
i
)=
y
where
F
(
x
)=
y
for
x
∈
P
i
}
and (2) for
x
∈
V
m
,
P
(
x
)=
P
i
where
x
∈
P
i
.
