Cryptography Reference
In-Depth Information
will assume that this is the case; we refer to [58] for specific details and for a
recommended procedure to generate these primes.
5. The signing algorithm requires the generation of an
-bit prime for each
signature. If not carefully implemented, this process may be the costliest part of
the algorithm. However, these primes need not be generated uniformly at random
and in [58] an efficient algorithm is suggested to generate them in case
l
(
l
+
1
)
=
160.
The security of the Cramer-Shoup scheme is given by the following result:
Theorem 9.3
The Cramer-Shoup signature scheme is UF-CMA secure under the
strong RSA assumption and the assumption that H is collision resistant.
We refer to [58, Theorem 1] for the proof, which is too long to be included here.
Exercise 9.16
2
p
+
2
q
+
1, with
p
and
q
distinct
(i) Show that if
n
=
pq
where
p
=
1 and
q
=
QR
n
is a cyclic group of order
p
q
.
(ii) Write a Maple function that, given the hypotheses of the preceding question,
and given
z
Sophie Germain primes, then
∈
QR
n
and a positive integer
e
which is not divisible by
p
nor by
q
, computes the
e
th root of
z
in
QR
n
as required by Cramer-Shoup signatures.
Test this function for suitable values of
z
and
e
, with
p
and
q
1024-bit primes.
9.6 Signatures with Added Functionality
Here we briefly review some signature schemes which have added functionality.
9.6.1 Blind Signatures
Blind signatures
were originally proposed byD. Chaumin the 1980s, with the purpose
of creating an electronic version of money. A blind signature scheme is a two-party
protocol between a sender (called also a blinder) and a signer. The sender
A
sends the
signer
B
some information (a 'blinded' message
m
that is in some sense analogous
to a sealed envelope containing
m
, which the signer does not see).
B
signs this
information and returns it to
A
. From this signature,
A
computes (or 'unblinds') the
signature of the message
m
but
B
knows neither
m
nor its signature. Thus the term
'blind signature' refers to the fact that the signer does not know what it signed. In
particular,
B
is later unable to associate the message
m
with sender
A
.
It might seem at first sight that blind signatures are completely useless because no
party would agree to sign a message without knowing its content. However, there are
interesting applications of this concept, for example, in the domain of digital cash.
