Efficient Rabin-type digital signature scheme (Q1283220)

Difficulties in getting exact results about the security of a cryptosystem have led to the practice of indirect arguments. Perhaps the most favorable approach is based on proving that breaking analyzed cryptosystem is as hard as solving some problem known or believed to be hard. It is interesting, however, that even such indirect arguments are not known for undoubtedly the most popular and widely used public-key cryptosystem (PKC) -- RSA. On the other hand similar PKC, known as Rabin's cryptosystem has been proved to be as hard as factorization. However, original digital signature scheme based on Rabin's cryptosystem is of probabilistic nature. In the paper two Rabin-type digital signature schemes are proposed. While both schemes are deterministic, it is shown that they run much faster and the size of a signature is smaller than for the original scheme of Rabin. Also it is shown that in the random oracle model breaking the proposed signature schemes by chosen plaintext attack is as hard as factoring.