Cryptography Reference
In-Depth Information
As stated, the claim indicated that for a bijective
C
∗
monomial,
f
,givenany
hyperplane,
H
=
π
(
k
), if we have:
Df
(
Ma,πx
)+
Df
(
πa, Mx
)=
Λ
M
Df
(
πa, πx
)
,
(10)
for all
a, x
k
.
To prove that the statement as given in [15] is in err, let us define the space sav-
ing notation
S
f
(
A, B
)(
a, x
)=
Df
(
Aa, Bx
)+
Df
(
Ba, Ax
), and take the following
example. Let
k
=
GF
(64) over
∈
k
,then
M
=
M
σ
◦
π
and
Λ
M
=
M
σ
+
σ
q
θ
,forsome
σ
∈
F
2
,
f
(
x
)=
x
5
,
πx
=
x
+
x
2
,and
Mx
=
x
4
+
x
8
.
By a simple calculation,
S
f
(
M, π
)(
a, x
)=(
a
16
+
a
32
)(
x
+
x
2
)+(
a
+
a
2
)(
x
16
+
x
32
)
=
a
16
x
+
ax
16
+
a
32
x
+
ax
32
+
a
16
x
2
+
a
2
x
16
+
a
32
x
2
+
a
2
x
32
=
ax
4
+
a
4
x
+
a
2
x
4
+
a
4
x
2
+
ax
8
+
a
8
x
+
a
2
x
8
+
a
8
x
2
16
=
Df
(
πa, πx
)
16
.
(11)
(Herewenotethattwotermsoftheform(
a
4
+
a
8
)(
x
4
+
x
8
) cancelled each other in
the first line above.) Thus, we have found a counterexample with
Λ
M
x
=
x
16
and
Mx
=(
πx
)
4
, which is certainly not the composition of a multiplication map and
π
. Here the fact that 2 (
codim
(
H
)+
θ
)=
n
created some extra symmetries in the
relations between the coecients of
M
and
Λ
M
. Informally,
θ
was an exceptional
choice which permits the existence of a linear map allowing collisions between
monomials generated from
Df
(
Ma,πx
)and
Df
(
πa, Mx
). Since the arithmetic
of
k
has characteristic 2, collision corresponds with annihilation.
We can resolve the minor issues with the result of Ding et al. and generalize
the statement somewhat by providing a more detailed analysis of the symmetry:
Df
(
Ma,πx
)+
Df
(
πa, Mx
)=
Λ
M
Df
(
πa, πx
)
,
(12)
for more general linear maps,
π
. In particular, a more precise formulation of the
result of Ding et al. is the special case of
d
= 1 in the following theorem.
and
πx
=
i
=0
x
q
i
f
(
x
)=
x
q
θ
+1
C
∗
map, and let
Theorem 3.
Let
be a
M
Df
(
Ma,πx
)+
Df
(
πa, Mx
)=
Λ
M
Df
(
πa, πx
)
.If
θ
+
d<
2
,
be linear. Suppose
|
n
−
3
θ
|
>d
,and
0
<d<θ
−
1
,then
M
=
M
σ
π
for some
σ
∈
k
.
Proof.
Our strategy for the proof will be to determine relations between the co-
ecients of the linearized polynomial forms of
M
and
Λ
M
. We will zigzag back
and forth between solving for coecients of
M
and of
Λ
M
, further resolving the
relationship between the two maps with each step. We will extensively use the
“space of indices,” the torus consisting of the pairs (
r, s
)(mod
n
) which corre-
spond to monomials of the form
a
q
r
x
q
s
. The geometry of this space of indices
will be useful in determining relations on the coecients of the corresponding
monomials in the expansions of (12).