##
The exact security of digital signatures: How to sign with RSA and
Rabin

** Authors: M. Bellare and P. Rogaway**
** Abstract: ** We describe an RSA-based signing scheme called PSS which
combines essentially optimal efficiency with attractive security
properties. Signing takes one RSA decryption plus some hashing, verification
takes one RSA encryption plus some hashing, and the size of the signature is
the size of the modulus. Assuming the underlying hash functions are ideal, our
schemes are not only provably secure, but are so in a * tight* way--- an
ability to forge signatures with a certain amount of computational resources
implies the ability to invert RSA (on the same size modulus) with about the
same computational effort. Furthermore, we provide a second scheme which
maintains all of the above features and in addition provides message
recovery. These ideas extend to provide schemes for Rabin signatures with
analogous properties; in particular their security can be tightly related to
the hardness of factoring.

** Ref:** Extended abstract in Advances in Cryptology - Eurocrypt 96
Proceedings, Lecture Notes in Computer Science Vol. 1070, U. Maurer ed,
Springer-Verlag, 1996. Full paper of revised version available below.

** Full paper: ** Available as compressed
postscript, postscript, or pdf. ( Help if
this doesn't work).

## Related work

The OAEP scheme is a similar proposal for encryption
with RSA.