This invention is a method and apparatus which provide a solution to the problem of constructing efficient and secure digital signature schemes. It presents a signature scheme that can be proven to be existentially unforgeable under a chosen message attack, assuming a variant of the RSA conjecture. This scheme is not based on “signature trees”, but instead it uses a “hash-and-sign” paradigm, while maintaining provable security. The security proof is based on well-defined and reasonable assumptions made on the cryptographic hash function in use. In particular, it does not model this function as a random oracle. The signature scheme which is described in this invention is efficient. Further, it is “stateless”, in the sense that the signer does not need to keep any state, other than the secret key, for the purpose of generating signatures.