Cryptography Reference
In-Depth Information
5
Symmetries for Non-permutation Polynomials
In [5, 6], two notable systems, Square and Square-Vinegar, introduced the idea
of utilizing a quadratic map over a field of odd characteristic. The
C
∗
form
of the core map of Square is
if
(
x
)=
x
q
θ
+1
where
θ
= 0. The theorem of the
preceding section doesn't apply to the case
θ
= 0, therefore we will treat this
case separately, and completely characterize
S
S
, the space of linear maps,
L
,
satisfying (2).
q
be odd. Then
S
S
=
k
.
Theorem 2.
Let
Proof.
First,
Df
(
a, x
)=2
ax
. Therefore, by the symmetric application of the
linear function
M
(
x
)=
n−
1
i
=0
m
i
x
q
i
,wehave:
Df
(
Ma,x
)+
Df
(
a, M x
)=2
n−
1
m
i
a
q
i
x
+2
a
n−
1
m
i
x
q
i
.
(8)
i
=0
i
=0
Setting this quantity equal to
Λ
M
Df
(
a, x
)wehave:
2
n−
1
m
i
a
q
i
x
+2
a
n−
1
m
i
x
q
i
=
n−
1
λ
i
2
q
i
a
q
i
x
q
i
.
(9)
i
=0
i
=0
i
=0
We can collect the coecients of each monomial
a
q
i
x
q
j
and set each equal to zero
to determine relations between
M
and
Λ
M
. Collecting coecients for monomials
of the form
ax
q
i
,for
i
= 0, we get the relations, 2
m
i
=0.Thus
m
i
=0forall
i
=0,and
M
is multiplication by
m
0
in
k
;consequently,
S
S
≈
k
.
It is important to note that the Square systems have been broken by a differen-
tial attack in [7] which recovers the multiplicative structure of
k
by utilizing a
symmetry Square exhibits under left composition. This method of finding a ter-
minal symmetry under left composition was discovered for two reasons: first, the
Square systems did not preclude such an attack by employing the minus mod-
ifier or an alternative precaution; and second, the designers were able to mask
the initial multiplicative symmetry of the core map of Square by projecting the
input of the
C
∗
monomial into a subspace, making an attack using a symmetry
of the form (2) infeasible. If we include the minus modifier, i.e. consider Square-,
then the attack of [7] fails, and the question of which symmetries exist over a
subspace becomesmorecritical.
6
Symmetries over Subspaces
In [15], Ding et al. began the work of classifying the initial general linear symme-
tries for
C
∗
monomial maps over subspaces. Their result was imprecisely stated,
but they successfully proved that “almost always” if a field map has an initial
general linear symmetry over a subspace then that symmetry is a multiplicative
symmetry.
