Abstract:

Digital signature schemes constitute a fundamental cryptographic
primitive, of use both in its own right, and as a building block in
cryptographic protocol design.

In this talk, I will look at the main two signature algorithms -- the
algorithm for signing, and the algorithm for verifying a signature -- as
protocols.  Given a signature scheme, the signing protocol is between a
user who wants his message m signed, and the signer with public key PK.
The verification protocol is between a user who holds a signature
\sigma_PK(m) and a verifier who wants to make sure that the signature
held by the user is valid.

The topic I will address is making these two protocols as secure as
possible.  That is to say, they must conform to their specification, and
should not leak any more information than the specification allows.  We
want to make possible a signing protocol in which the signer does not
learn anything about the message he is signing, and a verification
protocol in which the verifier does not learn anything about the
signature he is verifying, other than that it is a valid signature.

I will propose a practical and provably secure signature scheme and show
such secure protocols for signing and verifying a signature.  The
proposed signature scheme and protocols are secure under the strong RSA
assumption, and are efficient enough to be useful in practice, as a
building block for the design of anonymity-enhancing cryptographic
systems, such as electronic cash, group signatures, and anonymous
credential systems.

This is joint work with Jan Camenisch.