Cryptography Reference
In-Depth Information
9.5.5 Cramer-Shoup Signatures
If the RSA problem is hard, then the FDH and PSS signature schemes are UF-CMA
secure in the random oracle model but, so far, we have not mentioned any signature
scheme that is UF-CMA secure without assuming that the hash functions involved
are random oracles. However, such schemes exist and the price to pay for the stronger
security result is less efficiency and, sometimes, the use of a hardness hypothesis that
is stronger than the RSA assumption. Perhaps the most important scheme of the latter
type is the Cramer-Shoup signature scheme which we are now going to describe.
The Cramer-Shoup signature scheme was introduced in [58] and its security relies
on the hardness of the following problem:
← Z
n
,
Definition 9.10
The
flexible RSA problem
is, given an RSAmodulus
n
and
z
∈ Z
n
such that
y
e
to find an integer
e
>
1 and
y
≡
z
(
mod
n
)
.The
strong RSA
assumption
is the assumption that this problem is hard to solve.
Remark 9.4
The difference between the strong RSA assumption and the RSA
assumption is that in the latter the exponent
e
is chosen independently of
z
, whereas
in the former it may be chosen in a way that depends on
z
. An adversary breaks the
strong RSA assumption if it can find an exponent
e
such that it is able to extract an
e
th root of
z
, so it is clear that the strong RSA assumption is potentially stronger than
the RSA one. However, the only method known so far to break either assumption is
to solve the integer factorization problem.
9.5.5.1 Cramer-Shoup Signature Scheme
The scheme is parameterized by two security parameters
l
and
l
such that
l
l
−
1
andmakes use of a collision resistant hash function
H
whose output can be interpreted
as a positive integer less than 2
l
. A reasonable choice for
H
is SHA-256 and this
suggests using
l
+
1
<
256. The parameter
l
specifies the length of two primes that
are used to generate an RSA modulus of a special form. Thus, bearing in mind
the hardness of the factorization problem, a reasonable value for this parameter is
l
=
=
1024.
•
Key generation
. The algorithm proceeds as follows:
1. Two random
l
-bit safe primes
p
,
q
, are chosen (so that
p
2
p
+
=
1 and
q
=
2
q
+
1, where
p
and
q
are Sophie Germain primes) and
n
=
pq
is computed.
2. Two random quadratic residues
h
←
QR
n
,
x
←
QR
n
and a random
(
l
+
1
)
-bit
prime
e
are chosen.
3. The public key is
e
)
(
n
,
h
,
x
,
and the private key is
(
p
,
q
)
.
}
∗
be a message. To sign it with the private key
•
∈{
,
(
,
)
Signing
.Let
m
0
1
p
q
—plus
the public key—the following operations are performed:
