A new digital signature scheme is described and analyzed. Its security against chosen-message attack is based on the strong Rivest-Shamir-Adelman (RSA) assumption, defined in 1997 by Baric´ and  Pfitzmann  [1]. This scheme is state-free (that is, it does not require that the signer maintain any state). Basically, the ideas are the same as in the scheme of Cramer and Damgaard [2], but different from that of Gennaro et al. [3], which uses the same hypothesis.

A hash function can be incorporated into the scheme in such a way that it remains secure in the random oracle model under the standard RSA assumption. In this sense, the authors prove that their scheme can be made at least as secure as a standard RSA signature.

Some complementary problems are treated. The authors show that the problem of defining the strong RSA assumption is random self-reducible (section 4). A fast prime generation algorithm that generates prime numbers of the form , where is a prime number and is an integer, is proposed. The algorithm is defined for 161-bit prime numbers. An interesting result is that for any there are more than prime numbers of the form in the range . A procedure for generating Sophie Germain prime numbers and some preliminary study of the density of these numbers are presented. Finally, the authors briefly describe the implementation of a version of their signature scheme, using SHA-1 as the underlying hash function, and discuss its performance.