Cryptography Reference
In-Depth Information
F
q
-linear map,
Λ
M
(
x
)=
n−
1
i
=0
λ
i
x
q
i
such that the
equation
Df
(
Ma,x
)+
Df
(
a, M x
)=
Λ
M
Df
(
a, x
) holds. Therefore we have:
n−
1
Since
M
∈
S
G
,thereisan
a
q
i
+
θ
x
+
ax
q
i
+
θ
+
m
i
a
q
i
x
q
θ
+
a
q
θ
x
q
i
=
λ
i
a
q
θ
x
+
ax
q
θ
q
i
n−
1
m
q
θ
i
i
=0
i
=0
λ
i
a
q
i
+
θ
x
q
i
+
a
q
i
x
q
i
+
θ
.
n−
1
=
i
=0
(6)
We can collect the coe
cients of each monomial,
a
i
x
j
, and set each to zero,
obtaining relations on the coecients of the linearized form of
M
and
Λ
M
.
If
q
θ
+ 1 shares a nontrivial factor with
q
n
1, then
f
is not strictly speaking
a
C
∗
monomial, since it is not a permutation polynomial. Thus we treat the
case
θ/
−
, encompassing all
C
∗
monomials, as well as many functions
which are not
C
∗
monomials. If we collect the coecients of the monomial
ax
q
θ
,
we get the relation
λ
0
=
m
0
+
m
q
0
. The coecients of monomials of the form
ax
q
i
,for
i/
0
,
2
,
4
}
∈{
∈{
0
,
±
θ
}
, generate the relations
m
i−θ
=0.Thus
m
i
=0forall
. Collecting the coecients of the monomials of the form
a
q
θ
x
q
i
i/
∈{
0
,
−
θ,
−
2
θ
}
for
i/
,wehave
m
i
=0.
Therefore, if a nonzero coecient exists other than
m
0
, then either
∈{
0
,θ,
2
θ
}
−
θ
=
θ
,
2
,
which implies
θ
=
−
θ
=2
θ
, implying 3
θ
=
n
,or
−
2
θ
=2
θ
, which implies
4
. Of these cases, only 3
θ
=
n
represents a possible
C
∗
monomial. Thus, if
θ
=
3
θ
=0,
m
i
= 0, and in this case,
Mx
=
m
0
x
is multiplication
by an element in
k
;consequently,
S
G
=
k
.
If 3
θ
=
n
,then
m
0
,
m
3
,and
m
2
3
=
n
, then for all
i
can possibly be nonzero. To prove that
S
G
is still a ring in this case, notice that given two linear maps,
M
and
L
,eachwith
all coecients zero except possibly
m
0
,
m
3
,
m
2
3
,
l
0
,
l
3
,and
l
2
3
,wehave:
LMx
=(
l
0
m
0
+
l
3
m
q
3
m
q
2
3
n
3
+
l
2
3
)
x
2
n
3
+
l
3
m
q
3
m
q
2
3
2
n
3
)
x
q
3
(7)
+(
l
0
m
3
+
l
2
3
0
+
l
3
m
q
m
q
2
3
0
)
x
q
2
3
,
+(
l
0
m
2
3
+
l
2
3
3
which is, again a linear map with all coecients zero except for the 0-th,
3
-th,
and
2
3
-th. Thus
S
G
has multiplicative closure, and is a 3-dimensional
k
-algebra.
In the above theorem we didn't mention anything about characteristic. Strictly
speaking, a
C
∗
monomial is linearly equivalent to a quadratic permutation poly-
nomial of the form
f
(
x
)=
x
q
θ
+1
. This is only possible, however, when
q
is even,
since trivially, 2
(
q
θ
+1
,q
n
1). Some cryptosystems, however, do use this form
of core map in odd characteristic, choosing a map which is 2-to-1, or few-to-1.
Such systems never use
θ
|
−
2
,
4
}
, since such maps would have exponential col-
lisions. It is for this reason that in the above theorem we relaxed the constraints
and allowed any map with
θ/
∈{
0
,
2
,
4
}
∈{
. We have completely characterized the
symmetries in these cases.
