# A New Signature Scheme Based on Multiple Hard Number Theoretic Problems

Authors: E. S. Ismail; N. M. F. Tahat
Journal: ISRN Communications and Networking
 (2011)

---

## Abstract

The past years have seen many attempts to construct digital signature schemes based on a single hard problem, like factoring or discrete logarithm. But in the near future, those systems will no longer be secure if the solution of factoring or discrete logarithms problems is discovered. In this paper, we propose a new signature scheme based on two hard number theoretic problems, factoring and discrete logarithms. The major advantage of our scheme is that it is very unlikely that factoring and discrete logarithms can be efficiently solved simultaneously, and; therefore, the security of our scheme is longer or higher than that of any scheme based on a single hard number theoretic problem. We also show that the performance of the scheme requires only minimal operation both in signing and verifying logarithms and is resistant to attack.


---

## Body

## 1. Introduction

A digital signature scheme is used to authenticate the contents of a digital message, and a valid digital signature tells that the message was generated by a legal/known sender and was not altered during the transmission. Digital signatures are commonly applicable for software distribution, internet-based transactions, forgery detection or tampering. Most digital signature schemes have the common feature that they are based on a single cryptographic assumption [1], like discrete logarithms (DL) [2] or factoring a large composite number problem (FAC) [3]. Although such problems remain difficult to solve today, it is almost inevitable that one day the FAC and DL problems could be solved.  As soon as this happens, signatures based on such problems will no longer be secure. This has led researchers to propose digital signature schemes based on multiple hard number theoretic problems [4–9].The major motivation for this research is that such schemes are more secure than the schemes based on a single hard problem. However, many such schemes have been shown to be insecure [10, 11] due to the use of inappropriate algorithms and weak analysis of security. (See Qian et al. [12] for details of an example of an insecure signature scheme.) In this paper, we develop a new signature scheme based on a combination of factoring and discrete logarithm problems. We show that the performance of the new scheme is very efficient since it requires acceptable numbers of operations in both signature generation and signature verification.In the following, Section2 presents the proposed signature scheme. Section 3 analyzes the resultant security and efficiency from the new scheme, and finally, Section 4 gives our conclusions.


## 2. The Proposed Signature Scheme

The main purpose of proposing a signature scheme based on two hard problems is to enhance the security of the scheme. The difficulty of simultaneously solving two hard problems is harder than solving a single hard problem. The proposed scheme remains secure even if one can find a solution to one of the underlying problems.The proposed signature scheme involves the one-to-one interactions between a signer and a verifier to execute the system initialization phase, the key generation phase, the signature generation phase, and the signature verification phase, described as follows.


### 2.1. System Initialization Phase

The system initialization phase proceeds with the following commonly required parameters over the defined multiplicative groups. A one-way hash function is applied in the scheme with standard cryptographic characteristics, and to prevent the chosen message attack as defined by ElGamal [2] and Harn [13], the length of the signed message is reducible: (1)
a cryptographic hash functionh(·) whose output is a t-bitlength. In practice, we take t=128;(2)
a large primep, and n is a factor of p-1 and also the product of two safe primes, T and L, where n=TL. A function defined by ϕ(n)=(T-1)(L-1) is the phi-Euler function;(3)
an integerg is a primitive element in ℤp*={1,2,3,…,p-1} with order n such that gn≡1(modp);(4)
an integerα∈ℤn*={v:1≤v≤n-1and gcd(v,n)=1} is a square modulo n if there exists an β∈ℤn* such that α≡β2(modn), where gcd(a,b) denotes the greatest common divisor of a and b.


### 2.2. Key Generation Phase

In this phase, we do the following steps.(1)
Pick randomly an integere from ℤϕ(n)*.(2)
Calculate the secret numberd such that ed≡1(modϕ(n)).(3)
Select at random an integerx∈ℤp*.(4)
Compute the public numbery≡gx(modp).The public and secret keys of the signature scheme are now, respectively, given by the pairs of(e,y) and (d,x).


### 2.3. Signature Generation Phase

