An efficient signature scheme based on quadratic equations

Electronic messages, documents and checks must be authenticated by digital signatures which are not forgeable even by their recipients. The RSA system can generate and verify such signatures, but each message requires hundreds of high precision modular multiplications which can be implemented efficiently only on special purpose hardware. In this paper we propose a new signature scheme which can be easily implemented in software on microprocessors: signature generation requires one modular multiplication and one modular division, signature verification requires three modular multiplications, and the key size is comparable to that of the RSA system. The new scheme is based on the quadratic equation m = s21 + ks22 (mod n), where m is the message, s1 and s2 are the signature, and k and n are the publicly known key. While we cannot prove that the security of the scheme is equivalent to factoring, all the known methods for solving this quadratic equation for arbitrary k require the extraction of square roots modulo n or the solution of similar problems which are at least as hard as factoring. A novel property of the new scheme is that legitimate users can choose k in such a way that they can sign messages even without knowing the factorization of n, and thus everyone can use the same modulus if no one knows its factorization.