Signature schemes based on two hard problems simultaneously

Harn (1994) proposed a signature scheme based on the modified ElGamal scheme and claimed that the security relies on both the factorization and the discrete logarithm. That is, his scheme cannot be broken unless both of the above two problems can be solved simultaneously. Lee and Hwang (1996) showed that an attacker could generate a forged signature on the assumption when the discrete logarithm is solved. Recently, Shao (1998) proposed another two signature schemes, which the security rests on the two problems. In this paper, we propose two improved signature schemes that are really based on two hard problems simultaneously. In addition, the numbers of parameters and computations are reduced in comparison with those of Shao.