To create a signature for the messageM, 1<M<n, the signer first hashes the message to obtain h(M). Next, the signer randomly chooses a secret integer, r,  1<r<n such that gcd(r,n)=1 and then computes K≡gr(modp). The signer does the following steps.(1)
SolveKr≡γ2modn  and x≡ξ2modn for γ and ξ.(2)
Computes1≡(γ-ξh(M))dmodn and s2≡(γ+ξh(M))dmodn.(3)
Calculatev≡s1s2(modn).Then the original signer publishes(K,v) as the signature of the message M.


### 2.4. Signature Verification Phase

The verifier confirms the validity of the signature(K,v) for M as follows.(1)
Computeλ≡vemodn and η≡h(M)2modn.(2)
Check the equalitygλ≡KKy-ηmodp.(3)
If the equality in (2) holds, then validates the signature otherwise rejects it.Theorem 1.
Following the applied protocol, then the verification in the Signature Verification Phase is correct.Proof.
The equation in (2) in Signature Verification Phase is true for valid signatures since(1)gλ≡gve≡g(s1s2)e≡g(γ2-ξ2(h(M))2)≡gKr-xη≡KKy-η(mod⁡p).


## 2.1. System Initialization Phase

The system initialization phase proceeds with the following commonly required parameters over the defined multiplicative groups. A one-way hash function is applied in the scheme with standard cryptographic characteristics, and to prevent the chosen message attack as defined by ElGamal [2] and Harn [13], the length of the signed message is reducible: (1)
a cryptographic hash functionh(·) whose output is a t-bitlength. In practice, we take t=128;(2)
a large primep, and n is a factor of p-1 and also the product of two safe primes, T and L, where n=TL. A function defined by ϕ(n)=(T-1)(L-1) is the phi-Euler function;(3)
an integerg is a primitive element in ℤp*={1,2,3,…,p-1} with order n such that gn≡1(modp);(4)
an integerα∈ℤn*={v:1≤v≤n-1and gcd(v,n)=1} is a square modulo n if there exists an β∈ℤn* such that α≡β2(modn), where gcd(a,b) denotes the greatest common divisor of a and b.


## 2.2. Key Generation Phase

In this phase, we do the following steps.(1)
Pick randomly an integere from ℤϕ(n)*.(2)
Calculate the secret numberd such that ed≡1(modϕ(n)).(3)
Select at random an integerx∈ℤp*.(4)
Compute the public numbery≡gx(modp).The public and secret keys of the signature scheme are now, respectively, given by the pairs of(e,y) and (d,x).


## 2.3. Signature Generation Phase

To create a signature for the messageM, 1<M<n, the signer first hashes the message to obtain h(M). Next, the signer randomly chooses a secret integer, r,  1<r<n such that gcd(r,n)=1 and then computes K≡gr(modp). The signer does the following steps.(1)
SolveKr≡γ2modn  and x≡ξ2modn for γ and ξ.(2)
Computes1≡(γ-ξh(M))dmodn and s2≡(γ+ξh(M))dmodn.(3)
Calculatev≡s1s2(modn).Then the original signer publishes(K,v) as the signature of the message M.


## 2.4. Signature Verification Phase

The verifier confirms the validity of the signature(K,v) for M as follows.(1)
Computeλ≡vemodn and η≡h(M)2modn.(2)
Check the equalitygλ≡KKy-ηmodp.(3)
If the equality in (2) holds, then validates the signature otherwise rejects it.Theorem 1.
Following the applied protocol, then the verification in the Signature Verification Phase is correct.Proof.
The equation in (2) in Signature Verification Phase is true for valid signatures since(1)gλ≡gve≡g(s1s2)e≡g(γ2-ξ2(h(M))2)≡gKr-xη≡KKy-η(mod⁡p).


## 3. Security and Performance Analyses

### 3.1. Security Considerations

Now we will show some possible attacks by which an adversary (Adv) may try to take down the proposed signature scheme. We define each attack and provide an analysis of why each attack would fail.


#### 3.1.1. Attack 1

