RSA Laboratories

7.14 What is PSS/PSS-R?

PSS (Probabilistic Signature Scheme) is a provably secure way of creating signatures with RSA (see Question 3.1.8) due to Mihir Bellare and Phillip Rogaway [BR96]. Informally, a digital signature scheme is provably secure if its security can be tied closely to that of an underlying cryptographic primitive. The proof of security for PSS takes place in the random oracle model, in which hash functions are modeled as being truly random functions. Although this model is not realistically attainable, there is evidence that practical instantiations of provably secure schemes are still better than schemes without provable security [BR93]. The method for creating digital signatures with RSA that is described in PKCS #1 (see Question 5.3.3) has not been proven secure even if the underlying RSA primitive is secure; in contrast, PSS uses hashing in a sophisticated way to tie the security of the signature scheme to the security of RSA.

To minimize the length of communications, it is often desirable to have signature schemes in which the message can be ``folded'' into the signature. Schemes that accomplish this are called message recovery signature schemes. PSS-R is a message recovery variant of PSS with the same provable security.

Standards efforts related to PSS and PSS-R are underway in several forums, including ANSI X9F1, IEEE P1363, ISO/IEC JTC1 SC27, and PKCS.

Top of the page