Digital Signature Scheme Based on a New Hard Problem

Abstract

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 |k | ≥ 160. Difficulty of the last problem is estimated as O ( √ k). It is proposed a new DSS with the public key y = x k mod p, 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 = t k mod p and S = tx f(R,M) mod p, where f(R, M) is a compression function. The verification equation is S k mod p = y f(R,M) R mod p. The DSS is used to implement an efficient protocol for generating collective digital signatures. 1