Cryptography Reference
In-Depth Information
Table 2.
Success probability of our proposed fault attacks on some MPKCs
q
n
m
S
G
T
Scheme
Quarz(2,103,129,3,4) [14]
2
107 100 0.38 0.29 0.33
4HFE(31,10) [11]
31
40
40 0.37 0.26 0.37
Rainbow(31,24,20,20) [10]
31
64
40 0.07 0.90 0.03
Rainbow(256,18,12,12) [10] 256 42
24 0.10 0.87 0.03
(over
k
)in
m
quadratic forms of
n
variables is
m
(
n
+1)(
n
+2)
/
2. In general, the
total number of the coecients (over
k
)in
G
is less than
m
(
n
+1)(
n
+2)
/
2, since
G
is a special quadratic map. Such total numbers depend on the scheme (namely
G
), so it is not easy to discuss the general situations. We select several example
schemes, Quartz (HFEv
) [14], 4HFE [11] and Rainbows [10], and calculated
the number of
k
-elements in
S
,
G
and
T
. The results are shown in Table 2. In
“
S
”, we describe the ratio of the number of entries in
S
over the total sum of
the
k
-elements in
S, G
and
T
.Thenumbersin“
G
”and“
T
”arethesame.
In Quartz and 4HFE (which are BF type), the number of
k
-elements in
G
is
less than those in
S
and
T
, since, if a BF type
G
is constructed contains a large
number of coecients, the decryption process becomes much complex. However,
the probability around 25%
−
30% is large enough for attackers. On the other
hand, in two Rainbow examples (which are STS type), the number of
k
-elements
in
G
is much larger than that in
S
and
T
. For such schemes, there is quite a
large probability that
G
is faulty.
Distinguishing the faulty place.
Our fault attack succeeds if the fault changes
a coecient in
G
, and it does not if an entry in
S
or
T
is changed. We now discuss
how to distinguish the faulty place,
G
,
S
or
T
.
First, assume that the (
l
1
,l
2
l2)-entry in
T
is changed by the fault. Then
∼
,
0
,
l
ˇ
δ
(
i
)
=(
T
T
)
S
(
x
(
i
)
)=(0
,
,
0)
t
.
−
◦
G
◦
···
∗
,
0
,
···
(16)
This shows that, if only one entry in
δ
(
i
)
is non-zero and the others are all zero,
T
is faulty with high probability.
Next, assume that the (
l
1
,l
2
l2)-entry in
S
is faulty and denote by
S
(
x
(
i
)
)=(
δ
(
i
1
,
,δ
(
i
m
)
t
,x
(
i
)
=(
x
(
i
1
,
δ
(
i
)
=
T
S
(
x
(
i
)
)
,x
(
i
)
n
)
t
◦
G
◦
−
T
◦
G
◦
···
···
This shows that
δ
(
i
)
j
=
x
(
i
)
(linear form of
x
(
i
1
,
,x
(
i
)
n
l
2
×
···
)
.
(17)
Basedonthis,wecancheckwhether
S
is faulty as follows.
Prepare
N
pairs of (
x
(
i
)
,δ
(
i
)
)with
N
≥
n
+2.Put
=
x
v
a
(
j,l
)
1
x
n
+
b
(
j,l
)
,
y
(
l
)
j
+
a
(
j,l
)
n
x
1
+
···
(18)
