IMI/Publicaţii/CSJM/Ediţii/CSJM v.16, n.2 (47), 2008/

Digital Signature Scheme Based on a New Hard Problem

Authors: Nikolay A. Moldovyan


Factorizing composite number n=qr, where q and r are two large primes, and finding discrete logarithm modulo large prime number p are two difficult computational problems which are usually put into the base of different digital signature schemes (DSSes). This paper introduces a new hard computational problem that consists in finding the k th roots modulo large prime p=Nk2+1 where N is an even number and k is a prime with the length |k|≥160. Difficulty of the last problem is estimated as O(√k). It is proposed a new DSS with the public key xkmodp, where x is the private key. The signature corresponding to some message M represents a pair of the |p|$-bit numbers S and R calculated as follows: R=tk mod p and S=txf(R,M)modp, where f(R, M) is a compression function. The verification equation is Sk mod p=yf(R, M)Rmodp. The DSS is used to implement an efficient protocol for generating collective digital signatures.

N. A. Moldovyan
Specialized Center of Program Systems "SPECTR",
Kantemirovskaya, 10, St.Petersburg 197342, Russia;


Adobe PDF document0.19 Mb