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

Author: Mihir Bellare and Phillip Rogaway

Reference: Advances in Cryptology - EUROCRYPT 96, Lecture Notes in Computer Science Vol. 1070, U. Maurer ed, Springer-Verlag, 1996

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.

Availability: Full version available in PostScript or pdf .


PSS: Provably secure encoding method for digital signatures

Author: Mihir Bellare and Phillip Rogaway

Reference: Submission to IEEE P1363, August 1998, based on the paper above.

Abstract: We describe two encoding methods: EMSA-PSS, for signing with appendix, and EMSR-PSS, for signing with message recovery. These encodings are appropriate for signatures based on the RSA or Rabin/Williams primitive. The methods are as simple and efficient as the methods in the current P1363 draft (based on X9.31 and ISO 9796), but they have better demonstrated security. In particular, treating the underlying hash function as ideal, EMSA-PSS and EMSR-PSS give rise to provably-secure schemes: the ability to forge implies the ability to invert the underlying trapdoor permutation. In fact, when the underlying primitive is RSA, the schemes are not only provably secure, but are so in a tight way: the ability to forge with a certain amount of computational resources implies the ability to invert RSA (on the same size modulus) with essentially the same computational resources.

Availability: Distributed as PostScript or pdf.


Rogaway's home page.