Cryptography Reference
In-Depth Information
Let
N
be a divisor of gcd(
n, m
)and
K
an algebraic extension of
k
with
[
K
;
k
]=
N
. The central map
G
is given by
G
=
ψ
φ
,where
φ
:
k
n
K
n/N
◦G◦
→
and
ψ
:
K
m/N
k
m
:
K
n/N
K
m/N
→
are one-to-one maps and
G
→
is a map
given by polynomials over
K
.
φ
−→
ψ
−→
G
−→
G
:
k
n
K
n/N
K
m/N
k
m
(6)
This type was first introduced by Matsumoto and Imai [34]. In their original
scheme,
n
=
m
=
N
and
(
X
):=
X
q
i
+1
,
G
(7)
where
i
is an integer with gcd(
q
i
+1
,q
n
−
1) = 1. The decryption is computed
by
Y
θ
G
−
1
(
Y
)=
X
with
θ
(
q
i
+1)
−
1
mod
q
n
1. Unfortunately, Patarin
[39] developed a linearization attack that could find the message.
The hidden field equation (HFE) is a modification of MI proposed by Patarin
[40]. In this scheme,
≡
≡
−
G
is given by
α
ij
X
q
i
+
q
j
+
0
≤i<d
β
i
X
q
i
+
γ,
G
(
X
)=
(8)
0
≤i≤j<d
where
d ≥
1 is an integer and
α
ij
,β
i
,γ
is computed by
the Berlekamp algorithm whose complexity depends on the degree of
G
. Because
the degree of
∈
K
. The inversion of
G
is at most 2
q
d−
1
,thenumber
d
cannot be too large. Kipnis-Shamir
[32] developed an attack to recover the secret keys
S
and
T
on HFE by the
MinRank attacks (see also [25]). The complexity of these attacks depends on
d
,
namely, if
d
is small, the attack will find them effectively. Alternatively, Faugere-
Joux [24] developed attacks that find the message by the Grobner basis algorithm
[23]. While estimations of the complexity of the Grobner basis algorithm is not
easy, the message of the HFE with a small
d
seems to be found eciently.
The MI and HFE are given by a univariate
G
G
.The
l
IC [21] and
l
HFE [11]
are derived from
G
of
l
variables (
X
1
,
···
,X
l
). For example, in standard 3IC,
n
=
m
is a multiple of 3,
N
=
n/
3and
(
X
1
,X
2
,X
3
)=(
X
1
X
2
,X
2
X
3
,X
3
X
1
).
Both the encryption and the decryption of
l
lIC are faster than MI and HFE.
However, Fouque
et al.
[27] found that the Grobner basis attack recovers the
message eciently. The
l
lHFE is derived from more complicated polynomials.
Though Chen
et al.
[11] claimed that this scheme is also ecient, Bettale
et al.
[5] recently pointed out that it is less secure than HFE with the equal-sized keys.
G
2.1.2 Stepwise Triangular System (STS) Type
This type was first introduced independently of each other by Tsujii
et al.
[44]
and Shamir [42]. The basic idea is as follows.
Let
r
≥
1 be an integer and
{
n
1
,
···
,n
r
}
and
{
m
1
,
···
,m
r
}
series of integers
with 1
≤
n
1
<n
2
<
···
<n
r
=
n
and 1
≤
m
1
<m
2
<
···
<m
r
=
m
respectively. The central map
,g
m
(
x
))
t
G
(
x
)=(
g
1
(
x
)
,
···
(9)
