Cryptography Reference
In-Depth Information
and each equation
Δf
l
(
x
) be defined similar to equation (1) as
ij
x
i
x
j
+
i
a
(
l
)
b
(
l
)
i
x
i
+
c
(
l
)
,
Δf
l
(
x
):=
1
≤i≤j≤n
where
a
(
l
)
ij
,b
(
l
)
k
. At this point, the coecients
a
(
l
)
ij
,b
(
l
)
i
,c
(
l
)
are unknown.
To find them, substitute the pairs (
x
(
l
)
,δ
(
l
)
) into the above and construct a
system of linear equations of unknowns
a
(
l
)
,c
(
l
)
∈
i
ij
,b
(
l
)
,c
(
l
)
. Since the total number of
i
a
(
l
)
ij
,b
(
l
)
,c
(
l
)
is (
n
+1)(
n
+2)
/
2forafixed
l
, we can solve such equations and find
i
a
(
l
)
ij
,b
(
l
)
i
,c
(
l
)
with (
n
+1)(
n
+2)
/
2 pairs of (
x
(
l
)
,δ
(
l
)
). Remark that a univariate
polynomial equation
k
n
,
does not always have a solution, and the probability that it has no solutions is
around 0
.
33
G
(
X
)=
Y
(
l
)
,where
Y
(
l
)
K
is derived from
y
(
l
)
∈
∈
∼
0
.
5 [29] (about 0
.
368
···∼
1
/e
for large
q, n
). Thus the attacker
G
−
1
(
Y
(
l
)
) in practice.
Next, we explain how to find
S
and
T
by
ΔF
. Assume that the fault changes
α
ij
to
α
ij
. Then the central map of
ΔF
is derived from
has to compute more
α
ij
)
X
q
i
+
q
j
,
G
−G
)(
X
)=(
α
ij
−
(
G
−
which is similar to
G
(
X
) in MI. Since the rank of the coecient matrix of (
,X
q
n
−
1
)
t
is 2, Kipnis-Shamir's attack
[32,25] (the rank attack) for rank 2 will find (a part of)
S
and
T
.
If there is more than one
G
fault - namely several coe
cients are changed -
ΔF
(
x
) is no longer the case above and
ΔF
(
x
) is reduced to a public key of HFE
with a smaller
u
. For example, when two coe
cients are changed,
ΔF
is a public
key of HFE derived from
)(
X
) as a quadratic form of (
X, X
q
,
G
···
with two terms. The attacker can then find
S
and
T
by Kipnis-Shamir's attack [32,25] for rank 4 at most, which is much smaller than
the rank of the coecient matrix for
G
of the HFE without the fault. Since, if the
rank is smaller, Kipnis-Shamir's attack recover
S
and
T
with less complexity (see
[32,25] for the complexity estimations), our fault attack reduces the complexity
of recovering
S
and
T
.
G
3.2.2 Fault Attack on
G
for STS Type
We propose the fault attack on the STS type, which has a central map given by
(10). Note that, different to the attack on the BF type, we need to cause a fault
in several times for STS type.
First, assume that the coe
cient
a
(
l
1
)
i
1
j
1
is changed to (
a
(
l
1
)
i
1
j
1
)
by the fault. In
this case, it is easy to see that
l
1
−
1
0
,
G
)(
x
)=
,
0
t
,
,
0
,
(
a
(
l
1
)
(
a
(
l
1
)
i
1
j
1
)
)
x
i
1
x
j
1
,
0
,
(
G
−
···
i
1
j
1
−
···
,x
n
)
t
.Wethenseethat
where
x
=(
x
1
,
···
l
1
,
0
,
δ
(1)
=
ΔF
(
x
(1)
)=
T
1
◦
G
)
S
(
x
(1)
)=
cT
1
(0
,
,
0)
t
,
(
G
−
◦
···
,
0
,
···
