Efficient Rabin-type Digital Signature Scheme

Rabin's cryptosystem was proved to be as hard as factorization. However, Rabin's digital signature schemes is probabilistic. This paper shows two efficient Rabin type digital signature schemes, a basic scheme and an improved scheme. Both schemes run much faster than Rabin's scheme. They are deterministic and the size of a signature is much smaller than that of a signature in Rabin's scheme. Furthermore, it is proved that, by applying the technique of Bellare and Rogaway, the proposed scheme is secure against chosen plaintext attack. More precisely, breaking the proposed digital signature scheme by chosen plaintext attack is as hard as factoring N.