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 kth roots modulo large prime p = Nk2 1, where N is an even number and k is a prime with the length jkj ¸ 160. Difficulty of the last problem is estimated as O( p k). It is proposed a new DSS with the public key y = xk mod p, where x is the private key. The signature corresponding to some message M represents a pair of the jpj- bit numbers S and R calculated as follows: R = tk mod p and S = txf(R;M) mod p, where f(R;M) is a compression function. The verification equation is Sk mod p = yf(R;M)R mod p. The DSS is used to implement an efficient protocol for generating collective digital signatures.