Adv wishes to obtain all secret keys using all information that is available from the system. In this case, Adv needs to solve FAC and DL problems, which is clearly infeasible.


#### 3.1.2. Attack 2

Adv tries to forge(K,v) via the equation gve≡KKy-(h(M))2modp, and Adv has to ways two do this. First, he or she fixes the number K, computes α≡KKy-(h(M))2modp and finally solves gve≡αmodp, for v. Second, he or she fixes the number v, computes β≡gvey(h(M))2modp, and solves KK≡βmodp for K. In both scenarios, solving for such numbers is hard due to the difficulty of FAC and DL problems, only successful if Adv can solve the two problems simultaneously.


#### 3.1.3. Attack 3

Adv may also try collectingt valid signatures (Kj,vj) on message Mj to find the valuable secret keys. In this case, Adv has t equations as follows:(2)vje≡Kjrj-x(h(Mj))2mod⁡n,
where j=1,2,…,t. Note that, the above t equations have (t+1) variables, that is, x and rj. These secret variables are hard to find because Adv can generate infinite solutions of the above system of equations but cannot figure out which one is correct.


#### 3.1.4. Attack 4

Let us assume that Adv is able to solve the DL problem meaning that, Adv knows the secret integerx. Unfortunately for his efforts, he still does not know d and hence cannot compute the two components s1 and s2, thereby failing to calculate the integer v.


#### 3.1.5. Attack 5

Let us assume that Adv is able to solve the FAC problem, that is, he or she knows the prime factorization of modulusn and can find the number d. However, he cannot compute s1 and s2 since no information is known for ξ and thus fails to compute v.


### 3.2. Performance

The performance of our scheme is described in terms of number of keys, computational complexity, and communication costs. We use the following notations (Table1) to analyze the performance of our scheme.Table 1
Definition of given notations.
NotationsDefinitionTMULTime complexity for executing the modular multiplicationTEXPTime complexity for executing the modular exponentiationTSRTTime complexity for executing the modular square root computationTINVTime complexity for executing the modular inverse computationTHASTime complexity for performing hash functionWe ignore the negligible time performing for modular addition. The performance of our proposed signature scheme is summarized as follows: The number of secret keys (SK) and public keys (PK) of the scheme are respectively given by SK = 2 and PK = 2. The computational complexity for the key generation and signing generation and verification is given by the following Table2, and the last column converts various operation units to TMUL, where TEXP=240TMUL given by Koblitz et al. [14].Table 2
Time complexity in unit ofTMUL for our scheme.
ItemsTime complexityComplexity inTMULKey generationTEXP+TINV240TMUL+TINVSignature generation3TEXP+3TMUL+2TSRT+THAS963TMUL+2TSRT+THASSignature verification4TEXP+2TMUL+THAS962TMUL+THASFinally, the communication costs or size of parameters of the scheme (both signature generation and verification) is7|n|+2|p|, where |a| denotes the bitlength of a.


## 3.1. Security Considerations

Now we will show some possible attacks by which an adversary (Adv) may try to take down the proposed signature scheme. We define each attack and provide an analysis of why each attack would fail.


### 3.1.1. Attack 1

Adv wishes to obtain all secret keys using all information that is available from the system. In this case, Adv needs to solve FAC and DL problems, which is clearly infeasible.


### 3.1.2. Attack 2

Adv tries to forge(K,v) via the equation gve≡KKy-(h(M))2modp, and Adv has to ways two do this. First, he or she fixes the number K, computes α≡KKy-(h(M))2modp and finally solves gve≡αmodp, for v. Second, he or she fixes the number v, computes β≡gvey(h(M))2modp, and solves KK≡βmodp for K. In both scenarios, solving for such numbers is hard due to the difficulty of FAC and DL problems, only successful if Adv can solve the two problems simultaneously.


### 3.1.3. Attack 3

Adv may also try collectingt valid signatures (Kj,vj) on message Mj to find the valuable secret keys. In this case, Adv has t equations as follows:(2)vje≡Kjrj-x(h(Mj))2mod⁡n,
where j=1,2,…,t. Note that, the above t equations have (t+1) variables, that is, x and rj. These secret variables are hard to find because Adv can generate infinite solutions of the above system of equations but cannot figure out which one is correct.


