Cryptography Reference
In-Depth Information
−
f
(
x
)+
f
(0). The use of this discrete differential appears to occur in very many
cryptanalyses of post-quantum multivariate schemes. In fact, we can even con-
sider Patarin's initial attack, in [11], on Imai and Matsumoto's
C
∗
scheme, see
[12], as the exploitation of a trivial differential symmetry. Suppose
f
(
x
)=
x
q
θ
+1
and let
y
=
f
(
x
). Since the differential of
f
,
Df
, is a symmetric bilinear func-
tion, 0 =
Df
(
y, y
)=
Df
(
y, x
q
θ
+1
)=
yx
q
2
θ
+
q
θ
+
y
q
θ
x
q
θ
+1
=
x
q
θ
(
yx
q
2
θ
+
y
q
θ
x
).
Dividing by
x
q
θ
we have Patarin's linear relation,
yx
q
2
θ
=
y
q
θ
x
;see[11]for
details.
Differential methods provide powerful tools for decomposing a multivariate
scheme. To illustrate the nearly universal nature of differential attacks, we review
the attack of Kipnis and Shamir, see [9], on a non-big-field system, the oil and
vinegar scheme. Though they use differing terminology, the attack exploits a
symmetry hidden in the differential structure of the scheme.
Recall that the oil and vinegar scheme is based on a hidden quadratic system
of equations,
f
:
k
n
The differential of a field map,
f
, is defined by
Df
(
a, x
)=
f
(
a
+
x
)
−
f
(
a
)
k
o
,intwotypesofvariables,
x
1
, ..., x
o
,theoilvariables,
and
x
o
+1
, ..., x
o
+
v
=
n
, the vinegar variables. We focus on the balanced oil and
vinegar scheme, in which
o
=
v
.Let
c
1
, ..., c
v
be random constants. The map
f
has the property that
f
(
x
1
, ..., x
v
,c
1
, ..., c
v
)isanein
x
1
, ..., x
v
. The encryption
map,
f
is the composition of
f
with an
n
-dimensional invertible ane map,
L
.
Let
O
represent the subspace generated by the first
v
basis vectors, and let
V
denote the cosummand of
O
. Notice that the discrete differential given by
Df
(
a, x
)=
f
(
x
+
a
)
→
f
(
a
)+
f
(0) has the property that for all
a
and
x
in
O
,
Df
(
a, x
) = 0. Thus for each coordinate,
i
, the differential coordinate form
Df
i
can be represented:
−
f
(
x
)
−
Df
i
=
0
Df
i
1
.
Df
i
1
Df
i
2
Let
M
1
and
M
2
be two invertible matrices in the span of the
Df
i
.Then
M
−
1
M
2
1
is an
O
-invariant transformation of the form:
AB
0
C
.
L
)
i
=
L
T
Df
i
L
,sothe
L
T
Df
i
L
are
known. Notice that if
M
is in the span of the
Df
i
,then
L
T
ML
is in the span of
the
L
T
Df
i
L
.Also,since(
L
T
M
1
L
)
−
1
(
L
T
M
2
L
)=
L
−
1
M
−
1
M
2
L
, there is a large
space of matrices leaving
L
−
1
O
invariant, which Kipnis and Shamir are able to
exploit to effect an attack against the balanced oil and vinegar scheme; see [9]
for details. Making the oil and vinegar scheme unbalanced, see [13], corrects this
problem by making any subspace which is invariant under a general product
M
−
1
M
2
very small, see [14].
While the differential analysis of the oil and vinegar systems is a very spe-
cific case of utilizing an invariant related to the differential structure of the
hidden map, several general attacks on big field schemes rely on a type of linear
Now the
Df
i
are not known, but
D
(
f
◦
