Digital Signature Scheme Based on Factoring and Discrete Logarithms

A digital signature scheme allows one to sign an electronic message and later the produced signature can be validated by the owner of the message or by any verifier. Most of the existing digital signature schemes were developed based on a single hard problem like factoring, discrete logarithm, residuosity or elliptic curve discrete logarithm problems. Although these schemes appear secure, one day in a near future they may be exploded if one finds a solution of the single hard problem. Approach: To overcome this problem, in this study, we proposed a new signature scheme based on multiple hard problems namely factoring and discrete logarithms. We combined the two problems into both signing and verifying equations such that the former depends on two secret keys whereas the latter depends on two corresponding public keys. Results: The new scheme was shown to be secure against the most five considering attacks for signature schemes. The efficiency performance of our scheme only requires 1203Tmul+Th time complexity for signature generation and 1202Tmul+Th time complexity for verification generation and this magnitude of complexity is considered minimal for multiple hard problems-like signature schemes. Conclusions: The new signature scheme based on multiple hard problems provides longer and higher security level than that scheme based on one problem. This is because no enemy can solve multiple hard problems simultaneously.

In modern cryptography , the security of developed signature schemes are based on the hardness of solving some hard number theoretical problems. The schemes stay secure as long as the problem underlies the scheme stay unsolvable. The most used hard problems for someone designing a signature scheme are factoring (FAC) and Discrete Logarithms(DL) However, it is understood that one day in the future the FAC and DL problems could be solved and when it happens, all signature schemes that depend on one of these problems will no longer be secure. One of the strategies to surmount this situation is by designing a signature scheme based on multiple hard problems. Undoubtedly, the security of such schemes is longer than schemes based on a single problem. This is due to unlikely solving two hard problems simultaneously. Many digital signature scheme have been designed based on both FAC and DL but to design such schemes is not an easy task since many of them have been shown insecure

. In this study, we developed a new signature scheme based on the multiple hard problems namely factoring and discrete logarithms. Some notations: The following parameters and notations will be used throughout this paper unless otherwise specified:
• h (.) cryptographic hash function whose output is a
t-bit length. We assume here that t = 128.
• p is a large prime and n is a factor of p-1 that is the
product of two safe prime p′ and q′ i.e., n = p′q′.
• An additive group ]n
= {0, 1, 2, , n-1}.
• φ(n) = (p′-1)(q′-1) is a phi-Euler function.
• g is a primitive element in {0,1,2,,p-1} i.e., the
order of g is n which satisfies g
≡ 1 (mod p).
• gcd (a,b) is the greatest common divisor of a and b.

Free download research paper