Cryptography Reference
In-Depth Information
L
S
G
. Thus, the existence of a single linear map
L
satisfying
the initial general linear symmetry guarantees the existence of a relatively large
space of maps satisfying the symmetry.
Therefore
S
G
∈
S
G
then
p
(
L
)
∈
F
q
L
2
i
.
Given just a few elements of
S
G
, we can potentially generate a large subspace
of
S
G
, which is a very appealing situation for an adversary.
This situation is exactly the scenario which has resulted in the breaking of
SFLASH and other
C
∗
variants. In [8], it was shown that
k<S
G
when
f
is a
C
∗
monomial, and thus
S
G
is so large that an element can be detected using the
relation (2) even when up to one half of the public equations are removed.
Thus the task of constructing a differentially secure multivariate cryptosystem
must necessarily include an analysis of the space of linear maps,
S
G
, illustrating
the symmetry. If
S
G
is very small, then recovering an element from this subspace
may be an infeasible task, and the differential attack is doomed.
is the
F
q
-vector space sum of rings of the form
F
q
or
C
∗
Monomials
4
Properties Relative to
If we restrict our attention to the case in which
f
is a
C
∗
monomial map of the
form
f
(
x
)=
x
q
θ
+1
, we can derive some additional properties of
S
G
indicating
why so many
C
∗
variants have fallen to differential attacks. Immediately, we
know that there is an injective map
g
:
k
S
G
,since
f
has the multiplica-
tive symmetry. Furthermore, by considering the linearized polynomial form of
an arbitrary linear map,
L
→
∈
GL
(
F
q
,n
), we can continue, revealing the exact
multiplicative structure of
S
G
.
Theorem 1.
If
f
is a
C
∗
monomial, then
S
G
,
equipped with standard multipli-
cation is a
k
-algebra, and consequently has a large dimension as an
F
q
-vector
space. Furthermore, if
3
θ
=
n
,
S
G
=
k
.
S
G
,
Mx
=
n−
1
i
=0
m
i
x
q
i
.
We will find conditions on the coecients,
m
i
of this linearized polynomial form.
For the generic
C
∗
monomial map,
f
(
x
)=
x
q
θ
+1
, we have that the discrete
differential,
Df
(
a, x
)=
a
q
θ
x
+
ax
q
θ
.Thus:
Proof.
Consider the linearized polynomial form of
M
∈
m
q
θ
i
a
q
i
+
θ
x
+
m
i
a
q
i
x
q
θ
n−
1
Df
(
Ma,x
)+
Df
(
a, M x
)=
i
=0
m
i
a
q
θ
x
q
i
+
m
q
θ
ax
q
i
+
θ
n−
1
+
i
i
=0
(5)
a
q
i
+
θ
x
+
ax
q
i
+
θ
n−
1
m
q
θ
i
=
i
=0
m
i
a
q
i
x
q
θ
+
a
q
θ
x
q
i
.
n−
1
+
i
=0
