Cryptography Reference
In-Depth Information
=
/
experiment. The probability that
m
m
j
is 1
q
due to the random choice of
j
and
A
ε(
)/
(
)
(
)
hence the probability that
succeeds is
k
q
k
. Since
q
k
is a polynomial func-
tion,
B
succeeds with non-negligible probability in case
ε(
k
)
is a non-negligible
function, and this completes the proof.
The preceding security result has a drawback in that the reduction is not tight and
leaves open the possibility that signatures can be forged with a probability
q
times
higher than the probability of being able to invert the RSA function at a random
point with comparable execution time. An attack with
q
2
60
queries to the hash
oracle is conceivable and if, for example, the probability of success on inverting RSA
for some given parameters were
>
2
−
70
within a given time, then the probability of
breaking FDH in comparable time could be
≈
2
−
10
. It that case, the passage from
2
−
70
to 2
−
10
would entail a huge security loss.
5
≈
9.5.2 PSS Signatures
The lack of tightness in the FDH security reduction motivated the search for a
scheme based on the same principles but with a much tighter security reduction.
As a result, Bellare and Rogaway introduced such a scheme in [20]; the new scheme
is called the
Probabilistic Signature Scheme
(PSS) and, while still following the hash-
then-invert paradigm, it differs from FDH in that the signing algorithm uses a ran-
domly chosen seed and is, therefore, probabilistic. Efficiency is similar to that of
FDH but the tighter reduction implies that the probability of signature forgery is
almost as low as the RSA inversion probability, regardless of the number of hash or
sign oracle queries made by the adversary. PSS can be described as follows:
Definition 9.9
PSS signature scheme.
•
The parameters and the
Gen
algorithm are the following:
- PSS is parameterized by
k
0
and
k
1
, which are integers such that 1
<
k
0
,
k
1
<
k
and
k
0
+
1 where
k
denotes, as usual, the security parameter. Typical
values for these parameters are:
k
k
1
≤
k
−
256.
- The key generation algorithm
Gen
is the same as that of FDH:
Gen
RSA
is run
to obtain
pk
=
2048,
k
0
=
k
1
=
k
.
- The signing and verification algorithms make use of two hash functions:
H
=
(
n
,
e
)
and
sk
=
(
n
,
d
)
, where len
(
n
)
=
}
∗
→{
k
1
:{
0
,
1
0
,
1
}
(called the
compressor
).
k
1
k
−
k
1
−
1
(called the
generator
).
G
defines functions
G
1
:{
,
}
→{
,
}
:
G
0
1
0
1
k
1
k
0
and
G
2
k
1
k
−
k
0
−
k
1
−
1
by setting
G
{
,
}
→{
,
}
:{
,
}
→{
,
}
(
)
=
0
1
0
1
0
1
0
1
w
k
1
.
G
1
(
w
)
||
G
2
(
w
)
for
w
∈{
0
,
1
}
5
A tighter reduction, which depends on the number of signing oracle queries rather than on the
number of hash oracle queries, was found by J.S. Coron but a still tighter reduction is desirable.
