Abstract: To enhance the security, many signature schemes were designed based on two hard problems, such as factoring and discrete logarithm. The major goal of these schemes is that they cannot he broken if both problems cannot be solved simultaneously. However, --. this paper shows that YL scheme can be broken if the factoring problem is solved, LC scheme is insecure against forgery if the discrete logarithm problem is solved. A new signature scheme is proposed that is really based on two hard problems simultaneously, which can also make the message recovered. Comparing with other schemes, this scheme is more efficient.