A digital signature scheme based on polynomial operations
Tatsuaki Okamoto, Akira Shiraishi · Systems and Computers in Japan · 1986
Abstract The RSA scheme is considered as one of the most promising as a digital signature, i.e., the signature for document for digital information. However, the method has a problem in that the processing speed is slow. A method by high‐speed hash function is proposed as a solution to this problem, but the improvement is not remarkable for brief documents. To solve this problem, this paper proposes a new high‐speed digital signature scheme based on a congruent polynomial of lower degree. In this scheme, large prime numbers p and q are used as the secret information and n = p2q is used as the public information. A random number is used in the generation of the signature, and an equality is used in the verification. It is shown that the security of the proposed scheme is of the same order as the difficulty of the prime factorization of n. The processing speed and transfer/retained information of the proposed scheme are evaluated, indicating that the processing speed for a brief document is more than 100 times the RSA scheme, and the method requires larger secret information to be retained than in RSA scheme.