### 3.1.4. Attack 4

Let us assume that Adv is able to solve the DL problem meaning that, Adv knows the secret integerx. Unfortunately for his efforts, he still does not know d and hence cannot compute the two components s1 and s2, thereby failing to calculate the integer v.


### 3.1.5. Attack 5

Let us assume that Adv is able to solve the FAC problem, that is, he or she knows the prime factorization of modulusn and can find the number d. However, he cannot compute s1 and s2 since no information is known for ξ and thus fails to compute v.


## 3.1.1. Attack 1

Adv wishes to obtain all secret keys using all information that is available from the system. In this case, Adv needs to solve FAC and DL problems, which is clearly infeasible.


## 3.1.2. Attack 2

Adv tries to forge(K,v) via the equation gve≡KKy-(h(M))2modp, and Adv has to ways two do this. First, he or she fixes the number K, computes α≡KKy-(h(M))2modp and finally solves gve≡αmodp, for v. Second, he or she fixes the number v, computes β≡gvey(h(M))2modp, and solves KK≡βmodp for K. In both scenarios, solving for such numbers is hard due to the difficulty of FAC and DL problems, only successful if Adv can solve the two problems simultaneously.


## 3.1.3. Attack 3

Adv may also try collectingt valid signatures (Kj,vj) on message Mj to find the valuable secret keys. In this case, Adv has t equations as follows:(2)vje≡Kjrj-x(h(Mj))2mod⁡n,
where j=1,2,…,t. Note that, the above t equations have (t+1) variables, that is, x and rj. These secret variables are hard to find because Adv can generate infinite solutions of the above system of equations but cannot figure out which one is correct.


## 3.1.4. Attack 4

Let us assume that Adv is able to solve the DL problem meaning that, Adv knows the secret integerx. Unfortunately for his efforts, he still does not know d and hence cannot compute the two components s1 and s2, thereby failing to calculate the integer v.


## 3.1.5. Attack 5

Let us assume that Adv is able to solve the FAC problem, that is, he or she knows the prime factorization of modulusn and can find the number d. However, he cannot compute s1 and s2 since no information is known for ξ and thus fails to compute v.


## 3.2. Performance

The performance of our scheme is described in terms of number of keys, computational complexity, and communication costs. We use the following notations (Table1) to analyze the performance of our scheme.Table 1
Definition of given notations.
NotationsDefinitionTMULTime complexity for executing the modular multiplicationTEXPTime complexity for executing the modular exponentiationTSRTTime complexity for executing the modular square root computationTINVTime complexity for executing the modular inverse computationTHASTime complexity for performing hash functionWe ignore the negligible time performing for modular addition. The performance of our proposed signature scheme is summarized as follows: The number of secret keys (SK) and public keys (PK) of the scheme are respectively given by SK = 2 and PK = 2. The computational complexity for the key generation and signing generation and verification is given by the following Table2, and the last column converts various operation units to TMUL, where TEXP=240TMUL given by Koblitz et al. [14].Table 2
Time complexity in unit ofTMUL for our scheme.
ItemsTime complexityComplexity inTMULKey generationTEXP+TINV240TMUL+TINVSignature generation3TEXP+3TMUL+2TSRT+THAS963TMUL+2TSRT+THASSignature verification4TEXP+2TMUL+THAS962TMUL+THASFinally, the communication costs or size of parameters of the scheme (both signature generation and verification) is7|n|+2|p|, where |a| denotes the bitlength of a.


## 4. Conclusion

In this paper, we have proposed a new signature scheme based on two hard problems; factoring and discrete logarithms. The scheme offers a longer/higher level of security than that of scheme based on a single hard problem. Furthermore, the proposed scheme requires only963TMUL+2TSRT+THAS and 962TMUL+THAS, respectively, for both signature generation and verification. We considered some possible attacks and demonstrated that the proposed scheme would be secure against those attacks.



---

*Source: 231649-2011-06-30.xml*