A Fast Signature Scheme Based on Quadratic Inequalities

A new digital signature scheme is proposed in which the computation time is several hundred times faster than the RSA scheme and in which the key length and signature length are almost comparable to those for the RSA. Moreover, the scheme can be easily implemented and is, therefore, most practical for many digital signature applications. This new scheme is based on both a quadratic congruent inequality and a one-way hash function. The secret key consists of two large prime numbers p and q, and the public key is their product, n=p2q. An inequality is used for signature verification. Although the degree of security in this scheme has not been proved, it is shown that security seems to be equivalent to the difficulty of factoring a large number.