Cryptography Reference
In-Depth Information
(This paper does not describe the complexity estimations, but detailed discus-
sions of the min-rank attack are available elsewhere [32,25]).
On the other hand, the high-rank attack is used when the gap between the
highest and second highest rank is small. For the STS type scheme, the high-rank
attack recovers (a part of)
T
effectively when
n
1
in (10) is small [13,46].
2.3.3 Differential Attacks
The differential attack is an attack using the differential
F
(
x
+
t
)
−
F
(
x
)
−
F
(
t
), where
F
is the public key and
x, t
k
n
. The differential is a linear map
and its kernel or rank will give secret information. In fact, it is known that
dummy signatures of MI
∈
−
[41], PMI [26] and Sflash [22] can be generated by
the differential attacks.
2.3.4 Individual Attacks
In addition to the general attacks above, several attacks on individual schemes
can be used on other similar schemes. For example, Kipnis-Shamir's attack on
UOV [33,31], which recovers a part of
S
from the public key
F
,isusedwhenthe
public key
F
is given by
f
l
(
x
)=
x
t
S
1
0
o
∗
S
1
x
+ (linear form of
x
)
,
∗∗
n−o
where 1
n
. Rainbow and TTS are the examples of such schemes. Note
that this attack finds
M
such that
S
1
I
o
0
MI
n−o
≤
o
=
∗
o
∗
0
∗
n−o
with the complexity
O
(
q
n−
2
o
o
4
). Such partial information
M
of
S
is important,
since
f
l
I
o
0
MI
n−o
x
=
x
t
0
o
∗
∗∗
n−o
x
+ (linear)
.
(14)
The quadratic form above is also of UOV type, and thus a signature
x
for any
given message
y
can be generated. In Rainbow and TTS, (14) does not generate
a signature directly, however if such an
M
is found, recovering (a part of)
T
becomes much easier than doing so with only the original
F
, and ensuring the
security of Rainbow becomes as easy as when Rainbow was a smaller size.
3 The Proposed Fault Attacks on MPKCs
In this section, we discuss the fault attacks to be used on MPKCs.
3.1
Attack Model
Theentriesoftheanemaps
S, T
in (2) and the coecients of the central
map
G
are stored in the device as the fixed parameters used in MPKCs. Cipher
