Cryptography Reference
In-Depth Information
Remark 9.3
The formal definition of the FDH scheme is very similar to our earlier
definition of hashed RSA signatures in Sect.
9.3.1
but there is a fundamental differ-
ence in that now the hash function is a random oracle that must be queried by the
signing and verification algorithms. This hypothesis is crucial for the security analy-
sis but, in practice, the scheme may be implemented by defining
H
on top of some
hash function like SHA-1 or SHA-256. The random oracle hypothesis no longer
holds for such an implementation but the security analysis under this hypothesis
gives a certain indication of security and, in particular, shows that such a concrete
scheme may be secure against attacks that do not exploit specific properties of the
hash function used.
In order to analyze the security of the FDH scheme, we slightly modify the signa-
ture UF-CMA experiment in Definition 9.2 to adapt it to the concrete case of FDH
(in the random oracle model):
Definition 9.8
The
FDH signature unforgeability experiment under an adaptive
chosen message attack
Sign
uf-cma
A
,
FDH
(
k
)
is the following:
1
k
1. A key pair
(
pk
,
sk
)
is generated by running
Gen
(
)
.
}
∗
2. A random hash function
H
:{
0
,
1
→ Z
n
(for the RSA modulus
n
of
pk
)is
chosen.
3. The adversary
A
is given
pk
and oracle access to both
H
and
Sign
(
sk
,
−
)
.
A
asks a set of queries to these oracles and outputs a message/signature pair
.
4. The output of the experiment is defined to be 1 if
m
was not queried to the signing
oracle and
Ve r
(
m
,
t
)
(
pk
,
m
,
t
)
=
1, and 0 otherwise.
The security of the FDH scheme is given by the following theorem from [20]:
Theorem 9.1
If the RSA problem is hard relative to
Gen
RSA
and the hash function
H is modeled as a random oracle, then FDH is UF-CMA secure.
Proof
Let
be an FDH forger, i.e., a PPT adversary whose probability of success
in the experiment
Sign
uf-cma
A
A
,
FDH
(
k
)
is equal to
ε(
k
)
.
A
queries both the hash oracle and
the signing oracle, so let
q
be an upper bound on the number of queries to
the hash oracle. We construct a PPT algorithm
=
q
(
k
)
B
which is an adversary for the RSA
experiment
RSA
and tries to invert the RSA function as follows.
First,
Gen
RSA
is run on input 1
k
B
,
Gen
RSA
(
k
)
and an RSA key
(
n
,
e
,
d
)
is obtained, where
pk
=
(
n
,
e
)
and
sk
=
(
n
,
d
)
. A random
y
← Z
n
is chosen and
B
is given
(
n
,
e
,
y
)
tries to compute
y
d
mod
n
—without knowing
d
—by using
as input.
B
A
as a
subroutine as follows:
•
B
←{
,...,
}
picks a random integer
j
1
q
.
•
B
gives
A
the public key
pk
=
(
n
,
e
)
and simulates both the hash oracle and the
in experiment
Sign
uf-cma
signing oracle that are queried by
A
A
,
FDH
(
k
)
, answering all
queries posed by
A
.
B
initializes a counter
i
setting it to 0 and a table of elements
3
of
Z
n
, initially empty.
