Cryptography Reference
In-Depth Information
,x
n
+
u
)
t
,
v
(
if
)
if
where
u
≥
1,
x
n
+1
,
···
,x
n
+
u
are additional variables,
x
:= (
x
1
,
···
is a linear form and
w
(
if
)
if
is a quadratic form. For the signature generation, first
k
u
randomly and substitute
choose
r
=(
r
1
,
···
,r
u
)
∈
x
n
+1
=
r
1
,
···
,
n
+
u
=
r
u
.
(13)
Then
G
v
becomes the original
G
and the signature can be generated. The scheme
HFEv- (Quartz) [40,31] is the “minus” of HFEv (the “vinegar” of HFE-). It is
known that the secret keys can be recovered if the
u
is small [14,19].
2.2.3 Other Randomizations
The internal perturbation (IP) [16] is a randomization of
G
by adding the “per-
turbing” quadratic polynomials to
G
. This makes the decryption much slower
than the original scheme. Ding
et al.
[18] observed that the IP improves the
security against the Grobner basis attack. However, the differential attack [26]
removes the perturbation on PMI (the IP of MI) and then PMI is reduced to
Matsumoto-Imai's scheme. The “plus” of PMI (PMI+) has previously been pro-
posed to prevent the differential attack [17].
The piece in hand (PH) [45] has been proposed to randomize
G
.Tsujii
et
al.
[45] have observed that PH improves the security against the Grobner basis
attacks.
2.3
Major Attacks
While it is not easy to list all the attacks on MPKC, we give an overview of
several major attacks.
2.3.1 Direct Attacks
The direct attack is to find a solution
x
k
n
of the equation
y
=
F
(
x
)di-
rectly. The Grobner basis algorithms [23], the XL algorithms [15], and the fast
exhaustive searches [8] are the major approaches. Though their precise complex-
ity estimations are dicult [3], it is known that the Grobner basis algorithm can
effectively recover the message of the HFE if
∈
G
is simple [24].
2.3.2 Rank Attacks
The min-rank attack is based on the “min-rank problem”. This problem is, in
general, dicult to be solved. However, if the corresponding matrix is a linear
combination of other matrices
B
1
,
,B
m
and one (or more) of them are of
small rank, this problem can be solved eciently.
In most STS type schemes (except UOV), the minimal rank of the coecient
matrices in
G
is
n
···
n
r−
1
is small, the partial
information of
T
can be found eciently. In HFE (and MI),
−
n
r−
1
(see (10)). Thus, if
n
−
G
is described by
a quadratic form of (
X, X
q
,X
q
2
,
,X
q
n
−
1
)
t
over
K
and its coecient matrix
is of rank (at most)
d
. Then min-rank attack will find partial information of
T
when
d
is small. Note that, for most schemes,
S
can be recovered if
T
is recovered.
···
