Cryptography Reference
In-Depth Information
texts of MPKCs are decrypted using secret keys
S, T
and
G
by equation (4),
and signatures are generated using
S, T, G
and random ephemeral values
r
=
(
r
1
,
,r
u
) by equation (5). We deal with the following two attacks on MPKCs:
(Fault attacks on
G
)
the attacker causes a fault to change a coecient of the
central map
G
,
(Fault attacks on
r
)
the attacker causes a fault such that several random
ephemeral values of
r
are fixed to the same values.
···
3.2
G
Assume that the coecient
α
ij
in (6) for a BF type or
a
(
l
)
ij
Fault Attacks on
in (10) for an STS type
or (
a
(
l
)
or (
a
(
l
)
is changed to
α
ij
ij
)
by the fault, and
α
ij
ij
)
cannot be recovered
or
a
(
l
)
ij
to
α
ij
again. For the correct (not faulty) central map
G
and the public
S
from equation (3), denote by
G
key
F
=
T
◦
G
◦
the faulty central map,
F
:=
T
G
◦
◦
S
and
ΔF
:=
F
−
(
G
−
F
=
T
1
◦
G
)
◦
S,
where
T
1
is given in (2). The basic approach of our fault attack is as follows.
——————————————————————————————————
Step 1.
Cause a fault on
G
and make
G
.
Step 2.
Decrypt randomly chosen messages
y
(1)
,
,y
(
N
)
k
m
(
N
···
∈
≥
1) by the
faulty map
G
using equation (4);
x
(
l
)
:=
S
−
1
(
G
−
1
(
T
−
1
(
y
(
l
)
)))
.
Step 3.
Encrypt
x
(1)
,
,x
(
N
)
k
n
by the correct (not faulty) public key
F
in
···
∈
equation (3);
z
(
l
)
:=
F
(
x
(
l
)
)
.
Step 4.
Put
z
(
l
)
.
Find (partial information of)
S
and
T
by the pairs
δ
(
l
)
:=
y
(
l
)
−
(
x
(
l
)
,δ
(
l
)
)
}
1
δ(l))}1≤l≤N
.
——————————————————————————————————
Since
y
(
l
)
=
F
(
x
(
l
)
)and
z
(
l
)
:=
F
(
x
(
l
)
), we have
{
δ
(
l
)
=
ΔF
(
x
(
l
)
)=
T
1
◦
(
G
−
S
(
x
(
l
)
)
.
G
)
◦
Many coecients of both
G
and
G
are the same, so then
G
G
is a sparse
−
G
, we try to recover
S
and
T
.The
details of recovering
S
and
T
are described in the following subsections.
polynomial. From the sparseness of
G
−
3.2.1 Fault Attack on
G
for Big Field Type
We propose the fault attack on HFE, which is a typical BF-type model. Let
,Δf
m
(
x
))
t
ΔF
(
x
)=(
Δf
1
(
x
)
,
···
