Abstract: To promote the speed of the random signature generation and verification algorithms under the strong RSA hardness assumption, a new signature scheme is proposed. In this scheme, by randomly selecting the exponent e under modular n and using the RSA algorithm to sign the message bound with e, the redundant parameters in Cao et al.’s signature scheme are simplified or deleted. The new scheme is proved to be secure in the Random Oracle Model. Detailed comparisons show that the speed of the new scheme is at least two times faster than that of the other schemes of such a kind.

Key words: digital signature, strong RSA assumption, adaptive chosen-message attack