Cryptography Reference
In-Depth Information
(
,σ)
3. Given the signed message
, the verifier starts by computing
y
and then
recovers
w
,
r
∗
and, finally, the random seed
r
. Then these values are used to check
that
y
was correctly constructed and only if all these checks are successful, the
signature is accepted.
4. The scheme is efficient because the signing and verification algorithms each
require one application of
H
, one application of
G
, and one RSA operation
(decryption or encryption). The hash functions used in practice are very efficient,
so the costliest part is the RSA operation.
m
As alreadymentioned, PSS is UF-CMA secure in the randomoraclemodel assum-
ing that the RSA problem is hard relative to
Gen
RSA
. This was proved in [20] and
can be stated as follows:
Theorem 9.2
Consider the PSS scheme with security parameters k
0
and k
1
and
suppose that
is an adversary making q
s
signing oracle queries and q
h
hash ora-
cle queries (with q
h
A
≥
1
+
q
s
), whose probability of success in the experiment
Sign
uf-cma
A,
PSS
(
)
ε(
)
B
k
is equal to
k
. Then there exists an adversary
with probability of
ε
(
success in the
RSA
B
,
Gen
RSA
(
k
)
experiment equal to
k
)
, where
)
=
ε
(
2
2
−
k
0
2
−
k
1
ε(
k
k
)
+
3
(
q
h
−
1
)
(
+
)
k
3
and the running time of
B
is that of
A
plus q
h
·
k
0
·
O
(
)
.
Remarks 9.4
1. We have not explicitly defined the PSS unforgeability experiment used in the
theorem but suffice it to say that it is a signature experiment in the random oracle
model, defined similarly to the FDH experiment.
2. The fact that
q
h
≥
q
s
in the preceding theorem comes from the assumption—
discussed when analyzing the security of FDH—that each signing query is pre-
ceded by a hash query and that the hash query that corresponds to the message
output in the forgery is not followed by a signing query.
3. Since typically we will have
k
0
1
+
2
−
k
0
2
−
k
1
=
k
1
=
256, 1
/(
+
)
will dominate
2
and hence the value of
ε
(
(
q
h
−
)
)
the factor 3
1
k
will be close to the value of
ε(
)
. On the other hand, we see that the time reduction (expressed by the relation
between the running times of
k
)isalsotight.
4. It is obvious that the PSS construction (or the FDH scheme, for that matter) may
also be more generally defined by using a trapdoor one-way permutation instead
of the RSA function, obtaining a scheme which is secure in the random oracle
model relative to the one-wayness of the permutation used.
A
and
B
We refer to [20] for a proof of Theorem 9.2. The crucial difference between this
proof and that of Theorem 9.1 is that there the RSA inverter had to guess the index
value
j
∈{
1
,...,
q
}
for which the adversary
A
would forge a message and this guess
was correct only with probability 1
q
, with
q
equal to the number of hash oracle
queries. In the case of PSS, the proof shows that the inverter is successful, except
with very small probability, no matter which is the index value for which the forgery
/
